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

杨利霞

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

求两两不同的素数组成2019的方案数
) G" Q# x# K0 B9 d3 M. _注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
9 N" G# Z3 l9 c9 Z代码:
% D- B1 z% a' i' b+ b#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
" O7 @$ Z2 q" x. ?1 P/ {, @0 yusing namespace std;
" U) c/ U( W2 O8 g+ Y7 n+ H* ~typedef long long ll;
2 h6 R% \2 T' n  i8 Gconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
% }! ]4 s, i5 @, |" i0 yconst ll mod = 998244353;
const double eps = 1e-7;

, p. Q: _# T- o$ K3 N4 @$ Obool vis[12345];
vector<int>prime;
ll f[3000][3000];
, t9 S5 U4 B: F" [
1 e3 H, C  q% K2 W5 ?* P# Y/ Cvoid init() { //素数筛
1 {, x& \& {6 r( v; [& b    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
2 B5 H( w+ p& E% a8 t" u                vis[j] = true;
! ?! s3 d  ^+ C- D8 U2 g9 x            }
/ r6 Z, K$ O% b- P4 X, j        }
* p) i. R9 D# {6 W2 i/ r    }
    for(int i = 2;i<= 2019;i++) {
; }' r& j) b( b4 {0 G        if(!vis) prime.push_back(i);
+ C3 M+ `7 K$ T$ Z7 [- q    }
}

ll dfs(int pos,int sum) {
    if(f[pos][sum]!= -1) return f[pos][sum];
    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;
( ?0 I  h! z. U9 ]4 }: D7 J' ]  T
    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
6 e* b" h+ e, x$ Y- h    return f[pos][sum] = ans;
0 C" Q" K1 L% w1 `4 |, Y}
9 ~. u* J" o2 z1 l
2 n) I$ H  x; L$ H* tint main() {
    init();
' t8 o6 H2 s/ Q$ M
% ~9 V$ K* u# N3 y# k( F    mem(f,-1);
, ~. h5 ~' p; e1 o" V- r2 Y    ll ans = dfs(0,0);
    cout<<ans<<endl;

    return 0;
}
---------------------
& G5 t+ X7 M7 q6 m1 }) {作者：nka_kun