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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
$ F) e! N+ R/ _& F# L5 `4 S
. N) \' v' e- Y1 I求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
) Z! }# }2 ?$ q' T7 Q结果: 55965365465060
- w$ B, `6 j( O* ?7 P代码:
7 r- D2 n) b4 b# O6 E#include<bits/stdc++.h>
# X! v9 s5 t8 O& q6 f#define mem(a,b) memset(a,b,sizeof(a))
0 W! E2 ~7 k4 musing namespace std;
( b9 S' z2 D/ n% F/ ~) ttypedef long long ll;
; i  n- X. h  G0 M7 b7 Jconst int inf = 0x3f3f3f3f;
; f* S/ j( F7 r- Q+ a% A) lconst int maxn = 3e5+55555;
6 c& o2 Q; J# v; w! _" Zconst ll mod = 998244353;
0 f( u; X  }* W$ ?0 |2 Lconst double eps = 1e-7;
& V" G3 @" P. M, e- O# f# v
bool vis[12345];
6 w5 l3 M1 K; S, J, U! vvector<int>prime;
ll f[3000][3000];
* o8 ]7 F& v3 \: y
void init() { //素数筛
- \4 P9 r" w1 ^6 l3 U    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
                vis[j] = true;
$ T0 S1 ]& l$ B& x* E8 _  g            }
        }
# Z9 e% Q/ s) A    }
0 T. A' T, K! X+ b0 J3 B    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
    }
}

% J/ ]1 B7 N  \# v4 f  rll dfs(int pos,int sum) {
! d# [+ S! n* q- A    if(f[pos][sum]!= -1) return f[pos][sum];
3 ]2 O) c8 v; P& N  D- m1 {8 b    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;
* _7 ?, _% i) ^
$ W& i6 R4 I( J) T/ l9 v! N    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
% R- B4 F7 y# _- |6 d    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
! o/ y9 ]" c4 X. y5 M}
! n0 @6 d( f3 I+ L) f) S) P& S
int main() {
    init();
* X; _6 V6 Z' V6 o8 B% Y
    mem(f,-1);
) i; i& c5 e1 t1 a" F    ll ans = dfs(0,0);
    cout<<ans<<endl;
* f. ?2 y# z* J4 b/ b1 F& W$ W
    return 0;
) d6 D9 b2 l3 h- L0 N}
---------------------
作者：nka_kun
6 \+ W2 G% J6 }/ V8 x
( h' l9 |- M5 |% p$ D! l6 v