传送门

这个题要用到一个Hook length定理,这个定理是专门用来求这一类填数问题的方案数的。有了这个定理之后就好做了。我们考虑第$i$行,这一行每个元素的hook length就是一个递减数列中间删掉一些数,我们可以通过一个卷积来算出少了哪些数。这样就能求出所有hook length的乘积,然后直接套用Hook length定理就行了。

#include <bits/stdc++.h>
#define MAXN 4200000
#define LL long long
using namespace std;

const int MAXW=2097152;
const LL P=1004535809,G=3;

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

int n,m,len,sizew;
int p[MAXN];
LL fac[MAXN],invfac[MAXN],w[MAXN];
LL t1[MAXN],t2[MAXN];
LL a[MAXN],b[MAXN];

void FFT(LL *a,int len,int flag){
    static int rev[MAXN],revlen;
    if(revlen!=len){
        revlen=len;
        for(int i=1;i<len;i++) rev[i]=rev[i>>1]>>1|((i&1)?(len>>1):0);
    }
    for(int i=0;i<len;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int l=2;l<=len;l<<=1){
        int l2=l>>1;
        for(int i=0;i<len;i+=l){
            for(int j=0;j<l2;j++){
                LL t1=a[i+j],t2=a[i+j+l2]*w[MAXW/l*j];
                a[i+j]=(t1+t2)%P;
                a[i+j+l2]=(t1-t2)%P;
            }
        }
    }
    if(flag==-1){
        LL invn=getPow(len,P-2);
        for(int i=0;i<len;i++) a[i]=a[i]*invn%P;
        for(int i=1;i<len;i++) if(i<len-i) swap(a[i],a[len-i]);
    }
}

int main(){
#ifdef DEBUG
    freopen("124.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",p+i);
        if(p[i]>m) m=p[i];
    }
    len=(n+m)*2;
    for(sizew=1;sizew<=len;sizew<<=1);
    fac[0]=1;
    for(int i=1;i<=len;i++) fac[i]=fac[i-1]*i%P;
    invfac[len]=getPow(fac[len],P-2);
    for(int i=len-1;i>=0;i--) invfac[i]=invfac[i+1]*(i+1)%P;
    w[1]=getPow(G,(P-1)/MAXW);
    w[0]=1;
    for(int i=2;i<MAXW;i++) w[i]=w[i-1]*w[1]%P;
    for(int i=1;i<=n;i++) t1[(p[i]-i+sizew)%sizew]++;
    for(int i=1;i<n;i++)
        t2[(i+1-(p[i+1]+1)+sizew)%sizew]++;
    FFT(t1,sizew,1); FFT(t2,sizew,1);
    for(int i=0;i<sizew;i++) t1[i]=t1[i]*t2[i]%P;
    FFT(t1,sizew,-1);
    LL ans=1;
    int last=n;
    for(int i=n;i>=1;i--){
        ans=ans*fac[p[i]+n-i]%P;//*invfac[last-i]%P;
        if(p[i]!=p[i-1]){
            int len=last-i+1;
            last=i-1;
        }
    }
    for(int i=0;i<=n+m;i++)
        ans=ans*getPow(invfac[i+1]*fac[i]%P,(t1[i]+P)%P)%P;
    ans=getPow(ans,P-2);
    for(int i=1;i<=n;i++) ans=ans*fac[p[i]]%P;
    printf("%lld\n",ans);
    return 0;
}