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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
+ S. l2 k1 T+ m0 `1 R- x( H
求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
8 X) S3 Q5 m7 a* Q# M5 w4 u# U结果: 55965365465060
) f. Y/ K+ q& M# J代码:
  F$ B" x+ w7 d" N; y6 Z' b#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
' G$ A: F0 _0 Q' q( ousing namespace std;
, a# N" X8 l9 `6 u$ E5 Qtypedef long long ll;
const int inf = 0x3f3f3f3f;
% q) q) o* u1 |4 `const int maxn = 3e5+55555;
const ll mod = 998244353;
6 W8 E$ V5 ~- I6 d7 w" N. Uconst double eps = 1e-7;

bool vis[12345];
vector<int>prime;
ll f[3000][3000];
8 m9 N$ l% ?! W
# W) a4 T/ a" _$ y0 Cvoid init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
% i! o3 S# }+ }& j) h            for(int j = i*i;j<= 3000;j+= i) {
. y7 _; q1 r/ [) \, b                vis[j] = true;
            }
2 o  t+ }$ J) D        }
, }" o+ g) S1 t+ e8 ~    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
9 y3 f# }) O2 m- s: f  c: ~    }
}
9 A" Y, h) l$ j/ w0 ~
ll dfs(int pos,int sum) {
    if(f[pos][sum]!= -1) return f[pos][sum];
3 m5 q4 ]6 G; P  I    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;
. \3 g" e7 J( v' P& }0 Y0 N$ I
    ll ans = 0;
2 T# ~$ G7 \/ z7 [/ |$ G$ W% x    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
7 [3 G0 N) B* W& g    return f[pos][sum] = ans;
}

int main() {
1 m9 n2 T. P/ c7 w: s    init();

9 u/ D% s2 ^: {# ^0 Q2 f; E    mem(f,-1);
+ ]2 o5 d% J% {/ h. }3 S    ll ans = dfs(0,0);
+ t: C6 [5 N: V' E    cout<<ans<<endl;

0 l5 ]4 b& F7 v# h- a! \    return 0;
, q5 s# @, q; ]+ ?}
. k1 _) z  d1 p3 D---------------------
作者：nka_kun
  l+ w8 T# \9 k