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

杨利霞

2019第十届蓝桥杯B组决赛题解第二题
- Y2 M7 _- b. y2 K) k
求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
3 ?( F2 `% I- X% P, J7 }! Y代码:
& V% M  t  V  {0 H* C4 P5 U( T#include<bits/stdc++.h>
3 |9 y1 ]' W0 M$ X/ k' @#define mem(a,b) memset(a,b,sizeof(a))
5 H% L: P' H0 k9 u/ q7 R+ s5 I0 F. Ausing namespace std;
typedef long long ll;
9 k" |7 r9 R- [- r6 Xconst int inf = 0x3f3f3f3f;
. v8 P( H0 I6 ?! Sconst int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

0 v' x/ g- U# u$ S  o$ qbool vis[12345];
) O3 n! c' O; r: Zvector<int>prime;
1 Z) M6 B3 T: E; N( Mll f[3000][3000];

void init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
                vis[j] = true;
            }
        }
* u: h- |* b  a! Q: M/ G. a    }
- Y; p( C$ F# ~6 _! r: ]! d    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
/ P; O, n/ m. J* G7 u4 G* m! P    }
}
% w5 Z+ r( q9 g* m6 z+ s3 }0 b3 ^: Y
2 n- a' d& c" tll dfs(int pos,int sum) {
    if(f[pos][sum]!= -1) return f[pos][sum];
    if(sum == 2019) return 1;
! R  ~- K4 c! s* \& }    if(pos>= prime.size()||sum> 2019) return 0;

    ll ans = 0;
# N4 p, W# [0 ^2 X2 z0 \' [    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
/ U. f* Y5 t4 H& T    return f[pos][sum] = ans;
$ v. ^3 b+ B9 x3 K* ?- S: J$ G; B$ N& W}

8 A; V) m2 e& l) X3 x7 K  T6 }+ kint main() {
  @2 k/ s5 }4 h6 N# k    init();

    mem(f,-1);
, @* H* G; a2 r/ f7 W( m1 ~    ll ans = dfs(0,0);
    cout<<ans<<endl;

/ x4 B3 d+ Z4 T+ f' g* L- g/ g- s    return 0;
( E* W, X# w6 D, c}
  F# y6 Z+ e! ~& R/ r( w. x---------------------
作者：nka_kun


) [) G( e- l( ?' m" L  O% x6 [