bzoj 5340: [Ctsc2018]假面

题意：

有$n$个怪，第$i$个怪的血量为$m_i$。你有两个操作，0操作可以有$p$的概率使一个怪掉$1$血，1操作可以选定一个怪的集合，并等概率从中选一个存活的怪。如果一个怪的血量降至$0$或以下，他就会死亡。给你一个长度为Q操作序列，对于每个$1$操作求集合中每个怪被选中的概率。最后输出每个怪的期望血量。设$C$为1操作的数量，$n \le 200, Q \le 20000, m_i \le 100, C \le 1000$

题解：

~~阅读理解题~~

对于每个怪维护一个$p_i$表示这个怪剩$i$滴血的概率，0操作的时候更新：

$p_i = \begin{cases} (1 - \frac{u}{v}) p_i + \frac{u}{v} p_{i + 1}, & i \ne 0 \\\ p_i + \frac{u}{v} p_{i + 1}, & i = 0 \end{cases}$

1操作时，再用一个$f_i$表示恰好选中$i$个怪的概率。

$f_i = \begin{cases} p_{id, 0} f_i + (1 - p_{id, 0})f_{i - 1}, & i \ne 0 \\\ p_{id, 0} f_i, & i = 0 \end{cases}$

显然，$id$的顺序是不会影响$f$的，所以我们求$id_i$的答案的时候可以把它当成最后一个加进来的。这样就可以把$id_i$的影响消除，具体来说就是把原来的$f$解出来，然后随便算就好了。

最后的血量直接用期望的定义权值×概率就好了。

总复杂度$O(C n^2 + (Q - C)m)$
注意要预处理一下逆元，因为这个T了好几发。。

代码：

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
int n, m[210], q, a[210];
long long p[210][110], f[210]; // 第i个人有j滴血的概率   选了i个人的概率
long long g[210], inv[210];

long long Pow(long long x, long long y)
{
    long long ans = 1;
    for (; y; y >>= 1, x = x * x % mod)
        if (y & 1) ans = ans * x % mod;
    return ans;
}
int read()
{
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}
int add(int x, int y)
{
    int ans = x + y;
    if (ans >= mod) ans -= mod;
    if (ans <= -mod) ans += mod;
    return ans;
}
int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        m[i] = read();
        p[i][m[i]] = 1;
        inv[i] = Pow(i, mod - 2);
    }
    scanf("%d", &q);
    while (q--)
    {
        int op;
        op = read();
        if (op == 0)
        {
            int id;
            long long u, v;
            id = read(), u = read(), v = read();
            u = u * Pow(v, mod - 2) % mod;
            for (int i = 0; i <= m[id]; i++)
                p[id][i] = add(p[id][i] * (i ? 1 - u : 1) % mod, p[id][i + 1] * u % mod);
        }
        else
        {
            int k;
            k = read();
            for (int i = 1; i <= k; i++)
                a[i] = read();
            f[0] = 1;
            for (int i = 1; i <= k; i++)
            {
                f[i] = 0;
                for (int j = i; j > 0; j--)
                    f[j] = add(f[j] * p[a[i]][0] % mod, f[j - 1] * (1 - p[a[i]][0]) % mod);
                f[0] = f[0] * p[a[i]][0] % mod;
            }
            for (int i = 1; i <= k; i++)
            {
                long long ans = 0;
                if (p[a[i]][0])
                {
                    long long invp = Pow(p[a[i]][0], mod - 2);
                    g[0] = f[0] * invp % mod;
                    ans = add(ans, g[0]);
                    for (int j = 1; j < k; j++)
                    {
                        g[j] = (f[j] - g[j - 1] * (1 - p[a[i]][0]) % mod) % mod * invp % mod;
                        ans = add(ans, g[j] * inv[j + 1] % mod);
                    }
                }
                else
                {
                    for (int j = 1; j <= k; j++)
                        ans = add(ans, f[j] * inv[j] % mod);
                }
                printf("%lld ", (ans * (1 - p[a[i]][0]) % mod + mod) % mod);
            }
            puts("");
        }
    }
    for (int i = 1; i <= n; i++)
    {
        long long ans = 0;
        for (int j = 1; j <= m[i]; j++)
            ans = (ans + j * p[i][j] % mod) % mod;
        printf("%lld ", (ans + mod) % mod);
    }
    puts("");
}