专栏文章

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

违违规用户名1010570
P9823题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioigal9
此快照首次捕获于
2025/12/02 19:44
3 个月前
此快照最后确认于
2025/12/02 19:44
3 个月前
查看原文

关键观察

特殊情况分析：当 k≥nk ≥ n 时，不存在满足 k<i≤nk < i ≤ n 的 ii（因为 ii 最大为 nn ），所以所有 1∼n1∼n 的排列都是好排列。此时答案为 n!n!（ nn 的阶乘）。
最小值位置限制：对于 k<nk < n 的情况，排列中的最小值 11 必须位于前 kk 个位置。这是因为： 如果 11 位于位置 pp 且 p>kp > k，考虑 i=pi = p（此时 i>ki > k ） 根据定义，ai=1a_i = 1 必须大于前 kk 个元素的最小值 但前 kk 个元素都大于 11（因为 11 在位置 pp ），它们的最小值 ≥2≥2 这导致 1>1 > 最小值不成立，与好排列定义矛盾 。

动态规划设计

定义状态:
设 dp[i]dp [i] 表示长度为 ii 的好排列数与 i!i! 的比值，即： dp[i]dp [i] = f(i)/i!f (i) /i! ，其中 f(i)f (i) 是长度为 ii 的好排列总数 。
这样定义的好处是可以简化递推关系，避免直接处理阶乘带来的大数问题 。
基础情况：
当 i≤ki ≤ k 时，所有排列都是好排列（因为没有 i>ki > k 需要满足），所以 f(i)=i!f (i) = i!，因此 dp[i]=1dp [i] = 1 。
递推公式：
对于i>ki > k，有： dp[i]=(∑i−ki−1dp[j])/idp [i]=(\sum_{i-k}^{i-1}dp[j])/i 。
推导过程：
f(i)=(i−1)!×∑i−ki−1dp[j]f(i)=(i-1)!×\sum_{i-k}^{i-1}dp[j] 两边除以 i!i!（即 i×(i−1)!i×(i-1)! ）。
得到：dp[i]=(∑i−ki−1dp[j])/idp [i]=(\sum_{i-k}^{i-1}dp[j])/i 。
滑动窗口优化：
为了高效计算 ∑(dp[j])\sum (dp [j])，我们使用滑动窗口维护最近 k 个 dpdp 值的和，每次计算新的 dp[i]dp [i] 后，窗口向前移动一位（加入新值，移除过期值）。
时间复杂度与空间复杂度：
时间复杂度：O(n)O (n)，主要是预处理和一次线性遍历 。
空间复杂度：O(n)O (n)，需要存储 dpdp 数组和逆元数组 。

代码实现详解

CPP
#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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...