题解：P11802 【MX-X9-T6】『GROI-R3』Graph

george0929 · 2025-11-11 23:06:33 · 题解

模拟赛赛时认为 \gcd 必须等于 1，爆零了/ll。

看来考试时要把发现结论的依据写一写（周期结论）。

首先由题意，G 上任意一个点能走到他自己，因此 G 是若干环的并。

得到 \gcd=1 的错误结论是由于周期结论的直觉，让我们仔细想想这个结论能带给我们什么信息。

对于 G 上一个长为 len 的环，我们从一个点出发，每次走 k 步，能得到 \gcd(k,len) 个长为 \frac{len}{\gcd(k,len)} 的环。

因此，我们还可以选择把若干个相同长度的环在 G 中拼在一起。

具体地，用若干个长度为 i 的环拼成长为 i\times t 的大环，则有：

因此，设 cntloop_i 表示环长为 i 的环数，找到最小的 t 使得 \gcd(\frac{k}{t},i)=1，则 t|cntloop_i。这个条件是充要的。

考虑计数 DP。

按链 id DP要记录每个环长的 cnt，不可接受。

因此考虑按需要记录的值 DP，这样的好处是我们可以在进行 i\to i+1 的转移时顺便判断 i 是否合法。

令 f_{i,j,k} 表示当前处理长度 i，长度为 i 的链有 j 个，有 k 个剩余孤点（记录长度 \leq j 的链个数不容易保证不重不漏，因此选择 = 的定义）。

有一个技巧：我们可以把没有闭合的链各加上一个孤点，以保证 i 增加时链长 =i 的定义。

然而 w 个孤点在环上的贡献为 w!，这要求了我们不能实时计算这个贡献，只能在最后计算。

具体地，我们在转移时不区分孤点，最后乘上孤点个数的阶乘，根据组合意义，这个方法在不存在全是孤点组成的环时正确。

在孤点成环时，我们发现是阶乘和圆排列的区别。

具体地，对于一个 x，设长为 x 的全孤点环为 y 个，则我们多算了 x^y y! 倍，因为我们要：

• 除掉圆排列的循环。
• 当孤点都相同时，这些环没有顺序之分，除掉【最后乘上孤点个数的阶乘】对这些环顺序的错误贡献。

我们尝试用分步的思想来推导 DP 转移方程。

• 加入原图上的长为 i 的链，这一步是模拟题意。f_{i,j,k}\to f'_{i,j+cntlink_i,k}（cntlink_i 指原图上长为 i 的链个数）。

• 求出最小的 t 使得 \gcd(\frac{k}{t},i)=1，加入一些环，满足长为 i 的总环数是 t 的倍数，形成环有如下两种方式：

  • 选出若干孤点构成环。
  • 将已有的链闭合形成环。

  即枚举 c,l，\frac{f'_{i,j,k}\binom{j}{l}}{i^c c!}\to f''_{i,j-l,k-ic}，转移条件是 (cntloop_i+l+c)\bmod t=0。

• 把没有闭合的链加上一个孤点，f''_{i,j,k}\to f_{i+1,j,k-j}。

记孤点个数为 cnt1，答案即为 f_{n+1,0,0}\times cnt1!。

分析复杂度，有 ij\leq n,ic\leq k\leq n,l\leq j。