个人做完题目后的总结。
所有记录仅代表个人，如果您是神犇觉得我太菜/题目是 sb 题/马蜂奇特请亲喷。
树形 dp
P9437 『XYGOI round1』一棵树
首先写了 \(O(n^2)\) 的暴力，记录 \(a_i\) 的位数可以过 \(20\text{pts}\)
点击查看代码
#ifdef ONLINE_JUDGE
#else
#define FRZ_29
#endif
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
typedef long long LL;
using namespace std;
void RD() {}
template<typename T, typename... U> void RD(T &x, U&... arg) {
x = 0; int f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f; RD(arg...);
}
void WT() {}
template<typename T> void WT(T &x) {
if (x < 0) { putchar('-'); x = -x; };
if (x > 9) WT(x / 10);
putchar(x % 10 + '0');
}
const int mod = 998244353;
const int N = 1e6 + 5;
#define PRINT(x) cout << #x << " = " << x << "\n"
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)
LL head[N], ver[N << 1], Next[N << 1], tot = 1;
LL n, a[N], ans, dis[N], dig[N];
void add(int u, int v) {
Next[++tot] = head[u]; ver[head[u] = tot] = v;
}
void dfs(int u, int _f) {
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i]; if (v == _f) continue;
int x = a[v]; dis[v] = dis[u];
if (dig[v]) { dis[v] = 1LL * dis[v] * dig[v] % mod; }
else if (x == 0) { dig[v] = 10; dis[v] = dis[v] * 10 % mod; }
else while (x) { (dig[v] = dig[v] == 0 ? 10 : dig[v] * 10) %= mod; dis[v] = dis[v] * 10 % mod; x /= 10; }
dis[v] = (dis[v] + a[v]) % mod;
dfs(v, u);
}
(ans += dis[u]) %= mod;
}
int main() {
#ifdef FRZ_29
freopen("z_example.in", "r", stdin);
freopen("z_example.out", "w", stdout);
#endif
RD(n);
LF(i, 1, n) RD(a[i]);
LF(i, 2, n) {
int fa; RD(fa); add(fa, i), add(i, fa);
}
LF(i, 1, n) {
dis[i] = a[i]; dfs(i, 0);
// LF(i, 1, n) printf("dis[%d] = %d\n", i, dis[i]);
}
printf("%lld\n", ans);
return 0;
}
// START:2024/10/30 21:06:11;
然后考虑特殊性质 1。
设 \(T(i, j)\) 为 \(i \rightarrow j\) 经过所有数的位数和（不包括 \(i\)）。
想到 \(i \rightarrow j\) 的贡献中 \(a_i\) 的贡献为 \(10^{T(i, j)} \times a_i\)。
遂想到换根转移 \(f_u = \sum_{i \in [1, n]} ^ {i \not= u} T(u, i)\) 来计算每个点对答案的贡献。
但经过实操发现困难，于是向题解求助。
发现只要改变成求其他点到该点的贡献就好处理了。
点击查看代码
#ifdef ONLINE_JUDGE
#else
#define FRZ_29
#endif
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
typedef long long LL;
using namespace std;
void RD() {}
template<typename T, typename... U> void RD(T &x, U&... arg) {
x = 0; int f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f; RD(arg...);
}
void WT() {}
template<typename T> void WT(T &x) {
if (x < 0) { putchar('-'); x = -x; };
if (x > 9) WT(x / 10);
putchar(x % 10 + '0');
}
const int N = 1e6 + 5;
const int mod = 998244353;
#define PRINT(x) cout << #x << " = " << x << "\n"
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)
int lg(int x) {
int t = 0;
if (x == 0) return 1;
else while (x) t++, x /= 10;
return t;
}
int head[N], ver[N << 1], Next[N << 1], tot = 1;
int n, a[N], sz[N], dig[N];
LL f[N], g[N], pw[N], sum[N], ans;
void add(int u, int v) {
Next[++tot] = head[u];
ver[head[u] = tot] = v;
}
void dfs1(int u, int _f) {
dig[u] = lg(a[u]), sz[u] = 1;
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i]; if (v == _f) continue;
dfs1(v, u); sz[u] += sz[v];
(sum[u] += f[v]) %= mod;
(f[u] += f[v] * pw[dig[u]] % mod + 1LL * sz[v] * a[u]) %= mod;
}
(f[u] += a[u]) %= mod;
}
void dfs2(int u, int _f) {
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i]; if (v == _f) continue;
g[v] = ((g[u] + (sum[u] + mod - f[v]) % mod) % mod * pw[dig[u]] + 1LL * (n - sz[v]) * a[u] % mod) % mod;
(ans += (g[v] + sum[v]) % mod * pw[dig[v]] + 1LL * n * a[v] % mod) %= mod;
dfs2(v, u);
}
}
int main() {
#ifdef FRZ_29
freopen("z_example.in", "r", stdin);
freopen("z_example.out", "w", stdout);
#endif
pw[1] = 10;
LF(i, 2, 9) pw[i] = pw[i - 1] * 10 % mod;
RD(n);
LF(i, 1, n) RD(a[i]);
LF(i, 2, n) {
int fa; RD(fa);
add(fa, i), add(i, fa);
}
dfs1(1, 0);
ans += f[1];
dfs2(1, 0);
printf("%lld\n", ans);
return 0;
}
// START:2024/10/31 17:47:59;
似乎一条路走不通改换条路走呢。
标签：10,ch,记录,int,void,while,include,规划,动态 From： https://www.cnblogs.com/FRZ29/p/18519920无边落木萧萧下，不尽长江滚滚来。