Insertion Sort

标签： 数学

---

题目描述

戳这里

题解

首先我们可以分$LIS$为$n$和$n-1$两种情况。
对于$LIS$为$n$的情况很简单，只能将$1-k$放在前$k$个位置，答案为${A_{k}}^{k}$
现在我们来讨论$LIS$为$n-1$的情况。我们可以考虑枚举放在前$k$个位置中的最大值$maxn$
1.当$maxn=k$时，那么后$n-k$必须有一个错位，即有一个数不在原来的位置（emmm可以理解为相对位置），通过手画找规律发现这样的方案数为$(n-k-1)^2$
2.当$maxn=k+1$时，那么剩下$k-1$个位置有${C_{k+1}}^{k}=k-1$种选法且多出来的那个在后面有$n-k$种插入方式。即方案数为$k*(n-k)$
3.当$maxn>k+1$时，此时$k-1$的位置只能选$1,2,3…k-1$且后面全部有序，方案数为$n-k-1$
综上所述
$Ans = {A_{k}}^{k}+{A_{k}}^{k}(k(n-k)+(n-k-1)+(n-k-1)^2)$

代码

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

ll t, n, k, p;

int main()
{
    scanf("%lld", &t);
    ll cnt = 0;
    while(t --)
    {
        scanf("%lld%lld%lld", &n, &k, &p);
        ll fac = 1;
        k = min(k, n);
        for(int i = 1; i <= k; i ++)
            fac = fac * i % p;
        ll ans = (fac * k % p) * (n - k) + ((n - k - 1) * fac % p);
        ans = ans + fac + (fac * (n - k - 1) % p) * (n - k - 1) % p;
        ans %= p;
        printf("Case #%lld: %lld\n", ++ cnt, ans);
    }
    return 0;
}