题解：P9823 [ICPC 2020 Shanghai R] The Journey of Geor Autumn

· · 题解

关键观察

特殊情况分析：当 k ≥ n 时，不存在满足 k < i ≤ n 的 i（因为 i 最大为 n ），所以所有 1∼n 的排列都是好排列。此时答案为 n!（ n 的阶乘）。

最小值位置限制：对于 k < n 的情况，排列中的最小值 1 必须位于前 k 个位置。这是因为： 如果 1 位于位置 p 且 p > k，考虑 i = p（此时 i > k ） 根据定义，a_i = 1 必须大于前 k 个元素的最小值 但前 k 个元素都大于 1（因为 1 在位置 p ），它们的最小值 ≥2 这导致 1 > 最小值不成立，与好排列定义矛盾 。

动态规划设计

定义状态:\ 设 dp [i] 表示长度为 i 的好排列数与 i! 的比值，即：

这样定义的好处是可以简化递推关系，避免直接处理阶乘带来的大数问题 。 **基础情况**：\ 当 $i ≤ k$ 时，所有排列都是好排列（因为没有 $i > k$ 需要满足），所以 $f (i) = i!$，因此 $dp [i] = 1$ 。 **递推公式**：\ 对于$i > k$，有： $dp [i]=(\sum_{i-k}^{i-1}dp[j])/i$ 。 **推导过程**：\ $f(i)=(i-1)!×\sum_{i-k}^{i-1}dp[j]

两边除以 i!（即 i×(i-1)! ）。\ 得到：dp [i]=(\sum_{i-k}^{i-1}dp[j])/i 。

滑动窗口优化：\ 为了高效计算 \sum (dp [j])，我们使用滑动窗口维护最近 k 个 dp 值的和，每次计算新的 dp [i] 后，窗口向前移动一位（加入新值，移除过期值）。

时间复杂度与空间复杂度：\ 时间复杂度：O (n)，主要是预处理和一次线性遍历 。\ 空间复杂度：O (n)，需要存储 dp 数组和逆元数组 。

代码实现详解

#include<bits/stdc++.h>
#define int long long
#define modd 998244353
using namespace std;
int n,k,t;
int dp[10000005];// dp[i] = f(i)/i!
int inv[10000005];// 逆元数组，用于计算除法
signed main(){
    cin>>n>>k;
    t=1;
    inv[1]=1;
    // 预处理阶乘t = n! 和逆元inv[i]
    for(int i=2;i<=n;i++){
        t=t*i%modd;  // 计算阶乘n!
        // 线性求逆元：inv[i] = modd - modd/i * inv[modd%i] % modd
        inv[i]=modd-modd/i*inv[modd%i]%modd;
    }
    // 特殊情况：k >= n时，所有排列都是好排列
    if(k>=n){
        cout<<t;
        return 0;
    }
    // 初始化：i <= k时，dp[i] = 1
    for(int i=0;i<=k;i++){
        dp[i]=1;
    }
    // sum维护最近k个dp值的和，初始为dp[1]+dp[2]+...+dp[k] = k
    int sum=k;
    for(int i=k+1;i<=n;i++){
        // dp[i] = sum / i，用逆元实现除法
        dp[i]=sum*inv[i]%modd;
        // 滑动窗口更新：加入新元素dp[i]，移除过期元素dp[i-k]
        sum=(sum+dp[i]-dp[i-k]+modd)%modd;
    }
    // 最终答案为f(n) = dp[n] * n!
    int ans=dp[n]*t%modd;
    cout<<ans;
    return 0;
}
//For The Greater Good