题目描述

https://www.luogu.com.cn/problem/P7077

题解

第一眼看像是数据结构题?

后来发现这题压根不用数据结构

考虑对于给出的操作建一个图:对于所有操作3,按顺序向它调用的函数连边,这样会得到一个DAG

对于乘法操作,在最后给所有数组元素乘上就好了,关键在于每个加法操作最后乘了一个多大的系数

假设整个数组只有一个元素,对它依次执行:+1, *3, +2, *2

那么+1操作实际上就有一个2*3=6的系数,+2有2的系数,所以假设原来这个元素是$x$,那它最后会是$6x+1\times 6+ 2\times 2$

发现一个加法操作带的系数就等于它后面的所有乘法操作之积,所以可以倒着进行操作,一边记录已进行的所有乘法操作的积是多少,这样就能计算出每次加法操作带的系数是多少

至此,只含1,2操作的情况就处理完了,接下来考虑3操作

对于图上的每个点(代表着一种操作),维护一个mul属性,表示执行一次这个操作会给累计的积乘上多少

对于1类操作,它的mul=1;对于2类操作,它的mul就等于它要乘上的值;而对于3类操作,它的mul等于它直接连向的所有点的mul之积

如图,点2的mul为2,点3的mul为3,所以点1的mul为6,那么执行一次操作1就会让前面执行过的所有的加法操作再乘上6的系数

按照拓扑序倒序扫一遍或者直接dfs即可处理出mul

然后倒着进行$q$次操作,就可以求得每次操作(类型1或3)带着多少系数,记作sum,然后再把类型3的节点的sum下传到它所包含的类型1节点即可

但是有些类型3的操作既包含加法又包含乘法怎么办?

考虑这样一张图 假设编号为1的操作的sum是$x$,那么+2这个操作的sum应该额外增加$3x$,同理+1的sum应增加$12x$

所以下传sum时,假设一个点$x$的sum是$S$,它的儿子是$y_1,y_2,\cdots y_k$,
那么$y_i$的sum就应该增加$S$乘上$y_{i+1}\sim y_k$的mul之积

最后,让数组的每个元素乘上所有$q$次操作的mul,再遍历所有加法操作计算应该加多少即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
typedef long long ll;

template <typename T>
inline void read(T &num) {
T x = 0; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar());
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x;
}

const ll mod = 998244353;
int n, m, Q, F[N];
int head[N], pre[N<<1], to[N<<1], sz, inde[N];
ll a[N];

inline void addedge(int u, int v) {
pre[++sz] = head[u]; head[u] = sz; to[sz] = v; inde[v]++;
}

struct oper {
int tp, p;
ll v, mul, sum;
} b[N];

queue<int> q;
int ord[N], bnbn;
void toposort() { //拓扑排序
for (int i = 1; i <= m; i++) if (!inde[i]) q.push(i);
while (!q.empty()) {
int x = q.front(); q.pop();
ord[++bnbn] = x;
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
inde[y]--;
if (!inde[y]) q.push(y);
}
}
}

void getmul() { //计算节点的mul
for (int i = m; i; i--) {
int x = ord[i];
for (int j = head[x]; j; j = pre[j]) {
int y = to[j];
b[x].mul = b[x].mul * b[y].mul % mod;
}
}
}

void getsum() { //下传节点的sum
for (int i = 1; i <= m; i++) {
int x = ord[i]; ll now = 1;
for (int j = head[x]; j; j = pre[j]) {
int y = to[j];
b[y].sum = (b[y].sum + b[x].sum * now % mod) % mod;
now = now * b[y].mul % mod;
}
}
}

int main() {
read(n);
for (int i = 1; i <= n; i++) read(a[i]);
read(m);
for (int i = 1; i <= m; i++) {
read(b[i].tp);
if (b[i].tp == 1) {
read(b[i].p); read(b[i].v);
b[i].mul = 1;
} else if (b[i].tp == 2) {
read(b[i].v); b[i].mul = b[i].v;
} else {
read(b[i].p); b[i].mul = 1;
for (int j = 1, x; j <= b[i].p; j++) {
read(x);
addedge(i, x);
}
}
}
toposort();
getmul();
read(Q); ll now = 1;
for (int i = 1; i <= Q; i++) read(F[i]);
for (int i = Q; i; i--) {
int x = F[i]; b[x].sum = (b[x].sum + now) % mod;
now = now * b[x].mul % mod;
}
getsum();
for (int i = 1; i <= n; i++) a[i] = a[i] * now % mod;
for (int i = 1; i <= m; i++) {
if (b[i].tp == 1) {
a[b[i].p] = (a[b[i].p] + b[i].v * b[i].sum % mod) % mod;
}
}
for (int i = 1; i <= n; i++) printf("%lld ", a[i]);
return 0;
}

评论