自动搬运

查看原文

来自洛谷，原作者为

	lmh .

搬运于2025-08-24 23:07:13，当前版本为作者最后更新于2025-01-02 13:37:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

参考了官方题解。下文称“$A$ 在 $B$ 右边”当且仅当 $A$ 处在 $B$ 往顺时针方向移动一格走到的位置，类似地定义“$A$ 在 $B$ 左边”。

显然直接 dp 是没有前途的，它的极限在 $O(n^4)$，所以得容斥。考虑算结果的生成函数 $F(x)$，其中 $[x^{n+i}]F(x)$ 为 $i$ 位置的答案。

将 $U=[1,n]\cap \Z$ 划分为若干个集合 $S_1\cdots S_k$，对于每个 $S_i$，强制集合内所有数顺次相连，且这些数按照顺时针方向从小到大排列。不同集合间的顺序不做要求。

例如，如果我们划分出一个集合 $\{1,2,4\}$，则我们排列选手的方案必须满足 $1$ 右边为 $2$，$2$ 右边为 $4$。

或者说，我们固定若干个顺时针方向的单调增的连续段。

对于连续段相接的地方，贡献就是左边的人获胜的贡献。这个贡献可以拆到连续段的头尾处，具体地，开头贡献为 $x$ 当且仅当它是 B，结尾贡献为 $x$ 当且仅当它是 R。否则贡献为 $1$。

对于被固定的地方，$B\to R$ 贡献为 $x-1$，$R\to B$ 贡献为 $1-x^2$，其余情况下贡献为 $0$。同时这些连续段可以任意排列，最后还要乘一个阶乘。

这玩意看上去没啥道理，所以还是需要解释一下。

任选一个可能的排列，考虑所有可能的选择方式。

“对于没有被固定的地方，贡献就是左边的人获胜的贡献”相当于默认两个连续段相接的地方左边（逆时针方向）那个人赢了，所以开头贡献为 $x$ 当且仅当它是 B，结尾贡献为 $x$ 当且仅当它是 R。

当然我们有可能在胡说八道，右边那个人获胜也是有可能的。但是如果右边的人获胜了，那么一定存在一个强制选择上升段的方案使得其余位置全部相同，但目前出问题的两个人在一个上升段里面（显然有一个一一对应关系）。此时，$B\to R$ 贡献为 $x-1$，$R\to B$ 贡献为 $1-x^2$，其余情况下贡献为 $0$（实际上是 $x-x$），这是一个正的项和一个负的项相减，负的那玩意减掉的就是胡说八道的情况下凭空变出来的贡献。

现在把这些链放到 $1\sim n$ 的序列上，注意到只有 $R,B$ 交替的链有贡献，所以我们甚至不需要维护每条链，只需要记录 $R\to B$ 和 $B\to R$ 的出现次数即可。最后每一个 $R\to B$ 和 $B\to R$ 的边的集合与有意义的方案一一对应，且它们贡献相同。

准确地说，如果 $R\to B$ 出现了 $a$ 次，$B\to R$ 出现了 $b$ 次，那么它的贡献是 $(x-1)^a(1-x^2)^bx^{n-2b}(n-a-b-1)!$，证明显然。

$R\to B$ 和 $B\to R$ 出现 $i$ 次的方案数是好算的，设它们分别为 $\{A_i\},\{B_i\}$，则答案为 $x^n\sum_{i}\sum_{j}A_iB_j(n-i-j-1)!(x-1)^i(x^{-2}-1)^j$。

这玩意还是不好算的，但我们知道答案对应多项式的次数，所以可以代 $2n+2$ 个值进去，这样可以用 FFT 优化，最后用拉格朗日插值求答案。复杂度 $O(n^2\log n)$，需要狠狠卡常。

代码仅供参考，这个由于常数过大只能获得 85 分 现在这份代码可以通过了。

一些卡常的技巧：使用数组而非 vector；预处理 NTT 的系数；使用 unsigned long long 取模。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const ll N=17000;
const ull MOD=998244353,g[2]={3,332748118},inv2=499122177;
ll n,lenA,lenB,a[N],b[N],c[N],rev[N],A[N],B[N];
ull w[N],X[N],Y[N],ans[N],pu[N],pv[N],fac[N],ifac[N];
char s[N];
ull qpow(ull x,ll k){
	ull sum=1;
	while(k){
		if (k&1) (sum*=x)%=MOD;
		(x*=x)%=MOD;k>>=1;
	}
	return sum;
}
struct poly{
	vector<ull> a;
	int size()const{return a.size();}
	void resize(int n){a.resize(n);}
	ull operator [](int n)const{
		return (a.size()<=n)?0:a[n];
	}
	ull& operator [](int n){
		if (a.size()<=n) a.resize(n+1);
		return a[n];
	}
}F,G;
int init(int n){
	int len=0,w=1;
	while(w<=n){
		w<<=1;++len;
	}
	for (int i=1;i<w;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<len-1);
	return w;
}
void NTT(poly& f,const int& n,const int& sgn){
	assert(sgn==0||sgn==1);
	static ull a[N];
	for (int i=0;i<n;++i) a[i]=f[rev[i]];
	for (int len=2;len<=n;len<<=1){
		ull omega=qpow(g[sgn],(MOD-1)/len),i=len>>1;
		for (int k=w[0]=1;k<i;++k) w[k]=w[k-1]*omega%MOD;
		for (int j=0;j<n;j+=len){
			for (int k=0;k<i;++k){
				ull x=a[j|k],y=a[i|j|k]*w[k]%MOD;
				a[j|k]=x+y;
				if (a[j|k]>=MOD) a[j|k]-=MOD;
				a[i|j|k]=x-y+MOD;
				if (a[i|j|k]>=MOD) a[i|j|k]-=MOD;
			}
		}
	}
	if (sgn){
		ll inv=qpow(n,MOD-2);
		for (int i=0;i<n;++i) f[i]=a[i]*inv%MOD;
	}
	else for (int i=0;i<n;++i) f[i]=a[i];
}
poly operator *(const poly& a,const poly& b){
	ll len=init(a.size()+b.size());
	poly t1=a,t2=b;
	t1.resize(len);t2.resize(len);
	NTT(t1,len,0);NTT(t2,len,0);
	for (int i=0;i<len;++i) t1[i]=(ll)t1[i]*t2[i]%MOD;
	NTT(t1,len,1);
	t1.resize(a.size()+b.size());
	return t1;
}
ull H(ll x){
	ull ans=0,u=(x+MOD-1)%MOD,v=(qpow(x,MOD-3)+MOD-1)%MOD;
	pu[0]=pv[0]=1;
	for (int i=1;i<=n;++i){
		pu[i]=pu[i-1]*u%MOD;
		pv[i]=pv[i-1]*v%MOD;
	}
	F.resize(lenA);G.resize(lenB);
	for (int i=0;i<lenA;++i) F[i]=A[i]*pu[i]%MOD;
	for (int i=0;i<lenB;++i) G[i]=B[i]*pv[i]%MOD;
	F=F*G;
	for (int i=0;i<n&&i<F.size();++i) (ans+=F[i]*fac[n-i-1])%=MOD;
	return ans*qpow(x,n)%MOD;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	for (int i=fac[0]=1;i<N;++i) fac[i]=fac[i-1]*i%MOD;
	ifac[N-1]=qpow(fac[N-1],MOD-2);
	for (int i=N-1;i;--i) ifac[i-1]=ifac[i]*i%MOD;
	cin>>n>>(s+1);
	A[0]=B[0]=1;
	for (int i=1;i<=n;++i){
		a[i]=a[i-1]+(s[i]=='R');b[i]=b[i-1]+(s[i]=='B');
		if (s[i]=='R') for (int j=i;j;--j) (A[j]+=A[j-1]*max(b[i]-j+1,0ll))%=MOD;
		else for (int j=i;j;--j) (B[j]+=B[j-1]*max(a[i]-j+1,0ll))%=MOD;
	}
//	for (int i=0;i<=n;++i) cout<<A[i]<<' '<<B[i]<<endl;
	while(A[lenA]) lenA++;
	while(B[lenB]) lenB++;
	for (int i=0;i<=2*n+1;++i){
		X[i]=i;Y[i]=H(i);
//		cout<<i<<' '<<Y[i]<<endl;
	}
	n=2*n+2;
	memset(a,0,sizeof(a));memset(b,0,sizeof(b));
	for (int i=0;i<n;++i){
		ull mul=1;
		for (int j=0;j<n;++j) if (i!=j) (mul*=(X[i]+MOD-X[j]))%=MOD;
		a[i]=qpow(mul,MOD-2)*Y[i]%MOD;
	}
	b[0]=1;
	for (int i=0;i<n;++i){
		for (int j=i+1;j;--j) b[j]=(b[j]*(MOD-X[i])+b[j-1])%MOD;
		(b[0]*=MOD-X[i])%=MOD;
	}
	for (int i=0;i<n;++i){
		ull mul=qpow(MOD-X[i],MOD-2);
		if (!mul) for (int j=0;j<n;++j) c[j]=b[j+1];
		else{
			c[0]=b[0]*mul%MOD;
			for (int j=1;j<=n;++j) c[j]=(b[j]+MOD-c[j-1])*mul%MOD;
		}
		for (int j=0;j<n;++j) (ans[j]+=a[i]*c[j])%=MOD;
	}
	--n;
	for (int i=0;i<n;++i) cout<<ans[i]<<' ';cout<<endl;
	return 0;
}