2019第十届蓝桥杯B组决赛题解第二题

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
8 o( B8 t8 L9 u7 X
求两两不同的素数组成2019的方案数
7 @' X1 A5 g3 p" d3 N7 C注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
代码:
: \6 b- W0 V" m& \#include<bits/stdc++.h>
4 q" y$ y% l" c#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
0 k" S' y& [$ l' e6 Q/ itypedef long long ll;
const int inf = 0x3f3f3f3f;
0 r( J$ C( F) J$ G/ e1 Q2 e4 lconst int maxn = 3e5+55555;
const ll mod = 998244353;
- n& l$ M4 D& d6 ^+ z6 `const double eps = 1e-7;

4 Y) Q! S7 t! O5 N0 h0 |bool vis[12345];
vector<int>prime;
' C/ j; c" d) p4 y7 Z$ z1 Ell f[3000][3000];

void init() { //素数筛
8 ^' o2 O9 z, m+ g' ]    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
                vis[j] = true;
5 N- h! N( ~6 Q; c  F6 q+ A            }
        }
0 x: N* s6 x3 x! g/ M    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
* `9 ^4 q, H6 l5 V% h6 [    }
' D+ ^! G$ d- X6 [( J$ V3 g7 P* w5 m}
. ~  A, I$ h* u" U- p
1 m, D& s0 \2 k  y& x2 v* R! |ll dfs(int pos,int sum) {
7 |1 f& g6 ]1 @    if(f[pos][sum]!= -1) return f[pos][sum];
    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;
8 ?7 L! G; o6 g. ?" b
    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
) b& ^2 f$ H- z, ]}

; W+ d/ j1 o& t) ]5 g3 C6 i9 [int main() {
    init();
6 y7 W9 q2 S  d/ R
' r; Y% V1 L! O$ S4 H    mem(f,-1);
    ll ans = dfs(0,0);
    cout<<ans<<endl;

% Y2 D( i0 B7 f- F. ~    return 0;
  G6 ?0 Z$ H% U: `. h3 _1 S& `}
---------------------
作者：nka_kun
5 d5 B0 p9 M. r" n; G
1 {2 y( M* M, D8 H* i  Y3 v