题解：CF2146F Bubble Sort

沉石鱼惊旋 · 2025-09-25 14:45:32 · 题解

F. Bubble Sort

首先，冒泡排序轮数，等价于 \max\limits_{i=1}^n\{\sum\limits_{j=1}^{i-1}[a_j\gt a_i]\}。

而对于排列，我们有一个很经典的生成双射的方式：枚举插入的位置 x，然后插入到 x 位置。显然有 1\times 2\times \dots\times n 个选法。

那么这里，等价于一个点插入的时候，身后有几个数。也就是第 i 项的值域为 [0,i-1] 的序列，要求 l\leq k\leq r 个位置满足前缀 \max 是 \leq x 的。

这个限制，我们可以转化成，要求在 l 时刻的前缀 \max 要 \leq x，然后在 r+1 时刻的前缀 \max 要 \gt x。

然后发现，我们可以对限制去 DP，对值域和下标都离散化一下。

转移的系数是形如：『[l,r] 的数，要求在 [0,i-1] 值域并且 \leq k 的方案数』，这个分类讨论一下是若干个阶乘、阶乘逆元和 x^y 乘起来的。

cpp 提交记录：https://codeforces.com/contest/2146/submission/339811170

py 提交记录：https://codeforces.com/contest/2146/submission/339811189

py 被卡常了，但是 wrk 写的过了，我这份看个乐子吧。