某岛

… : "…アッカリ～ン . .. . " .. .
May 6, 2023

HDU 5279. YJC plays Minecraft

题意

给定一张由 n 组有标号完全图形成的图，第 i 个完全图的结点数为 ai。这些完全图之间形成一个环，每个完全图中编号最大的点向下一个完全图编号最小的点连一条边。
问该图中生成森林的方案数。

分析

首先自然考虑完全图内部的情况，定义 f_n 表示 n 点的完全图的生成森林方案数，
类似处理连通图时的方法，我们枚举 i 表示 0 号点所在的连通块中还有其它多少个点，可得转移方程：

(1)   \begin{align*} f_n &= \sum\limits_{i=0}^{n-1} \binom{n-1}{i} (i+1)^{i-1} f_{n-1-i} \\ &= (n-1)!\sum_{i=0}^{n-1}\frac{f_i}{i!}\frac{(n-i)^{n-i-2}}{(n-i-1)!} \end{align*}

这里 (i+1)^{i-1} 是经典的完全图生成树公式。上式进一步展开后可以发现卷积形式，可用分治 NTT 求解。

再考虑完全图之间的情况，考虑容斥。显然不合法的情况，只有环上边全部存在，且所有完全图中首尾均连通。
设这种情况是 g_i，只要把首位连起来考虑即可，转移和上面几乎一样：

(2)   \begin{align*} g_n &= \sum\limits_{i=0}^{n-2} \binom{n-2}{i} (i+2)^{i} f_{n-2-i} \\ &= (n-2)!\sum_{i=0}^{n-2}\frac{f_i}{i!}\frac{(n-i)^{n-i-2}}{(n-i-2)!} \end{align*}

不用分治直接 NTT 就行了

Posted by xiaodao
Category: 日常

« | »

  • Archives

    open all | close all