题解：P14352 排序

bilibili_daogu · 2025-10-30 21:47:45 · 题解

题目大意

给定一个长度为 n 的排列 a，定义排序算法 A(k) 如下：

• 执行 k 轮操作，每轮从 i=1 到 n-1 依次检查，如果 a_i > a_{i+1} 则交换它们。

问有多少个排列在执行 A(k) 后会变成完全升序的，答案对 998244353 取模。

思路

冒泡排序性质

冒泡排序有一个重要性质：

• 第 1 轮结束后，最大的元素会移动到最后一个位置。
• 第 2 轮结束后，第二大的元素会移动到倒数第二个位置。
• ...
• 第 t 轮结束后，前 t 大的元素都在它们的最终位置上。

因此，执行 k 轮冒泡排序后，最大的 k 个元素（即 n, n-1, \dots, n-k+1）已经在它们的正确位置上。

转化

一个排列可以唯一地由其逆序表 (e_1, e_2, \dots, e_n) 表示，其中 e_i 表示在 a_i 右边且比 a_i 小的元素个数。

冒泡排序每轮每个元素最多左移一次，因此：

• 如果某个元素需要左移 d 次才能到达最终位置，那么至少需要 d 轮排序。
• 换句话说，如果 e_i > k，那么 k 轮后这个元素还没到达最终位置。

所以，排列在 k 轮冒泡排序后完全有序的充要条件是：对于所有 i，e_i \leq k。

公式推导

由于 e_i 的取值范围是 0 到 n-i，加上限制 e_i \leq k 后，e_i 的取值范围是 0 到 \min(k, n-i)。

令 m = \min(k, n-1)，我们可以分两种情况：

1. 当 k \geq n 时

   • 所有排列都能在 n-1 轮内排好序。
   • 答案就是 n!。

2. 当 k < n 时

   • 对于 i \leq n-k，n-i \geq k，所以 e_i 有 k+1 种取值。
   • 对于 i > n-k，n-i < k，所以 e_i 有 n-i+1 种取值。
   • 总方案数为： \text{ans} = (k+1)^{n-k} \times \prod_{j=1}^k (j+1) = (k+1)^{n-k} \times k!

最终公式

算法实现

• 如果 k \geq n，直接计算 n! \bmod 998244353（注意 n 不会太大，因为 k \leq 2\times 10^7）。
• 如果 k < n，计算 k! \bmod 998244353 和 (k+1)^{n-k} \bmod 998244353（用快速幂）。
• 注意取模运算。

复杂度分析

• 计算阶乘：O(k)。
• 快速幂：O(\log(n-k))。
• 总复杂度：O(k + \log n)，可以处理 n 高达 10^{18} 的情况。

代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

// 计算 a^b % MOD
long long qpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    long long n, k;
    cin >> n >> k;
    if (k >= n) {
        // k >= n 时，所有排列都能排好序。
        long long ans = 1;
        for (int i = 1; i <= n; i++) {
            ans = ans * i % MOD;
        }
        cout << ans << endl;
    } else {
        // k < n 时，答案为 (k+1)^(n-k) * k!。
        long long fact = 1;
        for (int i = 1; i <= k; i++) {
            fact = fact * i % MOD;
        }
        long long ans = fact * qpow(k + 1, n - k) % MOD;
        cout << ans << endl;
    }

    return 0; // 好习惯。
}