题解：P11465 水上舞者索尼娅
Falashiro
·
·
题解
设 f_{i,j} 为初始只有一张费用为 i 的【一串香蕉（还剩 j 根）】时可以使用【一串香蕉】的次数，则 f_{0,1}=1，f_{1,1}=k\times f_{0,1}+1=k+1。
由题意易得，i>1 时：
\begin{aligned}
f_{1,i}&=k\times f_{0,i}+f_{1,i-1}+1\\
f_{0,i}&=f_{1,i-1}+1
\end{aligned}
则：
\begin{aligned}
f_{1,n}&=k\times f_{0,n}+f_{1,n-1}+1\\
&=k\times(f_{1,n-1}+1)+f_{1,n-1}+1\\
&=(k+1)\times f_{1,n-1}+(k+1)\\
&=(k+1)\times[(k+1)\times f_{1,n-2}+(k+1)]+(k+1)\\
&=(k+1)^2\times f_{1,n-2}+(k+1)^2+(k+1)\\
&\dots\\
&=(k+1)^{n-1}\times f_{1,1}+\sum\limits_{i=1}^{n-1}(k+1)^i\\
&=\sum\limits_{i=1}^{n}(k+1)^i\\
&=\frac{(k+1)\times[(k+1)^n-1]}{k}
\end{aligned}