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

杨利霞

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

. O& `5 S3 y# k# r5 Z* D$ _求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
& }- N- C" o! J+ e3 H$ H0 }结果: 55965365465060
- `0 ^. w" }/ C( i代码:
#include<bits/stdc++.h>
+ R4 P. v' C+ s6 P#define mem(a,b) memset(a,b,sizeof(a))
% r: l# W5 |* \# eusing namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
6 e, B% p+ {$ r8 Tconst ll mod = 998244353;
/ m9 @1 t8 T* c0 pconst double eps = 1e-7;

7 i  D7 [( _( Q; S' lbool vis[12345];
) e- u" \% ]; H% A3 Uvector<int>prime;
ll f[3000][3000];
! j$ R5 {& T4 G; Q) k
% D  v+ G8 w- ^' q0 \. |! m& H; Nvoid init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
                vis[j] = true;
            }
        }
+ R. `3 ?. U! D$ z    }
    for(int i = 2;i<= 2019;i++) {
0 N: v# O  H2 Q. v8 V  e) ]        if(!vis) prime.push_back(i);
+ c0 @8 N* }, h    }
6 K; D/ [2 y5 g; A' _3 ^5 D' w; u}
+ O% P' I( d# g/ |& b  O
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;

  I! q$ n2 y) ^4 h    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
" R9 A4 i- g7 x* o: J  |2 e0 O    return f[pos][sum] = ans;
}
! ?4 I% f! ?( A
  d% ~( F: U+ E5 xint main() {
    init();
. Q& m  l- _. s- I! L+ [
! ^2 z' ]* M- ~2 o$ m( _( F    mem(f,-1);
, P+ q2 M2 m: s& ?# B# b    ll ans = dfs(0,0);
1 m5 {( ~7 N) q& F7 ?; P1 ^    cout<<ans<<endl;
9 Y) ^8 Y9 a: \4 ~: g
9 X* l* x; I" c1 B$ I" [    return 0;
}
5 N! x0 L) Z8 s' L- |---------------------
作者：nka_kun


4 D( _' k/ L8 a# i0 e) G  W