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

杨利霞

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

. y4 R& W3 s1 K! i. }: i求两两不同的素数组成2019的方案数
. y# {4 O8 W* p1 X注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
0 t; O' q# L( u3 m# X% L& N8 f结果: 55965365465060
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
% z& b: j1 d3 u3 B( Susing namespace std;
! _) i$ G9 h7 \typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;
4 K' `( X$ m1 \9 M  u& ]/ \
4 k1 F( X4 [: ?7 {" B% Y# C& Dbool vis[12345];
0 e6 Q7 u2 X6 r4 ~vector<int>prime;
, X8 r8 @& u/ ]# }ll f[3000][3000];
, u5 x' `) [, l9 K
6 e3 b6 ~+ v7 U4 l+ d3 |; Zvoid init() { //素数筛
1 \/ l! z6 m- K# ]    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
8 r0 A+ N4 `2 T- W                vis[j] = true;
            }
/ R2 ~8 |2 h% D: E2 R  j: l        }
9 f8 k2 b1 s6 X% j' T    }
    for(int i = 2;i<= 2019;i++) {
+ W& o# J! s# C        if(!vis) prime.push_back(i);
, K" Y' A9 H; G( N( a8 ?    }
}

" B7 l6 j+ N! q; W' k) jll dfs(int pos,int sum) {
    if(f[pos][sum]!= -1) return f[pos][sum];
/ h% y) E" g; W. a+ m    if(sum == 2019) return 1;
; |# _( m, ~: @7 g' i; `) ~$ d% C    if(pos>= prime.size()||sum> 2019) return 0;
, @* x% s7 Y% N! V, E+ C) r
    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
2 D; _4 v! f/ l}
3 K+ X( t: C' L* e
int main() {
- N; Y) |. B6 Q. k) ]    init();
" H0 [4 B. n4 V4 w# }( E! B
    mem(f,-1);
) @# b5 J2 j& W  T' }    ll ans = dfs(0,0);
- S, M8 z$ ?* |$ C) l. i) o    cout<<ans<<endl;

% c& t5 O  R* J' {) ]    return 0;
}
---------------------
作者：nka_kun

2 }7 L  d; k* P* I
/ i+ ^  z3 C- s0 g* r