CF464D World of Darkraft - 2 题解

题意：

cxy 在玩 “World of Dardraft - 2” 游戏，有 $k$ 种不同的装备，初始状态下所有的装备都是 $1$ 级的。

每当打败一个怪物，她就能获得一个新的装备，新的装备由如下规则生成：

先从 $k$ 种装备中等概率随机选择一种装备，记作 $i$。

设当前类型为 $i$ 的装备的等级为 $t_i$，则会从 $[1, t_i + 1]$ 中等概率随机一个作为新的装备的等级。

cxy 会从新的装备和原来 (对应类型) 的装备中选择一个级别更高的，将它装备上，并出售剩下的一个装备，等级为 $x$ 的装备的售价为 $x$ (个硬币)。

请帮助 cxy 决定打败 $n$ 个怪物后获得的硬币数的期望。

输入格式：

共一行，包含两个正整数 $n, k$ 。

输出格式：

输出一行一个实数，表示打败 $n$ 个怪物后获得硬币数的期望。答案被认为正确当且仅当相对或绝对误差不超过 $10^{-9}$。

数据范围：

$1 \le n \le 10^5,1\le k \le 100$

注意到最终硬币的期望值对于各个装备是独立的。

根据期望的线性性质，我们可以算出单个装备的期望，然后再乘以 $k$ 。

设 $f_{i,j}$ 表示还需要打败 $i$ 个怪物，且当前装备等级为 $j$ 的情况下，后面 $i$ 次得到硬币的期望。

初始状态为 $f_{0,j} = 0$ 。

考虑转移。由于掉某一种装备的概率为 $\frac{1}{k}$ ，因此有 $\frac{k-1}{k}$ 的概率掉出其他装备

而掉出其他装备对这个装备的等级没有影响，故前者要乘上 $f_{i-1,j}$ 。

在这 $\frac{1}{k}$ 的概率中，有 $\frac{1}{j+1}$ 的概率产生 $j+1$ 级装备（乘法原理）

把原来的 $j$ 卖了，权值对应为 $\frac{1}{k(j+1)}\left(f_{i-1, j+1}+j\right)$ 。

显然还有 $\frac{j}{j+1}$ 的概率产生低级装备，则转移方程为

$\begin{aligned} f_{i, j}&=\frac{k-1}{k} f_{i-1, j}+\frac{1}{k(j+1)}\left[\sum_{t=1}^j\left(f_{i-1, j}+t\right)+\left(f_{i-1, j+1}+j\right)\right] \\[6pt]&=\frac{(k(j+1)-1) f_{i-1, j}+f_{i-1, j+1}+\frac{1}{2} j(j+3)}{k(j+1)} \end{aligned}$

最后答案为 $k\cdot f_{n,1}$ 时间复杂度 $\mathcal{O}(n^2)$ ，空间复杂度 $\mathcal{O}(n)$。

接下来就是神奇的浮点优化时间了。

注意到其实它升到等级极高的情况实际上可能性几乎为 $0$ ，因此有很多的 $f$ 在精度范围内都是无意义的

由几何分布，概率为 $p$ 的时间期望 $\frac{1}{p}$ 次才能成功，则对于一个特定的装备

它从第 $j$ 级升到第 $j+1$ 级的概率为 $\frac{1}{k(j+1)}$ ，因此其期望的次数为 $k(j+1)$ 。

则从 $1$ 级升到 $m$ 级的期望次数为 $2k + 3k + \cdots + mk \sim \frac{1}{2}m^2k < n$

则有 $m < \sqrt{\dfrac{2n}{k}}$ ，即期望等级大约在 $500$ 左右。

事实上，超过 $1000$ 在 double 中已经存不了了，因此不会对答案产生影响。

所以第二维开个 $1000$ 左右即可。

时间复杂度 $\mathcal{O}(1000 \times n ) = \mathcal{O}(n \sqrt{n})$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3+15))

int n,k,now,pre;
double A,B,C,f[2][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(15);
    cin >> n >> k;
    for(int i=1; i<=n; i++)
    {
        now = i & 1, pre = now ^ 1;
        for(int j=1; j<N-5; j++)
        {
            A = f[pre][j] * (k * (j+1) - 1);
            B = f[pre][j+1];
            C = (double)(j * (j+3) / 2);
            f[now][j] = (A + B + C) / (double)(k * (j+1));
        }
    }
    cout << f[n & 1][1] * k << '\n';
    return 0;
}