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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
; a; J$ B" ?' K! Q
# w7 f( p3 E4 }5 t求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
+ J" J! I4 K9 L+ p结果: 55965365465060
' E8 e5 l: s4 S4 K3 \, ^2 V代码:
: d6 I1 N1 o& ?1 n7 `#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
4 I  Q# T0 j2 t3 S/ C8 nusing namespace std;
. D3 ]5 u" Z0 itypedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;
6 f/ P) Q: L  _
bool vis[12345];
) T0 O% K; `1 f% A- Y, cvector<int>prime;
ll f[3000][3000];
8 G. Y  X, ~) J  {* k
void init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
; f1 `4 ~- ?' Z2 x" v                vis[j] = true;
8 b. o& q1 I/ a& L. U! ]! g            }
        }
2 o6 C- b, k; G5 I1 c3 f' g    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
4 p2 s2 S' P6 v3 o& M, }    }
$ O: a4 p! S$ P& q! G}
7 q. S6 g1 f1 Z* ]: R
ll dfs(int pos,int sum) {
/ Q& l* l; s% Z" F    if(f[pos][sum]!= -1) return f[pos][sum];
+ b  [" `' y; M5 g' \    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;
! f" _8 y4 F1 p3 M2 T# ?
    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
5 ^: P- D' X6 E7 C% I1 u0 j" M    return f[pos][sum] = ans;
# M7 L  R* l* d% e# Z; i}
6 I0 B: k8 g" H$ K& U
int main() {
    init();

    mem(f,-1);
    ll ans = dfs(0,0);
    cout<<ans<<endl;
+ e- w/ q# a6 H, K* L7 v% i
" i4 x8 d3 `0 F    return 0;
& C/ b* {) R3 X+ I}
---------------------
作者：nka_kun

% [2 ^4 W9 f6 \9 h0 L' r
- k% [3 U$ c/ C