Codeforces

Luogu

分析

显然装备之间没有区别，我们只要计算一种装备的期望，然后乘上 $k$ 即可。

考虑倒推。设 $dp_{i,j}$ 表示剩余 $i$ 个怪物、装备等级为 $j$ 期望获得的金币数，转移有三种：

• 选到了其它装备：概率为 $\frac{k-1}{k}$，期望收益为 $dp_{i-1,j}$。
• 选到了等级为 $j+1$ 的当前装备：概率为 $\frac{1}{k(j+1)}$，期望收益为 $dp_{i-1,j+1}+j$。
• 选到了等级为 $[1,j]$ 的当前装备：概率为 $\frac{j}{k(j+1)}$，期望收益为 $dp_{i-1,j}+\frac{j+1}{2}$。

这样子是 $\mathcal{O}(n^2)$ 的。注意到当装备等级很高时概率趋近于 $0$，所以我们可以只对前 $L$ 种等级 DP，复杂度 $\mathcal{O}(nL)$。计算得到期望等级大概是 $\mathcal{O}(\sqrt{\frac{n}{k}})$ 级别，所以我们可以令 $L=600$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,M=600+10;

int n,k;
double dp[2][M];

int main() {
    n=read(),k=read();
    for (int i=1;i<=n;++i) {
        int cur=i&1,pre=cur^1;
        for (int j=1;j<=600;++j) {
            dp[cur][j]=dp[pre][j]*(k-1)/k;
            dp[cur][j]+=(dp[pre][j+1]+j)/k/(j+1);
            dp[cur][j]+=(dp[pre][j]+(j+1)/2.0)/k*j/(j+1);
        }
    }
    printf("%.10lf\n",dp[n&1][1]*k);
    return 0;
}