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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
3 H1 T4 I  L: [' W( }# V) B
求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
( H% v; o) ]) q) ?8 z0 y结果: 55965365465060
代码:
#include<bits/stdc++.h>
" ?; S; |3 R* k' A2 H* v( b) s#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
, A7 G) E$ C. \6 w! @2 n- stypedef long long ll;
/ m, z( L' f. L. sconst int inf = 0x3f3f3f3f;
+ O& O- K  x) F5 U: }  cconst int maxn = 3e5+55555;
const ll mod = 998244353;
; b4 i4 G. O7 E7 O- a+ p3 @const double eps = 1e-7;
! z% e- @; `; X2 S* h) [
bool vis[12345];
vector<int>prime;
ll f[3000][3000];
" c9 a! x  n& [! F- b4 f: B4 q  @
void init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
# W- V0 @3 S9 O5 y5 \9 f' b  Q5 R        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
8 w0 E3 j( U7 P) X/ i" n3 C                vis[j] = true;
; d8 l; w- p0 [8 Z4 |6 r1 `  |            }
        }
    }
4 ~( C/ B0 J- Q' H    for(int i = 2;i<= 2019;i++) {
/ k0 s3 Z" u$ Y% I: v        if(!vis) prime.push_back(i);
) U/ W& Q6 q0 o/ {( k6 v    }
5 s' ?$ Z. L( _. j3 Y' x* J}
' \: E$ P( y' Y
ll dfs(int pos,int sum) {
    if(f[pos][sum]!= -1) return f[pos][sum];
1 g  ^3 m( z2 c; \0 R. N' S    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;
  T* d7 V" D5 Y* V
8 M+ y# v, K  A% F: Y    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
/ v$ J0 g/ P1 X' F}
6 p6 E/ A0 g" X$ O( i  h
6 O1 S: b# [: pint main() {
+ j) `5 @& T, O, D, I$ P    init();

    mem(f,-1);
    ll ans = dfs(0,0);
" K/ Y5 j; f* g/ f$ e    cout<<ans<<endl;

    return 0;
}
---------------------
# _+ {8 g6 T# h作者：nka_kun


4 H2 v! h5 {6 w) P3 g2 k