先DP
由析合树的知识，我们发现我们要算的就是根为析点，且儿子数等于 (n) 的树对应的排列的数量 ((n > 2))。
记此方案数为 (f_n) 。
我们容斥计算，首先排列任意，会有 (n!) 的贡献。
然后我们分别减去根为析点且儿子数不足 (n) 与根为合点的情况。
记把 (1 sim n) 划分为 (i) 段，每段值域是连续的且前面段中的数小于后面段中的数的方案数为 (w_{n,i}) 。
析点的计算方法：我们枚举根的儿子数，每个儿子对应的区间显然值域是连续的，我们枚举划分段数 (i(i<n)) ，则一共有 (f_iw_{n,i}) 种排列方式。
合点的计算方法：
假设 (nge2)，
我们记恰好分成 (i(ige 2)) 段的方案数为 (g_i) ，我们考虑 (w_{n,i}) 与 (g_i) 的关系。
显然有 (w_{n,i}=sum_{j=i}^n g_jinom{j-1}{i-1}) 。二项式反演一下就可以得到 (g_i) 的表达式。
因为我们要容斥掉的方案数是 (g_i) 的和，我们考虑每个 (w_{n,i}) 的贡献。
我们发现 (w_{n,i}) 的总贡献显然是 ((-1)^i) 。
因为合点的儿子可以单调上升或下降，所以减去的方案数要乘 (2) 。
于是对于 (nge 2) ，有：
我们可以做一些小小的变换：
考虑怎么算 (w_{n,i}) ，设 (G(x)=sum_{i=1}i!x^i) ，则 (w_{n,i}=[x^n]G(x)^i)。
也就是
设 (F(x)=sum_{i=0} f_ix^i) （记 (f_0=f_1=0)），
即 (F(G(x))=frac{-G(x)^2+G(x)}{1+G(x)}-x) 。
记 (G(x)) 的复合逆为 (P(x)) ，则有 (F(x)=frac{-x^2+x}{1+x}-P(x)) 。
直接拉格朗日反演可以获得 (60) 分的好成绩（
考虑加速，我们发现 (x^2G'(x)+x+xG(x)=G(x)) 。
于是有 (frac{P(x)^2}{P'(x)}+(x+1)P(x)=x) 。
展开得到 (sum_{i=0}^np_ip_{n-i}+sum_{i=0}^{n-1}(i+1)p_{i+1}(p_{n-i}+p_{n-i-1})=np_n) 。
其中 (p_0=0,p_1=1) 。
然后就可以分治FFT了，还可以使用 (O(frac{nlog^2n}{loglogn})) 的半在线卷积（