题解：AT_agc045_d [AGC045D] Lamps and Buttons

无名之雾 · 2025-12-13 22:05:05 · 题解

联训讲课的时候的题。讲课大神说他忘了他之前的做法，所以我尝试破译了一下。然后自己手推了一下得到了这么一个不伦不类的神秘做法。

solution

考虑一下 Snuke 应该怎么操作。显然，Snuke 的最优策略是直接贪心的按照 1, 2, \dots, A 的顺序，按亮着的灯。分析一下状态：

如果 P_i 指向一个熄灭的灯，该灯被点亮，Snuke 获得了新的操作机会。
如果 P_i 指向一个已亮的灯，且 P_i \neq i，状态反转，但通常不影响连通性。
如果 P_i = i 也就是存在自环，且此时灯 i 是亮着的，按下后灯 i 熄灭。由于 P_i=i，没有任何其他按钮指向 i，灯 i 将无法再亮。

Snuke 失败的唯一情况是：在所有初始熄灭的灯（集合 D = \{A+1, \dots, N\}）被点亮之前，Snuke 按下了一个自环按钮 k（1 \le k \le A）。

因此，我们可以将胜负条件形式化：设 k 为序列 1, \dots, A 中第一个满足 P_k = k 的下标。

若不存在这样的 k（即 1 \dots A 中无自环），设 k = A+1。
Snuke 获胜 \iff 集合 D 中的每一个元素，都在图上连通至集合 S = \{1, \dots, k-1\} 中的某点。
换言之，在排列的环分解中，不存在任何一个环，其所有元素均来自 D \cup \{k+1, \dots, A\}。

我们将问题转化为统计满足上述条件的排列 P 的数量。

对于枚举的第一个自环位置 k (1 \le k \le A+1)，我们将 1 \dots N 分为四个集合：

对于固定的 k，我们需要构造排列满足：

所有包含 D 中元素的环，都必须与 S 相交（即包含至少一个 S 中的元素）。

考虑上面的限制，只有所有环都与集合 S 相交这一限制有点麻烦，考虑以下引理：

引理：设 U 是一个大小为 n 的集合，指定其中 m 个元素组成子集 B (B \subset U, |B|=m)。

在 U 的所有排列中，使得每一个环都包含至少一个 B 中元素的排列总数为：
f(n, m) = m \times (n-1)!

:::success[证明]

考虑 U 中元素的圆排列。圆排列总数为 (n-1)!。

对于任意一个圆排列，我们通过断环成链或其他映射对应到线性排列的环分解。

该限制等价于：在圆排列中，所有的非 B 元素必须在 B 元素之后。

:::

我们需要计算满足以下条件的方案数：

枚举 R 中有 j 个元素加入覆盖范围：

选出 j 个元素：\binom{A-k}{j}
剩余 R 中元素任意排列：(A-k-j)!
对于覆盖点集的方案数，考虑容斥。总节点集 U = S \cup D \cup \{R_{j}\}，大小 L = (k-1) + (N-A) + j。
\sum_{i=0}^{k-1} (-1)^i \binom{k-1}{i} \times \text{Lemma}(U \setminus i, S \setminus i)
代入引理：
\sum_{i=0}^{k-1} (-1)^i \binom{k-1}{i} \times (k-1-i) \times (L - i - 1)! \tag {1}

把总的式子写出来就是：

\text{Ans}=\sum_{k=1}^{A} \sum_{j=0}^{A-k} \binom{A-k}{j} (A-k-j)! \times \left[ \sum_{i=0}^{k-1} (-1)^i \binom{k-1}{i} \cdot (k-1-i) \cdot (N - (A-k) + j - i - 2)! \right]

上面那个式子直接算上述公式复杂度是 O(A^3) 的。考虑优化。

观察 (1) 的结构，令 n = k-1，利用恒等式 (n-i)\binom{n}{i} = n\binom{n-1}{i}，得：

(1) = n \times \sum_{i=0}^{n-1} (-1)^i \binom{n-1}{i} \times ((N-A) + j + n - 1 - i)!

发挥一下贫瘠的注意力。发现式子 \sum_{i=0}^{m} (-1)^i \binom{m}{i} F(i) 本质上是函数 F 的 m 阶差分。

记 \Delta 为差分算子，\Delta F(x) = F(x) - F(x+1)。

根据差分性质：\Delta^m F(x) = \Delta^{m-1} F(x) - \Delta^{m-1} F(x+1)。

所以 (1) 我们直接递推就可以了。滚掉了一个求和符号。所以复杂度是 O(A^2) 的。

代码非常好写。submission。