[Usaco2005 Jan]Sumsets 求和
给出一个N(1≤N≤10^6),使用一些2的若干次幂的数相加来求之.问有多少种方法
Input
一个整数N.Output
方法数.这个数可能很大,请输出其在十进制下的最后9位.Sample Input
7
Sample Output
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
发现如果x是2的倍数则可以拆成x-1与x/2
为什么?拆成x-1相当于给(x-1)的每个方案+1,就变成了又一种方案了
拆成x/2相当于给x/2的每个方案*2 就变成了另一种方案了
仔细一想并不会重复,因为第一种情况每个方案必然带1,
而第二种情况每个方案必然不带1
再想想发现并不会重复,因为含1、含2的情况都存在
为什么不能从x-2递推上来?(x-2),因为x-2方案中可能有带2的情况
而2+2是一种,合并起来又可以产生个4,就变成两种了
int n,a[1000001];
int main(){
scanf("%d",&n);
a[1]=1;
for(int i=2;i<=n;i++){
a[i]=a[i-1];
if(!(i&1))a[i]=a[i-1]+a[i>>1];
a[i]%=1000000000;
}
printf("%d",a[n]);
return 0;
}
0 条评论