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

杨利霞

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

求两两不同的素数组成2019的方案数
5 S0 t6 ^2 X7 L( c/ j7 n: G* J' D注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
% \' z8 Q. C& ]结果: 55965365465060
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
) L. V4 O$ P3 _0 i( v1 @  uconst int inf = 0x3f3f3f3f;
' \; a- e: \0 U  N; oconst int maxn = 3e5+55555;
" M+ E7 d; N7 k# v+ K1 e/ Vconst ll mod = 998244353;
const double eps = 1e-7;
) d' s  X5 M2 b
0 J5 ]$ Z$ ?0 f7 s( C' `bool vis[12345];
+ v# y7 V6 l/ f) `9 N2 bvector<int>prime;
4 z9 e. h+ Y! e( W, Oll f[3000][3000];
" k6 f1 W) M, ~- g$ J2 o
void init() { //素数筛
  Q! G! k1 _, k2 n) F    for(int i = 2;i<= 3000;i++) {
9 H5 G0 x6 V* R" q        if(!vis) {
1 n+ _$ D5 k) t6 I4 X, j            for(int j = i*i;j<= 3000;j+= i) {
                vis[j] = true;
            }
        }
" `5 Z  ]- D* ~  L    }
: A/ j  N0 c- p' f+ ]# _4 Q    for(int i = 2;i<= 2019;i++) {
3 U6 a& u) t( E- B        if(!vis) prime.push_back(i);
    }
}
# Q' w0 N7 \/ I
0 a2 b1 E7 \. r7 A- P- qll dfs(int pos,int sum) {
$ C) o% G5 H  z% e- s4 S8 T+ f    if(f[pos][sum]!= -1) return f[pos][sum];
* x$ _6 Z& i+ T    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;
0 d% p7 n; l& o. v) D; h; E" V
    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
# r1 f* L! x6 J; u4 w% [$ N    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
}

2 _+ Y8 O( V3 O/ D" r  hint main() {
+ u: ^7 v0 z; h+ A) s, _    init();

0 K- d3 y  N+ ~/ d. b6 f    mem(f,-1);
    ll ans = dfs(0,0);
    cout<<ans<<endl;
9 K5 ~, Q  `/ j$ Y0 t% H* [
    return 0;
" z4 N9 V; d) G7 d/ K}
---------------------
作者：nka_kun