Subpermutation

题意：

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

思路：

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

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

2. m的排列在连续的两个n排列中
假设一个排列为{$p_1,p_2,\mathrm{.}\mathrm{.}\mathrm{.},p_{k-1},p_k,p_{k+1},\mathrm{.}\mathrm{.}\mathrm{.},p_j,\mathrm{.}\mathrm{.}\mathrm{.},p_{n}p\_1,p\_2,...,p\_\{k-1\},p\_k,p\_\{k+1\},\; ...\; ,p\_j,...,p\_n$}，满足，$[k+1,n][k+1,n]$降序，且$p_{j}p\_j$ 为最右侧＞$p_{k}p\_k$的一个。
可以推出，该排列按字典序后一个排列为{$p_1,p_2,\mathrm{.}\mathrm{.}\mathrm{.},p_{k-1},p_j,p_n,p_{n-1},\mathrm{.}\mathrm{.}\mathrm{.},p_{j+1},p_k,p_{j-1},\mathrm{.}\mathrm{.}\mathrm{.},p_{k+1}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\le k\mathrm{，}i+m-1>ni\le k\; ，i+m-1>n$

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

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

2）

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

综合所有，化简可求出答案为 ${\mathrm{\Sigma }}_{i=n-m+2}^n(n-m)!m!-\frac{m!}{(n-i+1)!}\backslash Sigma\_\{i=n-m+2\}^n\; (n-m)!m!-\backslash frac\{m!\}\{(n-i+1)!\}$
换元 $j=n-i+1j=n-i+1$
则答案为 ${\mathrm{\Sigma }}_{j=1}^{m-1}(n-m)!m!-\frac{m!}{j!}\backslash Sigma\_\{j=1\}^\{m-1\}\; (n-m)!m!-\backslash 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);
    }
}

心得：

第一次写复杂的排列组合，哇塞之余，总结一下做题思路，发现这类题就是分类讨论、逐层剥离问题，同时注意各个式子的性质，可以少走许多弯路，有大用！