题解（含代码解析）

问题分析

本题需要处理多层嵌套的函数调用，计算最终数据值。函数分为三类：单点加法、全局乘法、调用其他函数。直接模拟会因嵌套过深或重复调用超时，需通过预处理函数的“乘法贡献”和“加法贡献系数”优化计算。

核心思路

1. 拆分贡献：函数对数据的影响可分为乘法贡献和加法贡献，利用“乘法优先级高于加法”的特性分开计算：

   • 乘法贡献（pp数组）：每个函数执行后对后续操作的乘法系数（类型2函数直接贡献乘数，类型3函数贡献调用链的乘积）。
   • 加法贡献系数（ad数组）：类型1函数的实际加值 = 原始加值 × 该系数（系数由后续乘法操作的乘积决定）。

2. 计算流程：

   • 用DFS计算所有函数的乘法贡献。
   • 用拓扑排序计算加法贡献系数（保证调用顺序正确）。
   • 结合初始数据，应用总乘法和所有加法贡献得到结果。

完整代码与解析

#include <bits/stdc++.h>
using namespace std;

const long long M = 998244353;  // 取模常数
long long n, a[1100005];  // 数据初始值及结果
long long m, q;  // 函数个数、操作序列长度
long long p[1100005], v[1100005];  // p[i]：类型1函数的目标下标；v[i]：函数参数
long long pp[1100005];  // 乘法贡献：pp[x]表示函数x的总乘法系数
long long ad[1100005];  // 加法贡献系数：ad[x]表示函数x的加法放大系数
long long t[1100005];  // DFS标记（避免重复处理）
long long in[1100005];  // 入度（用于拓扑排序）
vector<long long> vt[1100005];  // 邻接表：vt[x]存储x调用的函数列表
queue<long long> qq;  // 拓扑排序队列

// DFS计算乘法贡献pp[x]
void dfs(long long x) {
    for (int i = 0; i < vt[x].size(); i++) {
        long long y = vt[x][i];
        if (!t[y]) {  // 未处理过的函数
            t[y] = 1;
            dfs(y);  // 递归计算子函数的乘法贡献
        }
        // 函数x的乘法贡献 = 自身初始值 × 所有子函数的乘法贡献（累乘）
        pp[x] = (pp[x] * pp[y]) % M;
        in[y]++;  // 记录子函数y的入度（被调用次数）
    }
}

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];  // 读取初始数据
    }

    cin >> m;
    for (int i = 1; i <= m; i++) {
        int op;
        cin >> op;
        if (op == 1) {  // 类型1：单点加法
            cin >> p[i] >> v[i];  // p[i]是下标，v[i]是加值
            pp[i] = 1;  // 加法不影响乘法，贡献为1
        } else if (op == 2) {  // 类型2：全局乘法
            cin >> v[i];  // v[i]是乘数
            pp[i] = v[i] % M;  // 乘法贡献直接为v[i]
        } else if (op == 3) {  // 类型3：调用其他函数
            int c;
            cin >> c;
            pp[i] = 1;  // 初始乘法贡献为1，后续由子函数乘积更新
            for (int j = 0; j < c; j++) {
                long long g;
                cin >> g;
                vt[i].push_back(g);  // 记录调用的函数
            }
        }
    }

    // 读取用户操作序列，作为虚拟根函数0的调用列表
    cin >> q;
    for (int i = 0; i < q; i++) {
        long long f;
        cin >> f;
        vt[0].push_back(f);  // 0号函数是所有用户操作的入口
    }

    // 计算乘法贡献：从虚拟根函数0开始DFS
    pp[0] = 1;  // 根函数初始乘法贡献为1
    dfs(0);

    // 计算加法贡献系数：拓扑排序
    ad[0] = 1;  // 根函数的加法系数为1（无前置放大）
    qq.push(0);  // 根函数入队

    while (!qq.empty()) {
        long long tp = qq.front();
        qq.pop();

        long long ss = 1;  // 记录后续函数的乘法贡献乘积（用于计算放大系数）
        // 逆序遍历调用列表（保证后续函数的乘法先被计算）
        for (int i = vt[tp].size() - 1; i >= 0; i--) {
            long long y = vt[tp][i];
            // 子函数y的加法系数 += 父函数tp的系数 × 后续乘法乘积ss
            ad[y] = (ad[y] + ad[tp] * ss) % M;
            // 更新ss：乘以当前子函数的乘法贡献（后续函数需累积该乘法）
            ss = (ss * pp[y]) % M;
            // 入度减1，若为0则入队处理
            if (--in[y] == 0) {
                qq.push(y);
            }
        }
    }

    // 计算最终结果：先应用总乘法贡献
    for (int i = 1; i <= n; i++) {
        a[i] = (a[i] * pp[0]) % M;
    }

    // 再应用所有加法贡献（仅类型1函数有效）
    for (int i = 1; i <= m; i++) {
        if (p[i] != 0) {  // p[i]不为0表示是类型1函数
            a[p[i]] = (a[p[i]] + ad[i] * v[i]) % M;
        }
    }

    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }

    return 0;
}

关键步骤解析

1. 输入处理：区分三类函数，初始化乘法贡献pp（类型1为1，类型2为乘数，类型3为1）。
2. DFS计算乘法贡献：从虚拟根函数0开始，递归计算每个函数的乘法贡献（类型3函数为调用链的乘积）。
3. 拓扑排序计算加法系数：按调用逆序计算，确保后续乘法对当前加法的放大作用被正确累积。
4. 结果计算：先将初始数据乘以总乘法贡献（pp[0]），再累加所有类型1函数的有效加法（ad[i] × v[i]）。

复杂度分析

• 时间复杂度：O(n + m + ∑C_j + Q)，其中∑C_j是所有类型3函数的调用总数，DFS和拓扑排序均线性遍历。
• 空间复杂度：O(m + ∑C_j)，用于存储函数调用关系和贡献数组。

该算法高效处理嵌套调用，避免了重复计算，适用于大规模数据。