题目描述
输入一个正整数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,1<=n<=1000000
输出
一个正整数,代表用2的幂组合出n的方案数,由于结果可能很大,仅保留后九位数字。
样例输入
7
样例输出
6
参考代码
#include<stdio.h>
int a[1000000];
int main()
{
int n;
scanf("%d",&n);
a[1]=1;
int i;
a[2]=2;
a[3]=2;
for (i=4;i<=n;i++)
a[i]=(a[i-2]+a[i/2])%1000000000;
printf("%d",a[n]%1000000000);
return 0;
}
解析
暂无