题目描述

计数。有多少个长度为 $n$ 的排列,使得可以通过栈排好序并且第 $ps$ 个位置是 $x$。
$n \leq 10^6$

题解

首先我们考虑反过来:变成问你 $1 \cdots n$ 的排列通过栈可以生成多少在 $ps$ 位置为 $x$ 的序列。
考虑将这个过程抽象成括号序列:长度为 2n 的括号序列,左括号表示入栈,右括号表示出栈。
那么我们实际上是为了计数长度为 $2n$ 的括号序列,满足第 $ps$ 个左括号和第 $x$ 个右括号是配对在一起的。我们可以枚举左括号在哪里,就可以唯一确定右括号在哪里。分成了三个不同的括号序列都用卡特兰数算一算就好了。
大概是长得这样:
.......(.......).......
首先 ( 和 ) 之间的左右括号数一定相等(也就是保证这两个括号匹配上)
我们枚举 ( 的位置是 $l$,可以轻易算出。(可以看代码)

/*
 * Author: RainAir
 * Time: 2019-11-01 21:53:24
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 4e6 + 5;
const int ha = 1e9 + 7;
int fac[MAXN],inv[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void prework(){
    fac[0] = 1;
    FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    if(n < m) return 0;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

inline int F(int n,int m){
    if(n < m) return 0;
    if(n < 0 || m < 0) return 0;
    return (C(n+m,n)+ha-C(n+m,n+1))%ha;
}

int ans = 0;
int n,ps,x;

int main(){
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    scanf("%d%d%d",&n,&ps,&x);
    prework();
    FOR(l,1,2*n){
        (ans += 1ll*F(ps-1,l-ps)*F(ps+x-l-1,ps+x-l-1)%ha*F(n-x,n-2*ps-x+l+1)%ha) %= ha;
    }
    printf("%d\n",ans);
    return 0;
}

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏