CTSC2018 假面

$$ \text{设}f\left( n,k \right) \text{表示第}n\text{个人，剩余血量为}k\text{的概率。} \\ \text{显然初始时}f\left( n,m_n \right) =\text{1,}f\left( n,m_k \right) =0\left( k\ne n \right) \\ \text{每一次操作1可以进行以下转移} \\ f\left( n,i \right) \gets \left( 1-p \right) f\left( n,i \right) +p\times f\left( n,i+1 \right) \left( i\ge 1 \right) \\ \text{特别的，}f\left( n,0 \right) \gets \left( 1-p \right) f\left( n,0 \right) +p\times \left( f\left( n,1 \right) +f\left( n,0 \right) \right) =f\left( n,0 \right) +p\times f\left( n,1 \right) \left( \text{此时再怎么扣血也还是}0 \right) \\ \text{单次操作1复杂度为}O\left( m_i \right) \\ \text{考虑操作}2 \\ \text{考虑生成函数}F\left( x \right) ,\text{其中}i\text{次项的意义是集合内还活着}i\text{个人的概率。} \\ \text{对于集合内的第}i\text{个人}\left( \text{设其为}a_i \right) ,\text{构造一个多项式}F_i\left( x \right) =\left( f\left( a_i,0 \right) +\left( 1-f\left( a_i,0 \right) \right) x \right) \\ \text{显然,}\prod{F_i\left( x \right)}\text{就是集合内还活着}i\text{个人的概率生成函数。} \\ \text{考虑如何对于每一个人统计答案} \\ \frac{\prod{F_i\left( x \right)}}{F_i\left( x \right)}\text{是除了集合内第}i\text{个人之外，剩下的人还活了}n\text{个的生成函数。} \\ \text{求出来这个多项式后，设其}j\text{次项前次数为}b_j,\text{则第}i\text{个人被命中的概率为} \\ \left( 1-f\left( a_i,0 \right) \right) \sum_{0\le j\le k-1}{\frac{b_j}{j+1}},\text{即保证这个人活着的前提下，依次枚举剩下还有几个人活着，从这些人中} \\ \text{选中第}i\text{个人。} \\ \text{实际由于涉及到的多项式次数较小，不需要}NTT\text{，直接暴力乘除即可。} \\ \\ $$

#include <assert.h>
#include <algorithm>
#include <cstring>
#include <iostream>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int mod = 998244353;
const int_t LARGE = 205;
int power(int base, int index) {
    const int phi = mod - 1;
    int result = 1;
    index = (index % phi + phi) % phi;
    while (index) {
        if (index & 1) result = 1ll * result * base % mod;
        index >>= 1;
        base = 1ll * base * base % mod;
    }
    return result;
}
int_t health[LARGE + 1];
int_t f[LARGE + 1][102];
int n, q;
void poly_multipy(const int_t* A, int_t n, const int_t* B, int_t m, int_t* C) {
    static int_t D[LARGE + 1];
    // std::fill(D, D + n + m + 1, 0);
    memset(D, 0, sizeof(int_t) * (n + m + 1));
    for (int_t i = 0; i <= n; i++) {
        for (int_t j = 0; j <= m; j++) {
            D[i + j] = (D[i + j] + A[i] * B[j] % mod) % mod;
        }
    }
    // std::copy(D, D + n + m + 1, C);
    memcpy(C, D, sizeof(int_t) * (n + m + 1));
}
void poly_divide(const int_t* A, int_t n, const int_t* B, int_t m, int_t* Q) {
    while (n >= 0 && A[n] == 0) n--;
    while (m >= 0 && B[m] == 0) m--;
    static int_t C[LARGE + 1];
    // std::copy(A, A + n + 1, C);
    memcpy(C, A, sizeof(int_t) * (n + 1));
    const int_t inv = power(B[m], -1);
    for (int_t i = n - m; i >= 0; i--) {
        int_t x = C[i + m] * inv % mod;
        Q[i] = x;
        for (int_t j = m; j >= 0; j--) {
            C[i + j] = (C[i + j] - B[j] * x + 2 * mod) % mod;
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int_t i = 1; i <= n; i++) {
        scanf("%lld", &health[i]);
        f[i][health[i]] = 1;
    }
    scanf("%d", &q);
    for (int _i = 1; _i <= q; _i++) {
        int opt;
        scanf("%d", &opt);
        if (opt == 0) {
            int target;
            int_t u, v;
            scanf("%d%lld%lld", &target, &u, &v);
            int_t p = u * power(v, -1) % mod;
            static int_t fx[102];
            auto& f = ::f[target];
            fx[0] = (f[0] + f[1] * p) % mod;
            for (int_t i = 1; i <= health[target]; i++) {
                fx[i] = ((mod + 1 - p) * f[i] + p * f[i + 1]) % mod;
            }
            for (int_t i = 0; i <= health[target]; i++) f[i] = fx[i];
        } else {
            // assert(false);
            int k;
            scanf("%d", &k);
            static int_t targets[LARGE + 1];
            for (int_t i = 1; i <= k; i++) {
                scanf("%lld", &targets[i]);
            }
            static int_t g[LARGE + 1], gx[10];
            memset(g, 0, sizeof(g));
            memset(gx, 0, sizeof(gx));
            g[0] = 1;
            //乘到一起
            for (int_t i = 1; i <= k; i++) {
                gx[0] = f[targets[i]][0];
                gx[1] = (1 - gx[0] + mod) % mod;
                poly_multipy(g, k, gx, 1, g);
            }
            //除掉第i个
            for (int_t i = 1; i <= k; i++) {
                int_t result = 0;
                gx[0] = f[targets[i]][0];
                gx[1] = (1 - gx[0] + mod) % mod;
                static int_t Q[LARGE + 1];
                //Q数组没清空导致上一次的结果影响到这一次
                memset(Q, 0, sizeof(Q));
                poly_divide(g, k, gx, 1, Q);
#ifdef DEBUG
                cout << "query " << _i << endl;
                for (int_t i = 0; i <= k - 1; i++) cout << Q[i] << " ";
                cout << endl;
#endif
                for (int_t j = 0; j <= k - 1; j++) {
                    result = (result + Q[j] * power(j + 1, -1) % mod) % mod;
                }
                result = result * (1 - f[targets[i]][0] + mod) % mod;
                printf("%lld ", (result % mod + mod) % mod);
            }
            printf("\n");
        }
    }
    for (int_t i = 1; i <= n; i++) {
        int_t sum = 0;
        for (int_t j = 0; j <= health[i]; j++) {
            sum = (sum + j * f[i][j]) % mod;
#ifdef DEBUG
            cout << "f " << i << " " << j << " = " << f[i][j] << endl;
#endif
        }
        printf("%lld ", sum);
    }
    return 0;
}