CF840C On the Bench 和 LG6151 青春豬頭少年不會夢到兔女郎學姐

On the Bench

有\(N\)種球，第\(i\)種球有\(A_i\)個，求排列方式，使得相同種類的球不相鄰。

每種球内部是否區分隻是答案後面是否有個系數的差别，不用糾結。

\(\sum_i A_i ≤ 3000\)。

老做法

運用插空法最好可以做到 \(O(n^3)\)。但是這個做法已經過時了。

Atcoder Typical DP Contest：O用的就是這個做法。

題解

限制是相鄰兩個球不能相同。當違反限制的時候，可以看成相鄰兩個球粘在了一起。

對于第\(i\)種球，如果違反了\(j(0 ≤ j < A_i)\)個限制，就相當于有\(j\)對相鄰的球被粘在了一起，方案數是 \(\binom{A_i−1}{j}\) ，帶上容斥系數就是\((−1)^j\)，這時候可以看成有\(A_i − j\)個球拿出去任意排列。

用背包DP把對每種球的容斥過程合并到一起即可。時間複雜度是\(O((\sum_i A_i)^2)\)的。

也可以用多項式優化做到更好的複雜度。

CO int N=300+10;
int fac[N],ifac[N];
int val[N],cnt[N];
int dp[N][N];

IN int C(int n,int m){
	return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
int main(){
	int n=read<int>();
	fac[0]=1;
	for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
	ifac[n]=fpow(fac[n],mod-2);
	for(int i=n-1;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
	for(int i=1;i<=n;++i){
		read(val[i]);
		bool flag=0;
		for(int j=1;j<i;++j){
			int64 s=(int64)val[i]*val[j],t=sqrt(s);
			if(t*t==s){
				++cnt[j];
				flag=1;break;
			}
		}
		if(!flag) ++cnt[i];
	}
	int m=0;
	for(int i=1;i<=n;++i)if(cnt[i]) cnt[++m]=cnt[i];
	dp[0][0]=1;
	int s=0;
	for(int i=1;i<=m;++i){
		for(int j=0;j<=s;++j)if(dp[i-1][j])
			for(int k=1;k<=cnt[i];++k){
				if((cnt[i]-k)%2==0)
					dp[i][j+k]=add(dp[i][j+k],mul(dp[i-1][j],mul(C(cnt[i]-1,k-1),C(j+k,k))));
				else
					dp[i][j+k]=add(dp[i][j+k],mod-mul(dp[i-1][j],mul(C(cnt[i]-1,k-1),C(j+k,k))));
			}
				
		s+=cnt[i];
	}
	int ans=0;
	for(int j=0;j<=s;++j) ans=add(ans,dp[m][j]);
	for(int i=1;i<=m;++i) ans=mul(ans,fac[cnt[i]]);
	printf("%d\n",ans);
	return 0;
}
           

青春豬頭少年不會夢到兔女郎學姐

有\(N\)種球，第\(i\)種球有\(A_i\)個。

對于一個序列，把它看成首尾相連的。一個序列的權值定義為每個極大相同顔色連續段長度的乘積。

求所有序列的權值和，對\(998244353\)取模。

\(\sum_i A_i ≤ 2 × 10^5\)。

倉鼠《雜題選講》。

想象這麼一種暴力。假如枚舉每種顔色最後分段是什麼樣的，那麼可以直接用前面說的容斥做法統計方案數，乘上這種分段帶來的價值加到答案裡面去。

實際上可以把每種暴力的結果合并到一起，丢到後面的容斥的過程裡面去。

先優化暴力的過程，數量為\(A_i\)的物品分成\(n\)段的貢獻和用之前說的插闆法計算。相當于每一段要選一個代表點。

然後用FFT計算出，每個分成\(n\)段的情況在容斥的時候又被分成了\(m\)段的方案數。

直接用分治FFT把容斥的情況合并到一起。

CO int N=262144;
int omg[2][N],rev[N];

void NTT(poly&a,int dir){
	int lim=a.size(),len=log2(lim);
	for(int i=0;i<lim;++i) rev[i]=rev[i>>1]>>1|(i&1)<<(len-1);
	for(int i=0;i<lim;++i)if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=1;i<lim;i<<=1)
		for(int j=0;j<lim;j+=i<<1)for(int k=0;k<i;++k){
			int t=mul(omg[dir][N/(i<<1)*k],a[j+i+k]);
			a[j+i+k]=add(a[j+k],mod-t),a[j+k]=add(a[j+k],t);
		}
	if(dir==1){
		int ilim=fpow(lim,mod-2);
		for(int i=0;i<lim;++i) a[i]=mul(a[i],ilim);
	}
}
poly operator*(poly a,poly b){
	int n=a.size()+b.size()-1,lim=1<<(int)ceil(log2(n));
	a.resize(lim),NTT(a,0);
	b.resize(lim),NTT(b,0);
	for(int i=0;i<lim;++i) a[i]=mul(a[i],b[i]);
	NTT(a,1),a.resize(n);
	return a;
}
poly operator+(poly a,poly b){
	int n=max(a.size(),b.size());
	a.resize(n),b.resize(n);
	for(int i=0;i<n;++i) a[i]=add(a[i],b[i]);
	return a;
}

int fac[N],ifac[N];
poly f[N],g[N];

IN int C(int n,int m){
	if(m<0 or m>n) return 0;
	return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
pair<poly,poly> solve(int l,int r){
	if(l==r) return {f[l],g[l]};
	int mid=(l+r)>>1;
	pair<poly,poly> left=solve(l,mid),right=solve(mid+1,r);
	return {left.first*right.first,left.first*right.second+left.second*right.first};
}
int main(){
	omg[0][0]=1,omg[0][1]=fpow(3,(mod-1)/N);
	omg[1][0]=1,omg[1][1]=fpow(omg[0][1],mod-2);
	for(int i=2;i<N;++i){
		omg[0][i]=mul(omg[0][i-1],omg[0][1]);
		omg[1][i]=mul(omg[1][i-1],omg[1][1]);
	}
	fac[0]=1;
	for(int i=1;i<N;++i) fac[i]=mul(fac[i-1],i);
	ifac[N-1]=fpow(fac[N-1],mod-2);
	for(int i=N-2;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
	
	int n=read<int>();
	if(n==1){
		printf("%d\n",read<int>());
		return 0;
	}
	
	for(int i=1;i<=n;++i){
		int c=read<int>();
		f[i].resize(c+1),g[i].resize(c+1);
		for(int j=1;j<=c;++j){
			f[i][j]=C(c+j-1,2*j-1);
			g[i][j]=add(f[i][j],mul(2,C(c+j-1,2*j)));
		}
//		cerr<<"f=";
//		for(int j=1;j<=c;++j) cerr<<" "<<f[i][j];
//		cerr<<endl;
//		cerr<<"g=";
//		for(int j=1;j<=c;++j) cerr<<" "<<g[i][j];
//		cerr<<endl;
		
		poly h(c+1);
		for(int j=1;j<=c;++j) f[i][j]=mul(f[i][j],fac[j-1]);
		for(int j=0;j<=c;++j) h[j]=j%2==1?mod-ifac[j]:ifac[j];
		reverse(h.begin(),h.end());
		f[i]=f[i]*h;
		for(int j=0;j<=c;++j) f[i][j]=f[i][j+c];
		f[i].resize(c+1);
		f[i][0]=0;
		for(int j=1;j<=c;++j) f[i][j]=mul(f[i][j],ifac[j-1]);
		
		for(int j=1;j<=c;++j) g[i][j]=mul(g[i][j],fac[j]);
		for(int j=0;j<=c;++j) h[j]=j%2==1?mod-ifac[j]:ifac[j];
		reverse(h.begin(),h.end());
		g[i]=g[i]*h;
		for(int j=0;j<=c;++j) g[i][j]=g[i][j+c];
		g[i].resize(c+1);
		g[i][0]=0;
		for(int j=1;j<=c;++j) g[i][j]=mul(g[i][j],ifac[j]);
		
//		cerr<<"nf=";
//		for(int j=1;j<=c;++j) cerr<<" "<<f[i][j];
//		cerr<<endl;
//		cerr<<"ng=";
//		for(int j=1;j<=c;++j) cerr<<" "<<g[i][j];
//		cerr<<endl;
		
		for(int j=1;j<=c;++j){
			f[i][j]=mul(f[i][j],ifac[j]);
			g[i][j]=mul(g[i][j],ifac[j-1]);
		}
	}
	
	poly res=solve(1,n).second;
	int ans=0;
	for(int i=n;i<(int)res.size();++i)
		ans=add(ans,mul(res[i],fac[i-1]));
	printf("%d\n",ans);
	return 0;
}