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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
; B5 [7 y' o$ P' q* T4 G
7 i  e" U4 D( v9 D! f( Y" h( i4 O求两两不同的素数组成2019的方案数
6 R, _/ w  B% w8 q1 b$ v% S注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
9 D; H5 f# C3 q: A结果: 55965365465060
$ n1 `6 x; v: F) K3 u. k$ ~代码:
1 `) X& B+ o7 I* n9 c9 E( l#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
' r0 h! Y2 b6 Z* Jusing namespace std;
4 H" V- f/ @0 Q$ n7 @typedef long long ll;
1 Z# }. G$ O* e2 T9 z7 J  ^const int inf = 0x3f3f3f3f;
* o. H6 X$ Q/ sconst int maxn = 3e5+55555;
: N5 o5 ^% l7 @0 }const ll mod = 998244353;
const double eps = 1e-7;

bool vis[12345];
vector<int>prime;
7 j& I3 Y& u- `' E% dll f[3000][3000];

) e6 b) Y4 _3 a3 |& b! }void init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
' ]* B; P1 J: ?5 V6 C        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
/ `9 T( m2 F( Y                vis[j] = true;
/ A# a0 Z& A4 U. n            }
        }
+ v  z! p- d: e# e6 d  [; ?    }
: G4 b( X. \* a' L; J    for(int i = 2;i<= 2019;i++) {
- ]( C+ a9 B  A" m        if(!vis) prime.push_back(i);
    }
}
5 H* _" O+ b, I, Y  _
2 N! H1 s5 Y: oll dfs(int pos,int sum) {
' }4 q2 M& o# H    if(f[pos][sum]!= -1) return f[pos][sum];
6 D& D& J% ?$ Q; L9 c3 T9 L    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;
3 x1 V, T* Q9 f- P# l
    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
3 u4 \3 C4 ?7 P6 K% X' K    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
/ n- r7 B& n9 h; [/ ~    return f[pos][sum] = ans;
}

2 E$ W- B' |6 @8 F- ]int main() {
    init();
) G7 N4 s! p  `7 Z! ^+ J
    mem(f,-1);
    ll ans = dfs(0,0);
    cout<<ans<<endl;

7 o- C+ F9 Y2 ^6 t% h8 N: o    return 0;
}
---------------------
/ L( k" x9 X5 Q4 K3 i作者：nka_kun
  _* z  ]' P6 S3 ~* Y7 {$ b