P7077 [CSP-S2020] 函数调用

题解

假如只有 (1) 操作，那么操作之间可交换，可以建出 DAG，统计出每种 (1) 操作的执行次数即可。

可以发现，执行完一个操作 (K)，再进行一次 (2 x) 操作，相当于执行了 (x) 次 (K) 操作。

于是先倒序拓扑出每个操作执行完会被乘多少，然后正序拓扑即可。

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T> void Read(T &_x){
	_x=0;int _f=1;
	char ch=getchar();
	while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
	while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();
	_x*=_f;
}
template<typename T,typename... Args> void Read(T &_x,Args& ...others){
	Read(_x);Read(others...);
}
typedef long long ll;
const int N=1e5+5,Mod=998244353;
int n,m,tp[N],p[N],w[N],q,f[N];
ll a[N];
vector<int> g[N],topo,gg[N];
int que[N<<1],head=1,tail;
int deg[N];ll mul[N],cnt[N];
int main(){
	Read(n);
	For(i,1,n) Read(a[i]);
	Read(m);
	For(i,1,m){
		Read(tp[i]);
		if(tp[i]==1) Read(p[i],w[i]);
		else if(tp[i]==2) Read(w[i]);
		else{
			int k,x;Read(k);
			For(j,1,k){
				Read(x);
				g[x].push_back(i),++deg[i];
				gg[i].push_back(x);
			}
			reverse(gg[i].begin(),gg[i].end());
		}
		mul[i]=1;
	}
	mul[0]=1;
	Read(q);
	For(i,1,q){
		Read(f[i]);
		g[f[i]].push_back(0),++deg[0];
		gg[0].push_back(f[i]);
	}
	reverse(gg[0].begin(),gg[0].end());
	For(i,1,m) if(!deg[i]){
		que[++tail]=i;
		if(tp[i]==2) mul[i]=w[i];
	}
	while(head<=tail){
		int u=que[head++];
		topo.push_back(u);
		for(int v:g[u]){
			mul[v]=mul[v]*mul[u]%Mod;
			if(--deg[v]==0) que[++tail]=v;
		}
	}
	reverse(topo.begin(),topo.end());
	cnt[0]=1;
	for(int u:topo){
		ll mu=1;
		for(int v:gg[u]){
			cnt[v]=(cnt[v]+mu*cnt[u])%Mod;
			mu=mu*mul[v]%Mod;
		}
	}
	For(i,1,n) a[i]=a[i]*mul[0]%Mod;
	For(i,1,m){
		if(tp[i]==1){
			a[p[i]]=(a[p[i]]+cnt[i]*w[i])%Mod;
		}
	}
	For(i,1,n) printf("%lld ",a[i]);
	return 0;
}