[Usaco2005 Jan]Sumsets 求和

作者: MayFlyyh 分类: 其他 发布时间: 2018-05-25 13:22 ė 6 没有评论

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

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/216

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部