题解：AT_abc470_f [ABC470F] Googol Swaps

· · 题解

前置知识（这些我都没学过，写得多请见谅）：

我们考虑一个排列 p，她的逆序对数量为 inv。

接下来对 p 进行邻项交换，交换次数为 cnt_1。

交换任意相邻两项，inv \mod 2 的值必然改变，与此同时，cnt_1 \mod 2 的值也会改变。

所以我们知道 inv \equiv cnt_1 \pmod 2。

那么考虑交换任意两项 (p_u, p_v)，我们设从 [1,2,...,n] 开始，交换任意两项的次数为 cnt，我们考虑 inv，cnt 的变化。

显然 p[u...v] 的逆序对数量奇偶并没有发生变化（贡献法），p[1...u - 1] 和 p[v + 1...n] 的数量没有变。

加上 (p_u,p_v) 这一对逆序状况的改变，那么 inv \mod 2 一定会变，因此 cnt_1 \mod 2 也变了。同时，cnt \leftarrow cnt + 1，所以 cnt \equiv cnt_1 \equiv inv \pmod 2。

经过上述推导，我们有：

接下来考虑解决问题：

我们不妨建图，连接每一条 (a_i, b_i) 的双向边。

弱化问题，恰好 10^{100} 次操作 \to 任意次操作。这种情况下，每一个连通分量里的字母可以任意排列。因此设这个连通分量大小为 s，字符 i 出现的次数为 cnt_i，则这个连通分量里的情况数就是 \frac{s!}{\prod_{i} cnt_i!}，我们把这些字符串集叫 T。

考虑恰好 10^{100} 次操作的情况。由于操作数实在太多了，而当我们达成某个字符串之后，可以不断通过进行偶数次同一条边的操作使字符串保持不变。因此这个东西对我们的约束，其实就是总操作次数为偶数。

我们对每个连通分量分别考虑它的置换 p，这个 p 其实就是我们上述的，由 [1,2,...,n] 不断交换得来的排列：进行一条边的交换，其实就是 p 上任意两项进行交换。

那么如果一个连通分量内有两个相同的字母 a_{p_u}，a_{p_v}，那么直接交换 p_u,p_v，字符串不变，但是排列的奇偶性，也就是总操作数的奇偶性可以发生变化。因此，我们可以用这两个字母调整操作次数的奇偶性，那么所有 T 中的字符串都可以达到。

如果没有连通分量满足有两个一样的字母，那么一定有一半的情况是无法达到的，答案为 \frac{|T|}{2}。要想到这点有点难，但是样例有提示。