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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
* y8 O1 @3 x; f4 b* L3 A
9 N. g' N( g' O1 |求两两不同的素数组成2019的方案数
* D* U# B& _4 c) N5 h% ~注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
$ u+ ]) Y: q* J5 h代码:
& j* u; h! a9 z3 b#include<bits/stdc++.h>
: p  \5 }5 \& ]#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
6 G8 R6 B" X* p: ]2 Etypedef long long ll;
const int inf = 0x3f3f3f3f;
2 d$ l, ~% i+ G" c: U2 T) J1 Pconst int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

, b9 W) M  ]+ H2 L9 m' T: f( o. hbool vis[12345];
vector<int>prime;
ll f[3000][3000];

void init() { //素数筛
6 q4 l" i9 x1 K6 g( b7 Y    for(int i = 2;i<= 3000;i++) {
, H0 p$ N* n; F  h0 m+ s5 j        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
/ L* G4 }. b6 L                vis[j] = true;
7 E  e9 H1 F$ X, c            }
        }
! ^5 W- N: L' o  l# }1 p    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
7 Q  \/ Z# P1 g  p3 B    }
}
6 h! |2 j$ l9 v
ll dfs(int pos,int sum) {
" L6 J. l# N$ w* I  B    if(f[pos][sum]!= -1) return f[pos][sum];
  m+ {3 N; a2 h    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;
) z: k; U* G! ?" ]' X
: b( `+ t; T/ b: I! g$ v( I% T- W2 O" S    ll ans = 0;
; \1 e0 i3 F; L+ |& H  t7 Y! {, G" Y" y    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
}

4 G4 ~$ ^! m6 r1 a6 oint main() {
    init();
' M; x: e' f' m1 J
    mem(f,-1);
( o* b! T( I2 G# d6 O6 V- y+ V    ll ans = dfs(0,0);
    cout<<ans<<endl;
8 z, m' p  S; w/ p8 [
$ H* Z! ^, p4 N4 V    return 0;
* f) M% w! c* \' d+ X0 z}
---------------------
作者：nka_kun