赛上不会的题目。

Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/lp7077/

题解

三种操作：

1. 单点加
2. 全局乘
3. 函数调用
   考虑到这个全局乘看上去就很假，可以考虑用什么全局 tag 维护一下。但这样不可避免需要用到逆元，要是 $0$ 没处理好就挂得不如暴力了。

于是可以处理后缀积，计算一个单点加操作后被乘了多少次。

原本的函数关系是一张有向无环图，将操作三看做依次往外连边即可。

考虑在这张图上处理。

首先用一次 dfs 处理出每个点往下操作会乘上多少倍率。

就是 DAG 上记忆化搜索的做法吧。

此时我们有一个 $O(nm)$ 的做法，对于每一个调用，直接图上搜索过去，搜索过程中维护一个后缀积，然后对操作一点才做真正的更改。

正解感觉很像是把询问的调用也打成标记，然后往下传。

考虑加一个虚点，看做是操作三，然后依次调用询问操作中的调用。

这次似乎需要用拓扑 dp 了，这次的目标是得知每个操作一的倍率。

从根往下推应该就可以了吧，维护每个点被调用多少次。注意操作三的调用顺序，要把后调用的倍率累计进来。

还有个初始值的问题，不想特判，可以考虑塞到图里，看做很多个一开始的加操作。

其实感觉难度不大，只是我太蠢了罢了，赛后可做赛上跳过系列。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int mod = 998244353;
const int maxn = 3e6 + 100;
struct node
{
    int to, next;
} E[maxn];
int head[maxn];
inline void addE(const int& x, const int& y)
{
    static int tot = 0;
    E[++tot].next = head[x], E[tot].to = y, head[x] = tot;
}
inline int add(int x, int y) { int res = x + y; return res >= mod ? res - mod : res; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
int n, m, q, a[maxn], type[maxn], tar[maxn], w[maxn], S, in[maxn];
int prod[maxn], g[maxn];
void dfs1(int u, int fa)
{
    if(prod[u] != -1) return;
    if (type[u] == 2) prod[u] = w[u];
    else prod[u] = 1;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if(v == fa) continue;
        dfs1(v, u), prod[u] = mul(prod[u], prod[v]);
    }
}
signed main()
{
    memset(prod, -1, sizeof(prod));
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    read(m);
    for (int i = 1; i <= m; ++i) 
    {
        read(type[i]);
        if (type[i] == 1) read(tar[i]), read(w[i]);
        else if(type[i] == 2) read(w[i]);
        else 
        {
            int num, x;
            read(num);
            while (num--) read(x), addE(i, x), in[x]++;
        }
    }
    S = n + m + 1;
    for (int i = 1; i <= n; ++i) type[i + m] = 1, tar[i + m] = i, w[i + m] = a[i], addE(S, i + m), in[i + m]++;
    read(q);
    for (int i = 1, x; i <= q; ++i) read(x), addE(S, x), in[x]++;
    dfs1(S, 0);
    static int q[maxn], qt = 0, qh = 1;
    for (int i = 1; i <= S; ++i) if(!in[i]) q[++qt] = i;
    g[S] = 1;
    while(qt >= qh)
    {
        int u = q[qh++];
        for (int p = head[u]; p; p = E[p].next)
        {
            int v = E[p].to;
            g[v] = add(g[v], g[u]), g[u] = mul(g[u], prod[v]);
            if (--in[v] == 0) q[++qt] = v;
        }
    }
    for (int i = 1; i <= n; ++i) a[i] = 0;
    for (int i = 1; i <= S; ++i) if (type[i] == 1) a[tar[i]] = add(a[tar[i]], mul(w[i], g[i]));
    for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
    return 0;
}