要注意的是,若干次的加操作尽管可能操作编号相同,但它们对应的乘积不同,即每个加操作的
V
i
V_i
Vi的贡献不一定是
V
i
∗
V
j
1
∗
V
j
2
∗
.
.
.
V
j
k
V_i*V_{j1}*V_{j2}*...V_{jk}
Vi∗Vj1∗Vj2∗...Vjk,而是
V
i
∗
∑
V
j
1
∗
V
j
2
∗
.
.
.
V
j
k
V_i*sum V_{j1}*V_{j2}*...V_{jk}
Vi∗∑Vj1∗Vj2∗...Vjk。
怎么维护呢?
首先把
Q
Q
Q个操作全部连向一个总的操作,记其编号为
0
0
0,
在这个有向无环图上DFS一遍,求出每个点所能到达的所有乘操作的乘积,记为
f
i
f_i
fi,
然后按拓扑序累加答案,把入度为
0
0
0的所有点加入队列中,(不能只加
0
0
0号操作,不然后面可能有些点无法被加入),但只有
0
0
0号点的当前操作次数
s
0
=
1
s_0=1
s0=1,其它
s
i
=
0
(
i
>
0
)
s_i=0(i>0)
si=0(i>0),
从右往左枚举队列每个点的的儿子,记录儿子
f
f
f值的后缀积
t
t
t,每个儿子的
s
s
o
n
x
s_{son_x}
ssonx依次加上
t
∗
s
f
a
t*s_{fa}
t∗sfa。
最后枚举所有操作,把加操作的乘上其
s
s
s值加入答案即可。
代码
#include<cstdio>#include<cstring>#include<algorithm>#include<queue>usingnamespace std;#define ll long long#define N 100010#define md 998244353
ll a[N], f[N], s[N];struct{int op, x, t;}b[N];int q[N *11], h[N], d[N], vi[N];
queue<int> qu;voiddfs(int k){
vi[k]=1;if(b[k].op ==3){
f[k]=1;for(int i = h[k]+ b[k].t; i > h[k]; i--){if(!vi[q[i]])dfs(q[i]);(f[k]*= f[q[i]])%= md;}}elseif(b[k].op ==2) f[k]= b[k].t;else f[k]=1;}intread(){int s =0;char x =getchar();while(x <'0'|| x >'9') x =getchar();while(x >='0'&& x <='9') s = s *10+ x -48, x =getchar();return s;}intmain(){int n =read(), m, tot =0, i, j, x;for(i =1; i <= n; i++) a[i]=read();
m =read();for(i =1; i <= m; i++){
b[i].op =read();if(b[i].op ==1) b[i].x =read(), b[i].t =read();elseif(b[i].op ==2) b[i].t =read();else{
b[i].t =read();
h[i]= tot;for(j =1; j <= b[i].t; j++) q[++tot]=read(), d[q[tot]]++;}}
h[0]= tot;
b[0].t =read();
b[0].op =3;for(i =1; i <= b[0].t; i++) q[++tot]=read(), d[q[tot]]++;dfs(0);for(i =1; i <= n; i++)(a[i]*= f[0])%= md;for(i =0; i <= m; i++)if(!d[i]) qu.push(i), s[i]=(i ==0);while(!qu.empty()){
x = qu.front();
qu.pop();if(b[x].op <3)continue;
ll t =1;for(i = h[x]+ b[x].t; i > h[x]; i--){(s[q[i]]+= t * s[x])%= md;(t *= f[q[i]])%= md;
d[q[i]]--;if(!d[q[i]]) qu.push(q[i]);}}for(i =1; i <= m; i++)if(b[i].op ==1)(a[b[i].x]+= s[i]* b[i].t)%= md;for(i =1; i <= n; i++)printf("%lld ", a[i]);return0;}