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;
}