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