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

杨利霞

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

求两两不同的素数组成2019的方案数
* _9 a5 k" I0 T6 C* w8 L% g! w注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
: f" W' t$ g6 H( j; Y* U! j结果: 55965365465060
& M- f" N7 t+ c( k代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
! [6 d, H' h# }  W+ susing namespace std;
) U# e; F. G, v0 X6 M& ftypedef long long ll;
! Z5 V  ^7 i9 t' D& nconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
5 x2 D5 m1 ~( z9 |/ A" ]) {0 |8 n9 Zconst double eps = 1e-7;

+ s0 K0 ]# u% U# X0 a/ g4 wbool vis[12345];
$ m& C: w" m0 d0 a$ @2 k8 W- dvector<int>prime;
  R6 S" o) r( x0 K6 I+ U: |4 ^$ Dll f[3000][3000];

1 U5 O) I9 W4 Y) `+ n1 B' J, }void init() { //素数筛
3 _- O4 P3 I  u# D; d5 B! N2 u    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
                vis[j] = true;
+ ]  k; O! ?+ F: N7 m  b7 V            }
        }
    }
    for(int i = 2;i<= 2019;i++) {
8 L' g7 H1 n; a2 |$ W( j" W! \        if(!vis) prime.push_back(i);
) ^3 a4 a: S9 v# X' i: {    }
$ Q& N3 Y) l8 |% x2 X8 e}

8 R+ z9 w" T8 F0 Sll dfs(int pos,int sum) {
! q: }  f- M" V. |& m    if(f[pos][sum]!= -1) return f[pos][sum];
# o/ D, O- A" f2 z    if(sum == 2019) return 1;
* a9 W* j8 B7 m  Q" q9 b    if(pos>= prime.size()||sum> 2019) return 0;
5 n' M- ~" O9 ?# I2 C
) |" H* A. c3 O5 O7 T9 t, \    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
2 T& e9 S5 r! S* z% z/ _' k, _    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
}

: X, `6 S/ k: kint main() {
    init();

- d/ F) `; r6 i7 F6 R& `    mem(f,-1);
    ll ans = dfs(0,0);
    cout<<ans<<endl;
' W' b  K0 d: W/ p$ E: u7 B' a- U- q
    return 0;
}
---------------------
作者：nka_kun

; N; l( i. l# \5 y9 }9 |