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

杨利霞

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

7 G7 C' V- q  ]% F" n求两两不同的素数组成2019的方案数
4 U5 E, |- n; U% C8 k& @注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
& c/ ^) C; l" s, w# g2 V% e结果: 55965365465060
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
. [5 q, w- g1 q# R& B# Kconst int inf = 0x3f3f3f3f;
' ]" V4 z; A! }+ H4 Uconst int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

bool vis[12345];
vector<int>prime;
: o( j/ p* f8 d3 c6 S; }" B$ Yll f[3000][3000];

% K" U( h! e! C& g9 t7 Nvoid init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
$ v; W5 I( k! S( g. o        if(!vis) {
; h. b5 U/ h; f# V            for(int j = i*i;j<= 3000;j+= i) {
                vis[j] = true;
9 O) I, L& H2 f* q            }
        }
6 d1 S, w; _, `. Q) m    }
/ B6 h+ c" q/ J& y4 |    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
( ~# I3 }$ j' \( V( d  o    }
}

* a0 p- H6 Z, M! U; R% r7 tll dfs(int pos,int sum) {
% U! o5 k; G2 u$ m    if(f[pos][sum]!= -1) return f[pos][sum];
( p4 ]2 y# E; O1 l  ?    if(sum == 2019) return 1;
3 f6 y9 h, K0 U+ ~- W    if(pos>= prime.size()||sum> 2019) return 0;

, H2 p. }2 Q; B    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
7 u8 h1 E- G8 b1 t    return f[pos][sum] = ans;
; T: N% n5 ]) ~: @}
6 q( g; B$ A  `5 K
int main() {
    init();
! ?9 W: T& S5 V6 h& l% s7 u
    mem(f,-1);
    ll ans = dfs(0,0);
    cout<<ans<<endl;

    return 0;
9 s: h! f9 b! [* n}
* {- F7 W9 G! b% C% H4 b---------------------
: a" J+ `$ k' {* v作者：nka_kun
3 ]+ ^' m, X8 S& a