题解：P14352 排序

题目大意

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

思路

冒泡排序性质

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

转化

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

公式推导

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; // 好习惯。
}