第一次写拉格朗日反演。
思路
考虑如何操作。
发现出根节点外有 \(n-1\) 个点是一。
由于我们只能操作 \(n-1\) 次，相当于每一次操作必须把两个一合并。
一个点最多往上跳两层，所以要求它的父亲或者爷爷是一。
考虑设 \(f_i\) 表示当前节点为一并且整个子树总和为 \(i\) 的方案数，\(g_i\) 表示当前节点为零并且整个子树总和为 \(i\) 的方案数。
考虑递推：
\[\begin{align} f_{x}&=2\times (f_{x-1}+g_{x-1})+\sum_{1\le i< x-1}(f_{i}+g_{i})(f_{x-1-i}+g_{x-1-i})\\ g_{x}&=2\times f_{x}+\sum_{1\le i<x}f_{i}f_{x-i} \end{align} \]发现是卷积形式。
我们不妨用生成函数来表示它们。
\[\begin{align} F(x)&=x+2x(F(x)+G(x))+x(F(x)+G(x))^2\\ G(x)&=2F(x)+F(x)^2 \end{align} \]把 \(G\) 代入 \(F\)。
\[\begin{align} F(x)&=x(F(x)+G(x)+1)^2\\ &=x(F(x)^2+3F(x)+1)^2\\ \end{align} \]由于我们要求第 \(n\) 次项系数，可以用拉格朗日反演提取。
令：
\[\begin{align} H(F(x))&=x\\ &=\frac{F(x)}{(F(x)^2+3F(x)+1)^2}\\ &=\frac{x}{(x^2+3x+1)^2}\\ \end{align} \]所以：
\[\begin{align} [x^n]F(x)&=\frac{1}{n}[x^{n-1}](\frac{x}{H(x)})^n\\ &=\frac{1}{n}[x^{n-1}](x^2+3x+1)^{2n} \end{align} \]然后有两种方法。
第一种直接组合数展开。
\[\begin{align} [x^n]F(x)&=\frac{1}{n}[x^{n-1}](x^2+3x+1)^{2n}\\ &=\frac{1}{n}\sum_{i=0}^{n-1}[(n-i-1)\bmod 2=0]3^{i}\binom{2n}{i,\frac{n-i-1}{2},2n-i-\frac{n-i-1}{2}}\\ \end{align} \]还有第二种方法。
因为这个函数是 D-finite 的，所以也可以求出递推式。
令 \(L(x)=(x^2+3x+1)^{2n}\)。
有：
\[\begin{align} L'(x)&=(2x+3)2n(x^2+3x+1)^{2n-1}\\ &=\frac{(2x+3)2nL(x)}{x^2+3x+1}\\ (x^2+3x+1)L'(x)&=(2x+3)2nL(x) \end{align} \]对比系数：
\[\begin{align} [x^k]L'(x)+3[x^{k-1}]L'(x)+[x^{k-2}]L'(x)&=6nL_k+4nL_{k-1}\\ (k+1)L_{k+1}+3kL_{k}+(k-1)L_{k-1}&=6nL_{k}+4nL_{k-1}\\ (k+1)L_{k+1}&=(6n-3k)L_{k}+(4n-k+1)L_{k-1} \end{align} \]其中：\(L_{0}=1,L_{1}=6n\)。
直接递推即可。
时间复杂度：\(O(n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int n;
int v[10000010];
int main() {
cin >> n;
long long f0 = 1, f1 = 6 * n, f2;
v[0] = v[1] = 1;
for (int i = 2; i <= n; i++)
v[i] = 1ll * (mod - mod / i) * v[mod % i] % mod;
for (int i = 1; i < n - 1; i++) {
f2 = ((6 * n - 3 * i) * f1 + (4 * n - i + 1) * f0) % mod * v[i + 1] % mod;
f0 = f1;
f1 = f2;
}
f0 = 1ll * f0 * v[n] % mod;
f1 = 1ll * f1 * v[n] % mod;
f2 = 1ll * f2 * v[n] % mod;
cout << (n == 1 ? f0 : (n == 2 ? f1 : f2)) << "\n";
}