Subpermutation

题意:

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

思路:

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

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

2. m的排列在连续的两个n排列中
假设一个排列为{p1,p2,...,pk1,pk,pk+1,...,pj,...,pnp_1,p_2,...,p_{k-1},p_k,p_{k+1}, ... ,p_j,...,p_n},满足pk<pk+1p_k<p_{k+1}[k+1,n][k+1,n]降序,且pjp_j 为最右侧>pkp_k的一个。
可以推出,该排列按字典序后一个排列为{p1,p2,...,pk1,pj,pn,pn1,...,pj+1,pk,pj1,...,pk+1p_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) iki+m1>n i≤k ,i+m-1>n

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

即为 (nm)![m!Cmni+1(mn+i1)!](n-m)![m!-C_m^{n-i+1}(m-n+i-1)!]

2)i>kn<i+m1<j+n i>k ,n<i+m-1<j+n

  • 这边我们可以证明,不存在 i+m1ji+m-1≥j 的情况。 (因为m排列中一定不包含pkp_k,且pj>pkp_j>p_k,所以m排列一定不能包含pjp_j
  • 可以发现,对于 [nm,n][n-m,n] 这些数的排列中,一定存在j,满足 pj<pj+1p_j<p_{j+1}。即一共有 (nm)!1(n-m)!-1 种。
  • 剩下 m 个数在后一个n排列中的排列有 [m(ni+1)]![m-(n-i+1)]! 种,则总共有Cmni+1[m(ni+1)]!C_m^{n-i+1}[m-(n-i+1)]! 种。

即为 [(nm)!1]Cmni+1[m(ni+1)]![(n-m)!-1]C_m^{n-i+1}[m-(n-i+1)]!

综合所有,化简可求出答案为 Σi=nm+2n(nm)!m!m!(ni+1)!\Sigma_{i=n-m+2}^n (n-m)!m!-\frac{m!}{(n-i+1)!}
换元 j=ni+1j=n-i+1
则答案为 Σj=1m1(nm)!m!m!j!\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);
    }
}

心得:

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