3034. 数字拆分

单点时限: 2.0 sec

内存限制: 256 MB

将一个正整数拆分为成 $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$ ($1≤n≤1000000$),输出 $f(n)%1000000000$。

输入格式

第 $1$ 行:一个整数 $T$ ($1 \le T \le 10$) 为问题数。

接下来 $T$ 行,每行输入一个正整数 $n(1≤n≤1000000)$。

输出格式

对于每个问题,输出一行问题的编号($0$ 开始编号,格式:case #0: 等)。

然后对应每个问题在一行中输出 $f(n)%1000000000$。

样例

Input
3
7
9
46
Output
case #0:
6
case #1:
10
case #2:
598

298 人解决,338 人已尝试。

476 份提交通过,共有 1281 份提交。

2.0 EMB 奖励。

创建: 6 年,1 月前.

修改: 1 年,10 月前.

最后提交: 3 天,15 小时前.

来源: 2014年编程实践课程第三次上机考试

题目标签