九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1084-九度Online Judge,用代码记录你的成长之路!

题目1084:整数拆分

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:3171

解决:1330

题目描述:

一个整数总可以拆分为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
来源:
2010年清华大学计算机研究生机试真题
答疑:
解题遇到问题?分享解题心得?讨论本题请访问:http://t.jobdu.com/thread-7807-1-1.html