P6694 强迫症 做题记录

一天，他问了小 H 和小 W 这样一个问题：

如果在一个圆上有 $n$ 个不同的点，依次标号为 $1$ 到 $n$，有多少种方案能把它们连成一棵树？

小 H & 小 W：这不是sb题吗？

小 L：那如果连边不能相交呢？

小 H & 小 W：这不是sb题吗？

小 L：那如果把「树」换成「图」呢呢？

小 H & 小 W：这不是sb题吗？

小 L：那如果给每个点一个权值 $a_i$，连接 $(i,j)$ 的边权值为 $a_i\times a_j$，求满足上面的图的期望所有边权值之和呢？

小 H & 小 W：这不是sb题吗？

小 L 见自己辛苦做了许久都没写出的题目被 dalao 轻松秒杀后十分郁闷。为了安慰他，你需要帮他做出这个问题。

注意

1. 两条边在端点处不视作相交。
2. 没有边的图（即只有 $n$ 个点，之间没有边相连）也合法
3. 点按顺时针从 $1$ 到 $n$ 编号。
4. 图中不能有自环和重边

设 $f_i$ 表示有 $i$ 个点的方案，$g_i$ 表示 $i$ 个点并且 $1$ 和 $i$ 之间有连边的方案。显然 $f_i=2g_i$ 因为在 $f_i$ 里 $1$ 和 $i$ 之间那一条边可以连也可以不连。那么答案就是：

$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n a_ia_j\dfrac{g_{j-i+1}g_{n-j+i+1}}{f_n}$

$=\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n a_ia_j\dfrac{f_{j-i+1}f_{n-j+i+1}}{4f_n}$

$=\dfrac{\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n a_ia_jf_{j-i+1}f_{n-j+i+1}}{4f_n}$

令 $t_i=f_{i+2}f_{n-i}$，那么：

$=\dfrac{\sum\limits_{j=1}^na_j\sum\limits_{i=1}^{j-1} a_it_{j-1-i}}{4f_n}$

注意到 $a_0=0$，那么：

$=\dfrac{\sum\limits_{j=1}^na_j\sum\limits_{i=0}^{j-1} a_it_{j-1-i}}{4f_n}$

是个卷积的形式，不难求。重点就变成了怎么求 $f$，显然边界是 $f_1=1$。

假设当前知道了 $f_{1\dots i-1}$，要求 $f_i$，那么令 $j$ 表示 $i$ 连到的最小编号的点，不难发现 $i$ 到 $j$ 这条边把图分成了两个相对独立的部分，所以：

$f_{i}=f_{i-1}+\sum\limits_{j=1}^{i-1}g_{i-j+1}f_j$ （注意这里是 $g_{i-j+1}f_{j}$ 因为另一部分不能包含 $i$）

$=f_{i-1}+\dfrac{\sum\limits_{j=1}^{i-1}f_{i-j+1}f_j}{2}$

$=2f_{i-1}+\sum\limits_{j=2}^{i-1}f_{i-j+1}f_j$（把 $\dfrac{f_if_1}{2}$ 移到左边再同时乘 $2$）

是个卷积的形式！但是朴素是 $O(n^2\log n)$ 的，TLE。

考虑让这个卷积变得更加标准，设 $h_i=f_{i+1}$，那么有：

$h_{i-1}=2h_{i-2}+\sum\limits_{j=2}^{i-1}h_{i-j}h_{j-1}$

$h_i=2h_{i-1}+\sum\limits_{j=2}^ih_{i+1-j}h_{j-1}$

$=2h_{i-1}+\sum\limits_{j=1}^{i-1}h_{i-j}h_j$

如果能带上 $h_0$ 就完美了！

$2h_i=2h_{i-1}+\sum\limits_{j=0}^{i-1}h_{i-j}h_j$

$3h_i=2h_{i-1}+\sum\limits_{i=0}^ih_{i-j}h_j$（因为 $h_0=f_1=1$）

$h_i=\dfrac{2}{3}h_{i-1}+\dfrac{1}{3}\sum\limits_{j=0}^ih_{i-j}h_j$

设 $H(x)=\sum\limits_{i=0}^{\inf}h_ix^i$ 即 $h$ 的生成函数，那么有：

$H=\dfrac{1}{3}H^2+\dfrac{2}{3}xH+\dfrac{2}{3}$（加上 $\dfrac{2}{3}$ 是因为 $h_0$）

$\dfrac{1}{3}H^2+\left(\dfrac{2}{3}x-1\right)H+\dfrac{2}{3}=0$

$H=\dfrac{1-\frac{2}{3}x\pm\sqrt{\frac{4}{9}x^2-\frac{4}{3}x+1-\frac{8}{9}}}{\frac{2}{3}}$

$=\dfrac{3-2x\pm\sqrt{4x^2-12x+1}}{2}$

因为 $H(0)=1$，所以显然取减号。

$H=\dfrac{3-2x-\sqrt{4x^2-12x+1}}{2}$

考虑拆掉根号，我们可以设 $q(x)=4x^2-12x+1,Q(x)=q(x)^{\frac{1}{2}}$，那么有：

$Q'(x)=\dfrac{1}{2}q(x)^{-\frac{1}{2}}q'(x)$（注意链式法则）

$Q'(x)q(x)=\dfrac{1}{2}q(x)^{\frac{1}{2}}q'(x)=\dfrac{1}{2}Q(x)q'(x)$

那么设 $Q(x)=\sum\limits_{i=0}^{\inf} b_ix^i,Q'(x)=\sum\limits_{i=0}^{\inf}b_{i+1}(i+1)x^i$，然后因为 $q(x)=4x^2-12x+1$，所以 $q'(x)=8x-12$，也即是说：

$Q'(x)q(x)=\left(\sum\limits_{i=0}^{\inf}b_{i+1}(i+1)x^i\right)4x^2-12x+1$

$=\sum\limits_{i=0}^{\inf}b_{i+1}(i+1)x^i-12b_{i+1}(i+1)x^{i+1}+4b_{i+1}(i+1)x^{i+2}$

$=\sum\limits_{i=0}^{\inf}(b_{i+1}(i+1)-12b_{i}i+4b_{i-1}(i-1))x^i$（假设 $b_{-1}=0$）

$\dfrac{1}{2}Q(x)q'(x)=\dfrac{1}{2}\left(\sum\limits_{i=0}^{\inf}b_ix^i\right)8x-12$

$=\sum\limits_{i=0}^{\inf}4b_ix^{i+1}-6b_ix^i$

$=\sum\limits_{i=0}^{\inf}(4b_{i-1}-6b_i)x^i$（假设 $b_{-1}=0$）

$\because Q'(x)q(x)=\dfrac{1}{2}Q(x)q'(x)$

$\therefore \sum\limits_{i=0}^{\inf}(b_{i+1}(i+1)-12b_{i}i+4b_{i-1}(i-1))x^i=\sum\limits_{i=0}^{\inf}(4b_{i-1}-6b_i)x^i$

$\therefore b_{i+1}(i+1)-12b_{i}i+4b_{i-1}(i-1)=4b_{i-1}-6b_i$

解得 $b_{i+1}=\dfrac{(8-4i)b_{i-1}+(12i-6)b_i}{i+1}$，显然边界时 $b_0=1,b_1=-6$，那么我们就成功去掉了根号。

看回 $H=\dfrac{3-2x-\sqrt{4x^2-12x+1}}{2}$ 这条柿子，现在我们知道它等于 $\dfrac{3-2x-\sum\limits_{i=0}^{\inf} b_ix^i}{2}$，那么我们只需要将 $b$ 全部负过来，$b_0\to b_0+3$，$b_1\to b_1-2$，然后对所有 $b$ 除以 $2$，$b$ 就变成了 $h$，我们就求得了 $f$。