题解：P11465 水上舞者索尼娅

设

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}

f_{1,n}

即为答案，使用快速幂与乘法逆元计算即可，时间复杂度为

\Theta(T(\log n+\log\text{mod}))

。

文章操作