Description
一棵 \(n\) 个结点的树。初始时 \(a\) 和 \(b\) 是黑的，其他点是白的。
每次可以把某个黑点染成红的并把与它相邻的白点染成黑的。
问把结点染红的顺序有多少种。
\(1\leqslant a,b\leqslant n\leqslant234567\)
答案对 \(998244353\) 取模，时限 10s 。
Solution
首先我们来考虑只有一个起点的情况。我们以这个点为根，进行树形 DP 可得（ \(s_i\) 是 \(i\) 的子树大小）
\[\begin{aligned} f_i &= (s_i - 1)!\prod_{j\in son_i}\frac{f_j}{s_j!}\\ \frac{f_i}{s_i!} &= s_i\prod_{j\in son_i}\frac{f_j}{s_j!} \end{aligned}\]
可以发现整棵树的方案数就是 \(n!/(\prod_is_i)\) 。
考虑有两个起点 \(a\) 和 \(b\) 。可以看成新建了一个点 \(s\) ，其与 \(a,b\) 相连；最开始只有 \(s\) 是黑色的。这是一棵基环树。
我们拿出 \(a\) 到 \(b\) 路径上的所有点 \((s=v_{-1},)a=v_0,v_1,\dots,v_m=b(,v_{m+1}=s)\) 。
枚举这条路径上最后一个被染红的点 \(v_i\) 。它既可以看做从左边染过来的又可以看做从右边染过来的。
如果我们把它看做从左边染过来的，那么相当于我们把 \(v_i-v_{i+1}\) 这条边（如果存在的话）切断了。同理如果我们把它看做从右边染过来的，那么相当于把 \(v_{i-1}-v_i\) 这条边切断了。
也就是说，如果我们切断了 \(v_i-v_{i+1}\) 这条边，那么现在的方案对应了 \(v_i\) 最后一个染色的方案和 \(v_{i+1}\) 最后一个染色的方案。
那么枚举切断了哪一条边。这个时候基环树变成了一棵树，其答案是 \(n!/(\prod_is_i)\) 。把所有答案都加起来除以 2 ，就可以得到正确答案（因为每个方案都算了两遍）。
考虑如何计算每种方案的 \(\prod_is_i\) 。显然除了 \(a,b\) 之间路径上的点之外所有点的 \(s\) 都不会变化，所以只需要考虑 \(a,b\) 路径上的点，即 \(\prod_{i=0}^ms_{v_i}\) 。
令 \(b_i\) 表示 \(v_i\) 这个点除去 \(v_{i-1},v_{i+1}\) 之外的子树大小（就是挂在链上的子树大小），那么如果割去 \(v_j-v_{j+1}\) 的边，那么 \(v_i\) 的子树大小为 \(\sum_{k=j+1}^ib_k\quad(i>j)\) 或者 \(\sum_{k=i}^kb_k\quad(i<j)\) 。如果我们取 \(b\) 的前缀和 \(x\) ，那么这就对应了 \(|s_i-s_j|\) 。也就是说，我们需要对于每个 \(j\) 计算 \(\prod_{i\neq j}|x_i-x_j|=(-1)^{m-j}\prod_{i\neq j}(x_j-x_i)\) 。
而 \(\prod_{i\neq j}(x_j-x_i)=f(x_j)\) ，其中 \(f(x)=\sum_i\prod_{j\neq i}(x-x_j)=\frac{\mathrm{d}}{\mathrm{d}x}\left(\prod_i(x-x_i)\right)\) 可以分治 NTT 求得。于是套多项式多点求值模板即可，复杂度 \(O(n\log^2n)\) 。
Code
1 |
|