题解
2023-08-18 09:34:52
发布于:广东
19阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int mod = 998244353;
int a[N], op[N], b[N], c[N];
long long d[N], f[N];
vector<pair<int, int> > G[N], H[N];
// 递归计算d数组
long long calculateD(int u) {
if (d[u] != -1) return d[u];
d[u] = op[u] == 2 ? c[u] : 1;
long long s = 1;
for (int i = G[u].size() - 1; i >= 0; i--) {
int v = G[u][i].first;
G[u][i].second = s;
d[u] = d[u] * calculateD(v) % mod;
s = s * d[v] % mod;
}
return d[u];
}
// 递归计算f数组
long long calculateF(int u) {
if (f[u] != -1) return f[u];
f[u] = 0;
for (int i = 0; i < H[u].size(); i++) {
int v = H[u][i].first, w = H[u][i].second;
f[u] = (f[u] + w * calculateF(v)) % mod;
}
return f[u];
}
int main() {
int n, m, q;
cin >> n;
// 输入数组a
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
// 根据输入初始化相关数据结构
for (int i = 1; i <= m; i++) {
cin >> op[i];
if (op[i] == 1) {
cin >> b[i] >> c[i];
} else if (op[i] == 2) {
cin >> c[i];
} else {
int t;
cin >> t;
while (t--) {
int v;
cin >> v;
G[i].push_back({v, 0});
}
}
}
cin >> q;
// 添加查询操作
while (q--) {
int v;
cin >> v;
G[0].push_back({v, 0});
}
// 初始化d和f数组
memset(d, -1, sizeof d);
memset(f, -1, sizeof f);
// 计算d数组
calculateD(0);
// 对数组a进行变换
for (int i = 1; i <= n; i++) {
a[i] = a[i] * d[0] % mod;
}
// 构建H数组
for (int u = 0; u <= m; u++) {
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].first, w = G[u][i].second;
H[v].push_back({u, w});
}
}
// 根据op数组进行计算并更新数组a
f[0] = 1;
for (int i = 1; i <= m; i++) {
if (op[i] == 1) {
a[b[i]] = (a[b[i]] + calculateF(i) * c[i]) % mod;
}
}
// 输出数组a
for (int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
return 0;
}
这里空空如也
有帮助,赞一个