BZOJ-1677: [Usaco2005 Jan]Sumsets 求和

[文章目录]

Description

给出一个N(1≤N≤10^6),使用一些2的若干次幂的数相加来求之.问有多少种方法

话说我什么时候菜成这样了,这种题都得找题解。
递推,设f[x]为求x的方法数。如果x是奇数,发现无论怎么分都会有一个1,所以f[x]=f[x-1]。如果x是偶数,分两种情况讨论,如果分出来的树中有1,方案数为f[x-1],如果没有,那么相当于f[x/2]的方案数,其中每个数都扩大二倍。f[x]=f[x>>1]+f[x-1]

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
const ll mod=1000000000;
ll f[1001000];
int main()
{
    scanf("%d",&n); f[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(i&1) f[i]=f[i-1];
        else f[i]=(f[i-1]+f[i>>1])%mod;
    }
    printf("%lld",f[n]);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注