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

杨利霞

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

/ ~# y  k# P" w+ W2 Q求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
. q/ Z+ V/ }* f8 i结果: 55965365465060
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
  `/ Q3 J% p+ Ausing namespace std;
5 K  j# _) R4 U) d9 y. V# O' p: }typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
. H- a: z0 \1 f8 y) b( v; econst ll mod = 998244353;
8 A* N* A1 i( f7 ?+ d6 z- mconst double eps = 1e-7;
6 H1 a' x4 w4 z3 |7 |7 p; Z
bool vis[12345];
& v# K6 A9 X5 K* U+ q( k1 }( cvector<int>prime;
: ~# P! g# e2 Vll f[3000][3000];
5 m# l  J3 d/ f) B1 h5 `% f% u
* t! B" Y3 u9 Q8 B  k# j7 m" hvoid init() { //素数筛
0 }- W3 u# u, m: a9 v: V3 S    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
6 i* _3 o' S' q6 E                vis[j] = true;
            }
6 F& y) [* X: Y8 U  S  b6 b        }
    }
    for(int i = 2;i<= 2019;i++) {
0 f- }3 c: L9 `7 m) y* t        if(!vis) prime.push_back(i);
    }
}

+ H+ e3 v/ d; ]6 ?4 wll dfs(int pos,int sum) {
" X% v; c, c/ E. m8 ?" L5 P3 }    if(f[pos][sum]!= -1) return f[pos][sum];
    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;

    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
0 h2 Z0 }6 y8 ]/ x/ ?5 [) k' j    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
8 Z1 F7 v, H% p+ @}

6 M, b9 I% W, E  Mint main() {
& \% W# d+ t9 Z3 P& G6 ~    init();
% Q, ^& [. i* G% Q+ @' `
$ Q$ j0 D) h* q% \4 a$ x+ V4 ~+ }    mem(f,-1);
2 p4 ^4 s+ K  p! ~4 T6 n6 z    ll ans = dfs(0,0);
    cout<<ans<<endl;
1 [3 r* V8 t  s( f8 R+ j& T
    return 0;
' i5 f4 H7 B! {6 w' }}
" ^, q6 D3 U3 D: Q$ w2 C; v: x* Q8 o---------------------
: E$ g1 t* C! N8 J$ B! d作者：nka_kun
% A5 k+ Z! V' A3 p" ]* V

3 \, x- d  Y: @  j1 g4 R7 y, V