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

杨利霞

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

求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
代码:
#include<bits/stdc++.h>
% X3 @! B5 U+ E% L: H% j#define mem(a,b) memset(a,b,sizeof(a))
0 O/ H& K% z2 h5 Z6 U4 v( l+ ]2 Husing namespace std;
2 \9 J' x6 x2 H* ^1 ytypedef long long ll;
const int inf = 0x3f3f3f3f;
9 g% z- v+ c$ b( Q0 v; Xconst int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

: X7 ]" p+ n# U6 J3 ybool vis[12345];
. y5 [) H- l- t9 }' \, Jvector<int>prime;
: d2 N* i8 I1 d2 y3 P0 Mll f[3000][3000];
9 d1 H  S' @( O7 r. G1 X
# M0 g. N! w( s2 Y2 ~& `  |' h3 \, vvoid init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
6 X, u, S2 f0 C        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
                vis[j] = true;
: z& r! O4 y1 I$ f' D) L& p. h            }
7 d2 W( _4 a! `0 W1 e: I        }
    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
1 H% Y, z  w$ W8 c* f    }
}
! X4 C! `1 k2 U- X0 v
ll dfs(int pos,int sum) {
* i* V2 S0 w  S  \6 H    if(f[pos][sum]!= -1) return f[pos][sum];
    if(sum == 2019) return 1;
3 e6 M# K' @$ f. h: C    if(pos>= prime.size()||sum> 2019) return 0;
- Y. k% {8 J6 k2 Y: m* K! g
: m$ D3 A) L1 y" d! c( x2 B; f    ll ans = 0;
, h0 N: \3 h. }    ans+= dfs(pos+1,sum);// 不要当前这个素数
' G# u+ K: F6 U, l% j. Q( r    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
3 K' R$ s$ E! N( v9 w$ r    return f[pos][sum] = ans;
}

int main() {
    init();

* t/ \  N/ N6 H; c4 M! O! z    mem(f,-1);
% a8 w. j: T" F4 q' d" ^& z    ll ans = dfs(0,0);
    cout<<ans<<endl;
! F2 ]3 R0 J4 n$ ~6 U
0 ?# P& A' K  d8 t# @    return 0;
5 a" g" R1 X2 y9 ^. z}
---------------------
( G) `6 @) S: J6 Z( L作者：nka_kun


# ^; |2 B* [5 v