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

杨利霞

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

7 ^2 l# t* N- ~4 X# L2 M/ [求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
代码:
#include<bits/stdc++.h>
9 B1 |; d9 w8 v$ R7 ^% y# H#define mem(a,b) memset(a,b,sizeof(a))
( e6 o. p1 u' c' R0 M) G3 }using namespace std;
typedef long long ll;
- R! y4 r- ?" |3 k+ X+ Iconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
1 R2 W6 }& Q9 S6 H# U# bconst ll mod = 998244353;
const double eps = 1e-7;
4 M  F, s1 ], G6 @- O
bool vis[12345];
vector<int>prime;
ll f[3000][3000];

void init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
2 T7 F: h( n! K& c        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
5 W  X, K6 E: \3 ~" ?2 [                vis[j] = true;
* `, I& W2 y, v- W            }
* U* L5 K. F+ O; I        }
    }
    for(int i = 2;i<= 2019;i++) {
- v9 t0 ^* `+ _  C8 S: [        if(!vis) prime.push_back(i);
    }
}

2 |8 f9 Z7 w, {/ T5 H# L6 v: fll dfs(int pos,int sum) {
3 P' t& |# [& D" ?- r! j    if(f[pos][sum]!= -1) return f[pos][sum];
    if(sum == 2019) return 1;
2 f! B$ E% E, I3 {& \    if(pos>= prime.size()||sum> 2019) return 0;
) B8 J, x3 |1 `+ V4 m
6 V  j% I6 d# G" x    ll ans = 0;
3 V, b- Q0 O* b! n9 B    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
" u4 Q+ @; M3 t    return f[pos][sum] = ans;
}

" l: X* i% q' v: u6 t7 Fint main() {
    init();
2 p9 \0 C- f0 I; Y2 V* s
" K6 E. S+ e! M1 u+ v& v" p* d    mem(f,-1);
% V3 i. O5 S0 T! Q4 @    ll ans = dfs(0,0);
    cout<<ans<<endl;

$ a7 u9 B% J& I) H+ y    return 0;
2 ^/ Y8 m* X( q. ~2 i; {}
---------------------
6 C! l8 L5 B( }, C作者：nka_kun