hdu2580 a simple stone game

设f(n,m) $f(n,m)$表示剩余n $n$个石子且这次最多取m $m$时的NP $NP$状态，显然这个函数在m $m$上是单调的，同时状态的转移产生一条对角线且随着n $n$的增大逐渐右移，故从下到上可以在O(n) $O(n)$下算出某个点的状态。

然而这并没什么卵用，因为这道题的n≤10 8  $n/le 10^8$。

考虑k=2 $k=2$时的情况，P $P$点集合为斐波那契数列。观察这个规律的证明： 由Zeckendorf定理可知，任意正整数可以表示为不相邻的斐波那契数的和且这个组合对每个数唯一。设MIN(x) $MIN(x)$表示x $x$用斐波那契数分解之后的最小的数，以下欲证f(n)=min{i|f(n,i)=P}=MIN(n) $f(n)=/min/{i|f(n,i)=P/}=MIN(n)$。 显然f(2)=1=MIN(2) $f(2)=1=MIN(2)$，以下对n $n$进行归纳。 对于0<x<MIN(n) $0<x<MIN(n)$，注意到MIN(n−x)=MIN(MIN(n)−x) $MIN(n-x)=MIN(MIN(n)-x)$。 (1)因为MIN(MIN(n)−x)≤2x $MIN(MIN(n)-x)/le 2x$，故0<x<MIN(n) $0<x<MIN(n)$的转移一定达到N $N$点。 (2)因为MIN(n-MIN(n))>2MIN(n)MIN(n−MIN(n))>2MIN(n) $MIN(n-MIN(n))>2MIN(n)$，故此时转移到了PP $P$点。 其中(1)的证明很模糊，将会为k/ge 2k≥2 $k/ge 2$的情况进行详细的证明，故略去。

从k=2k=2 $k=2$的证明想到，为任意的kk $k$构造一个数列AA $A$，使其可以同样地唯一表示[1,n][1,n] $[1,n]$的数同时相邻数比大于k $k$。构造很简单： 设X i  $X_i$表示A i  $A_i$可以分解[1,X i ] $[1,X_i]$的数，那么A i+1 =X i +1 $A_{i+1}=X_i+1$，X i+1 =X i +1+X j |max{j|A i+1 A j  >k} $X_{i+1}=X_i+1+X_j|max/{j|/frac {A_{i+1}} {A_j} > k/}$。 X i+1 X i+1 A i+2 −1A i+2 A i  =X i +X j +1=A i+1 +X j =A i+1 +A j+1 −1=A i+1 +A j+1 =A i−1 +A j |min{j|A i−1 A j  ≤k}   $$/begin{align}X_{i+1}&=X_i+X_j+1//X_{i+1}&=A_{i+1}+X_j//A_{i+2}-1&=A_{i+1}+A_{j+1}-1//A_{i+2}&=A_{i+1}+A_{j+1}//A_i&=A_{i-1}+A_j|min/{j|/frac {A_{i-1}} {A_j}/le k/}///end{align}$$ 以下证明对于任意A i =a+b $A_i=a+b$，MIN(a)b ≤k $/frac {MIN(a)} b /le k$。 设A j i   $A_{j_i}$表示对于A i −1 $A_i-1$的从小到大第i $i$个分解。 从b=1 $b=1$开始推导，此时b $b$与MIN(A i −b) $MIN(A_i-b)$都会落在[1,k] $[1,k]$上，故成立。 此后产生A j 1   $A_{j_1}$次减1，期间显然成立。 当b=A j 1  +1 $b=A_{j_1}+1$时，a $a$在之前的MIN $MIN$被完全消去，也就是说，此时的MIN(a) $MIN(a)$变为A j 2   $A_{j_2}$，同时，由于j 1 =max{j|A j 2  A j  >k} $j_1=max/{j|/frac {A_{j_2}} {A_j} > k/}$，故此时kb≥A j 2  =MIN(a) $kb/ge A_{j_2}=MIN(a)$。 而之后在A j 2   $A_{j_2}$被完全消去之前，都保持满足kb≥MIN(a) $kb/ge MIN(a)$，因为这期间产生的所有MIN $MIN$都小于A j 2   $A_{j_2}$。 在A j 2   $A_{j_2}$被完全消去时，推导同对A j 1   $A_{j_1}$的推导，即当A j i   $A_{j_i}$被消去时，b=A j i  +1 $b=A_{j_i}+1$。

故对于k>2 $k>2$，可以采用与k=2 $k=2$时的证明相同的方法证明f(n)=MIN(n) $f(n)=MIN(n)$。 那么生成了A $A$之后就可以贪心分解n $n$，即可得出结果。 生成A $A$所需的复杂度为O(|A|) $O(|A|)$： A i A i−1   =A i−1 A i−1  +A j A i−1  =1+A j A i−1  ≥1+1k    $$/begin{align}/frac {A_i} {A_{i-1}}&=/frac {A_{i-1}} {A_{i-1}} + /frac {A_j} {A_{i-1}}//&=1+/frac {A_j} {A_{i-1}}//&/ge 1+ /frac 1 k/end{align}$$ 故总的复杂度为O(log 1+1k  n) $O(log_{1+/frac 1 k}n)$。