题目来源：POJ2229

分析

题目大意为：

给出一个正整数N(<=10^6)，可知N可分解为多个2^K(>=0)的数相加

如:
7 = 1 + 1 + 1 + 1 + 1 + 1 + 1;

= 1 + 1 + 1 + 1 + 1 + 2;

= 1 + 1 + 1 + 2 + 2;

= 1 + 1 + 1 + 4;

= 1 + 2 + 2 + 2;

= 1 + 2 + 4;

共6种；

求种数。

刚拿到题目的时候，我联想到了整数的划分。

套用那个动归方程去做。

即F[I,J] 表示，将I划分成最大为J的整数和。

这样 F[I,J] = SIGMA{ F[I-J,K] J>=K }

这题便是，F[I,J] 表示，将I划分成最大为2^J(>=0)的整数和。

方程一样 F[I,J] = SIGMA{ F[I-1,K] J>=K }

可是这样做的时间复杂度为,O(nlognlogn)，会超时。

但我又想到F[I,J] 只从 F[I-J,0] + F[I-J,1] +...+ F[I-1,J]

这样可以用C[I,J] 表示 F[I,J] 的前缀和

方程转移变成 F[I,J] = C[I-J,T] 其中T = MIN { log(i-j) , j } (最大T,2^T不能超过I-J，T不能超过J)

`C[I,J] = C[I,J-1]+F[I,J]`

这样省去了K的那层循环，复杂度优化为O(n*logn)，非常遗憾，还是会超时。

解法

想了半天以后，只能去看题解。

题解也是用动归。

用F[I]表示把I划分的种数。

则 在所有构成I的加数中，只有1是奇数。

若I为奇数，则必然至少含1个1.且这个1必然独立。则F[I] = F[I-1]

若I为偶数，则若含1，至少含2个，且这2个1也独立。F[I] = F[I-2]

若不含1，则所有的加数都是偶数，所以所有的加数都可以映射到其1/2，如 8 = 2 + 2 + 4 可以映射到 4 = 1 + 1 + 2

                                则`F[I] = F[I/2]`

综上，

1
2
3
f[i] = f[i-1]   {i mod 2=1}               

f[i-2] + f[i/2] {i mod 2=0}

优化

详解

初始 f[1]=1 f[2]=2

细节

源程序

解一：(优化后)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Program Lwx;
Const 	md=1000000000;
Var 	n:longint;
    	a:array[0..1000000, 0..20] of longint;
    	c:array[0..1000000, -1..20] of longint;
    	b:array[0..100] of longint;
    	ans, i, j, k, l, x, y, z:longint;

Begin
  	readln(n);
  	b[0] := 1; k := 0;
  	while b[k] < n do
  	begin
   		inc(k);
   		b[k] := b[k-1] * 2;
  	end;
  	c[1, 0] := 1;
 	for i := 2 to n do
  	begin
   		c[i, -1] := 0;
   		for j := 0 to k do
    		if b[j] <= i then
    		begin
      			if b[j] = i then begin a[i, j] := 1; continue; end
      			else a[i, j] := 0;


      			y := trunc(ln(i-b[j])/ln(2));
      			if y > j then y := j;
      			a[i, j] := (a[i,j ] + c[i-b[j], y]) mod md;
      			c[i, j] := (c[i, j-1] + a[i, j]) mod md;
    		end else break;
  	end;
  	ans := 0;
  	for i := 0 to k do
  	if b[i] <= n then ans := (ans + a[n, i]) mod md;
  	write(ans);
End.

解二：(正解)

1
2
3
4
5
6
7
8
9
10
11
12
Program Lwx;
Const 	md=1000000000;
Var 	a:array[0..1000000] of longint;
   	n,i,j,k,l:longint;

Begin
  read(n);
  a[1] := 1; a[2] := 2;
  for i := 3 to n do 
  if i mod 2 = 1 then a[i] := a[i-1] else a[i] := (a[i-2] + a[i div 2]) mod md;
  write(a[n]);
End.