洛谷P5405 [CTS2019] 氪金手游题解

题目链接：P5405 [CTS2019] 氪金手游

题意：

小刘同学是一个喜欢氪金手游的男孩子。

他最近迷上了一个新游戏，游戏的内容就是不断地抽卡。现在已知： - 卡池里总共有 \(N\) 种卡，第 \(i\) 种卡有一个权值 \(W_i\)，小刘同学不知道 \(W_i\) 具体的值是什么。但是他通过和网友交流，他了解到 \(W_i\) 服从一个分布。 - 具体地，对每个 \(i\)，小刘了解到三个参数 \(p_{i,1},p_{i,2},p_{i,3}\)，\(W_i\) 将会以 \(p_{i,j}\) 的概率取值为 \(j\)，保证 \(p_{i,1}+p_{i,2}+p_{i,3}=1\)。

小刘开始玩游戏了，他每次会氪一元钱来抽一张卡，其中抽到卡 \(i\) 的概率为：\(\frac{W_i}{\sum_j W_j}\)

小刘会不停地抽卡，直到他手里集齐了全部 \(N\) 种卡。

抽卡结束之后，服务器记录下来了小刘第一次得到每张卡的时间 \(T_i\)。游戏公司在这里设置了一个彩蛋：公司准备了 \(N-1\) 个二元组 \((u_i,v_i)\)，如果对任意的 \(i\)，成立 \(T_{u_i}<T_{v_i}\)，那么游戏公司就会认为小刘是极其幸运的，从而送给他一个橱柜的手办作为幸运大奖。

游戏公司为了降低获奖概率，它准备的这些 \((u_i,v_i)\) 满足这样一个性质：

对于任意的 \(\varnothing\ne S\subsetneq\{1,2,\ldots,N\}\)，总能找到 \((u_i,v_i)\) 满足：\(u_i\in S,v_i\notin S\) 或者 \(u_i\notin S,v_i\in S\)。

请你求出小刘同学能够得到幸运大奖的概率，可以保证结果是一个有理数，请输出它对 \(998244353\) 取模的结果。

输入格式：

第一行一个整数 \(N\)，表示卡的种类数。

接下来 \(N\) 行，每行三个整数 \(a_{i,1},a_{i,2},a_{i,3}\)，而题目给出的 \(p_{i,j}=\frac{a_{i,j}}{a_{i,1}+a_{i,2}+a_{i,3}}\)。

接下来 \(N-1\) 行，每行两个整数 \(u_i,v_i\)，描述一个二元组（意义见题目描述）。

输出格式：

输出一行一个整数，表示所求概率对 \(998244353\) 取模的结果。

数据范围：

对于全部的测试数据，保证 \(N\le 1000\)，\(a_{i,j}\le 10^6\)。

题目给的奇怪性质，就是说 \((u_i,v_i)\) 的基图（转成无向边后的图）是一棵树。

首先考虑最简单的情况，即这张图是一个根为 \(1\) 的外向树。

考虑 \(u\) 所在子树，我们要求 \(T_u\) 小于其子树中任何的 \(T\) 。

假设 \(W\) 已经确定，我们枚举 \(t=T_u\) ，即可得到 \(u\) 合法的概率 \[ \begin{aligned} \frac{W_u}{\sum W} \sum_{t\ge 0}\left(\frac{\sum_{i \notin \mathrm{T}(u)} W_i}{\sum W}\right)^t & =\frac{W_u}{\sum W} \cdot \frac{1}{1-\frac{\sum_{i \notin \mathrm{T}(u)} W_i}{\sum W}} \\[6pt]& =\frac{W_u}{\sum W} \cdot \frac{\sum W}{\sum_{i \in \mathrm{T}(u)} W_i} \\[6pt]& =\frac{W_u}{\sum_{i \in \mathrm{T}(u)} W_i} \end{aligned} \] 其中 \(\mathrm{T}(u)\) 表示 \(u\) 所在子树。因为结果只和 \(u\) 的子树有关，那么就可以 dp 了

设 \(f(u,s)\) 表示 \(u\) 所在子树 \(\sum_{i \in \mathrm{T}(u)} W_i=s\) 时的中奖概率。

这是一个树上背包，复杂度 \(\mathcal{O}(n^2)\) 。然后不要忘记乘上 \(W\) 每种情况的贡献。

那么原题中的内向边怎么办呢？考虑容斥，用不考虑当前边的情况减去外向边的情况。

怎么算不考虑当前边呢？那就是转移的时候任何合法的情况都能算上 \[ g(u,i) \gets f(u,i)\cdot \sum_j f(v,j) \] 时间复杂度 \(\mathcal{O}(n^2)\)

代码：

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

vector< pair<int, bool> > vec[N];
int n, a[N][3], inv[N * 3], f[N][N * 3], g[N * 3], s[N];
int qpow(int a, int b)
{
    int r = 1;
    while(b)
    {
        if(b & 1) r = r * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return r;
}
void dfs(int u, int fa)
{
    f[u][0] = 1;
    for(auto [v, t] : vec[u]) if(v != fa)
    {
        dfs(v, u);
        for(int i = 0; i <= s[u] * 3; i++)
            for(int j = 0; j <= s[v] * 3; j++)
            {
                int p = f[u][i] * f[v][j] % mod;
                if(t) { add(g[i], p); add(g[i + j], mod - p); }
                else { add(g[i + j], p); }
            }
        s[u] += s[v];
        copy_n(g, s[u] * 3 + 1, f[u]);
        fill_n(g, s[u] * 3 + 1, 0ll);
    }
    for(int i = s[u] * 3; ~i; f[u][i] = 0, i--)
        for(int j = 1; j <= 3; j++)
            add(f[u][i + j], f[u][i] * a[u][j - 1] % mod * j * inv[i + j] % mod);
    ++s[u];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        int _inv = qpow(a[i][0] + a[i][1] + a[i][2], mod - 2);
        a[i][0] = a[i][0] * _inv % mod;
        a[i][1] = a[i][1] * _inv % mod;
        a[i][2] = a[i][2] * _inv % mod;
    }
    inv[1] = 1;
    for(int i = 2; i <= n * 3; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for(int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        vec[u].push_back({v, 0});
        vec[v].push_back({u, 1});
    }
    dfs(1, 0); int res = 0;
    for(int i = 1; i <= n * 3; i++) add(res, f[1][i]);
    cout << res << '\n';
    return 0;
}