每组输入包括一个整数:N(1<=N<=1000000)。
对于每组数据,输出f(n)%1000000000。
7
6
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[]b = new int[n+1]; int[]a = new int[n+1]; int x = 0; for(int i = 0;i<=n;i++){ b[i] = (int)Math.pow(2.0,i); if(b[i]>n){ x = i; break; } } a[0] = 1; for(int i = 0;i<x;i++){ for(int j = b[i];j<=n;j++){ a[j]+=(a[j-b[i]]%1000000000); a[j]%=1000000000; } } System.out.println(a[n]); } }
有两种情况
n是奇数,必定可以拆出一个1,不管其他的部分怎么变,这个1不会改变,也就是说这个1不会影响拆分的结果,即
dp[i]=dp[i-1]
n是偶数,拆分的结果只有两种情况,要么带有1的形式,要么不带1的形式(全是偶数)
奇拆分(带有1的形式):dp[i-1] 原因同上
偶拆分(全是偶数的形式):dp[i/2]
dp[8] 4+4 2+2+4 2+2+2+2
dp[4] 2+2 1+1+2 1+1+1+1
可以发现dp[8]的偶拆分刚好是dp[4]所有拆分情况的2倍形式
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s; int[] dp = new int[1000001]; dp[1] = 1; for (int i = 2; i <= 1000000; i++) { if (i % 2 == 0) { dp[i] = (dp[i / 2] + dp[i - 1]) % 1000000000; } else { dp[i] = dp[i - 1]; } } while ((s = br.readLine()) != null) { int n = Integer.parseInt(s); System.out.println(dp[n]); } } }