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

杨利霞

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

求两两不同的素数组成2019的方案数
2 g" e! _/ ^- ?( U) f注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
9 T" ?9 f7 R5 {  C. D结果: 55965365465060
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
( F) D4 Z$ L. L/ w6 L+ }using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
2 O5 z' E4 v9 \+ N/ z6 _const int maxn = 3e5+55555;
6 m6 a+ _/ B/ I6 econst ll mod = 998244353;
const double eps = 1e-7;
( j( M6 I( o$ B7 W
  v# z# k0 Q, A# F" o. qbool vis[12345];
vector<int>prime;
! d' e+ R, d; P2 w0 B8 |& T' {' Y7 Vll f[3000][3000];
6 x" r3 `* d6 y+ R/ r1 ~
3 c. `# H: Q# A/ \9 rvoid init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
+ [: A' e- E% ?- A  `1 h        if(!vis) {
* w& Y" M; _$ `3 |1 r& b# H            for(int j = i*i;j<= 3000;j+= i) {
8 c' q/ _2 F  u3 S  K2 s! z) R0 K                vis[j] = true;
            }
        }
    }
    for(int i = 2;i<= 2019;i++) {
3 z. X! M7 i/ ^! S) p; l8 X        if(!vis) prime.push_back(i);
: g" O8 ~! ]4 v: |    }
- O; p  @; D8 A) f3 g}
  a7 B: y% t8 Z/ L' @
$ }1 t$ P4 M4 Tll dfs(int pos,int sum) {
    if(f[pos][sum]!= -1) return f[pos][sum];
    if(sum == 2019) return 1;
% v. Y. F9 P$ h& ~) \0 d    if(pos>= prime.size()||sum> 2019) return 0;

    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
}
$ G! X0 L$ Z% J8 C. M2 k' h
int main() {
    init();

    mem(f,-1);
* k9 i0 w0 z  W( a    ll ans = dfs(0,0);
    cout<<ans<<endl;
5 n/ |  D' b* G- g* R
    return 0;
% p4 y. ]9 e, p}
/ ^  G" j8 M  y6 u! }* v4 o---------------------
作者：nka_kun

& N- u; N% H5 o* b! \9 q
- ^7 i8 S$ V1 {% Z# c9 T  J