真题解析:P7077 [CSP-S 2020] 函数调用(拓扑排序·逆序扫描·乘法标记下传·线性变换)

四季读书网 2026-10-06 09:22:49 8 0

题目来源：洛谷 P7077 [CSP-S 2020] 函数调用

题目大意

某数据库程序维护着 n 个数据，下标 1 到 n，初值给定。程序提供了 m 个函数，编号 1 到 m，每个函数的功能属于三类之一：

• 类型 1：把下标为 p 的元素加上 v，即 a[p] += v；
• 类型 2：把每个元素都乘以同一个值 v，即所有 a[i] *= v；
• 类型 3：依次调用 k 个函数 g1, g2, …, gk（保证不会出现递归，即不会直接或间接调用自身）。

程序会执行一个长度为 Q 的调用序列 c1, c2, …, cQ，即依次调用这些函数；一个函数可能在序列中出现多次，也可能被别的函数反复调用。求执行完整个序列之后，每个元素的最终值。结果对 998244353 取模。

数据范围：1 ≤ n, m, Q ≤ 10^5，所有函数调用列表中元素的总数不超过 10^6，0 ≤ a[i], v ≤ 10^4。

输入输出样例

样例 1 输入：

31 2 331 1 12 23 2 1 222 3

样例 1 输出：

6 8 12

样例 1 中：1 号函数给 a1 加 1，2 号函数给所有元素乘 2，3 号函数先调用 1 号、再调用 2 号。序列先执行 2 号函数，所有元素变为 [2, 4, 6]；再执行 3 号函数，先加后乘，最终得到 [6, 8, 12]。

样例 2 输入：

101 2 3 4 5 6 7 8 9 1083 2 2 33 2 4 53 2 5 82 23 2 6 71 2 51 7 62 331 2 3

样例 2 输出：

36 282 108 144 180 216 504 288 324 360

考点梳理

考点	在本题里的作用
有向无环图与拓扑排序	函数调用关系构成一张 DAG，拓扑序保证「调用者先于被调用者」，是把系数向下推的前提
后缀乘积（逆序扫描）	一段序列里，排在前面的加法会被排在它后面的乘法放大；倒序扫描时用一个变量维护后缀倍数，就能在线性时间内得到每个位置应有的权重
把「重复执行」转化为「执行份数」	一个函数可能被调用很多次，直接展开会爆炸；真正需要的是它被执行了多少份，记成系数 c[i]，把指数级过程压成线性计算
线性变换（整体乘 + 单点加）	由于类型 2 是全局乘，函数的乘性系数对所有下标一致，可退化成单个标量 mul[i] 与一组加性常数
取模运算	答案对 998244353 取模，累加、累乘随时取模，乘积用 long long 承接防止溢出

解题思路

一、核心观察：整体乘法与单点加法

整个执行过程对数组只有两种作用：整体乘法和单点加法。乘法会把「它之前的所有内容」（初始值和之前的所有加法）一起放大，而加法只影响一个位置。因此最终每个元素一定长成

a[i]最终 = a[i]初始 × 全局总倍数 + Σ(该位置上每次加法的值 × 它之后所有乘法的总倍数)

这提示我们：不必真的逐条模拟每一次调用，只要算出每个函数被有效执行了多少份（记为系数 c[i]），以及每个函数会让整体乘多少（记为 mul[i]），就能把整个过程合并起来算。

最外层的那串调用序列 c1..cQ，可以看成一个虚拟的「类型 3 函数」——它依次调用 Q 个函数，于是整个问题被统一成「求每个函数的执行份数」。

二、第一步：求每个函数的乘法倍数 mul[i]

mul[i] 表示单独执行一次函数 i，数组整体会乘上的倍数：

• 类型 1（加法）：mul[i] = 1；
• 类型 2（乘法）：mul[i] = v；
• 类型 3：mul[i] 等于它依次调用的所有子函数 mul 之积。

因为父函数的倍数依赖子函数，所以按拓扑序从后往前处理（先算子函数，再算父函数）：

for (int idx = m - 1; idx >= 0; idx--) {    int u = topo[idx];    if (type[u] == 1) mul[u] = 1;    else if (type[u] == 2) mul[u] = val[u] % MOD;    else {        long long p = 1;        for (int v : child[u]) p = p * mul[v] % MOD;        mul[u] = p;    }}

三、第二步：求主序列里每个函数的执行份数 c[i]

先处理最外层的调用序列。从最后一次调用往前扫，用变量 p 记录「已经扫过的、排在后面的那些调用」带来的总倍数。对第 i 次调用 q[i]：它前面发生的操作都要再乘上 p，所以给 c[q[i]] 加上 p；然后继续往前，p 再乘上 q[i] 自己的倍数 mul[q[i]]。扫完之后，p 就是整个主序列造成的总倍数 totalMul。

long long p = 1;for (int i = Q - 1; i >= 0; i--) {    c[q[i]] = (c[q[i]] + p) % MOD;    p = p * mul[q[i]] % MOD;}long long totalMul = p;

四、第三步：把份数沿调用关系向下传递

再按拓扑序（调用者在前）处理每个类型 3 函数 u。函数 u 被执行了 c[u] 份，它内部按顺序调用子函数 v1, v2, …，其中排在 vj后面的子函数会把 vj 的部分再放大。于是对子函数从后往前扫，用 prod 记录 v 后面所有子函数的倍数之积：先把 c[v] 加上 c[u] * prod，再让 prod 乘上 mul[v]。

for (int idx = 0; idx < m; idx++) {    int u = topo[idx];    if (type[u] != 3 || c[u] == 0) continue;    long long prod = 1;    for (int j = (int)child[u].size() - 1; j >= 0; j--) {        int v = child[u][j];        c[v] = (c[v] + c[u] * prod) % MOD;        prod = prod * mul[v] % MOD;    }}

五、第四步：汇总得到答案

遍历所有类型 1 函数 i，它会给下标 pos[i] 贡献 val[i] * c[i]，把它累加到加性数组 add[pos[i]]。最后，每个元素先整体乘上主序列的总倍数 totalMul，再加上前面累计好的加法贡献：

for (int i = 1; i <= n; i++) {    long long ans = (a[i] % MOD * totalMul + add[i]) % MOD;    printf("%lld%c", ans, i == n ? '\n' : ' ');}

六、易错点

• 类型 2 是「所有元素」乘同一个值，不是单点乘。正因为它是全局乘，乘性系数才对全部下标一致，才能用一个标量 mul 表示；读题时务必分清。
• 共享调用要分别累加：一个函数可能被多个父函数调用，也可能在主序列里出现多次，它的份数 c 要把各处的贡献都加进去，不能只算一次。
• 两处逆序的方向不同：算 mul 要按拓扑序从后往前（先子后父），而把份数 c 沿着调用关系下传要按拓扑序从前往后（先父后子）。
• mul[i] 可能等于 0（乘数为 0 是合法操作），不要用 mul[i] != 0 当作「是否算过」的判据；本实现按拓扑序让每个函数恰好被算一次，天然避免了重复。
• 取模：所有乘法、加法都随时对 998244353 取模，乘积用 long long 承接。

参考代码

#include <bits/stdc++.h>using namespace std;const long long MOD = 998244353;const int N = 100005;int n, m, Q;long long a[N];int type[N];long long val[N];int pos[N];vector<int> child[N];int indeg[N];long long mul[N];long long c[N];int topo[N];long long add[N];int main(){    scanf("%d", &n);    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);    scanf("%d", &m);    for (int i = 1; i <= m; i++) {        scanf("%d", &type[i]);        if (type[i] == 1) {            scanf("%d %lld", &pos[i], &val[i]);        } else if (type[i] == 2) {            scanf("%lld", &val[i]);        } else {            int cnt;            scanf("%d", &cnt);            child[i].resize(cnt);            for (int j = 0; j < cnt; j++) {                scanf("%d", &child[i][j]);                indeg[child[i][j]]++;            }        }    }    scanf("%d", &Q);    vector<int> q(Q);    for (int i = 0; i < Q; i++) scanf("%d", &q[i]);    int head = 0, tail = 0;    for (int i = 1; i <= m; i++)        if (indeg[i] == 0) topo[tail++] = i;    while (head < tail) {        int u = topo[head++];        for (int v : child[u])            if (--indeg[v] == 0) topo[tail++] = v;    }    for (int idx = m - 1; idx >= 0; idx--) {        int u = topo[idx];        if (type[u] == 1) mul[u] = 1;        else if (type[u] == 2) mul[u] = val[u] % MOD;        else {            long long p = 1;            for (int v : child[u]) p = p * mul[v] % MOD;            mul[u] = p;        }    }    long long p = 1;    for (int i = Q - 1; i >= 0; i--) {        c[q[i]] = (c[q[i]] + p) % MOD;        p = p * mul[q[i]] % MOD;    }    long long totalMul = p;    for (int idx = 0; idx < m; idx++) {        int u = topo[idx];        if (type[u] != 3 || c[u] == 0) continue;        long long prod = 1;        for (int j = (int)child[u].size() - 1; j >= 0; j--) {            int v = child[u][j];            c[v] = (c[v] + c[u] * prod) % MOD;            prod = prod * mul[v] % MOD;        }    }    for (int i = 1; i <= m; i++)        if (type[i] == 1)            add[pos[i]] = (add[pos[i]] + val[i] % MOD * c[i]) % MOD;    for (int i = 1; i <= n; i++) {        long long ans = (a[i] % MOD * totalMul + add[i]) % MOD;        printf("%lld%c", ans, i == n ? '\n' : ' ');    }    return 0;}

复杂度分析

• 时间：O(n + m + Σc_i + Q)。读入是 O(n + m + Σc_i + Q)，拓扑排序是 O(m + Σc_i)，算 mul、下推份数各按拓扑序扫一遍，合计 O(m + Σc_i)，输出 O(n)。其中 Σc_i 是所有函数调用列表中元素的总数（不超过 10^6）。
• 空间：O(n + m + Σc_i)。a、add 为 O(n)，mul、c、topo、indeg 为 O(m)，邻接表 child 合计 O(Σc_i)，远低于 256MB 的内存限制。