uoj#401. 【CTSC2018】青蕈领主（分治FFT）

话说分治$FFT$是个啥子啊……还有题目里那字好像念(蕈xùn)

首先考虑无解的情况：区间相交或者$L_n\neq n$

这两个都可以感性理解一下

所以区间之间只会有包含关系，我们把每个小区间向它右边的第一个包含它的大区间连边，那么会构成一个树形结构

对于一个大区间来说，那些作为它儿子的小区间每一个都是连续的，并且互不相交，假设它有$sz$个儿子，把每一个儿子都缩成一个点，那么就是需要一个排列满足$L$分别为$1,1,1,...,sz+1$，其中第$sz+1$个是大区间自己，也就是除了最后一个节点之外不存在任何一个大于$1$的连续子区间，我们称其为合法排列

设$f_i$为长度为$i+1$的除整个区间外不存在连续最长子区间的排列个数，那么答案就是$\prod f(sz)$

顺便说一句$sz$可以用单调栈$O(n)$求出

考虑$f$应该如何计算，有$$f_i=(i-1)f_{i-1}+\sum_{j=2}^{i-2}(j-1)f_jf_{i-j}$$

这个怎么解释嘞

我们设$b_{a_i}=i$，那么原数列中连续区间在新的数列中也还是连续区间，且在原序列中包含最后一个节点的区间就是新数列中包含最大值的区间

那么我们可以稍微改一下$f_i$的定义，为除包含最大值外不存在连续最长子区间的排列个数，这个定义是和之前等价的

然后考虑上面的递推式

即在一个长度为$i$的排列中插入一个数来得到$i+1$

1.原排列本来就合法，那么只要插入的$i+1$不和$i$相邻即可，有$i-1$个位置可放

2.原排列不合法，插入的$i+1$使其合法。这种时候原排列一定只有一个不经过最大值的连续最长子区间，那么枚举这个子区间的长度$j\in [2,i-2]$，插入这个最大值会使这个区间被分为两部分，这两部分和最大值形成的整个区间是一个合法的排列，长度为$j+1$，方案为$f_j$，这一段区间值域为$[x,x+j-1]$，那么$x$的选择方案为$n-j-1$种。再把这个区间视为一个整体，这样整个排列共有$i-j+1$个数字，方案数为$f_{i-j}$

于是递推过程就是$$f_i=(i-1)f_{i-1}+\sum_{j=2}^{i-2}(i-j-1)f_jf_{i-j}$$

\[f_i=(i-1)f_{i-1}+\sum_{j=2}^{i-2}(j-1)f_jf_{i-j}
\]

这个可以用分治$FFT$优化

然后说一下好了……这个分治$FFT$的过程比较神仙……

因为我们分治的时候使用$[l,mid]$卷上$[1,r-l]$，然后加到$[mid+1,r]$上，但问题是$r-l$之类的可能还没求出来……

于是我们让$[l,mid]$卷上$[1,\min(r-l,l-1)]$，这样的话卷的东西都是我们已经求好了的

然后本来是要$[l,mid]$和$[1,\min(r-l,l-1)]$，$[1,\min(r-l,l-1)]$和$[l,mid]$分别卷的，不过因为$(j-1)f_jf_{j-i}+(i-j-1)f_{j-i}f_j=(i-2)f_jf_{i-j}$，所以可以卷一次再乘上$i-2$

然后没啥然后了……

//minamoto

#include<bits/stdc++.h>

#define R register

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

inline int min(const R int &x,const R int &y){return x<y?x:y;}

inline int max(const R int &x,const R int &y){return x>y?x:y;}

inline void swap(R int &x,R int &y){x^=y^=x^=y;}

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

const int N=2e5+5,P=998244353,Gi=332748118;

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

int ksm(R int x,R int y){

	R int res=1;

	for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);

	return res;

}

int r[N],f[N],st[N],A[N],B[N],a[N],O[N];

int lim,l,n,m,res,top,sz;bool flag;

void NTT(int *A,int ty){

	fp(i,0,lim-1)if(i<r[i])swap(A[i],A[r[i]]);

	for(R int mid=1;mid<lim;mid<<=1){

		int I=(mid<<1),Wn=ksm(ty==1?3:Gi,(P-1)/I);O[0]=1;

		fp(i,1,mid-1)O[i]=mul(O[i-1],Wn);

		for(R int j=0;j<lim;j+=I)fp(k,0,mid-1){

			int x=A[j+k],y=mul(O[k],A[j+k+mid]);

			A[j+k]=add(x,y),A[j+k+mid]=dec(x,y);

		}

	}if(ty==-1)for(R int i=0,inv=ksm(lim,P-2);i<lim;++i)A[i]=mul(A[i],inv);

}

void Mul(int *A,int *B,int n,int m){

	lim=1,l=0;while(lim<=n+m)lim<<=1,++l;

	fp(i,0,lim-1)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

	fp(i,n,lim-1)A[i]=0;fp(i,m,lim-1)B[i]=0;

	NTT(A,1),NTT(B,1);

	fp(i,0,lim-1)A[i]=mul(A[i],B[i]);

	NTT(A,-1);

}

void CDQ(int l,int r){

	if(l==r)return f[l]=add(f[l],mul(l-1,f[l-1])),void();

	int mid=(l+r)>>1;CDQ(l,mid);

	fp(i,l,mid)A[i-l]=mul(i-1,f[i]),B[i-l]=f[i];

	Mul(A,B,mid-l+1,mid-l+1);

	fp(i,max(l<<1,mid+1),r)f[i]=add(f[i],A[i-(l<<1)]);

	if(l!=2){

		int d=min(l-1,r-l);

		fp(i,2,d)A[i-2]=f[i];

		fp(i,l,mid)B[i-l]=f[i];

		Mul(A,B,d-1,mid-l+1);

		fp(i,max(l+2,mid+1),r)f[i]=add(f[i],mul(i-2,A[i-l-2]));

	}CDQ(mid+1,r);

}

int main(){

//	freopen("testdata.in","r",stdin);

	int T=read();n=read();

	f[0]=1,f[1]=2;

	if(n>2)CDQ(2,n-1);

	while(T--){

		flag=true,res=1,top=0;

		fp(i,1,n)a[i]=read();

		if(a[n]!=n||a[1]!=1){puts("0");continue;}

		fp(i,1,n){

			sz=0;

			while(top&&i-a[i]+1<=st[top]){

				if(i-a[i]+1>st[top]-a[st[top]]+1){flag=false;break;}

				++sz,--top;

			}

			if(!flag)break;

			res=mul(res,f[sz]),st[++top]=i;

		}

		printf("%d\n",flag?res:0);

	}

	return 0;

}

巴特西

uoj#401. 【CTSC2018】青蕈领主（分治FFT）

最新文章

热门文章