[CSP-S 2020] 函数调用

GitHub跳转原题关系图返回列表

把函数调用关系看成 DAG，逆拓扑序求每个函数的整体乘法倍数，再正拓扑序从后往前传播加法的最终系数。

OJ: luogu

题目 ID: P7077

难度:提高+/省选-

标签:图论拓扑排序动态规划数学

创建: 2026-06-19 23:42

更新: 2026-10-24 00:10

前置题目

luogu P7113[NOIP2020] 排水系统B 复用 A 的「在调用 DAG 上按拓扑序沿边传播数值」这一步递推流程，只是把污水平均分换成 mul_all 乘积与 coef 系数的双向拓扑传播，并叠加乘法放大加法的线性合成

形式化题目

给定长度为 $n$ 的数组 $a_1,\dots,a_n$ ，以及 $m$ 个函数。每个函数属于以下三类之一：

单点加法： $a_{P_j}\mathrel{+}=V_j$ ；
整体乘法：对所有 $i$ ， $a_i\mathrel{*}=V_j$ ；
顺序调用：依次执行给定的若干函数 $g^{(j)}_1,\dots,g^{(j)}_{C_j}$ 。

再给定长度 $Q$ 的调用序列 $f_1,\dots,f_Q$ 。要求依次执行 $f_1,f_2,\dots,f_Q$ ，输出执行后的数组，答案对 $998244353$ 取模。

函数调用关系不递归，即构成一张有向无环图。所有运算都在模 $998244353$ 意义下进行。

样例 $1$ 的调用关系如下。

digraph G {
  rankdir=LR;
  F0["超级源点 0"] -> F2["f2: 全体 *2"];
  F0 -> F3["f3"];
  F3 -> F1["f1: a1 += 1"];
  F3 -> F2;
}

图中 f3 先调用 f1 再调用 f2，而总调用序列是先 f2 后 f3。可以看到 f1 加上的那个 $1$ 会被 f2 放大成 $2$ ，而 f2 在序列里出现两次，最终原数组被整体放大了 $4$ 倍。

暴力解法

思路

最直接的做法就是照着题意递归模拟：遇到 $1$ 类函数就单点加，遇到 $2$ 类函数就整段乘，遇到 $3$ 类函数就按顺序递归执行它调用的函数。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 20:59
 * update_at: 2026-10-01 21:09
 */
// brute.cpp：小数据暴力解，直接递归模拟每个函数的效果，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;   // 暴力只服务小数据，n 取到 100 左右
const int MAXM = 105;   // 函数个数同样只到小规模
const ll MOD = 998244353;

int n, m, qnum;
ll a[MAXN];             // a[i]：下标 i 的数据值，模拟过程中不断更新
int func_type[MAXM];    // func_type[f]：函数 f 的类型 1/2/3
int add_pos[MAXM];      // add_pos[f]：1 类函数要加的位置
ll func_val[MAXM];      // func_val[f]：1 类的加数 / 2 类的乘数
vector<int> calls[MAXM]; // calls[f]：3 类函数按顺序调用的函数编号
int query_list[MAXM];   // query_list[i]：总调用序列里的第 i 个函数

// 递归执行函数 id 的全部效果：1 类单点加，2 类整体乘，3 类按顺序递归子函数。
void exec_func(int id) {
    if (func_type[id] == 1) {
        a[add_pos[id]] = (a[add_pos[id]] + func_val[id]) % MOD;
    } else if (func_type[id] == 2) {
        for (int i = 1; i <= n; i++) {
            a[i] = a[i] * func_val[id] % MOD;
        }
    } else {
        int c = calls[id].size();
        for (int i = 0; i < c; i++) {
            exec_func(calls[id][i]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= MOD;
    }

    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> func_type[i];
        if (func_type[i] == 1) {
            cin >> add_pos[i] >> func_val[i];
            func_val[i] %= MOD;
        } else if (func_type[i] == 2) {
            cin >> func_val[i];
            func_val[i] %= MOD;
        } else {
            int c;
            cin >> c;
            calls[i].resize(c);
            for (int j = 0; j < c; j++) {
                cin >> calls[i][j];
            }
        }
    }

    cin >> qnum;
    for (int i = 0; i < qnum; i++) {
        cin >> query_list[i];
    }

    // 照题目要求依次执行整个调用序列，直接得到答案。
    for (int i = 0; i < qnum; i++) {
        exec_func(query_list[i]);
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << a[i];
    }
    cout << '\n';

    return 0;
}

复杂度

设 $E=\sum C_j$ 为调用边总数。一次函数执行最多展开 $O(E)$ 次子调用，总调用序列最多 $Q$ 项，最坏时间复杂度 $O(Q\cdot E)$ ，空间 $O(n+m+E)$ 。

瓶颈

这个做法在测试点 $1\sim 2$ 这种小数据上完全正确，但大数据的规模是 $n,m,Q\leqslant 10^5$ 、 $E\leqslant 10^6$ 。同一个函数如果在不同的调用链里被反复展开，暴力会把它重算很多遍， $O(Q\cdot E)$ 直接超时。

真正的问题是：我们其实并不需要知道每个函数被执行的过程，只需要知道两件事——它让整个数组乘了几倍，以及它里面的加法最后被乘了几倍。

正解

思路

第一个量：整体乘法倍数 `mul_all`

先只关心乘法。对每个函数 $f$ ，设

mul\_all[f]=\text{函数 } f \text{ 完整执行一次后，整个数组额外乘上的倍数}.

$1$ 类函数不改变整体倍数， $mul\_all[f]=1$ ；
$2$ 类函数就是它自己的乘数， $mul\_all[f]=V_f$ ；
$3$ 类函数按顺序执行 $g_1,\dots,g_k$ ，整体倍数就是各子函数倍数的乘积：

mul\_all[f]=\prod_{i=1}^{k}mul\_all[g_i].

因为 $mul\_all[f]$ 只依赖子函数，所以在调用 DAG 上按逆拓扑序就能一次算完。

第二个量：加法的最终系数 `coef`

光有 mul_all 还不够。以样例 $1$ 为例，f1 加的是 $1$ ，但它在 f3 里排在 f2 前面，会被 f2 放大成 $2$ ，而 f2 在总序列里又出现一次，最终贡献是 $2$ 。

设

coef[f]=\text{函数 } f \text{ 里的加法，落到最终答案时还要再乘上的系数}.

超级源点 $0$ 代表总调用序列，显然 $coef[0]=1$ 。

考虑一个父函数按顺序调用 $g_1,g_2,\dots,g_k$ ，父函数继承到的系数是 $C$ ：

$g_k$ 后面没有兄弟函数，直接继承 $C$ ；
$g_{k-1}$ 后面还要执行 $g_k$ ，所以继承 $C\cdot mul\_all[g_k]$ ；
更靠前的 $g_i$ 要再乘上它后面所有兄弟的倍数。

因此从后往前扫描子函数列表，维护一个后缀积 suffix，就能把系数发下去：

text

1
2
3
4suffix = C
for i = k down to 1:
    coef[g_i] += suffix
    suffix *= mul_all[g_i]

这里每个子函数接收到的都是“父函数系数 × 自己后面所有兄弟的倍数”，正是它执行完之后还会被放大多少次。

为什么必须先拓扑排序

注意函数编号和拓扑序没有关系：题面只保证调用关系无环，编号小的函数完全可能调用编号大的函数。所以不能简单地按 $1,2,\dots,m$ 的顺序递推，必须先把整张调用 DAG 拓扑排序，得到 order[]：

逆着 order[] 扫，求 mul_all；
顺着 order[] 扫，把 coef 从父传给子。

汇总答案

把所有 $1$ 类函数的贡献按最终系数加到对应位置上：

add\_sum[P_f]\mathrel{+}=coef[f]\cdot V_f.

最后

a_i\leftarrow a_i\cdot mul\_all[0]+add\_sum[i].

样例推演

样例 $1$ ： $n=3$ ， $a=[1,2,3]$ ， $f_1$ 是 a1 += 1， $f_2$ 是 all *= 2， $f_3$ 依次调用 $f_1,f_2$ ，总调用序列为 $[f_2,f_3]$ 。

阶段	对象	结果
`mul_all`	$f_1$	$1$ （加法不影响整体倍数）
`mul_all`	$f_2$	$2$
`mul_all`	$f_3$	$mul\_all[f_1]\cdot mul\_all[f_2]=2$
`mul_all`	源点 $0$	$mul\_all[f_2]\cdot mul\_all[f_3]=4$
`coef`	源点 $0$	$1$
`coef`	$f_3$	从 $0$ 的列表末尾继承， $1$
`coef`	$f_2$	源点列表里 $f_3$ 排在它后面， $1\cdot mul\_all[f_3]=2$ ；再加 $f_3$ 列表里它排在最后、直接继承 $coef[f_3]=1$ ，合计 $3$
`coef`	$f_1$	$f_3$ 列表里它后面是 $f_2$ ， $1\cdot mul\_all[f_2]=2$
`add_sum`	位置 $1$	$coef[f_1]\cdot V_{f_1}=2\cdot1=2$
答案	$a$	$[1\cdot4+2,\ 2\cdot4+0,\ 3\cdot4+0]=[6,8,12]$

与样例输出 6 8 12 一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 20:59
 * update_at: 2026-10-01 21:09
 */
// main.cpp：把函数调用关系看成 DAG 做两轮处理：
// 逆拓扑序求出每个函数执行完后的整体乘法倍数 mul_all，
// 再正拓扑序把加法系数 coef 从父函数传给子函数。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;   // n <= 1e5，下标用 int 足够
const int MAXM = 100005;   // m, Q <= 1e5，函数编号用 int 足够
const ll MOD = 998244353;

int n, m, qnum;
ll a[MAXN];             // a[i]：下标 i 的数据值，最后原地变成答案
int func_type[MAXM];    // func_type[f]：函数 f 的类型 1/2/3，取值很小但仍用 int 便于读
int add_pos[MAXM];      // add_pos[f]：1 类函数要加的位置
ll func_val[MAXM];      // func_val[f]：1 类的加数 / 2 类的乘数，均已取模

// calls[f]：3 类函数按顺序调用的函数编号；
// calls[0] 是超级源点，存放题目给出的总调用序列。
vector<int> calls[MAXM];

int indeg[MAXM];        // indeg[f]：调用 DAG 上的入度，用来做拓扑排序
int work_deg[MAXM];     // work_deg[f]：拓扑排序时的工作副本，避免破坏 indeg
int order[MAXM + 1];    // order[0..order_cnt-1]：整个调用 DAG 的拓扑序
int order_cnt;

ll mul_all[MAXM];       // mul_all[f]：执行完函数 f 后整个数组额外乘上的倍数
ll coef[MAXM];          // coef[f]：函数 f 里的加法落到最终答案时还要再乘的系数
ll add_sum[MAXN];       // add_sum[p]：位置 p 收到的全部加法贡献

// 读入数据，并把总调用序列挂到超级源点 0 上。
void read_input() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= MOD;
    }

    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> func_type[i];
        if (func_type[i] == 1) {
            cin >> add_pos[i] >> func_val[i];
            func_val[i] %= MOD;
        } else if (func_type[i] == 2) {
            cin >> func_val[i];
            func_val[i] %= MOD;
        } else {
            int c;
            cin >> c;
            calls[i].resize(c);
            for (int j = 0; j < c; j++) {
                cin >> calls[i][j];
                indeg[calls[i][j]]++;
            }
        }
    }

    cin >> qnum;
    calls[0].resize(qnum);   // 超级源点 0 的调用序列就是题目给的总调用序列
    for (int i = 0; i < qnum; i++) {
        cin >> calls[0][i];
        indeg[calls[0][i]]++;
    }
}

// 对所有函数做一次拓扑排序，结果存入 order[]。
// 调用关系保证无环，但子函数编号可能比父函数大，所以不能只按编号顺序处理。
void build_topological_order() {
    queue<int> que;

    for (int i = 0; i <= m; i++) {
        work_deg[i] = indeg[i];
        if (work_deg[i] == 0) {
            que.push(i);
        }
    }

    order_cnt = 0;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        order[order_cnt++] = u;

        int c = calls[u].size();
        for (int i = 0; i < c; i++) {
            int v = calls[u][i];
            work_deg[v]--;
            if (work_deg[v] == 0) {
                que.push(v);
            }
        }
    }
}

// 逆拓扑序求 mul_all：函数 f 执行完后，整个数组会额外乘上的倍数。
void calc_mul_all() {
    for (int idx = order_cnt - 1; idx >= 0; idx--) {
        int u = order[idx];

        // 3 类函数的倍数就是全部子函数倍数的乘积；超级源点同理。
        ll product = 1;
        int c = calls[u].size();
        for (int i = 0; i < c; i++) {
            product = product * mul_all[calls[u][i]] % MOD;
        }

        if (u == 0) {
            mul_all[u] = product;         // 总调用序列的整体倍数
        } else if (func_type[u] == 1) {
            mul_all[u] = 1;               // 加法不改变整体倍数
        } else if (func_type[u] == 2) {
            mul_all[u] = func_val[u];     // 乘法函数的倍数就是自己的乘数
        } else {
            mul_all[u] = product;
        }
    }
}

// 正拓扑序传播 coef：父函数从后往前把系数分给子函数。
// 某个子函数后面还会执行的兄弟函数越多，它能继承到的系数就越小。
void propagate_coef() {
    coef[0] = 1;

    for (int idx = 0; idx < order_cnt; idx++) {
        int u = order[idx];
        if (u != 0 && func_type[u] != 3) {
            continue;   // 只有超级源点和 3 类函数会继续往下调用
        }

        // suffix 是当前子函数能继承的系数：它后面所有兄弟函数倍数的乘积。
        ll suffix = coef[u];
        int c = calls[u].size();
        for (int i = c - 1; i >= 0; i--) {
            int v = calls[u][i];
            coef[v] = (coef[v] + suffix) % MOD;
            suffix = suffix * mul_all[v] % MOD;
        }
    }
}

void solve() {
    build_topological_order();
    calc_mul_all();
    propagate_coef();

    // 把每个 1 类函数的加法按最终系数汇总到具体位置上。
    for (int f = 1; f <= m; f++) {
        if (func_type[f] == 1) {
            int p = add_pos[f];
            add_sum[p] = (add_sum[p] + coef[f] * func_val[f]) % MOD;
        }
    }

    // 原数组先整体乘上总调用序列的倍数，再加上所有加法贡献。
    for (int i = 1; i <= n; i++) {
        a[i] = (a[i] * mul_all[0] + add_sum[i]) % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << a[i];
    }
    cout << '\n';

    return 0;
}

复杂度

设 $E=\sum C_j$ 为调用边总数。

拓扑排序 $O(m+E)$ ；
逆拓扑序求 mul_all 一次 $O(m+E)$ ；
正拓扑序传播 coef 一次 $O(m+E)$ ；
汇总答案 $O(n+m)$ 。

总时间复杂度 $O(n+m+E)$ ，空间复杂度 $O(n+m+E)$ 。

总结

这题不是模拟题，而是把“顺序调用”拆成两个可以复用的量：

mul_all[f]：函数 $f$ 对整体数组的乘法倍数，逆拓扑序求；
coef[f]：函数 $f$ 中加法落到答案上的最终系数，正拓扑序从后往前传播。

一旦把这两个量分开，每个函数就只需要被处理常数次，问题落成调用 DAG 上的两次线性扫描。最容易踩的坑是函数编号不等于拓扑序，必须先做一次拓扑排序。

本文的 main.cpp 已用递归模拟的 brute.cpp 对拍 $400$ 组随机数据（链与随机树各半），并另外核对了两组题面样例：in1 / out1（样例 1）与 in2 / out2（样例 2）。题面列出的样例 3 是 call/call3.in 外部附件，本题目录未收录。

图示解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P7077 [CSP-S 2020] 函数调用

题目描述

函数是各种编程语言中一项重要的概念，借助函数，我们总可以将复杂的任务分解成一个个相对简单的子任务，直到细化为十分简单的基础操作，从而使代码的组织更加严密、更加有条理。然而，过多的函数调用也会导致额外的开销，影响程序的运行效率。

某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类：

将数据中的指定元素加上一个值；
将数据中的每一个元素乘以一个相同值；
依次执行若干次函数调用，保证不会出现递归（即不会直接或间接地调用本身）。

在使用该数据库应用时，用户可一次性输入要调用的函数序列（一个函数可能被调用多次），在依次执行完序列中的函数后，系统中的数据被加以更新。某一天，小 A 在应用该数据库程序处理数据时遇到了困难：由于频繁而低效的函数调用，系统在执行操作时进入了无响应的状态，他只好强制结束了数据库程序。为了计算出正确数据，小 A 查阅了软件的文档，了解到每个函数的具体功能信息，现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。

输入格式

第一行一个正整数 $n$ ，表示数据的个数。
第二行 $n$ 个整数，第 $i$ 个整数表示下标为 $i$ 的数据的初始值为 $a_i$ 。
第三行一个正整数 $m$ ，表示数据库应用程序提供的函数个数。函数从 $1 \sim m$ 编号。
接下来 $m$ 行中，第 $j$ （ $1 \le j \le m$ ）行的第一个整数为 $T_j$ ，表示 $j$ 号函数的类型：

若 $T_j = 1$ ，接下来两个整数 $P_j, V_j$ 分别表示要执行加法的元素的下标及其增加的值；
若 $T_j = 2$ ，接下来一个整数 $V_j$ 表示所有元素所乘的值；
若 $T_j = 3$ ，接下来一个正整数 $C_j$ 表示 $j$ 号函数要调用的函数个数，
随后 $C_j$ 个整数 $g^{(j)}_1, g^{(j)}_2, \ldots , g^{(j)}_{C_j}$ 依次表示其所调用的函数的编号。

第 $m + 4$ 行一个正整数 $Q$ ，表示输入的函数操作序列长度。
第 $m + 5$ 行 $Q$ 个整数 $f_i$ ，第 $i$ 个整数表示第 $i$ 个执行的函数的编号。

输出格式

一行 $n$ 个用空格隔开的整数，按照下标 $1 \sim n$ 的顺序，分别输出在执行完输入的函数序列后，数据库中每一个元素的值。答案对 $\boldsymbol{998244353}$ 取模。

输入输出样例 #1

输入 #1

text

输出 #1

text

16 8 12

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7
8
9
10
11
12
1310
1 2 3 4 5 6 7 8 9 10
8
3 2 2 3
3 2 4 5
3 2 5 8
2 2
3 2 6 7
1 2 5
1 7 6
2 3
3
1 2 3

输出 #2

text

136 282 108 144 180 216 504 288 324 360

输入输出样例 #3

输入 #3

text

1见附件中的 call/call3.in

输出 #3

text

1见附件中的 call/call3.ans

说明/提示

【样例 #1 解释】

$1$ 号函数功能为将 $a_1$ 的值加一。 $2$ 号函数功能为所有元素乘 $2$ 。 $3$ 号函数将先调用 $1$ 号函数，再调用 $2$ 号函数。

最终的函数序列先执行 $2$ 号函数，所有元素的值变为 $2, 4, 6$ 。

再执行 $3$ 号函数时，先调用 $1$ 号函数，所有元素的值变为 $3, 4, 6$ 。再调用 $2$ 号函数，所有元素的值变为 $6, 8, 12$ 。

【数据范围】

::cute-table{tuack}

测试点编号	$n, m, Q \le$	$\sum C_j$	其他特殊限制
$1 \sim 2$	$1000$	$= m - 1$	函数调用关系构成一棵树
$3 \sim 4$	$1000$	$\le 100$	无
$5 \sim 6$	$20000$	$\le 40000$	不含第 $2$ 类函数或不含第 $1$ 类函数
$7$	$20000$	$= 0$	无
$8 \sim 9$	$20000$	$= m - 1$	函数调用关系构成一棵树
$10 \sim 11$	$20000$	$\le 2 \times 10^5$	无
$12 \sim 13$	$10^5$	$\le 2 \times 10^5$	不含第 $2$ 类函数或不含第 $1$ 类函数
$14$	$10^5$	$= 0$	无
$15 \sim 16$	$10^5$	$= m - 1$	函数调用关系构成一棵树
$17 \sim 18$	$10^5$	$\le 5 \times 10^5$	无
$19 \sim 20$	$10^5$	$\le 10^6$	无

对于所有数据： $0 \le a_i \le 10^4$ ， $T_j \in \{1,2,3\}$ ， $1 \le P_j \le n$ ， $0 \le V_j \le 10^4$ ， $1 \le g^{(j)}_k \le m$ ， $1 \le f_i \le m$ 。

[CSP-S 2020] 函数调用

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

第一个量：整体乘法倍数 mul_all

第二个量：加法的最终系数 coef

为什么必须先拓扑排序

汇总答案

样例推演

代码

复杂度

总结

图示解析

第一个量：整体乘法倍数 `mul_all`

第二个量：加法的最终系数 `coef`