CF248E Piglet’s Birthday 题解

题意：

小猪今天过生日了。他的朋友小熊维尼想要给他最好的礼物 —— 一个蜂蜜罐。当然，小熊明白他不可能把整个罐子都送给小猪。事实上，他很可能会把罐子里的蜂蜜全都吃掉。因此，当小熊计划在路上吃一点小吃时，罐子最开始应该有尽可能多的蜂蜜。

前一天，小熊维尼补充了他的蜂蜜储备。小熊维尼家里有 $n$ 个货架，每个货架上可能有一些，也可能一个蜂蜜罐都没有。在一天中，小熊维尼来到蜂蜜货架上 $q$ 次；在第 $i$ 次来到货架 $u_{i}$，从中取出一些罐子 $k_{i}$，尝试了每个罐子的蜂蜜后，将所有这些罐子放在某个货架 $v_{i}$ 上。当小熊选择罐子时，他遵循自己的直觉。这意味着在货架 $u_{i}$ 上所有 $k_{i}$ 个罐子的集合中，他等概率地选择一个。

现在小熊记得他对蜂蜜罐执行的所有动作。他想要带着前一天没有尝试过的罐子参加聚会。为此，他必须知道没有一罐蜂蜜尝试过的货架数量 $m$ 的数学期望。为了更好地评估自己的机会，小熊维尼希望在执行每个动作后都知道 $m$ 的值。

你的任务是编写一个程序来为他找到这些值。

省流：

给定 $n$ 个货架，初始时每个上面有 $a_i$ 个蜜罐。

有 $q$ 次操作，每次操作形如 $u,v,k$，表示从货架 $u$ 上任意选择 $k$ 个蜜罐试吃（吃过的也还能吃），吃完后把这 $k$ 个蜜罐放到 $v$ 货架上去。

每次操作完之后回答所有蜜罐都被试吃过的货架数量的期望。

输入格式：

输入的第一行包含一个单独的数字 $n$（$1 \leq n \leq 10^{5}$）——小熊家的货架数量。第二行包含 $n$ 个整数 $a_{i}$（$1 \leq i \leq n$，$0 \leq a_{i} \leq 100$）——第 $i$ 个货架上的蜂蜜罐数量。

接下来一行包含一个整数 $q$（$1 \leq q \leq 10^{5}$）——小熊前一天所做动作的数量。然后是 $q$ 行，其中第 $i$ 行描述了按时间顺序发生的一个事件；该行包含三个整数 $u_{i}$，$v_{i}$ 和 $k_{i}$（$1 \leq u_{i},v_{i} \leq n$，$1 \leq k_{i} \leq 5$）——小熊从哪个货架取出罐子，小熊尝试了每个罐子后将罐子放在哪个货架上，以及小熊尝试的罐子数量，分别。

货架上的罐子编号从 $1$ 到 $n$。保证小熊维尼从未尝试过从货架上取更多的罐子。

输出格式：

对于每个小熊的动作，打印出该动作执行时的数学期望值 $m$。每个值的相对或绝对误差不得超过 $10^{-9}$。

可以发现，每个架子上没吃过的蜜罐 $🍯$ 永远不会超过 $100$ 个。

记没吃过的蜜罐初始有 $a_i$ 个，并记当前吃过和没吃过的一共有 $b_i$ 个。

设 $f(i,j)$ 表示第 $i$ 个架子上还剩 $j$ 个蜜罐没吃过的概率。（老套路了，期望转概率计算）

考虑转移，对于操作 $(u,v,w)$ ，有

$f(u,j) = \dfrac{\sum_{k=j}^{\min \{j + w,~b_u\}}f(u,k)\dbinom{k}{k-j}\dbinom{b_u-k}{w-(k-j)}}{\dbinom{b_i}{w}}$

注意这道题没有限制 $b_i$ 的大小，因此组合数的数组要开到 C[500000 + 15][5 + 5] ，并使用 double 。

时间复杂度 $\mathcal{O}(500\times q)$

代码：

#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)(1e5 + 15))
#define M ((int)(5e5 + 15))

int a[N], now[N];
double res, f[N][114], C[M][14];
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(10);
    int n, q; cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i]; now[i] = a[i];
        f[i][a[i]] = 1; res += f[i][0];
    }
    for(int i = 0; i < M - 5; i++) C[i][0] = 1;
    for(int i = 1; i < M - 5; i++)
        for(int j = 1; j <= min(i, 5ll); j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    cin >> q;
    for(int i = 1, u, v, w; i <= q; i++)
    {
        cin >> u >> v >> w; res -= f[u][0];
        for(int j = 0; j <= a[u]; j++)
        {
            double sum = 0;
            for(int k = j; k <= min(j + w, now[u]); k++)
                sum += f[u][k] * C[k][k - j] * C[now[u] - k][w - (k - j)];
            f[u][j] = sum / C[now[u]][w];
        }
        res += f[u][0]; now[u] -= w; now[v] += w;
        cout << res << '\n';
    }
    return 0;
}