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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
/ R' y$ f$ n" l: F
5 G/ R/ E  w3 N/ b求两两不同的素数组成2019的方案数
& P* r$ ?" Q: p% Z注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
* n$ J/ b9 V1 {% X. ~+ y代码:
. N$ G9 f0 R1 g3 Q#include<bits/stdc++.h>
0 c) F1 ]! k( q8 M2 S! N#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
, M: n" m9 L3 Z5 \  etypedef long long ll;
* B+ Y+ I" W7 B, ?/ Uconst int inf = 0x3f3f3f3f;
! L% Y9 Z/ i4 Gconst int maxn = 3e5+55555;
7 `% l6 E( F  t) E/ K: A8 Nconst ll mod = 998244353;
4 P+ J" i$ r- O. W& gconst double eps = 1e-7;
$ X* Q$ H1 B6 Z: R; M$ v
! H6 O, k9 L- s- R+ k5 Nbool vis[12345];
# y( N" f* o: @0 ^: E0 ivector<int>prime;
ll f[3000][3000];

void init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
8 F. X. R1 o) I) @  d0 S! ^        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
' Q& r5 u  R# |+ C8 r; G8 q5 x$ N                vis[j] = true;
; |! R5 h% V* A! j+ O# i2 X0 X            }
4 U! n4 y/ l# j6 {6 r+ d: J: Z        }
    }
0 `+ U9 t- v  x2 e9 \" w6 y    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
    }
5 @  F4 G# w3 @" b}

0 I7 I+ A; t# l# Yll dfs(int pos,int sum) {
    if(f[pos][sum]!= -1) return f[pos][sum];
/ v3 s+ y# B& U+ J7 l    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;

    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
/ E  U  n2 W4 c) x3 ^, Q    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
, U+ R; e5 U% R0 Q    return f[pos][sum] = ans;
}
6 ?2 }4 C- n  a. e7 e
7 ]$ W- a) v3 B- Bint main() {
. M, \. t8 d& j& D- ]    init();
+ T$ k3 z0 ^" e6 B
' P' z$ u' m. K: Y2 m    mem(f,-1);
    ll ans = dfs(0,0);
    cout<<ans<<endl;

    return 0;
}
0 |+ S, W+ J% Z, d8 a& N! N---------------------
作者：nka_kun


+ n5 I  F1 g( B" W; o