囧仙 的博客

囧仙 的博客

题解 P7077 【函数调用】

posted on 2020-11-11 12:46:45 | under 题解 |

题目大意

  • $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$ ,就可以更新并删除这个节点了。

有个细节。有些操作可能根本不会被执行,这时候我们要忽略它们。防止它们的出边对拓扑造成影响。

参考代码

#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;
}