「JoyOI1087」sumsets

2014年1月23日2,8000

题目描述

正整数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位数字）。

输入

一个整数，表示正整数N。

输出

一个整数，表示不同方案的数量。

样例输入

样例输出

提示

1 < = N < = 1000000

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[21],f[1000001];
int main()
{
    a[1]=1;
    for(int i=2;i<=20;i++)
       a[i]=a[i-1]<<1;
    f[0]=1;
    scanf("%d",&n);
    for(int i=1;i<=20;i++)
       for(int j=a[i];j<=n;j++)
       {
               f[j]+=f[j-a[i]];
               f[j]%=1000000000;
               }
    printf("%d",f[n]);
    return 0;
    }

#include<iostream>

#include<cstdio>

using namespace std;

int n,a[21],f[1000001];

int main()

{

a[1]=1;

for(int i=2;i<=20;i++)

a[i]=a[i-1]<<1;

f[0]=1;

scanf("%d",&n);

for(int i=1;i<=20;i++)

for(int j=a[i];j<=n;j++)

{

f[j]+=f[j-a[i]];

f[j]%=1000000000;

}

printf("%d",f[n]);

return 0;

}

« 「JoyOI1089」smrtfun 无聊写的A+B问题。。。 »

hzwer.com _ Home | http://hzwer.com

「JoyOI1087」sumsets

题目描述

输入

输出

样例输入

样例输出

提示

代码

分类目录

热门文章

Myfriends

近期评论