题目

[CodeForces 438E] The Child and Binary Tree

分析

首先列出 DP 式，设 $dp[i]$ 表示用权值和为 $i$ 的点，形成的合法二叉树数量，于是有 $dp[i] = \begin{cases} \sum_{k = 0}^{i} \sum_{j = 0}^{i - k} (dp[i - k] \times dp[i - k - j] \times [k \in C]) & i > 0 \\ 1 & i = 0\end{cases}$ 转移就是枚举根节点的权值和左子树的权值和，边界条件是便于转移的时候可以有一个儿子为空树。

发现这个转移是一个多项式乘法的形式（即和为某个定值的几项相乘，再把乘积加起来），因此设 $F(x) = \sum_{i = 0}^{m} dp[i] \cdot x^i$，$G(x) = \sum_{i = 0}^{m} [i \in C] \cdot x^i$，只考虑有意义的前 $m$ 项，有 $F(x) = F^2(x)G(x) + 1$（加一就是因为 $dp[0] = 1$，但是 $G(x)$ 没有常数项），将 $F(x)$ 作为未知数、$G(x)$ 作为参数解这个一元二次方程得到 $F(x) = \frac{1 \pm \sqrt{1 - 4G(x)}}{2G(x)}$

可能细心的读者会发现，对于某些 $x$ 来说，$\Delta<0$，那这个“解”没有意义。但实际上我们是将一个多项式看做一个整体，而不是一个函数，而多项式开根也变成了和数字开根不一样的定义，所以，与其这样写不如写成 $F = \frac{1 \pm \sqrt{1 - 4G}}{2G}$ 其中 $F$ 和 $G$ 就是一个系数给定的多项式，我们不需要往里面代值，我们只需要最终的系数！而这些运算是新定义的，但是他们满足与数字运算相似的性质（因为他们是整式运算，整式运算就相当于数字运算），所以我们可以像数字一样解！

首先要解决的问题是 $G(x)$ 的常数项为 $0$，没有乘法逆元。这时候用一个分母无理化的神仙操作即可：$F(x) = \frac{1 \pm \sqrt{1 - 4G(x)}}{2G(x)} = \frac{2}{1 \mp \sqrt{1 - 4G(x)}}$ 然后要解决的问题是正负号，显然不会都取，注意到 $F(0) = 1$，代入发现 $F(x) = \frac{2}{1 + \sqrt{1 - 4G(x)}}$ 于是多项式开根 + 多项式求逆即可。

代码

花了一上午 + 一晚上写板子，现在这个板子是对的并且很好用，缺点是大部分时候需要氧气。

#include <bits/stdc++.h>#define RG registertypedef long long LL;int Read() {int x = 0; bool f = false; char c = getchar();while (c < '0' || c > '9')f |= c == '-', c = getchar();while (c >= '0' && c <= '9')x = (x * 10) + (c ^ 48), c = getchar();return f ? -x : x;
}template <const int _MOD> struct ModNumber { // 为了效率 (事实上还是不高) 省去了一些实用性int x;inline ModNumber() { x = 0; }inline ModNumber(const int &y) { x = y; }// 需保证 y 的范围! (如果在这 % _MOD 会 T, 因为代码中大量调用该构造函数)// (当然, 开 O2 可以起飞)inline int Int() { return x; }inline ModNumber Pow(int y) const {RG int ret = 1, tmp = x;while (y) {if (y & 1) ret = ((LL)ret * tmp) % _MOD;y >>= 1; tmp = ((LL)tmp * tmp) % _MOD;}return ModNumber(ret);}inline bool operator == (const ModNumber &y) const { return x == y.x; }inline bool operator != (const ModNumber &y) const { return x != y.x; }inline bool operator < (const ModNumber &y) const { return x < y.x; }inline bool operator > (const ModNumber &y) const { return x > y.x; }inline bool operator <= (const ModNumber &y) const { return x <= y.x; }inline bool operator >= (const ModNumber &y) const { return x >= y.x; }inline ModNumber operator + (const ModNumber &y) const { return (x + y.x >= _MOD) ? (x + y.x - _MOD) : (x + y.x); }inline ModNumber operator - (const ModNumber &y) const { return (x - y.x < 0) ? (x - y.x + _MOD) : (x - y.x); }inline ModNumber operator * (const ModNumber &y) const { return ModNumber((LL)x * y.x % _MOD); }inline ModNumber operator / (const ModNumber &y) const { return *this * y.Pow(_MOD - 2); }inline ModNumber operator ^ (const int &y) const { return Pow(y); }inline void operator += (const ModNumber &y) { *this = *this + y; }inline void operator *= (const ModNumber &y) { *this = *this * y; }inline void operator -= (const ModNumber &y) { *this = *this - y; }inline void operator /= (const ModNumber &y) { *this = *this / y; }inline void operator ^= (const LL &y) const { *this = *this ^ y; }
};const int MAXN = 100000 * 4; // 所有 MAXN 都要开 4 倍!
const int MOD = 998244353;typedef ModNumber<MOD> Int;const Int __G = 3, One = 1, Two = 2, InvTwo = One / Two;namespace Polynomial {// 好氧, 好氧, 好氧! (无氧原地去世)// 所有 n: 多项式的项数 (即次数 + 1)// 数组从 0 开始存int Rev[MAXN + 5];Int G0[2][MAXN + 5];void GetG0(const int &n) { // 使用前必须先初始化 G0for (RG int i = 2; i <= n; i <<= 1) {G0[0][i] = __G ^ ((MOD - 1) / i);G0[1][i] = G0[0][i] ^ (MOD - 2);}}inline void GetRev(const int n) { // Rev 在函数内初始化for (RG int i = 0; i < n; i++)Rev[i] = (Rev[i >> 1] >> 1) | ((i & 1) * (n >> 1));}inline int ToPow(const int &n) { // lim 在函数内初始化RG int ret = 1;while (ret < n)ret <<= 1;return ret;}void PrintPoly(Int *A, const int &n) {for (RG int i = 0; i < n; i++)printf("%d ", A[i].x);puts("");}void ReadPoly(Int *A, const int &n) {for (RG int i = 0; i < n; i++)A[i].x = Read();}void NTT(Int *A, const int &n, const int &opt) {for (RG int i = 0; i < n; i++)if (i < Rev[i])std::swap(A[i], A[Rev[i]]);for (RG int mid = 1; mid < n; mid <<= 1) {const int k = mid << 1;const Int g0 = G0[opt][k];for (RG int i = 0; i < n; i += k) {Int g = 1;for (RG int j = 0; j < mid; j++, g *= g0) {Int tmp1 = A[i + j], tmp2 = A[i + j + mid] * g;A[i + j] = tmp1 + tmp2, A[i + j + mid] = tmp1 - tmp2;}}}if (opt == 1) {const Int inv = One / n;for (RG int i = 0; i < n; i++)A[i] *= inv;}}Int A0[MAXN + 5], B0[MAXN + 5];void Multiply(const Int *A, const Int *B, Int *P, const int &n, const int &m) { // P = A * Bint lim = ToPow(n + m - 1); GetRev(lim);for (int i = 0; i < lim; i++) A0[i] = B0[i] = 0;for (RG int i = 0; i < n; i++) A0[i] = A[i];for (RG int i = 0; i < m; i++) B0[i] = B[i];NTT(A0, lim, 0), NTT(B0, lim, 0);for (RG int i = 0; i < lim; i++) P[i] = A0[i] * B0[i];NTT(P, lim, 1);}Int A1[MAXN + 5], B1[MAXN + 5], C1[MAXN + 5];void Inverse(const Int *A, Int *B, const int &n) { // B = 1 / A, A 不变if (n == 1) { B[0] =  A[0] ^ (MOD - 2); return; }Inverse(A, B, (n + 1) >> 1);const int lim = ToPow(n + n - 1); GetRev(lim);for (RG int i = 0; i < n; i++) A1[i] = A[i], B1[i] = B[i];for (RG int i = n; i < lim; i++) A1[i] = B1[i] = 0;NTT(A1, lim, 0), NTT(B1, lim, 0);for (RG int i = 0; i < lim; i++) C1[i] = A1[i] * B1[i] * B1[i];NTT(C1, lim, 1);for (RG int i = 0; i < n; i++) B[i] = Two * B[i] - C1[i];for (RG int i = n; i < lim; i++) B[i] = 0;}Int C2[MAXN + 5], InvB[MAXN + 5], B2[MAXN + 5];void Sqrt(const Int *A, Int *B, const int &n) { // B = √A, A 不变 (默认开根的多项式常数项为 1)if (n == 1) { B[0] = 1; return; }Sqrt(A, B, (n + 1) >> 1);Inverse(B, InvB, n);Multiply(B, B, B2, n, n);for (RG int i = 0; i < n; i++) InvB[i] *= InvTwo;for (RG int i = 0; i < n; i++) B2[i] += A[i];Multiply(B2, InvB, C2, n, n);for (RG int i = 0; i < n; i++) B[i] = C2[i];}Int AR[MAXN + 5], BR[MAXN + 5], InvBR[MAXN + 5], A2[MAXN + 5], CR[MAXN + 5], C3[MAXN + 5];void Divide(const Int *A, const Int *B, Int *C, Int *R, const int &n, const int &m) { // C = A / B, R = A % B, A 不变, B 不变for (RG int i = 0; i < n; i++) AR[i] = A[n - i - 1], A2[i] = A[i];for (RG int i = 0; i < n - m + 1; i++) BR[i] = B[m - i - 1];Inverse(BR, InvBR, n - m + 1);Multiply(AR, InvBR, CR, n, n - m + 1);for (int i = 0; i < n - m + 1; i++) C[i] = CR[n - m - i];Multiply(B, C, C3, m, n - m + 1);for (RG int i = 0; i < m - 1; i++) R[i] = A[i] - C3[i];}void Derivative(const Int *A, Int *B, const int &n) { // B = A', A 不变for (RG int i = 0; i < n - 1; i++)B[i] = A[i + 1] * (i + 1);B[n - 1] = 0;}void Integral(const Int *A, Int *B, const int &n) { // B = ∫A, A 不变for (RG int i = 1; i < n; i++)B[i] = A[i - 1] / i;B[0] = 0;}Int AD[MAXN + 5], InvA[MAXN + 5], C4[MAXN + 5];void Ln(const Int *A, Int *B, const int &n) { // B = ln A, A 不变Derivative(A, AD, n);Inverse(A, InvA, n);Multiply(AD, InvA, C4, n, n);Integral(C4, B, n);}Int LnB[MAXN + 5], B3[MAXN + 5], B4[MAXN + 5];void Exp(const Int *A, Int *B, const int &n) { // B = e^A, A 不变if (n == 1) { B[0] = 1; return; }Exp(A, B, (n + 1) >> 1); Ln(B, LnB, n);const int lim = ToPow(n + n - 1);for (int i = 0; i < n; i++) B3[i] = A[i] - LnB[i], B4[i] = B[i]; B3[0] += One;Multiply(B3, B4, B, n, n); for (int i = n; i < lim; i++) B[i] = 0;}Int kA[MAXN + 5];void Pow(const Int *A, Int *B, const int &n, const Int &k) { // B = A^k, A 不变for (int i = 0; i < n; i++) kA[i] = A[i] * k; Exp(kA, B, n);}
}const Int Four = 4, Zero = 0;int N, M;
Int F[MAXN + 5], G[MAXN + 5], Sqr[MAXN + 5], Inv[MAXN + 5];int main() {Polynomial::GetG0(MAXN);N = Read(), M = Read();for (int i = 1; i <= N; i++)G[Read()] = 1;for (int i = 1; i <= M; i++)G[i] = Zero - Four * G[i];G[0] += One; Polynomial::Sqrt(G, Sqr, M + 1);Sqr[0] += One; Polynomial::Inverse(Sqr, Inv, M + 1);for (int i = 1; i <= M; i++)printf("%d\n", (Inv[i] + Inv[i]).x);return 0;
}