【CDQ分治+FFT】LGP4566 [CTSC2018]青蕈领主

【题目】
原题地址
有一个长度为$n$的排列$a$，给定$l_i$，表示$a_{i-l_i+1}\dots a_i$在排序后公差为$1$，且$l_i$为满足条件的最小数字，求方案数。$n\le 5\times 10^4$

【解题思路】
以下思路来自大佬的博客

神仙题。
很容易证明所有的连续区间只能相离或者相互包含，不可能相交。因此只要存在区间相交或者$L[n]̸=n$，就无解。
有解的时候，把每一个点对应的极大连续区间向包含它的最小的极大连续区间连边，这显然是一棵树。

对于一个根，它代表了一段连续区间，而它的每一个儿子都分别代表了一个极大的连续区间，那么把每一个儿子代表的区间缩成一个点，按原相对大小重新编号后不存在除整个区间以外的连续区间。
就相当于求解$1,2,3\dots ,m+1$的方案数（$m+1$表示儿子的个数，即区间长度），记这个值为$f_m$。

设第$i$个点的儿子个数是$cn{t}_i$，那么答案就是${\prod }_{i=1}^n{f}_{cn{t}_i}$

现在求$f_i$，首先给出一个结论$f_n=(n-1)f_{n-1}+{\sum }_{i=2}^{n-2}(i-1)f_i{f}_{n-i}$
这个递推式可以这样证明：
我们对于一个满足条件的排列$a$，我们令$b_{a_i}=i$
那么$b$中值$i\sim j$的下标对应$a_i\sim a_j$，也就是说$b$中一段连续区间，就对应了$a$中一段连续区间，说明$b$中不存在不经过最大值的连续区间。
那么$a$和$b$一一对应，现在转化为求满足$b$性质的方案数。

考虑从$f_n$转移到$f_{n+1}$

• 从一个合法排列转移到另一个合法排列，假设原排列是$2\sim n+1$的一个排列，那么插入的$1$只要不与$2$相邻即可，也就是$(n-1)f_{n-1}$
• 从一个非法排列转移到一个合法排列，原排列必须有且仅有一个极大的不包含最大值的连续区间，设长度为$l(2\le l\le n-2)$。
  这个不合法的区间要在插入一个数后合法，等价于分成两部分，左右都不存在连续区间的方案数。也就是一个合法排列去掉最大值后的两边，方案数即为fl。再考虑这段区间的值域（也就是$[x,x+l-1]$）范围，$x>2$且$x+l-1<n+1$，就有$n-l-1$个合法值域。其它部分为$f_{n-l}$

于是
$$f_n=(n-1)f_{n-1}+\sum _{i=2}^{n-2}(n-i-1)f_i{f}_{n-i}$$
$$=(n-1)f_{n-1}+\sum _{i=1}^{n-2}(i-1)f_i{f}_{n-i}$$

可以用分治$+FFT$得到$f$数组，用单调栈处理出$cnt$数组。

【参考代码】

#include<bits/stdc++.h> using namespace std;typedef long long ll; const int mod=998244353,g=3,N=166666; int T,n,top,ans,cnt,flag; int f[N],l[N],a[N],b[N],q[N];int read() {int ret=0;char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) ret=ret*10+(c^48),c=getchar();return ret; }int qpow(int x,int y) {int ret=1;for(;y;y>>=1,x=(ll)x*x%mod) if(y&1) ret=(ll)ret*x%mod;return ret; } void up(int &x,int y){x+=y;if(x>=mod)x-=mod;} int upm(int x){if(x>=mod)x-=mod;return x;}namespace NTT {int L,m;int rev[N],tmp1[N],tmp2[N];void ntt(int *a,int n,int f){for(int i=0;i<n;++i) if(i>rev[i]) swap(a[i],a[rev[i]]);for(int i=1;i<n;i<<=1){int wn=qpow(g,(mod-1)/(i<<1));if(f==-1) wn=qpow(wn,mod-2);for(int j=0;j<n;j+=i<<1){int w=1;for(int k=0;k<i;++k,w=(ll)w*wn%mod){int x=a[j+k],y=(ll)w*a[i+j+k]%mod;a[j+k]=upm(x+y);a[i+j+k]=upm(x-y+mod);}}}int inv=qpow(n,mod-2);if(f==-1) for(int i=0;i<n;++i) a[i]=(ll)a[i]*inv%mod;}void mul(int *a,int *b,int *c,int l1,int l2){for(L=0,m=1;m<=l1+l2;m<<=1) ++L;for(int i=0;i<m;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));for(int i=0;i<l1;++i) tmp1[i]=a[i];for(int i=l1;i<m;++i) tmp1[i]=0;for(int i=0;i<l2;++i) tmp2[i]=b[i];for(int i=l2;i<m;++i) tmp2[i]=0;ntt(tmp1,m,1);ntt(tmp2,m,1);for(int i=0;i<m;++i) c[i]=(ll)tmp1[i]*tmp2[i]%mod;ntt(c,m,-1);} }; using NTT::mul;void cdq(int l,int r) {if(l==r){up(f[l],(ll)f[l-1]*(l-1)%mod);return;}int mid=(l+r)>>1;cdq(l,mid);for(int i=l;i<=mid;++i)a[i-l]=(ll)f[i]*(i-1)%mod,b[i-l]=f[i];mul(a,b,a,mid-l+1,mid-l+1);for(int i=max(l<<1,mid+1);i<=r;++i) up(f[i],a[i-(l<<1)]);if(l^2){for(int i=2;i<=min(l-1,r-l);++i) a[i-2]=f[i];for(int i=l;i<=mid;++i) b[i-l]=f[i];mul(a,b,a,min(l-1,r-l)-1,mid-l+1);for(int i=max(l+2,mid+1);i<=r;++i) up(f[i],(ll)a[i-l-2]*(i-2)%mod);}cdq(mid+1,r); }int main() { #ifndef ONLINE_JUDGEfreopen("LGP4566.in","r",stdin);freopen("LGP4566.out","w",stdout); #endifT=read();n=read();f[0]=1;f[1]=2;cdq(2,n-1);while(T--){ans=1;top=0;for(int i=1;i<=n;++i) l[i]=read();if(l[n]^n){puts("0");continue;}for(int i=1;i<=n;++i){cnt=flag=0;while(top && i-l[i]+1<=q[top]){if(i-l[i]+1>q[top]-l[q[top]]+1){flag=1;break;}--top;++cnt;}if(flag) break;q[++top]=i;ans=(ll)ans*f[cnt]%mod;}if(flag) puts("0"); else printf("%d\n",ans);}return 0; }

【总结】
分治$FFT$的过程忘了，还是看了别人的代码才搞清楚的。
巨菜无比。

总结

以上是生活随笔为你收集整理的【CDQ分治+FFT】LGP4566 [CTSC2018]青蕈领主的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。