CSP-S2020 T3 函数调用

洛谷传送门 —— Code来自fysbb

分析：

题面自己去读吧

我们设此函数为 $F\raisebox{0.7em}{t=1,2,3}$

当 $F\raisebox{0.7em}{t=1}$ 时乘了 $K$ 次，那就是此函数被调用了 $K$ 次

但这时 $F\raisebox{0.7em}{t=1}$ 与 $F\raisebox{0.7em}{t=2}$ 都有可能出现，

那么 $F\raisebox{0.7em}{t=2}$ 的调用的先后顺序就会对 $F\raisebox{0.7em}{t=1}$ 产生了影响

因此，$F\raisebox{0.7em}{t=2}$ 的调用，就必然会对 $F\raisebox{0.7em}{t=1}$ 产生贡献 $——$ 每一个 $F\raisebox{0.7em}{t=2}$ 的乘积。

还有 $F\raisebox{0.7em}{t=3}$ 的情况，首先它不会递归处理，其次得注意上面的情况，

即我们可以 ① 计算函数被调用的次数； ② 计算 $F\raisebox{0.7em}{t=3}$ 中嵌套的 $F\raisebox{0.7em}{t=2}$ 带来的贡献

注意：

① 倒序处理序列
② 依照函数处理的顺序进行处理

剩下的看代码吧

分三段看
$$
1.Operating1 —— 处理F\raisebox{0.7em}{t=3}的贡献 \
2.Operating2 —— 倒序处理原序列，计算乘对答案的贡献后，统计答案 \
3.Operating3 —— 处理函数对每一个子函数的贡献
$$

#include <cstdio>
#include <algorithm>

#define MOD 998244353 // 模数
#define INF int(1e5 + 10) // n 最大上限，注意数组越界 要稍微开大

#define IL inline
#define RE register

typedef long long ll;

struct node
{
    int type;
    int tot;
    int v;
    int flag;
    int num;
    ll q; // 因为加数可能会加的很大，于是就开 long long
    ll sum;
    int *next;
    /*
     * type : function 类型
     * tot : function 总数（function 3)
     * v : function value
     * flag : function 是否被处理
     * num : function 包含 function 的数目
     * q : function 的 加数 / 乘数
     * sum : function 乘对函数的贡献
     * */
    node() {
        type = tot = v = flag = sum = num = 0; // 赋初值
        q = 1;
        next = NULL; // NOLINT
    }
};

node f[INF];
int a[INF]; // 需要处理的序列
int num[INF]; // 函数处理的编号
ll ans[INF];
int n, m, t;

IL int read_int() // 快读 int
{
    RE int s = 0;
    RE int w = 1;
    RE char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 3) + (s << 1) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

IL ll read_ll() // 快读 long long
{
    RE ll s = 0;
    RE ll w = 1;
    RE char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 3) + (s << 1) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

void read() // 总读 自己看理解
{
    n = read_int(); // 读入
    for (int i = 1; i <= n; i ++) {
        a[i] = read_int(); // 读入需要处理的序列
    }
    m = read_int();
    for (int i = 1; i <= m; i ++) {
        f[i].type = read_int(); // 读入 function 类型
        switch (f[i].type) {
            case 1:
                f[i].v = read_int();
                f[i].q = read_ll(); // 注意 f[i].q 的类型
                f[i].flag = 1;
                break;
            case 2:
                f[i].q = read_ll();
                f[i].flag = 1;
                break;
            case 3:
                f[i].tot = read_int();
                f[i].next = (int *) calloc(f[i].tot + 2, sizeof(int)); // 动态分配内存，+1可能会爆，不妨开大些
                for (int j = 1; j <= f[i].tot; j ++) {
                    f[i].next[j] = read_int(); // 读入运行的函数顺序
                }
        }
    }
    t = read_int();
    for (int i = 1; i <= t; i ++) { // 读入函数处理的顺序
        num[i] = read_int();
    }
}

ll dfs(int q)
{
    if (f[q].flag == 1) {   // 出口，是否处理过了
        if (f[q].type != 1) { // 如果不是 function 1 的话，直接返回加数
            return f[q].q;
        } else {
            return 1; // 因为 function 1 的加数只有 1 倍，直接返回即可
        }
    }
    f[q].flag = 1; // 没处理过标记成处理
    for (int i = f[q].tot; i >= 1; i --) {  // 需要倒着求，
        f[q].q = f[q].q * dfs(f[q].next[i]) % MOD; // 记得模上 MOD 否则会爆
        f[f[q].next[i]].num ++; // 包含的函数 + 1
    }
    return f[q].q;
}

void operating_1()
{
    for (int i = 1; i <= m; i ++) { // 进行处理
        if (f[i].flag == 0) {
            dfs(i);
        }
    }
}

void operating_2()
{
    ll q = 1;
    for (int i = t; i >= 1; i --) { // 倒序处理
        switch (f[num[i]].type) {
            case 1:
                f[num[i]].sum = (f[num[i]].sum + q) % MOD; // 单点加
                break;
            case 2:
                q = q * f[num[i]].q % MOD; // 全部都乘
                break;
            case 3:
                f[num[i]].sum = (f[num[i]].sum + q) % MOD; // 先加
                q = q * f[num[i]].q % MOD; // 后乘
                break;
        }
    }
    for (int i = 1; i <= n; i ++) {
        ans[i] = a[i] * q % MOD; // 处理原序列，统计贡献
    }
}

void operating_3()
{
    ll q;
    int l;
    int *p;
    int head = 0, tail = 0;
    p = (int *) calloc(m + 5, sizeof(int)); // 动态分配，基本同上
    for (int i = 1; i <= m; i ++) {
        if (f[i].num == 0) {
            p[tail ++] = i; // 利用
        }
    }
    while (head < tail)
    {
        l = p[head ++]; // 利用一个队列，按照顺序进行
        switch (f[l].type) {
            case 1:
                ans[f[l].v] = (ans[f[l].v] + f[l].q * f[l].sum) % MOD;
                break;
            case 3:
                q = f[l].sum;
                for (int i = f[l].tot; i >= 1; i --) {
                    int next = f[l].next[i];
                    if (-- f[next].num == 0) {
                        p[tail ++] = next;
                    }
                    switch (f[next].type) { // 和上面的一样，统计答案贡献
                        case 1:
                            f[next].sum = (f[next].sum + q) % MOD;
                            break;
                        case 2:
                            q = q * f[next].q % MOD;
                            break;
                        case 3:
                            f[next].sum = (f[next].sum + q) % MOD;
                            q = q * f[next].q % MOD;
                            break;
                    }
                }
                break;
        }
    }
    for (int i = 1; i <= n; i ++) {
        printf("%lld ", ans[i]); // 输出
    }
}

int main()
{
    read();
    operating_1();
    operating_2();
    operating_3();
    return 0;
}