题解：P13037 [GCJ 2021 #2] Hidden Pancakes

· · 题解

首先这道题一眼排列计数。

然后考虑最大的煎饼所在位置。

不难发现最大的煎饼就是在最右边的 1 的位置。

感性证明一下，最大的煎饼覆盖完之后肯定是 1 而且不能在被覆盖，也就是后面都会 +1 所以后面的至少为 2。

所以以最大的煎饼为分界点，将序列分成两段，对右半段 -1 以去除影响，最后递归解决

一次划分对答案的贡献为 \binom{N}{K} 其中 N 是整个序列的长度（不包括最大煎饼），K 是划分出的一段的长度，可以这样理解，因为整个序列被分成了不相关的两段，而我们只在乎煎饼的相对大小，所以要选 K 个煎饼放在其中一段中。

所以共有 \binom{N}{K} 种方案。

找最大的煎饼也就是找区间最右边的 1，使用线段树维护。

时间复杂度约为 \mathcal{O}(n\log^2(n))

实现时，维护最小值可以不对右半段 -1，因为相对大小不变。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+20,mod=1e9+7;

int qpow(int a,int b,int md){
    if(a==0)return 0;
    int ans=1;
    while(1){
        if(b==0)break; 
        if(b&1)ans=(ans*a)%md;
        a=a*a%md;
        b>>=1;
    }
    return ans;
}
int fc[N+10],infc[N+10]; 

int C(int n,int m){
    return fc[n]%mod*infc[m]%mod*infc[n-m]%mod;
}
void init(){
    fc[0]=infc[0]=1;
    for(int i=1;i<=N;i++)
        fc[i]=fc[i-1]*i%mod,
        infc[i]=qpow(fc[i],mod-2,mod)%mod;
}

int n;
int wh[N*4],a[N];
#define mid ((l+r)>>1)
void build(int p,int l,int r){
    if(l==r){wh[p]=l;return;}
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    if(a[wh[p*2]]<a[wh[p*2+1]])wh[p]=wh[p*2];
    else wh[p]=wh[p*2+1];//右边优先
}
void clear__(int p,int l,int r){
    if(l==r){wh[p]=0;return;}
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    wh[p]=0;
}
int ask(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R){return wh[p];}
    int ans1=0,ans2=0;
    if(L<=mid)ans1=ask(p*2,l,mid,L,R);
    if(mid+1<=R)ans2=ask(p*2+1,mid+1,r,L,R);
    if(ans1==0||ans2==0)return ans1+ans2;
    if(a[ans1]<a[ans2])return ans1;
    return ans2;
}
int ans=1;
void f(int l,int r){
    if(l>=r)return;
    int w=ask(1,1,n,l,r);
    f(l,w-1);
    f(w+1,r);
    ans=(ans*C(r-l,w-l))%mod;
}
int one(){
    ans=1;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        if(a[i]-a[i-1]>1||a[i]>i)ans=0;
    }
    if(ans==0)return 0;
    build(1,1,n);
    f(1,n);
    return ans;
}
signed main(){
    init();
    int T;
    scanf("%lld",&T);
    for(int i=1;i<=T;i++){
        printf("Case #%lld: %lld\n",i,one());
    }
    return 0;
}