AT_jsc2019_final_f

模拟赛题。赛时暴力被放过了。

考虑如下 $O(n^2q)$ 暴力：将询问区间拎出来成一个序列并排序，设 $dp_{i,j}$ 表示前 $i$ 个数，已经钦定了 $j$ 个位置 $a_i=p_i$。转移是 naive 的，枚举当前位置是否钦定即可。因为有重复数字所以再加一维 $0/1$ 表示当前相同数字是否选过。最后乘上没钦定的数量的阶乘。

然后考虑优化。考虑分治，因为不同的数字之间不关联，考虑将前后两半出现过的不同元素数平均。然后考虑合并两边答案，会发现要进行的操作类似 $dp_{l,i}\times dp_{r,j}\to dp_{r,i+j}$ 。是卷积形式，使 NTT。单次时间复杂度是 $T(n)=2T(\frac{n}{2})+O(n\log n)=O(n\log^2n)$。总复杂度为 $O(nq\log^2n)$。可能需要一定卡常。

冷知识：暴力卷积刚好卡过。某些实现的好的（可能是内存访问连续的）$O(n^2q)$ 暴力也能过。

code：

int n,m,q,pw[27][2],a[N],b[N],fac[N],dp[N][N<<1],to[N<<1];
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
il int qpow(int x,int y){
	int ret=1;
	while(y){
		if(y&1){
			ret=1ll*ret*x%mod;
		}
		x=1ll*x*x%mod,y>>=1;
	}
	return ret;
}
const int G=3,iG=qpow(G,mod-2);
void NTT(int id,int n,bool op){
	rep(i,0,n-1){
		if(i<to[i]){
			swap(dp[id][i],dp[id][to[i]]);
		}
	}
	for(int k=2,lg=1;k<=n;k<<=1,lg++){
		int p=1,dt=op?pw[lg][0]:pw[lg][1],l=k/2;
		for(int i=0;i<n;i+=k){
			int p=1;
			rep(j,i,i+l-1){
				int tmp=1ll*dp[id][j+l]*p%mod;
				dp[id][j+l]=Mod(dp[id][j],mod-tmp);
				dp[id][j]=Mod(dp[id][j],tmp);
				p=1ll*p*dt%mod;
			}
		}
	}
	if(!op){
		int tmp=qpow(n,mod-2);
		rep(i,0,n-1){
			dp[id][i]=1ll*dp[id][i]*tmp%mod;
		}
	}
}
void solve(int l,int r){
	int cnt=0;
	rep(i,l,r){
		cnt+=b[i]!=b[i-1];
	}
	if(cnt==1){
		dp[r][0]=1,dp[r][1]=mod-(r-l+1);
		return;
	}
	int tmp=0,p=0;
	rep(i,l,r){
		tmp+=b[i]!=b[i-1];
		if(tmp==cnt/2+1){
			p=i-1;
			break;
		}
	}
	tmp--;
	solve(l,p),solve(p+1,r);
	int len=1;
	while(len<=cnt){
		len<<=1;
	}
	rep(i,0,len-1){
		to[i]=(to[i>>1]>>1)|((i&1)?((len+1)>>1):0);
	}
	rep(i,tmp+1,len){
		dp[p][i]=0;
	}
	rep(i,cnt-tmp+1,len){
		dp[r][i]=0;
	}
	NTT(p,len,1),NTT(r,len,1);
	rep(i,0,len-1){
		dp[r][i]=1ll*dp[r][i]*dp[p][i]%mod;
	}
	NTT(r,len,0);
}
void Yorushika(){
	read(n,q);
	fac[0]=1;
	rep(i,1,n){
		read(a[i]);
		fac[i]=1ll*fac[i-1]*i%mod;
	}
	b[0]=-1;
	rep(i,1,20){
		pw[i][0]=qpow(G,(mod-1)/(1<<i));
		pw[i][1]=qpow(iG,(mod-1)/(1<<i));
	}
	while(q--){
		int l,r;read(l,r);
		l++;
		rep(i,l,r){
			b[i-l+1]=a[i];
		}
		m=r-l+1;
		sort(b+1,b+m+1);
		int cnt=0;
		rep(i,1,m){
			if(b[i]!=b[i-1]){
				cnt++;
			}
		}
		solve(1,m);
		int ans=0;
		rep(i,0,cnt){
			ans=Mod(ans,1ll*dp[m][i]*fac[n-i]%mod);
		}
		printf("%d\n",ans);
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}

但是考场上忘了 NTT 怎么写于是写了个 $O(n^2q)$，模拟赛数据跑了 700ms。