2020 函数调用 · 方案二拓扑序乘子回推

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 3858 字
两遍拓扑：正向求乘子，反向回推每次调用的贡献
2020
拓扑
正文

// CSP-S 2020 复赛 T3 · 函数调用（方案二：拓扑序 + 乘子回推，满分）
// 原题：https://oj.yecheng.tv/p/CSPS2020C
// 题意：同方案一（n, m, Q ≤ 2e5 / ΣC ≤ 2e6，需满分）。
// 思路（两遍拓扑，把 Q 次执行合并成一遍计算）：
//   最终 a_i = 初始 a_i × M + addAll[i]，其中 M 是全部执行的乘子之积。
//   关键在 addAll：加法会被"它之后发生的乘法"放大。
//   第一步（逆拓扑）：mul[v] = v 执行一次带来的总乘子——
//       类型 2：val；类型 1：1；类型 3：各子调用 mul 之积。
//   第二步（正拓扑）：W[v] = "v 执行一次时，v 内部的加法发生之后，
//   还会经历的乘子之积"（按 v 的每个调用位置分别累计后求和——同一
//   函数被多处调用时 W 是各处贡献之和，因为加法贡献对乘子线性）：
//       对调用边 u → g（g 是 u 的第 idx 个子调用）：
//           W[g] += W[u] × (g 之后的兄弟 mul 之积)。
//   从虚拟根 W=1 出发沿 Q 次调用序列正拓扑传播一遍。
//   答案：addAll[pos_v] = Σ val_v × W[v]（对每个类型 1 函数 v）。
//   复杂度：O(n + m + Q + ΣC)。
// 易错点：
//   1. mul 逆拓扑、W 正拓扑，顺序不能反；
//   2. "g 之后的兄弟乘积"要从右往左扫子列表维护后缀积；
//   3. 同一函数多个调用点：W 累加（线性性），不是取最大；
//   4. Q 次调用串成虚拟根的孩子序列；全部取模。
#include <cstdio>
#include <vector>
using namespace std;

const int MOD = 998244353;
int n, m, q;
long long a0[100005];
int typ[100005];
long long pos1[100005], val1[100005];
vector<int> sons[100005];
long long mulF[100005];
long long W[100005];
long long addAll[100005];
int deg[100005], topo[400005], tn = 0;

int main() {
    freopen("call.in", "r", stdin);
    freopen("call.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a0[i]);
    for (int f = 1; f <= m; f++) {
        scanf("%d", &typ[f]);
        if (typ[f] == 1) scanf("%lld%lld", &pos1[f], &val1[f]);
        else if (typ[f] == 2) scanf("%lld", &val1[f]);
        else {
            int c;
            scanf("%d", &c);
            for (int j = 0; j < c; j++) {
                int g;
                scanf("%d", &g);
                sons[f].push_back(g);
                deg[g]++;
            }
        }
    }
    // Q 次调用：串成链 root（前一次调用完才下一次，等价虚拟根孩子序列）
    vector<int> calls;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int f;
        scanf("%d", &f);
        calls.push_back(f);
    }
    // 拓扑序（函数图）
    {
        vector<int> st;
        for (int f = 1; f <= m; f++) if (deg[f] == 0) st.push_back(f);
        while (!st.empty()) {
            int u = st.back();
            st.pop_back();
            topo[tn++] = u;
            for (int v : sons[u]) if (--deg[v] == 0) st.push_back(v);
        }
    }
    // 逆拓扑求 mulF
    for (int f = 1; f <= m; f++) mulF[f] = (typ[f] == 2) ? val1[f] % MOD : 1;
    for (int i = tn - 1; i >= 0; i--) {
        int u = topo[i];
        for (int v : sons[u]) mulF[u] = mulF[u] * mulF[v] % MOD;
    }
    // 正拓扑求 W：从调用序列出发（虚拟根 W=1）
    {
        // 调用序列是"多源"起点：每个 calls[i] 的 W += Π_{calls[j], j>i} mulF
        {
            long long sufMul = 1;
            vector<long long> edge(q);
            for (int i = q - 1; i >= 0; i--) {
                edge[i] = sufMul;
                sufMul = sufMul * mulF[calls[i]] % MOD;
            }
            for (int i = 0; i < q; i++) W[calls[i]] = (W[calls[i]] + edge[i]) % MOD;
        }
        // 总乘子 M = Π calls 的 mulF
        long long M = 1;
        for (int i = 0; i < q; i++) M = M * mulF[calls[i]] % MOD;
        // 沿拓扑向内传播 W（函数图上正序）
        for (int i = 0; i < tn; i++) {
            int u = topo[i];
            if (!W[u]) continue;
            if (typ[u] == 1) {
                addAll[pos1[u]] = (addAll[pos1[u]] + val1[u] % MOD * W[u]) % MOD;
            }
            long long suf = 1;
            vector<long long> edge(sons[u].size());
            for (int idx = (int)sons[u].size() - 1; idx >= 0; idx--) {
                edge[idx] = suf;
                suf = suf * mulF[sons[u][idx]] % MOD;
            }
            for (int idx = 0; idx < (int)sons[u].size(); idx++) {
                int g = sons[u][idx];
                W[g] = (W[g] + W[u] * edge[idx]) % MOD;
            }
        }
        // 输出
        for (int i = 1; i <= n; i++)
            printf("%lld ", (a0[i] * M + addAll[i]) % MOD);
        printf("\n");
    }
    return 0;
}
2020 函数调用 · 方案二 拓扑序乘子回推

正文

CSP-S 标程 · 复赛真题的其它内容

2020 函数调用 · 方案二拓扑序乘子回推
