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

杨利霞

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

( @4 C3 o! V; u7 f求两两不同的素数组成2019的方案数
2 E. A3 Y6 U2 a8 _1 B* v注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
8 I: C6 e5 m+ X: F7 A" [9 Oconst int inf = 0x3f3f3f3f;
! w3 t8 H( u( _0 @. Y' x, i# o' S8 ^const int maxn = 3e5+55555;
* E7 D; |0 R- ~const ll mod = 998244353;
const double eps = 1e-7;

2 u& ?$ G, Z+ d  ]2 x* xbool vis[12345];
vector<int>prime;
9 [* a; s+ v4 C. Sll f[3000][3000];
2 a* ]$ V, q, C# S: V5 M, R
! D# i2 ^' ?" G/ f" d, Rvoid init() { //素数筛
4 D" [. n* c1 f; _1 l* l    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
( N) ]0 ]8 n! G3 t            for(int j = i*i;j<= 3000;j+= i) {
                vis[j] = true;
            }
- w7 C* [5 j5 {1 n        }
    }
2 Q. N! J. `: }0 [. z* |6 Q    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
    }
}
& ]6 c2 u8 }, ^* C" E
% W7 _* n5 c: L- ^' Wll dfs(int pos,int sum) {
( Q6 Y+ G; t6 V    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;
  b" J! L/ L# g& b7 j    ans+= dfs(pos+1,sum);// 不要当前这个素数
  Y" ~6 K+ J  ^/ X3 |    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
* r8 }, A% R* i+ g9 I    return f[pos][sum] = ans;
( A1 P6 c8 ~9 r5 e! W# d}

8 d( U% t* v% J6 K( ~/ Z0 lint main() {
    init();
( ?  C  X1 c. G( w9 L
    mem(f,-1);
6 @9 d0 k8 E5 Q! X* N  x    ll ans = dfs(0,0);
    cout<<ans<<endl;

, f1 B& d$ v8 L1 C3 W4 @    return 0;
}
---------------------
作者：nka_kun


/ F' D) O+ G9 B/ t) }5 e