题解：洛谷 P7077 [CSP-S 2020] 函数调用
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：P7077 [CSP-S 2020] 函数调用 - 洛谷
【题目描述】
函数是各种编程语言中一项重要的概念，借助函数，我们总可以将复杂的任务分解成一个个相对简单的子任务，直到细化为十分简单的基础操作，从而使代码的组织更加严密、更加有条理。然而，过多的函数调用也会导致额外的开销，影响程序的运行效率。
某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类：
- 将数据中的指定元素加上一个值；
- 将数据中的每一个元素乘以一个相同值；
- 依次执行若干次函数调用，保证不会出现递归（即不会直接或间接地调用本身）。
在使用该数据库应用时，用户可一次性输入要调用的函数序列（一个函数可能被调用多次），在依次执行完序列中的函数后，系统中的数据被加以更新。某一天，小 A 在应用该数据库程序处理数据时遇到了困难：由于频繁而低效的函数调用，系统在执行操作时进入了无响应的状态，他只好强制结束了数据库程序。为了计算出正确数据，小 A 查阅了软件的文档，了解到每个函数的具体功能信息，现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。
【输入】
第一行一个正整数n nn，表示数据的个数。
第二行n nn个整数，第i ii个整数表示下标为i ii的数据的初始值为a i a_iai。
第三行一个正整数m mm，表示数据库应用程序提供的函数个数。函数从1 ∼ m 1 \sim m1∼m编号。
接下来m mm行中，第j jj（1 ≤ j ≤ m 1 \le j \le m1≤j≤m）行的第一个整数为T j T_jTj，表示j jj号函数的类型：
- 若T j = 1 T_j = 1Tj=1，接下来两个整数P j , V j P_j, V_jPj,Vj分别表示要执行加法的元素的下标及其增加的值；
- 若T j = 2 T_j = 2Tj=2，接下来一个整数V j V_jVj表示所有元素所乘的值；
- 若T j = 3 T_j = 3Tj=3，接下来一个正整数C j C_jCj表示j jj号函数要调用的函数个数，
随后C j C_jCj个整数g 1 ( j ) , g 2 ( j ) , … , g C j ( j ) g^{(j)}_1, g^{(j)}_2, \ldots , g^{(j)}_{C_j}g1(j),g2(j),…,gCj(j)依次表示其所调用的函数的编号。
第m + 4 m + 4m+4行一个正整数Q QQ，表示输入的函数操作序列长度。
第m + 5 m + 5m+5行Q QQ个整数f i f_ifi，第i ii个整数表示第i ii个执行的函数的编号。
【输出】
一行n nn个用空格隔开的整数，按照下标1 ∼ n 1 \sim n1∼n的顺序，分别输出在执行完输入的函数序列后，数据库中每一个元素的值。答案对998244353 \boldsymbol{998244353}998244353取模。
【输入样例】
3 1 2 3 3 1 1 1 2 2 3 2 1 2 2 2 3【输出样例】
6 8 12【算法标签】
#提高+# #拓扑排序#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005,mod=998244353;// 函数结构体，表示每个操作structFunc{intop,p,v;// op: 操作类型, p: 位置参数, v: 值参数}func[N];// 边结构体，表示图的边structEdge{intv,w;// v: 目标节点, w: 边权};intn,m,q;// n: 初始变量数量, m: 操作数量, q: 查询数量intmul[N];// 乘法因子，表示从该节点开始的累积乘积intans[N];// 最终答案数组intin[N];// 入度数组，用于拓扑排序intp[N];// 系数数组，表示每个节点对最终结果的贡献系数vector<Edge>adj[N];// 邻接表，表示有向图// 递归计算从节点u开始的累积乘积intinit(intu){if(mul[u]!=-1||adj[u].empty())// 如果已经计算过或者是叶子节点{returnmul[u];}mul[u]=1;// 初始化为1// 递归计算所有后继节点的乘积for(inti=0;i<adj[u].size();i++){intv=adj[u][i].v;mul[u]=mul[u]*init(v)%mod;}returnmul[u];}// 计算每条边的权重voidwork(){for(intu=0;u<=n+m;u++)// 遍历所有节点{intr=1;// 从右向左的累积乘积// 从后向前遍历邻接表for(inti=adj[u].size()-1;i>=0;i--){intv=adj[u][i].v;adj[u][i].w=r;// 设置边的权重为右侧的累积乘积r=r*mul[v]%mod;// 更新累积乘积}}}// 拓扑排序，计算每个节点的贡献系数voidtopo(){queue<int>q;// 用于拓扑排序的队列p[0]=1;// 起点节点的系数为1// 将所有入度为0的节点加入队列for(inti=0;i<=n+m;i++){if(in[i]==0){q.push(i);}}// 拓扑排序主循环while(!q.empty()){intu=q.front();q.pop();// 遍历u的所有出边for(inti=0;i<adj[u].size();i++){intv=adj[u][i].v;intw=adj[u][i].w;// 更新后继节点的系数p[v]=(p[v]+w*p[u]%mod)%mod;in[v]--;// 减少入度// 如果入度变为0，加入队列if(in[v]==0){q.push(v);}}}}signedmain(){memset(mul,-1,sizeof(mul));// 初始化mul数组为-1// 第一部分：输入初始变量cin>>n;for(inti=1;i<=n;i++){cin>>func[i].v;// 输入初始值func[i].op=1;// 操作类型1：赋值func[i].p=i;// 赋值位置mul[i]=1;// 乘法因子为1in[i]++;// 增加入度adj[0].push_back({i,0});// 从0节点连接到i节点}// 第二部分：输入操作cin>>m;for(inti=n+1;i<=m+n;i++){cin>>func[i].op;// 输入操作类型if(func[i].op==1)// 操作类型1：赋值{cin>>func[i].p>>func[i].v;// 输入位置和值mul[i]=1;// 乘法因子为1}elseif(func[i].op==2)// 操作类型2：乘法{cin>>func[i].v;// 输入乘数mul[i]=func[i].v;// 乘法因子为v}else// 操作类型3：函数调用{intc,g;cin>>c;// 输入参数个数for(intj=1;j<=c;j++){cin>>g;// 输入每个参数adj[i].push_back({g+n,0});// 添加边in[g+n]++;// 增加入度}}}// 第三部分：输入查询cin>>q;for(intj=1;j<=q;j++){intf;cin>>f;// 输入查询的函数adj[0].push_back({f+n,0});// 从0节点连接到查询函数in[f+n]++;// 增加入度}// 第四部分：计算和处理init(0);// 从0节点开始计算累积乘积work();// 计算边权topo();// 拓扑排序，计算系数// 第五部分：计算结果for(inti=1;i<=n+m;i++){if(func[i].op==1)// 如果是赋值操作{// 将值乘以系数，累加到对应位置ans[func[i].p]=(ans[func[i].p]+func[i].v*p[i]%mod)%mod;}}// 输出结果for(inti=1;i<=n;i++){cout<<ans[i]<<" ";}cout<<endl;return0;// 程序正常结束}【运行结果】
3 1 2 3 3 1 1 1 2 2 3 2 1 2 2 2 3 6 8 12