题意
求n的全排列中将前k个数排序后最长公共子序列>=n-1的个数
思考
我们先把最后可能产生的结果找出来，再找有多少种排列能构成这些结果
设排列为s
- S like 1,2,3,...,n , 个数=1
- S like 1,2,3, ... i-1, j, i, ... j-1, j+1, ...n
- 当j<=k时不存在
- 当j>k时， 个数= (j-1)-k+1=j-k
- 综上，个数=\(\Sigma_{j=k+1}^{n}j-k\)
- S like 1,2,3,...i-1, i+1, ..j,i,j+1..n
- 当j<=k时，个数=n-(k+1)+1=n-k
- 当j>k时， 个数= n-(j+1)+1=n-j
- 综上， 个数=\(k(n-k)+\Sigma_{j=k+1}^{n}n-j\)
- 但是 S like 1,2,3,...,i+1,i,...被重复计算了，个数=n-(k+1)+1=n-k
- 综上，结果数=1+k(n-k)+(n-k)^2-(n-k)=1+(n-1)(n-k)
又因为对于每种结果可以由k!个排列构成
所以最后答案是 [1+(n-1)(n-k)]k! , k<=n
ICPC 沈阳 Problem C
原文：https://www.cnblogs.com/Merodach/p/9829344.html
