题解 P4566 [CTSC2018]青蕈领主

· · 题解

显然若将每个 i 对应的区间 [i-a_i+1,i] 画出，这些区间一定形成树的结构，否则不合法。

具体而言，区间 [i-a_i+1,i-1] 一定能被分成若干极长连续的子区间（即儿子）。可以将每个子区间看成一个数，故设子区间个数为 son_u，只需要求出形如 1 1 ... 1 n+1 问题的答案 f_n，答案即为 \prod\limits_u f_{son_u}。

利用递归的结构，设 G(x)=\sum\limits_{i=1}^{+ \infty} i! x^i，则有：

G(x)=xF(G(x))+x F(G(x))+1=\dfrac{G(x)}{x}

设 R(x) 为 G(x) 的复合逆，代入 R(x) 可得：

F(x)=\dfrac{x}{R(x)}-1

接下来只需要求 R(x) 即可。注意到 G(x) 是 D-finite 的，可知 (x-1)G(x)+x^2 G'(x)+x=0，代入 R(x) 得：

x(R(x)-1)+R(x)^2 G'(R(x))+R(x)=0

由 1=G(R(x))'=R'(x) G'(R(x))，

x(R(x)-1)+\dfrac{R(x)^2}{R'(x)}+R(x)=0 xR(x)R'(x)-xR'(x)+R(x)^2+R(x)R'(x)=0 \sum\limits_{i=1}^{n-1} ir_ir_{n-i}+\sum\limits_{i=1}^{n-1} r_ir_{n-i}+\sum\limits_{i=1}^{n} ir_ir_{n+1-i}=nr_n -r_n=\sum\limits_{i=1}^{n-1} (i+1)r_ir_{n-i}+\sum\limits_{i=2}^{n-1} ir_ir_{n+1-i}

分治 FFT 即可。时间复杂度 O(n \log^2 n)。

代码

常数超大

upd：减小了常数

long long F[N],G[N],P[N],Q[N];
long long A[N],B[N];
void Devide_solve(long long l,long long r){
    if(l==r){
        G[l]=(mod-G[l])%mod;
        P[l]=(l+1)*G[l]%mod;
        if(l>1) Q[l]=l*G[l]%mod;
        return ;
    }
    long long mid=(l+r)>>1ll;
    Devide_solve(l,mid);

    long long lim=r-l+1,len=lim>>1ll;

    if(l==1){
        for(long long i=1;i<=len;i++) A[i]=(P[i]+Q[i+1])%mod;
        for(long long i=1;i<=len;i++) B[i]=G[i];
        NTT::solve(A,A,B,len,len);
        for(long long i=len+1;i<=lim;i++){
            int t=i-len+mid;
            G[t]=(G[t]+A[i])%mod;
        }
    }
    else{
        for(long long i=1;i<=len;i++) A[i]=P[l+i-1];
        for(long long i=0;i<=len;i++) A[i]=(A[i]+Q[l+i])%mod;
        for(long long i=1;i<=lim;i++) B[i]=G[i];
        NTT::solve(A,A,B,len,lim);
        for(long long i=len+1;i<=lim;i++){
            int t=i-len+mid;
            G[t]=(G[t]+A[i])%mod;
        }

        for(long long i=1;i<=len;i++) A[i]=G[l+i-1];
        for(long long i=1;i<=lim;i++) B[i]=(P[i]+Q[i+1])%mod;
        NTT::solve(A,A,B,len,lim);
        for(long long i=len+1;i<=lim;i++){
            int t=i-len+mid;
            G[t]=(G[t]+A[i])%mod;
        }
    }
    Devide_solve(mid+1,r);
}

long long T,n,ans;
long long a[N];

void solve(long long l,long long r){
    if(a[r]!=r-l+1) ans=0;
    if(l==r) return ;
    long long mx=r,tot=0;
    for(long long i=r-1;i>=l;i--){
        if(i<mx){
            mx=i-a[i]+1;
            solve(mx,i);
            tot++;
        }
        else if(i-a[i]+1<mx) ans=0;
    }
    ans=ans*F[tot]%mod;
}

int main(){
    pre();
    cin>>T>>n;

    G[1]=mod-1;
    long long lim=NTT::init(n,0);
    long long m=1ll<<lim;
    Devide_solve(1,m);

    for(long long i=0;i<n;i++) F[i]=G[i+1];
    INV::solve(F,F,n);

    while(T--){
        for(long long i=1;i<=n;i++) scanf("%lld",&a[i]);
        ans=1;
        solve(1,n);
        printf("%lld\n",ans);
    }
}