题解 P7077 【函数调用】

## 题目大意 - $n$ 个数，初始为 $a_i$ 。现在有 $m$ 个操作，共三种： - $\verb!1 p v!$ 给 $a_p$ 加上 $v$ 。 - $\verb!2 v !$ 给所有数字乘上 $v$ 。 - $\verb!3 c g1 g2 ... gc!$ 依次执行操作 $g_1,g_2,\cdots g_c$ 。 - 现在依次执行 $f_1,f_2,\cdots f_q$ 操作，输出最终结果。结果对 $998244353$ 取模。 ## 题解 显然，数列的初始化就相当于在所有操作前依次执行 $\verb!1 i ai!$ 。 考虑没有操作 $3$ 的情况。现在我们考虑一个初始为 $0$ ，长度为 $3$ 的序列。操作序列如下： $$\verb!(1 1 1),(2 2),(1 3 2),(2 3),(1,2,5)!$$ 它会依次执行以下操作： - $1.$ 给 $a_1$ 加上 $1$ 。数列变为 $\text{1 0 0}$ 。 - $2.$ 所有 $a_i$ 乘 $2$ 。数列变为 $\text{2 0 0}$ 。 - $3.$ 给 $a_3$ 加上 $2$ 。数列变为 $\text{2 0 2}$ 。 - $4.$ 所有 $a_i$ 乘 $3$ 。数列变为 $\text{6 0 6}$ 。 - $5.$ 给 $a_2$ 加上 $5$ 。数列变为 $\text{6 5 6}$ 。 现在考虑每个操作对前面操作的影响。（下面“第 $i$ 个操作”表示操作的序号）。我们发现， 第二个操作相当于使第一个操作一共执行两次；第四个操作相当于使“执行了两次的第一个操作”又执行了三次，因此第一个操作一共执行了六次。 我们能够发现，第二种操作的用处是，使之前第一种操作的执行次数变成 $v_i$ 倍。 - $a_1=(p_1\times v_2\times v_3)=6,a_3=(p_3\times v_3)$ 。 那么考虑倒过来处理问题。比如依然是上面这个例子。我们设 $x$ 表示第二种操作的**叠乘系数**，初始为 $1$ 。 - $5.$ 执行 $x=1$ 次让 $a_2$ 加上 $p_5=5$ 。数列变为 $\text{0 5 0}$ 。 - $4.$ 让叠乘系数 $x$ 乘上 $3$ ，此时 $x=3$ 。 - $3.$ 执行 $x=3$ 次让 $a_3$ 加上 $p_3=2$ 。数列变为 $\text{0 5 6}$ 。 - $2.$ 让叠乘系数 $x$ 乘上 $2$ ，此时 $x=6$ 。 - $1.$ 执行 $x=6$ 次让 $a_1$ 加上 $p_1=1$ 。数列变为 $\text{6 5 6}$ 。 此时，没有操作 $3$ 的子情况被我们解决了。现在考虑有操作 $3$ 的情况。 将每个操作看成一个节点，每个操作 $3$ 向子操作连边。此外，题面的最后一步会从 $1$ 到 $q$ 执行 $f_i$ 。我们可以用一个特殊的第 $0$ 个操作向 $f_i$ 连边来简化问题。 由于题面保证了这张图有向无环（没有递归），所以我们能用 $dp$ 计算出执行完每个操作后叠乘系数将会乘上的值 $T_i$ 。我们假设每个操作会被执行 $C_i$ 次。 考虑什么情况下 $C_i$ 会被改变。显然，当操作 $i$ 之后还有操作需要执行时， $C_i$ 的值会乘上它之后操作的 $\prod T_j$ 。但我们能发现，当他后面没有操作时，这个操作就能直接执行 $C_i$ 次。也就是说，当他的入度为 $0$ ，就可以更新并删除这个节点了。 有个细节。有些操作可能根本不会被执行，这时候我们要忽略它们。防止它们的出边对拓扑造成影响。 ## 参考代码 ```cpp #include<bits/stdc++.h> #define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i) #define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i) using namespace std; typedef long long i64; const int MOD =998244353; const int MAXN=1e5+3,MAXM=2e6+1e5+3; int H[MAXM],R[MAXM],N[MAXM],O[MAXM],tot; int qread(){ int w=1,c,ret; while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0'; while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0'; return ret*w; } void add(int u,int v){ R[++tot]=v,N[tot]=H[u],H[u]=tot,++O[v]; } int I[MAXM],P[MAXM],V[MAXM],T[MAXM],F[MAXM]; int clc(int u){ if(T[u]!=-1) return T[u]; T[u]=1; for(int i=H[u];i;i=N[i]) T[u]=1ll*T[u]*clc(R[i])%MOD; return T[u]; } int A[MAXM],Q[MAXM],C[MAXM],n,m,q,r; int main(){ n=qread(); up(1,n,i) add(0,i),P[i]=i,V[i]=qread(),T[i]=1,I[i]=1; m=qread(); up(n+1,n+m,i) switch(I[i]=qread()){ case 1: P[i]=qread(),V[i]=qread(),T[i]=1; break; case 2: V[i]=qread(),T[i]=V[i]; break; case 3: up(1,qread(),j) add(i,qread()+n); T[i]=-1; } up(1,n+m,i) clc(i); q=qread(); up(1,q,i) add(0,n+qread()); up(0,n+m,i) if(O[i]==0) Q[++r]=i; I[0]=3,C[0]=1; while(r>0){ int u=Q[r],x=C[u]; --r; if(I[u]==3) for(int i=H[u];i;i=N[i]){ C[R[i]]=(x+C[R[i]])%MOD,--O[R[i]]; if(O[R[i]]==0) Q[++r]=R[i]; x=1ll*x*T[R[i]]%MOD; } else if(I[u]==1) A[P[u]]=(1ll*V[u]*x+A[P[u]])%MOD; } up(1,n,i) printf("%d ",A[i]); return 0; } ```