hdu 2709

地址：http://acm.hdu.edu.cn/showproblem.php?pid=2709

题意：一个整数n，表示为若干个2的幂的数字和，问有多少种(mod 1e9)。

mark：递推题，考虑1的个数不同，剩下的都是2的幂，可以除以2转移成更小的状态。得递推方程为dp[i] = dp[i-2] + dp[i/2]。注意初始值。

代码：

 1 # include <stdio.h>
 2 
 3 
 4 int tab[1000010] = {1, 1, 2} ;
 5 
 6 
 7 int main ()
 8 {
 9     int i ;
10     for (i = 3 ; i <= 1000000 ; i++)
11         tab[i] = (tab[i-2] + tab[i/2] ) % 1000000000 ;
12     while (~scanf ("%d", &i))
13         printf ("%d\n", tab[i]) ;
14     return 0 ;
15 }