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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
6 q0 Q* x1 r  F4 [8 a' o
求两两不同的素数组成2019的方案数
8 o. N* x) T9 O: j0 \注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
代码:
#include<bits/stdc++.h>
# z; o5 P0 h6 |7 O+ y1 r+ ]) U0 q#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
& q; F) b4 B4 X$ J- V" Gtypedef long long ll;
( ?9 W! d+ n' }, cconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
$ ?, S4 k$ C) A- O' q$ U; g' g0 yconst ll mod = 998244353;
const double eps = 1e-7;
: c. ~, V. K- x# t4 P0 ]7 s& ]
bool vis[12345];
$ R: z' ~6 _! e9 ^; F- K) `vector<int>prime;
ll f[3000][3000];
1 M3 N9 G" S/ Y6 S% T
void init() { //素数筛
3 ~8 c9 {9 Q+ W  {- A% B7 I0 ~" T    for(int i = 2;i<= 3000;i++) {
6 }# s( n7 y4 f        if(!vis) {
) L$ c- Y8 c7 v3 N) e5 Z* W: w  j            for(int j = i*i;j<= 3000;j+= i) {
                vis[j] = true;
            }
        }
" f* E  f8 {* a% B    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
    }
- o% o7 g" `1 H4 {6 e/ n}

* p2 B' C$ _3 G: N7 O7 x: j) ~ll 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;

    ll ans = 0;
, p- [4 P* @/ T' ~    ans+= dfs(pos+1,sum);// 不要当前这个素数
5 i0 o& B4 p" P8 C# ]    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
! @4 u4 T: G$ q+ k    return f[pos][sum] = ans;
. c; j1 ?# t+ M0 z* U  a}

7 f3 H/ G# R- Q. G- u! N4 v1 p# q8 Nint main() {
    init();

0 f2 K- Y# f3 E" N$ t( ?    mem(f,-1);
    ll ans = dfs(0,0);
1 _8 M5 c( f- {    cout<<ans<<endl;

2 A- q, ^* l% j$ }" {$ q    return 0;
}
- v- d- I( f/ Q& k3 O---------------------
1 |- C1 L6 ~7 v' d' T0 \0 t2 U作者：nka_kun