简答题 偏难
#23305

函数调用(call) 【题目描述】 函数是各种编程语言中一项重要的概念,借助函数,我们总可以将复杂的任务分解成一个个相对简单的子任务,直到细化为十分简单的基础操…

函数调用(call)

【题目描述】

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

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

1. 将数据中的指定元素加上一个值;

2. 将数据中的每一个元素乘以一个相同值;

3. 依次执行若干次函数调用,保证不会出现递归(即不会直接或间接地调用本身)。

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

【输入格式】

输入文件名为 call.in。

第 1 行一个正整数 n,表示数据的个数。

第 2 行 n 个整数,第 i 个整数表示下标为 i 的数据的初始值为 ai。

第 3 行一个正整数 m,表示数据库应用程序提供的函数个数。函数从 1 ∼m 编号。

接下来 m 行中,第 j(1 ≤ j ≤ m)行的第一个整数为 Tj,表示 j 号函数的类型:

1. 若 Tj = 1,接下来两个整数 Pj, Vj 分别表示要执行加法的元素的下标及其增加的值;

2. 若 Tj = 2,接下来一个整数 Vj 表示所有元素所乘的值;

3. 若 Tj = 3,接下来一个正整数 Cj 表示 j 号函数要调用的函数个数,随后 Cj个整数 g1(j), g2(j), ⋯ , gCj(j) 依次表示其所调用的函数的编号。

第 m + 4 行一个正整数 Q,表示输入的函数操作序列长度。

第 m+ 5 行 Q 个整数 fi,第 i 个整数表示第 i 个执行的函数的编号。

【输出格式】

输出文件名为 call.out。

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

【样例 1 输入】

3

1 2 3

3

1 1 1

2 2

3 2 1 2

2

2 3

【样例 1 输出】

6 8 12

【样例 1 解释】

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

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

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

【样例 2 输入】

10

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 输出】

36 282 108 144 180 216 504 288 324 360

【数据范围与提示】

对于所有数据:0 ≤ ai ≤ 10^4,Tj ∈ {1,2,3},1 ≤ Pj ≤ n,0 ≤ Vj ≤ 10^4,1 ≤≤ m,1 ≤fi ≤ m。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include &lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">typedef long long LL;</p><p style="text-align: left;">const int INF = 0x3f3f3f3f;</p><p style="text-align: left;">const LL mod = 998244353;</p><p style="text-align: left;">const int N = 100005;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">// d[i]表示全局积 f[i] 表示后继积</p><p style="text-align: left;">int a[N], op[N], b[N], c[N];</p><p style="text-align: left;">LL d[N], f[N];</p><p style="text-align: left;">vector&lt;pair&lt;int, int&gt; &gt; G[N], H[N];</p><p style="text-align: left;">LL dfs(int u) {</p><p style="text-align: left;">    if (~d[u]) return d[u];</p><p style="text-align: left;">    d[u] = op[u] == 2 ? c[u] : 1;</p><p style="text-align: left;">    LL s = 1;</p><p style="text-align: left;">    for (int i = G[u].size() - 1; i &gt;= 0; i--) {</p><p style="text-align: left;">        int v = G[u][i].first;</p><p style="text-align: left;">        G[u][i].second = s;</p><p style="text-align: left;">        d[u] = d[u] * dfs(v) % mod;</p><p style="text-align: left;">        s = s * d[v] % mod;  // 所有右兄弟的积</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return d[u];</p><p style="text-align: left;">}</p><p style="text-align: left;">LL dfs2(int u) {</p><p style="text-align: left;">    if (~f[u]) return f[u];</p><p style="text-align: left;">    f[u] = 0;</p><p style="text-align: left;">    for (int i = 0; i &lt; H[u].size(); i++) {</p><p style="text-align: left;">        int v = H[u][i].first, w = H[u][i].second;</p><p style="text-align: left;">        f[u] = (f[u] + w * dfs2(v)) % mod;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return f[u];</p><p style="text-align: left;">}</p><p style="text-align: left;">int main() {</p><p style="text-align: left;">    // freopen("call.in", "r", stdin);</p><p style="text-align: left;">    // freopen("call.out", "w", stdout);</p><p style="text-align: left;">    int n, m, q;</p><p style="text-align: left;">    scanf("%d", &amp;n);</p><p style="text-align: left;">    for (int i = 1; i &lt;= n; i++) scanf("%d", &amp;a[i]);</p><p style="text-align: left;">    scanf("%d", &amp;m);</p><p style="text-align: left;">    for (int i = 1; i &lt;= m; i++) {</p><p style="text-align: left;">        scanf("%d", &amp;op[i]);</p><p style="text-align: left;">        if (op[i] == 1) {</p><p style="text-align: left;">            scanf("%d %d", &amp;b[i], &amp;c[i]);</p><p style="text-align: left;">        } else if (op[i] == 2) {</p><p style="text-align: left;">            scanf("%d", &amp;c[i]);</p><p style="text-align: left;">        } else {</p><p style="text-align: left;">            int t;</p><p style="text-align: left;">            scanf("%d", &amp;t);</p><p style="text-align: left;">            while (t--) {</p><p style="text-align: left;">                int v;</p><p style="text-align: left;">                scanf("%d", &amp;v);</p><p style="text-align: left;">                G[i].push_back({v, 0});</p><p style="text-align: left;">            }</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    scanf("%d", &amp;q);</p><p style="text-align: left;">    while (q--) {</p><p style="text-align: left;">        int v;</p><p style="text-align: left;">        scanf("%d", &amp;v);</p><p style="text-align: left;">        G[0].push_back({v, 0});</p><p style="text-align: left;">    }</p><p style="text-align: left;">    memset(d, -1, sizeof d);</p><p style="text-align: left;">    memset(f, -1, sizeof f);</p><p style="text-align: left;">    dfs(0);</p><p style="text-align: left;">    for (int i = 1; i &lt;= n; i++) {</p><p style="text-align: left;">        a[i] = a[i] * d[0] % mod;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    for (int u = 0; u &lt;= m; u++) {</p><p style="text-align: left;">        for (int i = 0; i &lt; G[u].size(); i++) {</p><p style="text-align: left;">            int v = G[u][i].first, w = G[u][i].second;</p><p style="text-align: left;">            H[v].push_back({u, w});</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    f[0] = 1;</p><p style="text-align: left;">    for (int i = 1; i &lt;= m; i++) {</p><p style="text-align: left;">        if (op[i] == 1) {</p><p style="text-align: left;">            a[b[i]] = (a[b[i]] + dfs2(i) * c[i]) % mod;</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    for (int i = 1; i &lt;= n; i++) {</p><p style="text-align: left;">        printf("%d%c", a[i], " \n"[i == n]);</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。