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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
. h- \, _+ R% Y$ `; g3 |
求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
% H, F. a/ W; [! j结果: 55965365465060
代码:
0 T- ?! D; |  a6 o- a#include<bits/stdc++.h>
2 m& p( p/ v: y4 `9 v' U#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
' B1 f* o4 X8 K! i! z* j3 Ntypedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
) H- B8 p% T+ b. `/ M" Econst double eps = 1e-7;
" n4 r) e& Q. x: o1 i
bool vis[12345];
& h5 ]7 f/ m  F/ F- `vector<int>prime;
ll f[3000][3000];
0 d2 D  p% ^1 I4 T( C7 H5 d
void init() { //素数筛
! o+ C7 u. N8 j) Q9 g9 o    for(int i = 2;i<= 3000;i++) {
5 j; Y: O0 G9 ^) A, e- N: e        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
                vis[j] = true;
            }
( H. Z4 @" _+ V: T* p+ r        }
    }
* \2 T0 k5 M7 }, E6 g- U/ x    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
    }
}

9 J0 l) X$ Z6 ~9 h+ r' E) |6 all dfs(int pos,int sum) {
$ j( I/ k, b2 n9 ?    if(f[pos][sum]!= -1) return f[pos][sum];
    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;

' V# |, @# R0 z6 j8 Q% E$ ^    ll ans = 0;
  r# X5 K9 I' y# E) H: \    ans+= dfs(pos+1,sum);// 不要当前这个素数
4 z9 i% n* k" o/ E+ y) u7 D    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
}
) r: q, P' M) ^# Q( ?
. T' a: h4 g: l" G: m9 Wint main() {
    init();

- Z7 q$ @8 L) i) o% d* d: V8 S/ i    mem(f,-1);
    ll ans = dfs(0,0);
    cout<<ans<<endl;

+ `8 y; h1 @; J0 k. j" C1 J! b/ E8 S# T    return 0;
; Y) ~- W! z! J}
3 l  b: e. ?$ ?/ {! A: t1 u---------------------
( z. `4 ?5 m. V8 n& u, J作者：nka_kun
7 c. y1 H8 O+ M5 a3 C4 b! W
* [$ F8 H2 Q- ^: I/ H% V' y. H
% v% @9 ^0 f! \/ G