Problem Link

感谢

题目大意

给定长度为 $n$ 的环，把 $1\sim n$ 填入这个环，每个元素有一个颜色，如果相邻两个元素异色，那么编号较大的元素所属的颜色得分 $+1$。

特别的，如果某个蓝色元素顺时针下一个元素是红色的，且红色元素权值较大，则这种情况不会让红色得分 $+1$。

对于 $k\in[-n,n]$，计数有多少个有圆排列，使得红色得分比蓝色得分多 $k$。

数据范围：$n\le 3000$。

思路分析

首先观察，用 $w_{R<B},w_{R>B},w_{B<R},w_{B>R}$ 分别表示顺时针方向上异色元素对的四种情况。

那么权值就是是 $w_{R>B}-w_{B>R}-w_{R<B}$，由于 $w_{R>B}+w_{R<B}=w_{B>R}+w_{B<R}$，因此权值可以写成 $w_{B<R}-2w_{R<B}$。

此时我们只要考虑顺时针方向上的点权值较大的情况，那么可以从最小值处破环为链。

这种只关心相邻元素大小关系的问题可以考虑插入 dp 或容斥。

插入 dp 的状态数显然无法接受，因此考虑容斥，即二项式反演。

此时我们钦定 $x$ 对相邻元素满足 $B<R$，$y$ 对相邻元素满足 $R<B$。

设方案数为 $f_{x,y}$，然后做二元二项式反演，即对每一维分别反演，得到的 $f'_{x,y}$ 就是恰好 $w_{B<R}=x,w_{R<B}=y$ 的方案数。

我们只要计数 $f_{x,y}$ 即可。

这种问题可以从两种视角看：一种是由这些钦定的边构成的极长连续段的视角，另一种是直接考虑每条边确定了哪些元素的前驱后继。

这题上考虑连续段显然过于困，因此选择视角二。

那么对于这 $x+y$ 条边，我们直接确定每条边是由哪两个元素构成的，那么相当于在排列上确定了若干个元素的前驱后继。

只要每个点的前驱后继不重复，那么就会形成若干条链，贡献就是链数的阶乘。

我们注意到 $B<R$ 的边只确定红色元素的前驱，$R<B$ 的边只确定红色元素的后继，蓝色元素同理。

那么这两种边分别去一个选择元素不重复的解，他们之间一定不冲突。

那么我们只需要计算选出 $x$ 条 $B<R$ 的边的方案数，以及 $y$ 条 $R<B$ 的边的方案数，此时这 $x+y$ 条边一定互补矛盾，把整个排列变成 $n-x-y$ 条链。

由于我们钦定最小值在最前面，那么对答案的贡献就是 $(n-x-y-1)!$。

这样就求出了所有 $f_{x,y}$，计算出 $f'_{x,y}$ 只要对每个 $x,y$ 分别二项式反演，可以用 NTT 优化。

时间复杂度 $\mathcal O(n^2\log n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353,N=1<<13,G=3;
int rev[N],inv[N],fac[N],ifac[N],w[N<<1];
int ksm(int a,int b=MOD-2) {
	int ret=1;
	for(;b;a=1ll*a*a%MOD,b=b>>1) if(b&1) ret=1ll*ret*a%MOD;
	return ret;
}
namespace P {
void poly_init() {
	inv[1]=1;
	for(int i=2;i<N;++i) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
	fac[0]=ifac[0]=1;
	for(int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*inv[i]%MOD;
	for(int k=1;k<=N;k<<=1) {
		int x=ksm(G,(MOD-1)/k); w[k]=1;
		for(int i=1;i<k;++i) w[i+k]=1ll*x*w[i+k-1]%MOD;
	}
}
int plen(int x) { int y=1; for(;y<x;y<<=1); return y;  }
void ntt(int *f,bool idft,int n) {
	for(int i=0;i<n;++i) {
		rev[i]=(rev[i>>1]>>1);
		if(i&1) rev[i]|=n>>1;
	}
	for(int i=0;i<n;++i) if(rev[i]<i) swap(f[i],f[rev[i]]);
	for(int k=2,x,y;k<=n;k<<=1) {
		for(int i=0;i<n;i+=k) {
			for(int j=i;j<i+k/2;++j) {
				x=f[j],y=1ll*f[j+k/2]*w[k+j-i]%MOD;
				f[j]=(x+y>=MOD)?x+y-MOD:x+y,f[j+k/2]=(x>=y)?x-y:x+MOD-y;
			}
		}
	}
	if(idft) {
		reverse(f+1,f+n);
		for(int i=0,x=ksm(n);i<n;++i) f[i]=1ll*f[i]*x%MOD;
	}
}
}
int C(int x,int y) {
	return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
int n,fb[N],fr[N],f[N][N],g[N],ans[N],c[N];
char str[N];
//ans = B<R-2R<B, fb=BR, fr=RB
void INV(int *a) {
	static int b[N];
	memset(b,0,sizeof(b));
	for(int i=0;i<=n;++i) b[i]=1ll*a[i]*fac[i]%MOD;
	P::ntt(b,0,N);
	for(int i=0;i<N;++i) b[i]=1ll*b[i]*c[i]%MOD;
	P::ntt(b,1,N);
	for(int i=0;i<=n;++i) a[i]=1ll*b[i+n]*ifac[i]%MOD;
}
signed main() {
	P::poly_init();
	scanf("%d%s",&n,str+1);
	fb[0]=fr[0]=1;
	for(int i=1,cb=0,cr=0;i<=n;++i) {
		if(str[i]=='R') {
			for(int j=cb;j;--j) fb[j]=(fb[j]+1ll*fb[j-1]*(cb+1-j))%MOD;
			++cr;
		} else {
			for(int j=cr;j;--j) fr[j]=(fr[j]+1ll*fr[j-1]*(cr+1-j))%MOD;
			++cb;
		}
	}
	for(int i=0;i<=n;++i) c[n-i]=(i&1?MOD-ifac[i]:ifac[i]);
	P::ntt(c,0,N);
	for(int x=0;x<=n;++x) for(int y=0;x+y<n;++y) f[x][y]=(f[x][y]+1ll*fb[x]*fr[y]%MOD*fac[n-1-x-y])%MOD;
	for(int x=0;x<=n;++x) INV(f[x]);
	for(int y=0;y<=n;++y) {
		memset(g,0,sizeof(g));
		for(int x=0;x<=n;++x) g[x]=f[x][y];
		INV(g);
		for(int x=0;x<=n;++x) ans[x+n-2*y]=(ans[x+n-2*y]+g[x])%MOD;
	}
	for(int i=0;i<=2*n;++i) printf("%d ",ans[i]); puts("");
	return 0;
}