Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:完全背包可解...

Posted by LinJunPing at 2020-07-22 22:34:00 on Problem 2229
In Reply To:完全背包可解... Posted by:JamesHarden at 2016-08-08 17:41:10
```> #include <iostream>
> #include <cstdio>
> #include <string.h>
> #include <stack>
> #include <queue>
> #include <map>
> #include <set>
> #include <vector>
> #include <math.h>
> #include <algorithm>
> using namespace std;
> #define LL long long
> #define INF 0x3f3f3f3f
> const double pi = acos(-1.0);
> const int mod = 1e9;
>
> const int N =1e6+10;
>
> int dp[N];
>
> void Init()
> {
> 	memset(dp,0,sizeof(dp));
>
>
> 	dp[0]=dp[1]=1;
> 	for(int i=1;i<=22;i++)
> 	{
> 		for(int j=2;j<=1000000;j++)
> 		{
> 			int v=1<<(i-1);
> 			if(j>=v)
> 				dp[j]=dp[j-v]+dp[j];
> 			while(dp[j]>mod)
> 				dp[j]-=mod;
> 		}
> 	}
> }
> int main()
> {
> 	int n;
> 	Init();
> 	while(~scanf("%d",&n))
> 		printf("%d\n",dp[n]);
> 	return 0;
> }
>
>
>
```

Followed by: