由于代码习惯，下文中用$h _i$表示题目中的$m _i$.
看到998244353不知道为什么就去想NTT……其实完全没有必要，因为$n$和$C$和$h _i$都非常小.
记$f _{i,j}$表示$i$这个人生命值恰为$j$的概率，直接暴力dp，每次更新复杂度为$\mathcal O(m)$. 这样就可以求出最后每个人生命值的期望.
考虑怎么求另一问，显然$f _{i,0}$就是$i$这个人死去的概率. 记$\textrm{al} _{i,j}$表示除了$i$以外还活下来$j$个人的概率，显然可以$\mathcal O(n^3)$dp出来. 其实这样做了很多重复的工作，可以直接求出$\textrm{al} _j$表示有$j$个人活下来的概率，那么要除去某个人，相当于是从背包里面删去一个元素，考虑之前的递推式$\textrm{al}^\prime _i=\textrm{al} _i f _{x,0}+\textrm{al} _{i-1}(1-f _{x,0})$，可以得到$\textrm{al} _i=\frac{\textrm{al}^\prime _i-\textrm{al} _{i-1}(1-f _{x,0})}{f _{x,0}}$，这样就能从背包中删去一个元素了. 这部分计算的复杂度就降到了$\mathcal O(n^2)$.
最后的复杂度是$\mathcal O(Qm+Cn^2)$.
线性预处理$1,2,\ldots,n$的逆元可以显著减小常数.
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
using namespace std;
ele n,Q,k,h[maxn],f[maxn][maxh],g[maxh],a[maxn],al[maxn],tal[maxn],inv[maxn];
inline ele pw(ele a,ele x){
ele ans=1,tmp=a%MOD;
for (; x; x>>=1,tmp=(ll)tmp*tmp%MOD)
if (x&1) ans=(ll)ans*tmp%MOD;
return ans;
}
int main(){
scanf("%d",&n);
inv[1]=1;
for (int i=2; i<=n; ++i) inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
memset(f,0,sizeof(f));
for (int i=0; i<n; ++i) scanf("%d",h+i),f[i][h[i]]=1;
scanf("%d",&Q);
while (Q--){
ele op;
scanf("%d",&op);
if (!op){
ele i,u,v;
scanf("%d%d%d",&i,&u,&v); --i;
u=(ll)u*pw(v,MOD-2)%MOD;
g[0]=((ll)f[i][1]*u+f[i][0])%MOD;
for (int j=1; j<=h[i]; ++j)
g[j]=((ll)f[i][j]*(1+MOD-u)+(ll)f[i][j+1]*u)%MOD;
memcpy(f[i],g,sizeof(ele)*(h[i]+1));
}
else{
scanf("%d",&k);
for (int i=0; i<k; ++i) scanf("%d",a+i),--a[i];
memset(al,0,sizeof(al)); al[0]=1;
for (int i=0; i<k; ++i){
tal[0]=(ll)al[0]*f[a[i]][0]%MOD;
for (int j=1; j<=k; ++j)
tal[j]=((ll)al[j]*f[a[i]][0]+(ll)al[j-1]*(1+MOD-f[a[i]][0]))%MOD;
memcpy(al,tal,sizeof(ele)*(k+1));
}
for (int i=0; i<k; ++i){
if (f[a[i]][0]){
ele tmp=pw(f[a[i]][0],MOD-2);
tal[0]=(ll)al[0]*tmp%MOD;
for (int j=1; j<=k; ++j)
tal[j]=(ll)tmp*
(al[j]+MOD-(ll)tal[j-1]*(1+MOD-f[a[i]][0])%MOD)%MOD;
}
else memcpy(tal,al+1,sizeof(ele)*k);
ele ans=0;
for (int j=0; j<k; ++j)
(ans+=(ll)inv[j+1]*(1+MOD-f[a[i]][0])%MOD*tal[j]%MOD)%=MOD;
printf(i?" %d":"%d",ans);
}
puts("");
}
}
for (int i=0; i<n; ++i){
ele ans=0;
for (int j=0; j<=h[i]; ++j)
(ans+=(ll)j*f[i][j]%MOD)%=MOD;
printf(i?" %d":"%d",ans);
}
puts("");
return 0;
}