题目描述
https://www.luogu.com.cn/problem/P7077
题解
第一眼看像是数据结构题？
后来发现这题压根不用数据结构
考虑对于给出的操作建一个图：对于所有操作3，按顺序向它调用的函数连边，这样会得到一个DAG
对于乘法操作，在最后给所有数组元素乘上就好了，关键在于每个加法操作最后乘了一个多大的系数
假设整个数组只有一个元素，对它依次执行：+1, *3, +2, *2
那么+1操作实际上就有一个2*3=6的系数，+2有2的系数，所以假设原来这个元素是 (x)，那它最后会是 (6x+1 imes 6+ 2 imes 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，再遍历所有加法操作计算应该加多少即可
代码
#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;
}