前言
【题目传送门】
时光飞逝...
去年爆零的一道题。
赛时直接题意模拟了，啥也没看出来，写的 DFS（现在重新看，实际上就是邻接表存图，我当时居然没反应过来），样例过了，但是不知道哪里挂了。
贴一下代码：
赛时代码
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int maxn=1e5+5;
int a[maxn];
int n,m,t[maxn],p[maxn],v[maxn],c[maxn],g[105][maxn];//shujufanwei!!!
int q,f[maxn];
void dfs(int num)
{
int x=num;
if(t[x]==1) a[p[x]]=(long long)(a[p[x]]+v[x])%mod;
if(t[x]==2)
for(int j=1;j<=n;j++)
a[j]=(long long)(a[j]*v[x])%mod;
if(t[x]==3)
for(int j=1;j<=c[x];j++)
{
int y=g[j][x];
dfs(y);
}
/*
for(int i=1;i<=n;i++)
printf("%d ",a[i]%mod);
printf("
");
*/
}
int main()
{
// freopen("call.in","r",stdin);
// freopen("call.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(int j=1;j<=m;j++)
{
scanf("%d",&t[j]);
if(t[j]==1) scanf("%d%d",&p[j],&v[j]);
if(t[j]==2) scanf("%d",&v[j]);
if(t[j]==3)
{
scanf("%d",&c[j]);
for(int i=1;i<=c[j];i++)
scanf("%d",&g[i][j]);
}
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d",&f[i]);
}
for(int i=1;i<=q;i++)
{
dfs(f[i]);
}
for(int i=1;i<=n;i++)
printf("%d ",a[i]%mod);
return 0;
}
题解
分解问题，想到拓扑排序并不难，但是想到正解还有一段距离。
类型三显然按照拓扑建图即可，由于要预处理出调用每一个函数造成多少全局乘法，所以这个图建反图（(topo0)）。
然后要递推出每一个函数等价的调用次数，建立一个超级源点 (0)，表示要执行的函数串，遍历的时候要反着遍历，因为每个函数造成乘法的次数只影响它之前的函数，不过由于链前的特性，正常的遍历就是倒序遍历。这个图建正图（(topo1)）。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FCC fclose(stdin),fclose(stdout)
const int INF = 0x3f3f3f3f,N = 1e5+10,M = 1e6+10,mod = 998244353;
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9')) ch=c,c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
ll mul[N],cnt[N],ans[N];
int n,m,Q,pos[N],add[N],typ[N];
int head[2][N],ecnt[2],ind[2][N];
void init_edge(){memset(head,-1,sizeof(head)),ecnt[0]=ecnt[1]=-1;}
struct edge
{
int nxt,to;
}a[2][M<<1];
inline void add_edge(int x,int y,bool op)
{
a[op][++ecnt[op]]=(edge){head[op][x],y};
head[op][x]=ecnt[op];
ind[op][y]++;
}
void topo0()//计算出调用每个函数被乘的次数
{
queue<int>q;
mul[0]=1LL;//初始化
for(int i=0;i<=m;i++) //[0,m]
if(!ind[0][i]) q.push(i);
while(!q.empty())
{
// printf("topo0
");
int u=q.front(); q.pop();
// printf("u=%d
",u);
for(int i=head[0][u];~i;i=a[0][i].nxt)
{
int v=a[0][i].to;
mul[v]=mul[v]*mul[u]%mod;
// printf("mul[%d]=%lld
",v,mul[v]);
ind[0][v]--;
if(!ind[0][v]) q.push(v);
}
}
}
void topo1()//计算出每个函数被调用的次数
{
queue<int>q;
cnt[0]=1LL;
for(int i=0;i<=Q;i++) //[0,Q]
if(!ind[1][i]) q.push(i);
while(!q.empty())
{
// printf("topo1
");
int u=q.front(); q.pop();
ll sum=1LL;
for(int i=head[1][u];~i;i=a[1][i].nxt)
{
int v=a[1][i].to;
cnt[v]=(cnt[v]+cnt[u]*sum%mod)%mod;
sum=sum*mul[v]%mod;
ind[1][v]--;
if(!ind[1][v]) q.push(v);
}
}
}
void work()
{
init_edge();
n=read(); for(int i=1;i<=n;i++) ans[i]=read();
m=read();
for(int i=1;i<=m;i++)
{
int op=read(); typ[i]=op;
if(op==1) pos[i]=read(),add[i]=read(),mul[i]=1LL;
else if(op==2) mul[i]=read();
else
{
mul[i]=1LL;
int x=read();
for(int j=1;j<=x;j++)
{
int v=read();
add_edge(v,i,0);
add_edge(i,v,1);
}
}
}
Q=read();
for(int i=1;i<=Q;i++)
{
int id=read();
add_edge(id,0,0);
add_edge(0,id,1);
}
topo0(),topo1();
for(int i=1;i<=n;i++) ans[i]=ans[i]*mul[0]%mod;
for(int i=1;i<=m;i++)
if(typ[i]==1) (ans[pos[i]]+=1LL*cnt[i]*add[i]%mod)%=mod;
for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
}
int main()
{
work();
return 0;
}