描述
正整数N可以被表示成若干2的幂次之和。例如,N = 7时,共有下列6种不同的方案:
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4
给出正整数N,计算不同方案的数量(保留最后9位数字)。
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4
给出正整数N,计算不同方案的数量(保留最后9位数字)。
输入格式
一个整数,表示正整数N。
输出格式
一个整数,表示不同方案的数量。
测试样例1
输入
输出
备注
1 <= N <= 1000000
题解
#include<iostream>
using namespace std;
int n,bin[],f[];
int main(){
cin>>n;
bin[]=;
for(int i=;i<=;i++)
bin[i]=bin[i-]<<;
f[]=;
for(int i=;i<=;i++)
for(int j=bin[i];j<=n;j++)
f[j]=(f[j]+f[j-bin[i]])%;
cout<<f[n]<<endl;
return ;
}