P10547 [THUPC 2024 决赛] 排列游戏

太非人类了。

首先想如果给定一个排列如何简单的判断合法，再困难的计数题如果连这个都不可以简单计数那就完犊子了。

经典结论是交换距离为 \(\sum [p_i > i](p_i - i) \le m\)，容易证明充分性，必要性可以感性理解，主要就是任意一对元素的交换距离之和。

你还发现一个事情就是必须要经过 \(n\) 次操作后得到这个排列，这非常不好，我们也要去刻画这个东西。这一步相对比较简单，经典结论是交换两个位置会改变置换环个数奇偶性，那么充要条件便是排列置换环个数为奇数。

考虑从置换环的角度设计整个 DP，就是给置换环赋权，将一整个置换环断环为链，假设是 \(p_1 \to p_2 \to ... \to p_k\)，那么可以将贡献简单的记为所有上升边的贡献，最后那条边的贡献可以简单记录。

因此我们设计 DP 状态 \(f_{i, j, k, 0/1}\) 为填入 \(1 \sim i\)，共有 \(j\) 条链，记录链上贡献为 \(k\)，目前置换环个数奇偶性为奇/偶的方案数。

转移比较复杂，综合来说这是一道思维和套路都比较强的题目，我在 NOIP 考场上不一定能够做到第二步。