C++(g++ 7.5.0) 解法, 执行用时: 99ms, 内存消耗: 16368K, 提交时间: 2023-08-05 14:40:40

#include <bits/stdc++.h>
using namespace std;

#define ll long long
inline ll read(){
	ll x=0,sign=0; char s=getchar();
	while(s>'9'||s<'0')sign|=s=='-',s=getchar();
	while(s<='9'&&s>='0')x=(x<<1)+(x<<3)+s-'0',s=getchar();
	return sign?-x:x;
}

const int N=1e5+5;
const int mod=998244353;

int n,m,c,a[N],deg[N],func[N];
int tp[N],pos[N],val[N];
ll mu=1,mul[N],dp[N],add[N];
vector <int> e[N];
queue <int> q;

bool vis[N];
void dfs(int id){
	vis[id]=1,mul[id]=(tp[id]==2?val[id]:1);
	for(int it:e[id]){
		if(!vis[it])dfs(it);
		mul[id]=mul[id]*mul[it]%mod;
	}
}

int main(){
	n=read(); for(int i=1;i<=n;i++)a[i]=read();
	m=read();
	for(int i=1;i<=m;i++){
		tp[i]=read();
		if(tp[i]==1)pos[i]=read(),val[i]=read();
		else if(tp[i]==2)val[i]=read();
		else{
			c=read();
			while(c--){
				int to=read();
				e[i].push_back(to),deg[to]++;
			}
		}
	} c=read();
	for(int i=1;i<=m;i++)if(!vis[i]&&!deg[i])dfs(i);
	for(int i=1;i<=c;i++)func[i]=read();
	for(int i=c,f=func[i];i;i--,f=func[i]){
		if(tp[f]==1)dp[f]=(dp[f]+mu);
		else if(tp[f]==2)mu=mu*val[f]%mod;
		else dp[f]=(dp[f]+mu),mu=mu*mul[f]%mod;
	} for(int i=1;i<=m;i++)if(!deg[i])q.push(i);
	while(!q.empty()){
		int t=q.front(); q.pop();
		if(tp[t]==1)add[pos[t]]=(add[pos[t]]+dp[t]*val[t])%mod;
		ll z=dp[t]; reverse(e[t].begin(),e[t].end());
		for(int p:e[t]){
			deg[p]--; if(!deg[p])q.push(p);
			dp[p]=(dp[p]+z)%mod,z=z*mul[p]%mod;
		}
	} for(int i=1;i<=n;i++)cout<<(a[i]*mu+add[i])%mod<<" ";
	return 0;
}

C++(clang++11) 解法, 执行用时: 208ms, 内存消耗: 13564K, 提交时间: 2020-11-08 18:25:00

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=1e5+5;
const int mod=998244353;
int n,m,a[N],b[N],x[N],y[N],ind[N],seq[N],len,mul[N],val[N];
vector<int>vec[N];
queue<int>Q;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1,t,k,g;i<=m+1;++i){
		if(i<=m)
			scanf("%d",&t);
		else
			t=3;
		mul[i]=1;
		if(t==1)
			scanf("%d%d",&x[i],&y[i]);
		if(t==2)
			scanf("%d",&mul[i]);
		if(t==3){
			scanf("%d",&k);
			while(k--){
				scanf("%d",&g);
				vec[i].push_back(g);
				++ind[g];
			}
		}
	}
	for(int i=1;i<=m+1;++i)
		if(!ind[i])
			Q.push(i);
	while(!Q.empty()){
		int u=Q.front();
		Q.pop();
		seq[++len]=u;
		for(int v:vec[u])
			if(!--ind[v])
				Q.push(v);
	}
	for(int i=m+1;i;--i)
		for(int j:vec[seq[i]])
			mul[seq[i]]=1ll*mul[seq[i]]*mul[j]%mod;
	val[m+1]=1;
	for(int i=1;i<=m+1;++i){
		int u=seq[i];
		if(x[u])
			b[x[u]]=(b[x[u]]+1ll*val[u]*y[u])%mod;
		reverse(vec[u].begin(),vec[u].end());
		for(int v:vec[u]){
			val[v]=(val[v]+val[u])%mod;
			val[u]=1ll*val[u]*mul[v]%mod;
		}
	}
	for(int i=1;i<=n;++i)
		printf("%lld%c",(1ll*a[i]*mul[m+1]+b[i])%mod,i==n?'\n':' ');
	return 0;
}