正文
Codeforces 438E The Child and Binary Tree - 生成函数 - 多项式
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目传送门
传送点I
传送点II
传送点III
题目大意
每个点的权值$c\in {c_{1}, c_{2}, \cdots, c_{n}}$，问对于每个$1\leqslant s\leqslant m$有多少种不同的这样的有根二叉树满足所有点的点权和等于$s$。
先考虑一下怎么用dp来做。
设$f_{n}$表示点权和为$n$的满足条件的二叉树的个数，那么有：
$f_{n} = \sum_{c \in C}\sum_{i = 0}^{n - c}f_{i}f_{n - c - i}$
初值满足$f_{0} = 1$。
注意到右边的式子有点像卷积，考虑$f_{n}$的普通生成函数$F(x) = \sum_{n = 0}f_{n}x^{n}$。
将$F(x)$平方就能得到$f\otimes f$的生成函数。我们用它替换右半边，得到了：
$F(x) = \sum_{c \in C}x^{c}F^2(x) + 1$
设某个常数$A = \sum_{c \in C}x^{c}$，则有$A\cdot F^2(x) - F(x) + 1$。
解得$F_{1}(x) = \frac{1 + \sqrt{1 - 4A}}{2A}, F_{2}(x) = \frac{1 - \sqrt{1 - 4A}}{2A} = \frac{1 - (1 - 4A)}{2A\sqrt{1 + 4A}} = \frac{2}{\sqrt{1 + 4A}}$。
我们考虑$F_{1}(x)$的分母的常数项，它是2，分子的常数项为0，然后求逆的时候就会出事情。
但是$F_{2}(x)$可以通过恒等变换使得分母的常数项为非0。
然后做一次多项式开根，一次多项式求逆就做完了。
Code
/**
* Codeforces
* Problem#438E
* Accepted
* Time: 1091ms
* Memory: 5100k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; const int N = ;
const int bzmax = ;
const int M = ;
const int g = ;
const int inv2 = (M + ) >> ; int qpow(int a, int p) {
if (p < )
p += M - ;
int rt = , pa = a;
for ( ; p; p >>= , pa = pa * 1ll * pa % M)
if (p & )
rt = rt * 1ll * pa % M;
return rt;
} int add(int a, int b) {
return ((a += b) >= M) ? (a - M) : (a);
} int sub(int a, int b) {
return ((a -= b) < ) ? (a + M) : (a);
} class NTT {
public:
int gn[bzmax], _gn[bzmax]; NTT() {
for (int i = , L = ; i < bzmax; i++, L <<= ) {
gn[i] = qpow(g, (M - ) / L);
_gn[i] = qpow(g, -(M - ) / L);
}
} void operator () (int* f, int len, int sgn) {
for (int i = , j = len >> , k; i < len - ; i++, j += k) {
if (i < j)
swap(f[i], f[j]);
for (k = len >> ; j >= k; j -= k, k >>= );
} for (int b = , t = ; b <= len; b <<= , t++) {
int wn = ((sgn > ) ? (gn[t]) : (_gn[t])), w = , hb = b >> ;
for (int i = ; i < len; i += b, w = )
for (int j = i; j < i + hb; j++, w = w * 1ll * wn % M) {
int a = f[j], b = f[j + hb] * 1ll * w % M;
f[j] = add(a, b);
f[j + hb] = sub(a, b);
}
} if (sgn < ) {
int invlen = qpow(len, -);
for (int i = ; i < len; i++)
f[i] = f[i] * 1ll * invlen % M;
}
} int correctLen(int n) {
int m = ;
while (m < n) m <<= ;
return m;
}
}NTT; template<typename T>
void pcopy(T* ns, T* ne, const T* os) {
for ( ; ns != ne; *ns = *os, ns++, os++);
} template<typename T>
void pfill(T* ps, T* pt, T val) {
for ( ; ps != pt; *ps = val, ps++);
} void debug(const int* f, int n) {
for (int i = ; i < n; i++)
cerr << f[i] << " ";
cerr << endl;
} void pol_inverse(int *f, int *g, int n) {
static int h[N];
if (n == )
g[] = qpow(f[], -);
else {
pol_inverse(f, g, (n + ) >> ); int t = NTT.correctLen(n << | );
pcopy(h, h + n, f);
pfill(h + n, h + t, );
NTT(h, t, );
NTT(g, t, );
for (int i = ; i < t; i++)
g[i] = g[i] * 1ll * sub(, g[i] * 1ll * h[i] % M) % M;
NTT(g, t, -);
pfill(g + n, g + t, );
}
} void pol_sqrt(int *f, int *g, int n) {
static int C[N], D[N];
if (n == )
g[] = ;
else {
pol_sqrt(f, g, (n + ) >> ); int t = NTT.correctLen(n << );
pcopy(C, C + n, f);
pfill(C + n, C + t, );
pfill(D, D + t, );
pol_inverse(g, D, n);
NTT(C, t, );
NTT(D, t, );
NTT(g, t, );
for (int i = ; i < t; i++)
g[i] = add(C[i] * 1ll * D[i] % M, g[i]) * 1ll * inv2 % M;
NTT(g, t, -);
pfill(g + n, g + t, );
}
} int n, m;
int C[N], qC[N]; inline void init() {
scanf("%d%d", &n, &m);
for (int i = , x; i <= n; i++) {
scanf("%d", &x);
if (x <= m)
C[x] = -;
}
} inline void solve() {
C[]++, m++;
pol_sqrt(C, qC, m);
qC[]++;
pfill(C, C + m, );
pol_inverse(qC, C, m);
for (int i = ; i < m; i++)
printf("%d\n", add(C[i], C[i]));
} int main() {
init();
solve();
return ;
}
