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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
2 ]! Y) V+ T, B# U, ~0 S
求两两不同的素数组成2019的方案数
- p6 x% ^% y0 J9 W5 H( {注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
$ w: X& \4 n9 c/ x+ J结果: 55965365465060
代码:
2 m1 q2 h! H+ n3 [8 H- g: F#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
# O; ~/ w7 P3 O  btypedef long long ll;
const int inf = 0x3f3f3f3f;
+ M% V) y9 Y/ B$ p( O+ ]const int maxn = 3e5+55555;
const ll mod = 998244353;
; u: }+ n( J; b* H# Q7 Vconst double eps = 1e-7;

bool vis[12345];
vector<int>prime;
ll f[3000][3000];
/ W; H1 r9 D. k( i  ~( ~
void init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
) O# q  j% U' |            for(int j = i*i;j<= 3000;j+= i) {
9 t. y" Q  c4 Y                vis[j] = true;
+ _9 t7 u0 _! h1 a2 N            }
2 u4 \4 R! J, B: P! Y        }
    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
( f7 R8 C& D/ P* d# |    }
}

9 l4 N# m  x/ [7 u) N0 F& Bll 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;
  T. @3 C7 f1 {' ?, k3 E0 E3 |, ?
3 K, K; x8 q/ {& `9 B  R    ll ans = 0;
- ]" z  ^+ D- a- c    ans+= dfs(pos+1,sum);// 不要当前这个素数
. X- j" y& q* i9 W" d2 {5 t    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
}
* a% ^2 B! T1 A+ p. s  h8 o0 V3 |$ l
int main() {
    init();

* q" U3 f* g5 ^; H. K5 ~% g8 K    mem(f,-1);
: m$ G3 O( K" z& s4 y    ll ans = dfs(0,0);
    cout<<ans<<endl;

6 L( B% v* T; j8 H    return 0;
- O& e6 Z+ ~1 h: @}
$ g: `6 E! x! x+ J! X---------------------
+ f/ X3 ^& F& J/ D作者：nka_kun
1 d4 V; \0 D* A- E
2 p. {! E2 [4 Z
( B: I2 [* `: r: L5 i+ @