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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
: G: a, C" T8 \+ s+ o
# L$ M! p0 w2 K& i, E0 Y& S求两两不同的素数组成2019的方案数
2 w' H8 L" X" N* N( u, Z( ?  i注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
9 I& F9 c* L( J( W$ ^; @结果: 55965365465060
代码:
; B  k; f$ O" m#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
; m; K( `3 h# e' m2 `- Utypedef long long ll;
const int inf = 0x3f3f3f3f;
$ j  @" d- U) T+ Z5 Y% kconst int maxn = 3e5+55555;
3 y; q0 D' Y7 U" h: Pconst ll mod = 998244353;
3 ]( I: S4 X+ w# Fconst double eps = 1e-7;
4 ?' ]1 u/ _* r' h: A1 d5 c
bool vis[12345];
vector<int>prime;
ll f[3000][3000];
' @9 \& ^( O- C; c( @: o
" s3 I! c* Z" tvoid init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
" y3 n2 m0 Q9 _: I' u& I            for(int j = i*i;j<= 3000;j+= i) {
+ \. T  z3 f, e5 H/ k% n, a                vis[j] = true;
            }
        }
8 j; c4 W% Q6 U9 z$ `/ h    }
; J+ {5 H( e# B* G, b( Y% T$ I    for(int i = 2;i<= 2019;i++) {
- z2 Q$ ?; o3 z& g        if(!vis) prime.push_back(i);
    }
. G8 i* b2 ^! }. o4 L$ i' c# `& T1 D}
" F7 c7 X" K( H# k& c( w% A
- K% b: ?- e! y5 ]8 k5 _9 E' Zll dfs(int pos,int sum) {
    if(f[pos][sum]!= -1) return f[pos][sum];
    if(sum == 2019) return 1;
! x" W& p5 Y- L% t    if(pos>= prime.size()||sum> 2019) return 0;
7 i9 L+ \  B3 f5 I- }/ r
    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
) n5 u* l; o; T2 j! N    return f[pos][sum] = ans;
}

int main() {
6 C; G& o; ?% t! A& ^    init();

. k; |; P: t' B    mem(f,-1);
    ll ans = dfs(0,0);
    cout<<ans<<endl;

    return 0;
' \9 I& N, N' \- }0 R}
" B$ h% |- }0 f2 h( Q---------------------
作者：nka_kun
& T, `! ]2 n& t1 b; T9 K

' v- w# y. {% D3 w