CSP2020-S T3 函数调用

前言

其实挺毒瘤的，我尽量写的简单而易懂。下文的加操作指一类操作，乘操作指二类操作。

思路

首先显而易见的是函数之间的调用关系是 DAG ，（因为不会调用到自己，即没有环），为了方便，我们将最后的操作建成一个超级三类函数，需要求出这个超级函数的影响。

现在对于每一个 (a_i) 进行考虑。由于是全局乘，所以调用一次超级函数的所有乘操作都会作用于它。在最简单的情况下，若是没有加操作，或者没有以 (a_i) 为对象的加操作，那么直接输出 (a_i*mult) 就行，（mult 指所有乘操作的积）。于是问题放在了如何处理那些以 (a_i) 为对象的加操作上。

不妨设有一个以 (a_i) 为对象的加操作为 (g)，加的值为 (v) ，那么比较好想出，(g) 最后对 (a_i) 的贡献是 (v*k) （其中 k 表示在 g 之后被调用的乘操作的积，此处希望意识到与 mult 的含义十分相似）。正确性显然。现在需要求 k。

于是设状态 (f_{i,j}),为函数 i 的第 j 个子函数中的所有被调用的乘操作的积。(k_i) 意义与上一段相同。于是有转移方程

[k_i=sum_{i为u的第j个子函数}k_uprod _{a=j+1}^{size(u)}f_{u,a} ]

这之中出现 (sum) 的原因是 i 可能被多个三类函数调用，这些贡献是累加的。

略微观察可以得到 (f) 可以使用后缀积来预处理，转移拓扑排序就行。边界条件：超级三类函数的 k 为1。问题缩小到了如何求出 (f) 。

使用一边 DFS 求出，有点像记忆化，比较简单，看代码十分好懂。

CODE

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
inline int read(){
	char ch=getchar();
	int res=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())res=(res<<3)+(res<<1)+(ch-'0');
	return res*f;
}
const int MAXN=1e5+12,mod=998244353;
inline int M(long long x){return (x>=mod)?x%mod:x;}
int n,a[MAXN],m,t[MAXN],p[MAXN],v[MAXN],deg[MAXN],f[MAXN];
bool vis[MAXN];
vector<int>prod[MAXN],son[MAXN];
inline void add(int x,int y){son[x].push_back(y),deg[y]++;}
void dfs(int x){
    //此处的 prod 数组已经为后缀积了,prod[x][0] 相当于表示整个子树中的乘操作的积
	vis[x]=1;
	if(t[x]==1)prod[x].push_back(1);//特殊处理
	else if(t[x]==2)prod[x].push_back(v[x]);
	else{
		if(!son[x].size()){prod[x].push_back(0);return ;}//防止违法访问，有可能会 RE 。吧。
		prod[x].resize(son[x].size());
		for(int i=0,qwq=son[x].size();i<qwq;++i){
			if(!vis[son[x][i]])dfs(son[x][i]);//递归
			prod[x][i]=prod[son[x][i]][0];//此处还不是后缀积，只是第 i 个子函数中的乘操作的积
		}
		for(int i=son[x].size()-2;i>=0;--i)prod[x][i]=M(1LL*prod[x][i]*prod[x][i+1]);//后缀积
	}
}
queue<int> q;
int main(){
	n=read();
	for(int i=1;i<=n;++i)a[i]=read();
	m=read();
	for(int i=1;i<=m;++i){
		t[i]=read();
		if(t[i]==1)p[i]=read(),v[i]=read();
		else if(t[i]==2)v[i]=read();
		else for(int j=1,cj=read();j<=cj;++j)add(i,read());//建图
	}
	++m;
	for(int i=1,Q=read();i<=Q;++i)add(m,read());//建立超级函数
	dfs(m);//dfs求出 f 函数，在代码中为 prod 数组
	for(int i=1;i<=m;++i)if(!deg[i])q.push(i);
    //拓扑排序，不能直接 push(m) 没有调用的函数也可以削减入度。
	f[m]=1;//其实是状态 k
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0,qwq=son[u].size();i<qwq;++i){
			int x=son[u][i];
			if(!(--deg[x]))q.push(x);
			if(!vis[u])continue;
			f[x]=M(1LL*f[x]+1LL*f[u]*((i<qwq-1)?prod[u][i+1]:1));//转移
		}
	}
	for(int i=1;i<=n;++i)a[i]=M(1LL*a[i]*prod[m][0]);//乘上总的
	for(int i=1;i<=m;++i)if(t[i]==1)a[p[i]]=M(1LL*a[p[i]]+1LL*v[i]*f[i]);//添加贡献
	for(int i=1;i<=n;++i)printf("%d ",a[i]);
	return 0;
}