AT_agc054_c 题解

BINYU · 2023-10-16 21:22:38 · 题解

题意

给定 k 和一个排列 P'，问有多少个排列 P 以最少步数交换相邻两个元素来进行收敛，最终的排列可能是 P'，一个排列是收敛的当且仅当对于每一个数，在该数前且比这个数大的数的个数不超过 k 个。

思路

考虑正向的让一个排列收敛，我们设在第 i 个位置前且比 P_i 大的数有 cnt_i 个，最终收敛的条件为 \max\{cnt_1,cnt_2,\dots,cnt_n\} \le k。

考虑一次交换中 cnt 数组的变化，由于在 [1,i-1] 区间的贡献对于 i 和 i+1 是可以直接交换的，我们只需要考虑 P_i 对 P_{i+1} 的贡献即可：

我们肯定不会对第二种情况进行交换，而对于第一种情况，我们也只会对原来 cnt_{i+1}>k 的位置进行交换，进一步考虑，发现第一种情况等价于 cnt_i < cnt_{i+1}，故交换的条件为：cnt_i < cnt_{i+1} 且 cnt_{i+1}>k。

接下来考虑从 P' 反着交换回 P 的情况，相当于前面的逆运算，我们设在第 i 个位置前且比 P_i 大的数有 cnt'_ i 个，则交换的条件为 cnt'_ i + 1 > cnt'_ {i+1} 且 cnt'_ i + 1 > k，又因为 P' 一定是已经收敛的数组，所以 cnt'_ i 一定不大于 k，故条件可进一步简化为 cnt'_ i = k。

每次交换相当于把这个数往后挪一位并加一，所以我们从后往前算方案数更方便。

对于最后一个满足 cnt'_ i = k 的 i ，它往后挪多少位都是可以的，而对于前面的，在它挪到上一个 cnt'_ i = k 现在所在的位置之前，显然也是可以的，而因为挪的过程中它会自增 1，所以前面来的数一定不会小于后面的数，所以在此时交换也是合法的。综上，对于每一个满足 cnt'_ i = k 的 i，都能随意往后挪动，至多可以挪动 n - i 次，故一共有 n - i + 1 中选择，所以答案为 \prod\limits_{cnt'_ i=k}(n-i+1)。

对于求 cnt'_ i，直接遍历是 O(n^2) 的，使用树状数组是 O(n\log n) 的，都可以通过本题（应该没人会在这里写分块啥的吧）。