A. P5721 分治 FFT
Problem Link
Y5 下课程里分治结构有放 Antichain, Tree 两道 Poly 题,故进行了一个学习。
半在线卷积。虽然没学过这个东西,但是其思想是比较经典的。半在线要求每一个 \(f_i\) 由 \(f_{1-i-1}\) 与 \(g\) 卷积而得,发现不同的 \(f\) 对后面的贡献之间无关,可以拆开然后加起来。所以可以拆分成若干个区间分别对后面的东西贡献,考虑使用分治,每次做完左区间就卷积贡献到右区间,这样可以把一个前缀的贡献拆分成 \(\log\) 个区间去计算。分治每层复杂度 \(n\log n\),总复杂度 \(\mathcal{O}(n\log^2 n)\)。
之前在学习决策单调性 dp 的高贵分治做法时也有看到类似的东西。它说单调队列做法的应用场景在 dp 转移与前缀具体 dp 值相关时,即有半在线需求时。它的做法也是分治用左区间贡献右区间,或许看到半在线问题就要试图思考拆分贡献分治转化。
Code
// STOOOOOOOOOOOOOOOOOOOOOOOOO hzt CCCCCCCCCCCCCCCCCCCCCCCORZ
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>using namespace std;
using LL = long long;
using PII = pair<int, int>;
constexpr int kN = 1 << 17, kP = 998244353, G = 3, iG = 332748118;
int Pow(int a, int b) {int ret = 1;for (; b > 0; b /= 2) {if (b % 2 == 1)ret = 1ll * ret * a % kP;a = 1ll * a * a % kP;}return ret;
}int n, g[kN], f[kN];
int lim, ts[kN], tmp, a[kN], b[kN];inline void NTT(int *f, int n, int o) {for (int i = 0; i < n; i++)ts[i] > i && (swap(f[i], f[ts[i]]), 0);for (int len = 2; len <= n; len *= 2) {int w = Pow(o == 1 ? G : iG, (kP - 1) / len);for (int l = 0; l < n; l += len)for (int i = l, cur = 1; i < l + len / 2; i++, cur = 1ll * cur * w % kP) {int a = f[i], b = 1ll * cur * f[i + len / 2] % kP;f[i] = (a + b) % kP, f[i + len / 2] = (a - b + kP) % kP;}}
}void Divide(int l, int r) {if (l == r)return;int mid = (l + r) / 2, len = r - l + 1;Divide(l, mid);for (int i = 0; i < len; i++)ts[i] = (ts[i >> 1] >> 1) | ((i & 1) * len / 2);for (int i = l; i <= r; i++)a[i - l] = (i <= mid ? f[i] : 0), b[i - l] = g[i - l];NTT(a, len, 1), NTT(b, len, 1);for (int i = 0; i < len; i++)a[i] = 1ll * a[i] * b[i] % kP;NTT(a, len, -1);for (int i = mid + 1, inv = Pow(len, kP - 2); i <= r; i++)f[i] = (f[i] + 1ll * inv * a[i - l]) % kP;Divide(mid + 1, r);
}int main() {cin.tie(0)->sync_with_stdio(0);cin >> n, lim = 1 << __lg(n - 1) + 1;for (int i = 1; i < n; i++)cin >> g[i];f[0] = 1, Divide(0, lim - 1);for (int i = 0; i < n; i++)cout << f[i] << ' ';return 0;
}
B. ABC269Ex Antichain / C. CF1010F Tree (7)
Problem Link B
Problem Link C
两个使用相同技巧的好题。有可能已经是套路了/xk
Tree 转化一下题意变成求出 \(n\) 个点的二叉树中包含 \(1\) 的连通块个数。然后这两题都可以直接列出一个卷积形式的 DP 式子。
Antichain: \(f_u[x]=[x=1]+(\prod\limits_{v\in son_x}f_v)[x]\),Tree: \(f_u[x]=[x=0]+(f_{l_u}*f_{r_u})[x-1]\),当然可以用生成函数表示。但是复杂度很高,因为 \(F_u\) 项数是 \(sz_u\) 的,复杂度保底一个 \(n^2\)。
但是怎么优化这个东西呢?由于它的复杂度和子树大小强相关,所以考虑怎么优化我所计算的东西的子树大小和。考虑重链剖分,每次只暴力合并重链轻儿子的答案,重链放到一起做。这样我合并的信息量是轻儿子子树大小和的。这个东西相当于树上所有节点跳到根经过的轻边数量和。很明显这是 \(\mathcal{O}(n\log n)\) 的。于是算子树的答案将重链和轻子树分开考虑。
对这两道题而言,接下来就是考虑重链上选哪个点/连通块伸入哪个点处,然后暴力把生成函数嵌套式拆开,形成前缀积的和之类的东西,然后分治合并轻儿子多项式 NTT 卷积起来即可。
虽然题目用到了超纲知识 Poly,但是其对子树大小相关信息合并的处理非常巧妙,深刻利用了“深度”和“子树大小”之间的关系。虽然真正需要使用到多项式的地方并不多,但是很多的 DP 转移和其有着一些联系,使用多项式的思考方式来做 DP 的特殊优化或许会有比较好的效果。
Antichain
// STOOOOOOOOOOOOOOOOOOOOOOOOO hzt CCCCCCCCCCCCCCCCCCCCCCCORZ
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>using namespace std;
using LL = long long;
using Poly = vector<int>;
using PII = pair<int, int>;
constexpr int kN = 1 << 18, kP = 998244353, G = 3, iG = 332748118;
inline int Pow(int a, int b) {int ret = 1;for (; b > 0; b /= 2) {b % 2 == 1 && (ret = 1ll * ret * a % kP);a = 1ll * a * a % kP;}return ret;
}namespace POLY {int rev[kN], f[kN], g[kN];inline void NTT(int *f, int n, int o) {for (int i = 0; i < n; i++)i < rev[i] && (swap(f[i], f[rev[i]]), 0);for (int len = 2; len <= n; len *= 2) {int w = Pow(o == 1 ? G : iG, (kP - 1) / len);for (int l = 0; l < n; l += len)for (int i = l, cur = 1; i < l + len / 2; i++, cur = 1ll * cur * w % kP) {int a = f[i], b = 1ll * cur * f[i + len / 2] % kP;f[i] = (a + b) % kP, f[i + len / 2] = (a - b + kP) % kP;}}}inline Poly operator+(Poly a, Poly b) {a.size() < b.size() && (swap(a, b), 0);for (int i = 0; i < b.size(); i++)a[i] = (a[i] + b[i]) % kP;return a;}inline Poly operator*(const Poly &a, const Poly &b) {int sz = a.size() + b.size() - 1, len = 1 << __lg(sz) + 1;for (int i = 0; i < len; i++) {rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * len / 2);f[i] = (i < a.size() ? a[i] : 0), g[i] = (i < b.size() ? b[i] : 0);}NTT(f, len, 1), NTT(g, len, 1);for (int i = 0; i < len; i++)f[i] = 1ll * f[i] * g[i] % kP;NTT(f, len, -1);Poly ret(sz);for (int i = 0, inv = Pow(len, kP - 2); i < sz; i++)ret[i] = 1ll * inv * f[i] % kP;return ret;}
}
using POLY::operator*;
using POLY::operator+;int n;
vector<int> e[kN];
int sz[kN], hson[kN];
void Init(int x, int fa) {sz[x] = 1;for (auto v : e[x]) {if (v == fa)continue;Init(v, x), sz[x] += sz[v];(sz[v] > sz[hson[x]]) && (hson[x] = v);}
}vector<Poly> vec, all;
Poly Mul(int l = 0, int r = vec.size() - 1) {if (l == r)return vec[l];int mid = (l + r) / 2;return Mul(l, mid) * Mul(mid + 1, r);
}
pair<Poly, Poly> Get(int l = 0, int r = all.size() - 1) {if (l == r)return {all[l], Poly{1}};int mid = (l + r) / 2;auto [lm, lp] = Get(l, mid);auto [rm, rp] = Get(mid + 1, r);return {lm * rm, lp + lm * rp};
}
Poly f[kN];
void DP(int x) {for (int i = x; i != 0; i = hson[i]) {for (auto v : e[i])v != hson[i] && (DP(v), 0);}for (int i = x; i != 0; i = hson[i]) {for (auto v : e[i])v != hson[i] && (vec.push_back(f[v]), 0);all.push_back(vec.empty() ? Poly{1} : Mul());vec.clear(), vec.shrink_to_fit();}auto [mul, pre] = Get();f[x] = mul + Poly{0, 1} * pre;all.clear(), all.shrink_to_fit();
}int main() {
#ifndef ONLINE_JUDGEfreopen("input.in", "r", stdin);freopen("output.out", "w", stdout);
#endifcin.tie(0)->sync_with_stdio(0);cin >> n;for (int i = 2, fa; i <= n; i++)cin >> fa, e[fa].push_back(i);Init(1, 0), DP(1);for (int i = 1; i <= n; i++)cout << (i < f[1].size() ? f[1][i] : 0) << '\n';return 0;
}
\(\\\)
Tree
// STOOOOOOOOOOOOOOOOOOOOOOOOO hzt CCCCCCCCCCCCCCCCCCCCCCCORZ
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>using namespace std;
using LL = long long;
using Poly = vector<int>;
using PII = pair<int, int>;
constexpr int kN = 1 << 17, kP = 998244353, G = 3, iG = 332748118;
inline int Pow(int a, int b) {int ret = 1;for (; b > 0; b /= 2) {b % 2 == 1 && (ret = 1ll * ret * a % kP);a = 1ll * a * a % kP;}return ret;
}namespace POLY {int f[kN], g[kN], rev[kN];inline void NTT(int *f, int n, int o) {for (int i = 0; i < n; i++)rev[i] > i && (swap(f[i], f[rev[i]]), 0);for (int len = 2; len <= n; len *= 2) {int w = Pow(o == 1 ? G : iG, (kP - 1) / len);for (int l = 0; l < n; l += len)for (int i = l, cur = 1; i < l + len / 2; i++, cur = 1ll * cur * w % kP) {int a = f[i], b = 1ll * cur * f[i + len / 2] % kP;f[i] = (a + b) % kP, f[i + len / 2] = (a - b + kP) % kP;}}}inline Poly operator+(Poly a, Poly b) {a.size() < b.size() && (swap(a, b), 0);for (int i = 0; i < b.size(); i++)a[i] = (a[i] + b[i]) % kP;return a;}inline Poly operator*(const Poly &a, const Poly &b) {int sz = a.size() + b.size() - 1, len = 1 << __lg(sz - 1) + 1;for (int i = 0; i < len; i++) {rev[i] = (rev[i >> 1] >> 1 | ((i & 1) * len / 2));f[i] = (i < a.size() ? a[i] : 0), g[i] = (i < b.size() ? b[i] : 0);}NTT(f, len, 1), NTT(g, len, 1);for (int i = 0; i < len; i++)f[i] = 1ll * f[i] * g[i] % kP;NTT(f, len, -1);Poly ret(sz);for (int i = 0, inv = Pow(len, kP - 2); i < sz; i++)ret[i] = 1ll * inv * f[i] % kP;return ret;}
}
using POLY::operator*;
using POLY::operator+;int n;
vector<int> e[kN];
int sz[kN], hson[kN];
void Init(int x, int fa) {sz[x] = 1;for (auto v : e[x]) {if (v == fa)continue;Init(v, x), sz[x] += sz[v];(sz[v] > sz[hson[x]]) && (hson[x] = v);}
}Poly f[kN];
vector<Poly> vec;
pair<Poly, Poly> Solve(int l = 0, int r = vec.size() - 1) {if (l == r)return {vec[l], vec[l]};int mid = (l + r) / 2;auto [ml, pl] = Solve(l, mid);auto [mr, pr] = Solve(mid + 1, r);return {ml * mr, pl + ml * pr};
}
void DP(int x, int fa) {for (int i = x, lst = fa; i != 0; lst = i, i = hson[i]) {for (auto v : e[i])(v != hson[i] && v != lst) && (DP(v, i), 0);}for (int i = x; i != 0; fa = i, i = hson[i]) {int son = 0;for (auto v : e[i])(v != hson[i] && v != fa) && (son = v);vec.push_back(f[son] * Poly{0, 1});}f[x] = Solve().second + Poly{1};vec.clear(), vec.shrink_to_fit();
}LL x;
int main() {cin.tie(0)->sync_with_stdio(0);cin >> n >> x, x %= kP;for (int i = 1, u, v; i < n; i++) {cin >> u >> v;e[u].push_back(v), e[v].push_back(u);}Init(1, 0);f[0] = {1}, DP(1, 0);int ans = 0;for (int i = 1, fx = 1, fi = 1; i <= n; i++) {ans = (ans + 1ll * fx * Pow(fi, kP - 2) % kP * f[1][i]) % kP;fx = 1ll * fx * (x + i) % kP, fi = 1ll * fi * i % kP;}cout << ans << '\n';return 0;
}