期望好题，可以帮助我们更加深入地了解期望。
由于 \(k\) 种装备相同，所以只要计算卖掉一种装备得到的金币期望乘以 \(k\) 就行了。
为了避免讨论当前状态的概率，期望 DP 通常采用逆推的方式。
设 \(f_{i,j}\) 表示从当前打了 \(i\) 只怪兽，这种装备等级为 \(j\) 这个状态开始，最终获得金币的期望。
分类讨论贡献。
- 有 \(\dfrac {k-1}k\) 的概率抽不到这种装备。这个时候直接从 \(f_{i+1,j}\) 继承，贡献为 \(\dfrac {(k-1)f_{i+1,j}}k\)。
- 有 \(\dfrac j{(j+1)k}\) 的概率抽到等级不超过当前装备的同种装备，此时的贡献为 \(\dfrac {\sum_{l=1}^jf_{i+1,j}+l}{(j+1)k}=\dfrac {jf_{i+1,j}+\frac 12 j(j+1)}{(j+1)k}\)。
- 有 \(\dfrac 1{(j+1)k}\) 的概率抽到等级为 \(j+1\) 的同种装备，此时的贡献为 \(\dfrac {f_{i+1,j+1}+j}{(j+1)k}\)。
综上，可以得出状态转移方程：
\[\begin{aligned} f_{i,j}&=\dfrac {(k-1)f_{i+1,j}}k+\dfrac {jf_{i+1,j}+\frac 12 j(j+1)}{(j+1)k}+\dfrac {f_{i+1,j+1}+j}{(j+1)k}\\ &=\dfrac{2(k-1)f_{i+1,j}}{2k}+\dfrac {2jf_{i+1,j}}{2(j+1)k}+\dfrac{j}{2k}+\dfrac {2f_{i+1,j+1}+2j}{2(j+1)k}\\ &=\frac{2(j+1)(k-1)f_{i+1,j}+2jf_{i+1,j}+j(j+3)+2f_{i+1,j+1}}{2(j+1)k}\\ &=\frac{2(kj+k-1)f_{i+1,j}+j(j+3)+2f_{i+1,j+1}}{2(j+1)k} \end{aligned} \]发现状态是 \(\mathcal O(n^2)\) 的。怎么办呢？
我们发现如果 \(j\) 取到比较大的值时，概率是很小的。由于题目要求使用浮点数而非取模，我们可以在允许的精度范围内损失一些。所以我们为 \(j\) 设置一个上限 \(M\)，舍弃后面的状态。上限越大，精度损失越小。
具体分析一下，从 \(j\) 级升到 \(j+1\) 级概率为 \(\dfrac 1{(j+1)k}\)，所以期望还要打 \((j+1)k\) 个怪兽才能从 \(j\) 级升到 \(j+1\) 级。则这个装备升级到 \(t\) 的期望次数为 \(\sum_{j=2}^tjk=\dfrac k2(t+2)(t-1)\)。若这个值不超过 \(n\)，则 \(t\) 的上界约为 \(500\)。我们取上界 \(M=800\) 就差不多了。
时间复杂度为 \(\mathcal O(nM)\)。本来以为不开滚动数组也能过，没想到还是 MLE 了。
不过开了滚动数组代码依然很短：
#include<cstdio>
using namespace std;
typedef double ld;
const int N=1e5+5,M=800;
int n,k;ld f[2][M+5];
int main(){
scanf("%d%d",&n,&k);
for(int i=n;i>=1;i--)for(int j=1;j<=M;j++){
f[i&1][j]=(2*(k*j+k-1)*f[(i&1)^1][j]+j*(j+3)+2*f[(i&1)^1][j+1])/(2.0*(j+1)*k);
}
printf("%.10lf\n",f[1][1]*k);
return 0;
}