Steven_MengのBlog

一个裸的完全背包,考虑将$2^k$当做物品,做完全背包即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdio>
#define MAXN 1000005
#define MAXM 24
#define MOD 1000000000
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int pow2[MAXN];
int dp[MAXN];//dp[i]和为i的方法数
int main(){
int n=read();
for (register int i=0;i<MAXM;++i){
pow2[i]=(1<<i);
}
dp[0]=1;
for (register int j=0;j<MAXM;++j){
for (register int i=1;i<=n;++i){
if (i-pow2[j]>=0){
dp[i]+=dp[i-pow2[j]];
dp[i]%=MOD;
}
}
}
printf("%d\n",dp[n]);
}

 评论