首页 > ACM题库 > 九度OJ > 九度-1084-整数拆分[解题代码]
2013
12-12

九度-1084-整数拆分[解题代码]

题目来源:2010年清华大学计算机研究生机试真题

题目描述:

一个整数总可以拆分为2的幂的和,例如:
7=1+2+4
7=1+2+2+2
7=1+1+1+4
7=1+1+1+2+2
7=1+1+1+1+1+2
7=1+1+1+1+1+1+1
总共有六种不同的拆分方式。
再比如:4可以拆分成:4 = 4,4 = 1 + 1 + 1 + 1,4 = 2 + 2,4=1+1+2。
用f(n)表示n的不同拆分的种数,例如f(7)=6.
要求编写程序,读入n(不超过1000000),输出f(n)%1000000000。

输入:

每组输入包括一个整数:N(1<=N<=1000000)。

输出:

对于每组数据,输出f(n)%1000000000。

样例输入:
7
样例输出:
6

cpp 代码如下:
#include<stdio.h>
int f[500000];
int main(){int i;f[f[0]=1]=2;for(i=2;i<=500000;++i)f[i]=(f[i-1]+f[i>>1])%1000000000;while(~scanf("%d",&i))printf("%d\n",f[i>>1]);}
/**************************************************************
	Problem: 1084
	User: coder
	Language: C++
	Result: Accepted
	Time:10 ms
	Memory:2972 kb
****************************************************************/