题解：P17394 [ICPC 2018 Shenyang R] Insertion Sort

tuntunQwQ · 2026-09-25 12:23:03 · 题解

神秘原题大赛 T1，赛时瞪眼找的规律，现在证明一下。

一个排列的最长上升子序列长度至少为 (n-1)，相当于从 1,2,3,\dots,n 中选出至多一个数插到别的位置，其他数相对位置不变所构成的排列。下文中，我们称这个数为错位数。

考虑固定 k，计算 n 变化带来的贡献。

• 当 n=k 时，显然这 k 个元素最终会从小到大排列，原始排列可以随便放，答案就是 k!。
• 当 n=k+1 时，我们可以把新加入的 k+1 放到排列末尾，方案数与 n=k 的答案一致为 k!；也可以从前 k 个元素中选出一个错位数插到末尾，k+1 则被挤入前 k 个位置参与排序操作，方案数为 k!\times k。总的答案就是 k!+(k!\times k)。
• 当 n=k+2 时，我们还是可以把新加入的 k+2 放到排列末尾，方案数与 n=k+1 一致为 k!+k!\times k；也可以从前 k+1 个元素中选出一个错位数插到末尾，k+2 则被推入 k+1 的位置，方案数为 k!\times (k+1)；我们发现，前面的两种情况都不能让 k+2 进入前 k 个位置，如果我们把 k+2 插到前 k 个位置当作错位数，就又多了 k! 个方案。总的答案就是 k!+k!\times k+(k!\times k+2k!)。
• 当 n=k+3 时，除了把 k+3 放在末尾，也可以把前 k+2 个元素中选出一个错位数插到末尾，k+3 则被推入 k+2 的位置，方案数为 k!\times (k+2)；也可以把 k+3 插在 k+1 的位置上当作错位数，方案数为 k!；同理，把 k+3 插到前 k 个位置当作错位数，方案数也是 k!。总的答案就是 k!+k!\times k+k!\times k+2k!+(k!\times k+4k!)。
• 当 n=k+i 时，我们的答案就是 n=k+i-1 的答案加上 \bigl(k! \times (k+i-1) + k! \times (i-1)\bigr)，i 每增加 1，这个值就增加 2k!。

综上所述，每次我们求一遍阶乘，递推记录上一个答案与偏移量即可，时间复杂度 O(Tn)。代码如下，可供参考：

#include<bits/stdc++.h>
using namespace std;
int T,n,k,q,fac;
int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>n>>k>>q;
        k=min(n,k),fac=1;
        for(int i=1;i<=k;i++)fac=1ll*fac*i%q;
        int ans=fac,del=1ll*fac*k%q;
        for(int i=k+1;i<=n;i++)ans=(ans+del)%q,del=(del+2*fac%q)%q;
        cout<<"Case #"<<t<<": "<<ans<<'\n';
    }
    return 0;
}