日记

Mon Jun 30 2025

2 分钟

422 字

今天纯被自己唐到了。

我们枚举 $st$ ，并钦定只有 $[1,st]$ 之间的点能被算进环里。因为这样好算不会算重。然后就是一个简单状压了。

考虑正难则反。我们考虑至少有一对互质和至少有一对不互质的。我们枚举 $a_i$ 。然后求有 $cnt1$ 个与 $a_i$ 互质，有 $cnt2$ 个与 $a_i$ 不互质。两两搭配就是 $cnt1 \times cnt2$ 个，将其加入答案。

我们发现这玩意还算重了。经过一番严密的推理，我们发现每个都被算了两次。除以 $2$ 就是了。

首先有显然的结论：必须每行或者每列都有棋子合法。每行有和每列有可以通过旋转转化，这里只考虑每行有，到时候 $\times 2$ 就是了。

我们设有 $m$ 列有棋子，那么会有 $n - m$ 列相互攻击。可得 $m = n - k$ 。题意变成了把 $n$ 个相同的棋子分配到 $n - k$ 个不同的非空集合的方案数。我们直接大力容斥，钦定有 $i$ 个集合是空的。答案就是

\binom{n}{n - k} \times \sum_{i = 0}^{n - k}(-1)^i\binom{n - k}{i}(n - k - i)^n

记得在 $k$ 非零的时候乘 $2$ 。

今天被自己的高超期望技术恶心到了。于是去做了几道期望题。