T3
假设有函数1,后有函数2为 ( imes v),则函数1相当于做了 (v) 次。
利用这个性质可以把所有的操作变成加法操作。
考虑执行函数序列 (q_1,q_2,cdots,q_Q) ,设 (f_i) 为 (i) 函数做的乘法操作的值的积,则函数 (q_{Q-1}) 相当于做了 (f_{q_Q}) 次,函数 (q_i) 的实际执行次数 (cnt_{q_i} = prodlimits_{j=i+1}^{Q} f_{q_j}) 次。
可以先 DFS 求出 (f_i) ,再从 (Q) 到 (1) 扫一遍求出 (cnt_{q_i}) ,然后跑一遍拓扑排序,用 (cnt_u) 更新 (cnt_v) 即可。
#include <cstdio>
#include <cctype>
#include <cstring>
#define MAX_N (100000 + 5)
#define MAX_M (100000 + 5)
#define MAX_Q (100000 + 5)
#define MAX_SUM (1000000 + 5)
typedef long long LL;
const int mod = 998244353;
int n, m, Q;
int a[MAX_N];
struct Opt {
int t, p, v;
int c;
} o[MAX_N];
int h[MAX_N], tot;
struct Edge {
int to, next;
} e[MAX_SUM];
int q[MAX_Q];
int in[MAX_M];
int f[MAX_M];
bool vis[MAX_M];
int cnt[MAX_M];
int st[MAX_M], l, r;
int Read() {
int res = 0;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar();
return res;
}
void Write(int x) {
if (x >= 10) Write(x / 10);
putchar(x % 10 + '0');
}
void Add_Edge(int u, int v) {
e[++tot].to = v;
e[tot].next = h[u];
h[u] = tot;
++in[v];
}
void DFS(int u) {
if (vis[u]) return;
vis[u] = 1;
int v;
for (int i = h[u]; i; i = e[i].next) {
v = e[i].to;
DFS(v);
f[u] = (LL)f[u] * f[v] % mod;
}
}
int main() {
n = Read();
for (int i = 1; i <= n; ++i)
a[i] = Read();
m = Read();
for (int i = 1; i <= m; ++i) {
o[i].t = Read();
switch (o[i].t) {
case 1:
o[i].p = Read(), o[i].v = Read();
break;
case 2:
o[i].v = Read();
break;
default:
o[i].c = Read();
for (int j = 1; j <= o[i].c; ++j)
Add_Edge(i, Read());
}
}
Q = Read();
for (int i = 1; i <= Q; ++i)
q[i] = Read();
for (int i = 1; i <= m; ++i)
f[i] = o[i].t == 2 ? o[i].v : 1;
for (int i = 1; i <= m; ++i)
if (!in[i]) DFS(i);
int prod = 1;
for (int i = Q; i; --i) {
cnt[q[i]] = (cnt[q[i]] + prod) % mod;
prod = (LL)prod * f[q[i]] % mod;
}
l = 1;
for (int i = 1; i <= m; ++i)
if (!in[i]) st[++r] = i;
int u, v, tmp;
while (l <= r) {
u = st[l++];
tmp = cnt[u];
for (int i = h[u]; i; i = e[i].next) {
v = e[i].to;
cnt[v] = (cnt[v] + tmp) % mod;
tmp = (LL)tmp * f[v] % mod;
--in[v];
if (!in[v]) st[++r] = v;
}
}
for (int i = 1; i <= n; ++i)
a[i] = (LL)a[i] * prod % mod;
for (int i = 1; i <= m; ++i)
if (o[i].t == 1)
a[o[i].p] = (a[o[i].p] + (LL)cnt[i] * o[i].v) % mod;
for (int i = 1; i <= n; ++i)
Write(a[i]), putchar(' ');
return 0;
}
T4