#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;
}

• Re:完全背包可解... (793) LinJunPing 2020-07-22 22:34:00
  • Re:完全背包可解... (17) LinJunPing 2020-07-22 22:36:00