记录编号	571709	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2020S]函数调用	最终得分	100
用户昵称	Benjamin	是否通过	通过
代码语言	C++	运行时间	1.343 s
提交时间	2022-06-14 10:55:33	内存使用	65.85 MiB

#include<bits/stdc++.h>
#define LL long long
#define mod 998244353
#define N 1100005
using namespace std;
LL n,m,q;
LL a[N];//序列
LL addid[N],addval[N],num[N],mul[N];
struct edge
{
	LL to,nxt;
}e[N];//调用关系，总数 <= sum(Cj)+Q
LL head[N],cnt=0;
LL ind[N];//入度
bool vis[N];
void add(LL u,LL v)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void dfs(LL from)
{//求解mul[i]:调用函数i对全局乘的倍数贡献;
	vis[from]=1;//访问标记
	for(LL i=head[from];i;i=e[i].nxt)
	{
		LL to=e[i].to;//被调函数
		if(!vis[to]) dfs(to);
		mul[from]=mul[from]*mul[to]%mod;
		//被调函数处理完后,更新mul[from]
	}
}
void toposort()
{//按拓扑序下传函数调用次数num[]
	queue<LL>q;
	for(LL i=0;i<=m;i++) if(!ind[i]) q.push(i);
	num[0]=1;
	while(!q.empty())
	{
		LL from=q.front();	q.pop();//取队头
		LL cur_mul=1;//初始化当前倍数贡献
		for(LL i=head[from];i;i=e[i].nxt)
		{//倒序处理调用的子函数（链式前向星存储保证边倒序）
			LL to=e[i].to;
			//+=父结点调用次数 * 已处理兄弟结点mul[]之积
			(num[to] += num[from] * cur_mul % mod) %= mod;
			cur_mul = cur_mul * mul[to] % mod;//更新当前倍数贡献
			ind[to]--;//入度减1
			if(!ind[to]) q.push(to);
		}
	}
}

int main()
{
	freopen("2020call.in","r",stdin);
	freopen("2020call.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);//数列a
	scanf("%lld",&m);//函数个数
	for(int i=1;i<=m;i++)
	{
		LL op;//函数类型
		scanf("%lld",&op);
		if(op==1)//元素加
		{
			scanf("%lld%lld",&addid[i],&addval[i]);
			mul[i]=1;
		}
		if(op==2)//全局乘
		{
			scanf("%lld",&mul[i]);
		}
		if(op==3)//调用函数序列
		{
			LL C;
			scanf("%lld",&C);
			mul[i]=1;
			for(LL j=1;j<=C;j++)
			{
				LL g;
				scanf("%lld",&g);
				add(i,g);//函数i调用函数g
				ind[g]++;//函数g入度+1
			}
		}
	}
	scanf("%lld",&q);
	for(LL i=1;i<=q;i++)
	{
		LL f;
		scanf("%lld",&f);
		add(0,f);//从0到所有询问函数序列中的函数连边
		ind[f]++;
	}
	mul[0]=1;
	
	dfs(0);//求解mul[]
	
	for(int i=1;i<=n;i++)
		a[i] = a[i] * mul[0] % mod;//数列元素乘以全局倍数

	toposort();//按拓扑序下传函数调用次数
	
	for(int i=1;i<=m;i++)//处理单点修改
        if(addval[i])//a[i]+=调用次数num[i] * 单次修改值addval[i]
			(a[addid[i]]+=num[i]*addval[i]%mod)%=mod;
	
	for(int i=1;i<=n;i++) printf("%lld ",a[i]);
	
	return 0;
}