[CSP-S 2020] 函数调用

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

把函数调用关系看成 DAG，先反向求每个函数整体乘法效果，再正向统计每个加法函数最终会被乘上的系数。

OJ: luogu

题目 ID: P7077

难度:提高+/省选-

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

日期: 2026-06-19 23:42

题意

有一个长度为 n 的数组，以及 m 个函数。

函数分三类：

给某个位置加上一个值；
把整个数组都乘上一个值；
按顺序调用若干个函数。

最后还会给出一个总调用序列，要求你把这些函数依次执行完，输出最终数组。

函数之间不会递归，也就是函数调用关系是一张 DAG。

样例图

这张图展示样例 1 中的函数调用关系：

digraph G {
  rankdir=LR;
  F3["f3"] -> F1["f1: a1 += 1"];
  F3 -> F2["f2: all *= 2"];
  Q["query"] -> F2;
  Q -> F3;
}

f3 会先执行 f1，再执行 f2。而总调用序列又是先执行 f2，再执行 f3。这说明某个加法到底最后会给答案带来多大贡献，不只看它自己加了多少，还要看它后面还会被多少个乘法放大。

思路

先看一个最直接的小数据暴力：

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
const int MAXM = 25;
const int MOD = 998244353;

int n;
int a[MAXN];
int m;
int typ[MAXM];
int pos_[MAXM];
int val_[MAXM];
vector<int> calls[MAXM];
int qnum;
vector<int> queries;

void exec_func(int id) {
    if (typ[id] == 1) {
        a[pos_[id]] += val_[id];
        a[pos_[id]] %= MOD;
    } else if (typ[id] == 2) {
        for (int i = 1; i <= n; i++) {
            a[i] = 1LL * a[i] * val_[id] % MOD;
        }
    } else {
        for (int v : calls[id]) {
            exec_func(v);
        }
    }
}

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

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

    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> typ[i];
        calls[i].clear();

        if (typ[i] == 1) {
            cin >> pos_[i] >> val_[i];
            val_[i] %= MOD;
        } else if (typ[i] == 2) {
            cin >> val_[i];
            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;
    queries.resize(qnum);
    for (int i = 0; i < qnum; i++) {
        cin >> queries[i];
    }

    for (int x : queries) {
        exec_func(x);
    }

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

    return 0;
}

暴力就是递归模拟函数调用：

遇到 1 类函数就直接加
遇到 2 类函数就整段乘
遇到 3 类函数就按顺序递归调用

这个写法适合小数据验证，但大数据下会重复展开很多次同一个函数。

关键观察有两个。

第一步，先看“一个函数整体执行完之后，会让整个数组额外乘上多少”。

1 类函数不会改变整体乘法效果，所以是 1
2 类函数的整体乘法效果就是自己的乘数
3 类函数按顺序调用若干个子函数，所以整体乘法效果就是这些子函数整体乘法效果的乘积

记这个量为 mul[f]。因为 mul[f] 依赖于子函数，所以可以在调用 DAG 上按逆拓扑序计算。

第二步，考虑一个 1 类加法函数到底会被执行多少次、并且它加上的值最后还要再乘上多少。

我们定义 coef[f]：

表示函数 f 里的加法，放到最终答案里时，还要再乘上的系数

如果一个父函数按顺序调用：

g1, g2, ..., gk

那么：

gk 后面没有兄弟函数，所以它直接继承父函数的系数
g(k-1) 后面还会再执行一次 gk，所以它的系数要再乘上 mul[gk]
更前面的函数同理

因此对一段调用序列，我们应该从后往前传播系数。

实现上可以新建一个超级源点 0，把总调用序列也看成一次 3 类函数调用。然后：

先拓扑排序；
逆拓扑序求出每个函数的 mul；
再按拓扑序，从超级源点开始，把 coef 从父函数往子函数传播；
最后把所有 1 类函数的贡献加到对应位置上。

最终答案为：

原数组每个元素先乘上总调用序列的整体乘法 mul[0]
再加上所有 1 类函数留下的贡献

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXM = 100005;
const int MOD = 998244353;

int n;
int a[MAXN];
int m;
int typ[MAXM];      // typ[i] : 第 i 个函数的类型
int pos_[MAXM];     // type1 修改的位置
int val_[MAXM];     // type1 / type2 的参数
vector<int> calls[MAXM]; // type3 按顺序调用的函数列表

int qnum;
vector<int> queries;

vector<int> graph[MAXM];
int indeg[MAXM];
int mul[MAXM];      // mul[i] : 执行完函数 i 后，对整个数组的整体乘法效果
int coef[MAXM];     // coef[i] : 函数 i 中 type1 加法最终要乘上的系数
int add_sum[MAXN];  // add_sum[p] : 所有对位置 p 的加法总贡献

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

    cin >> m;
    for (int i = 0; i <= m; i++) {
        graph[i].clear();
        indeg[i] = 0;
        calls[i].clear();
        mul[i] = 1;
        coef[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        add_sum[i] = 0;
    }

    for (int i = 1; i <= m; i++) {
        cin >> typ[i];
        if (typ[i] == 1) {
            cin >> pos_[i] >> val_[i];
            val_[i] %= MOD;
        } else if (typ[i] == 2) {
            cin >> val_[i];
            val_[i] %= MOD;
        } else {
            int c;
            cin >> c;
            calls[i].resize(c);
            for (int j = 0; j < c; j++) {
                cin >> calls[i][j];
                graph[i].push_back(calls[i][j]);
                indeg[calls[i][j]]++;
            }
        }
    }

    cin >> qnum;
    queries.resize(qnum);
    for (int i = 0; i < qnum; i++) {
        cin >> queries[i];
        graph[0].push_back(queries[i]);
        indeg[queries[i]]++;
    }
}

vector<int> get_topological_order() {
    queue<int> q;
    vector<int> deg(m + 1);
    vector<int> order;

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

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);

        for (int v : graph[u]) {
            deg[v]--;
            if (deg[v] == 0) {
                q.push(v);
            }
        }
    }

    return order;
}

void calc_mul(const vector<int> &order) {
    for (int idx = (int) order.size() - 1; idx >= 0; idx--) {
        int u = order[idx];

        if (u == 0) {
            long long ret = 1;
            for (int v : queries) {
                ret = ret * mul[v] % MOD;
            }
            mul[u] = ret;
        } else if (typ[u] == 1) {
            mul[u] = 1;
        } else if (typ[u] == 2) {
            mul[u] = val_[u];
        } else {
            long long ret = 1;
            for (int v : calls[u]) {
                ret = ret * mul[v] % MOD;
            }
            mul[u] = ret;
        }
    }
}

void propagate_coef(const vector<int> &order) {
    coef[0] = 1;

    for (int u : order) {
        long long cur = coef[u];

        if (u == 0) {
            for (int i = qnum - 1; i >= 0; i--) {
                int v = queries[i];
                coef[v] = (coef[v] + cur) % MOD;
                cur = cur * mul[v] % MOD;
            }
        } else if (typ[u] == 3) {
            for (int i = (int) calls[u].size() - 1; i >= 0; i--) {
                int v = calls[u][i];
                coef[v] = (coef[v] + cur) % MOD;
                cur = cur * mul[v] % MOD;
            }
        }
    }
}

void solve() {
    vector<int> order = get_topological_order();
    calc_mul(order);
    propagate_coef(order);

    for (int i = 1; i <= m; i++) {
        if (typ[i] == 1) {
            int p = pos_[i];
            add_sum[p] = (add_sum[p] + 1LL * coef[i] * val_[i]) % MOD;
        }
    }

    for (int i = 1; i <= n; i++) {
        a[i] = (1LL * a[i] * mul[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。

拓扑排序 $O(m + E)$
反向计算 mul 一次 $O(m + E)$
正向传播 coef 一次 $O(m + E)$

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

总结

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

一个是整体乘法效果 mul
一个是加法最终系数 coef

一旦把这两个量分开，问题就落成了一张函数调用 DAG 上的两次拓扑处理。

一图流解析

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

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] 函数调用

目录

题意

样例图

思路

代码

复杂度

总结

一图流解析