链接：http://codeforces.com/gym/101955/problem/C
题意：Q次询问，每次给出N，M，Mod，问你有多少种排列，满足前面M个数字排序之后整个序列的LIS>=N-1。
题解：前k个排序之后分四种情况讨论：
长度为N的排列的LIS为N-1的个数=(N-1)^2
1. 排序之后整个就有序了：k!
2. 排序之后前面是 1 到 k，后面最长上升子序列的长度是 n−k−1：k!⋅(n−k−1)^2。
3. 排序之后前 k 个数里有一个被换成了 k+1，被换的那个数可以插到后面里面去：k!⋅k(n−k)。
4. 排序之后前 k 个数里有一个（只能是 k）被换成了 k+2 以上的数，后面 n−k 个数必须有序：k!⋅(n−k−1)。
综上，答案就是 k!(1+(n−k−1)2+k(n−k)+(n−k−1))。
#include <bits/stdc++.h> using namespace std; int n, k, mod; long long fact[100]; void pre_fact() { fact[0]=1; for(int i=1; i<=55; i++) fact[i]=fact[i-1]*i%mod; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T, kase=0; for(cin>>T; T--; ) { cin>>n>>k>>mod; k=min(n, k); pre_fact(); long long ans=fact[k]*(1+(n-k-1)*(n-k-1)+k*(n-k)+n-k-1)%mod; printf("Case #%d: %I64d\n", ++kase, ans); } return 0; }
或者打表找规律：
打表代码：
#include <bits/stdc++.h> using namespace std; int a[100], b[100], dis[100]; int solve_lis(int n) { int res=1; for(int i=1; i<=n; i++) { dis[i]=1; for(int j=1; j<=i; j++) if(b[i]>b[j]){ dis[i]=max(dis[i], dis[j]+1); res=max(res, dis[i]); } } return res>=n-1; } int db(int n, int k) { int res=0; for(int i=1; i<=n; i++) a[i]=i; do{ for(int i=1; i<=n; i++) b[i]=a[i]; sort(b+1, b+1+k); res+=solve_lis(n); }while(next_permutation(a+1, a+1+n)); return res; } int main() { for(int n=1; n<=10; n++) { for(int k=1; k<=n; k++) printf("%d %d %d\n", n, k, db(n, k)); printf("\n"); } return 0; }
原文：https://www.cnblogs.com/Yokel062/p/11638141.html
