Subpermutation

https://ac.nowcoder.com/acm/contest/21791/J

Subpermutation

题意：

将 n 的所有排列按字典序连接成一个新的序列，求在该序列中有多少连续子序列是 m 的排列。(1≤m≤n) (mod 1e9+7)

思路：

很明显，m的排列要么出现在一个n的排列中，要么出现在连续的两个n排列中。分类讨论。

1. m的排列在一个n的排列中
1 至 m 的排列有 $m!$ 种；
将 1 至 m 视为一体，与剩余 $n - m$ 个数排列有 $(n - m + 1)!$ 种。
共计为 $m! (n - m + 1)!$ 种

2. m的排列在连续的两个n排列中
假设一个排列为{ $p_1,p_2,...,p_{k-1},p_k,p_{k+1}, ... ,p_j,...,p_n$ }，满足 $p_k<p_{k+1}$ ， $[k + 1, n]$ 降序，且 $p_{j}$ 为最右侧＞ $p_{k}$ 的一个。
可以推出，该排列按字典序后一个排列为{ $p_1,p_2,...,p_{k-1},p_j,p_n,p_{n-1},... ,p_{j+1},p_k,p_{j-1},...,p_{k+1}$ }。
通俗的讲，排列A的后一个排列B，满足，排列B是将排列A最右侧的降序段翻转，同时交换排列A降序段的前一个数 k 与降序段中最右侧大于 k 的数得到的。

我们可以根据 k 的位置进行分类讨论。设 m 的排列起始点为 i。

1） $i \leq k ， i + m - 1 > n i≤k ，i+m-1>n$

则必须满足前一个n排列在 $[i, n - 1]$ 中存在 j，满足 $p_j<p_{j+1}$ 。
对于 $[n - m, n]$ 这些数有 $(n - m)!$ 种排列；
剩下 m 个数的排列有 $m!$ 种，同时减去前一个n排列 $[i, n]$ 是降序的种类数，为 $C_m^{n-i+1}[m-(n-i+1)]!$ 种。

即为 $(n-m)![m!-C_m^{n-i+1}(m-n+i-1)!]$ ①

2） $i > k ， n < i + m - 1 < j + n$

这边我们可以证明，不存在 $i + m - 1 \geq j i+m-1≥j$ 的情况。（因为m排列中一定不包含 $p_{k}$ ，且 $p_{j} > p_{k}$ ，所以m排列一定不能包含 $p_{j}$ ）
可以发现，对于 $[n - m, n]$ 这些数的排列中，一定存在j，满足 $p_j<p_{j+1}$ 。即一共有 $(n - m)! - 1$ 种。
剩下 m 个数在后一个n排列中的排列有 $[m - (n - i + 1)]!$ 种，则总共有 $C_m^{n-i+1}[m-(n-i+1)]!$ 种。

即为 $[(n-m)!-1]C_m^{n-i+1}[m-(n-i+1)]!$ ②

综合所有，化简可求出答案为 $\Sigma_{i=n-m+2}^n (n-m)!m!-\frac{m!}{(n-i+1)!}$
换元 $j = n - i + 1$
则答案为 $\Sigma_{j=1}^{m-1} (n-m)!m!-\frac{m!}{j!}$
预处理求解即可。

代码：

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10;
const double pi=acos(-1);
ll mod=1e9+7,mmod=mod-1;
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
int a[N],dp[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char mapp,zz[5];
struct qq{ll x,y,z;}q;
struct tree{ll l,r,taga,tagb,suma,sumb;}trs;
struct Tree{ll fa,dep,dfn,siz,son,top,w;};
struct Trp{ll l,r,fat,dep,n,w;}trp;
struct E{ll to,nxt,w;}eg;
struct matrix{ll n,m[M][M];};

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<int>v[N],vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

ll fac[N];
void init(ll m){//dp预处理m!/j!的和
    fac[0]=1;fac[1]=1;dp[1]=0;
    L(i,2,m){ 
        fac[i]=fac[i-1]*i%mod;
        dp[i]=(dp[i-1]*i%mod+i)%mod;
    }
}

int main(){
    scanf("%lld",&t);
    init(1e6);
    while(t--){
        scanf("%lld%lld",&n,&m);
        k=((m-1)*fac[n-m]%mod*fac[m]%mod-dp[m]+mod)%mod;
        ans=(fac[m]*fac[n-m+1]%mod+k)%mod;
        printf("%lld\n",ans);
    }
}