【UER #12】电子运动

【UER #12】电子运动

考虑手动模拟一下电子的运动过程。

假设舱室序列为 ++-+--+++-+，初始电子在第 \(6\) 个舱室。

接下来，电子会向左运动到第 \(4\) 个舱室，状态变为 ++-++++++-+。

接下来，电子会向右运动到第 \(10\) 个舱室，状态变为 ++--------+。

接下来，电子会向左运动到第 \(2\) 个舱室，状态变为 +++++++++++。

接下来，电子会向右运动到最右端，状态变为 +----------。

在移动过程中，我们发现了如下事实：

• 电子每向右移动一次，+ 的数量减 \(1\)。电子每向左移动一次，+ 的数量加 \(1\)。

考虑电子一开始在舱室 \(x\)，且初始状态 + 的个数为 \(t\)，则有两种情况：

• 电子运动到最左端，最后的答案为 \(t + x\)

• 电子运动到最右端，最后的答案为 \(t + x - (n+1)\)

显然最终的 + 个数在 \(0\) 到 \(n\) 之间。

同时根据上面的模拟来看，不可能存在电子无法结束运动的情况。

因此，我们猜测最终的答案为 \((t+x) \bmod (n+1)\)。

这是正确的，因为两种答案里一定恰好有一种成立，并且两种答案在模意义下同余。

接下来我们需要考虑 \(x\) 和 \(t\) 的分布。

首先对于 \(x\) 的分布，就是题面中的 \(p\)。

接下来对于 \(t\) 的分布，显然是二项式系数，容易求出。

最后我们求出 \(x\) 和 \(t\) 的卷积，就可以算出答案了。

时间复杂度 \(O(n \log n)\)。

#include<iostream>
#include<cstdio>
using namespace std;
const int mod=998244353,root=15311432,inv_2=499122177;
const int L=23,N=1<<21;
int omega[1<<L],inv_omega[1<<L];
void init(){
	omega[0]=1;
	for(int i=1;i<(1<<L);i++){
		omega[i]=(long long)omega[i-1]*root%mod;
	}
	inv_omega[0]=1;
	for(int i=1;i<(1<<L);i++){
		inv_omega[i]=omega[(1<<L)-i];
	}
}
int f[N],g[N],h[N],t;
int buf[N];
void NTT(int* a){
	for(int i=t;i>=1;i--){
		for(int j=0;j<(1<<t);j+=(1<<i)){
			for(int k=0;k<(1<<i-1);k++){
				buf[j+k]=a[j+k*2];
				buf[j+k+(1<<i-1)]=a[j+k*2+1];
			}
			for(int k=0;k<(1<<i);k++){
				a[j+k]=buf[j+k];
			}
		}
	}
	for(int i=1;i<=t;i++){
		for(int j=0;j<(1<<t);j+=(1<<i)){
			for(int k=0;k<(1<<i-1);k++){
				buf[j+k]=(a[j+k]+(long long)omega[k<<L-i]*a[j+k+(1<<i-1)]%mod+mod)%mod;
				buf[j+k+(1<<i-1)]=(a[j+k]-(long long)omega[k<<L-i]*a[j+k+(1<<i-1)]%mod+mod)%mod;
			}
			for(int k=0;k<(1<<i);k++){
				a[j+k]=buf[j+k];
			}
		}
	}
}
void INTT(int* a){
	for(int i=t;i>=1;i--){
		for(int j=0;j<(1<<t);j+=(1<<i)){
			for(int k=0;k<(1<<i-1);k++){
				buf[j+k]=((long long)(a[j+k]+a[j+k+(1<<i-1)])+mod)%mod*inv_2%mod;
				buf[j+k+(1<<i-1)]=((long long)(a[j+k]-a[j+k+(1<<i-1)])+mod)%mod*inv_2%mod*inv_omega[k<<L-i]%mod;
			}
			for(int k=0;k<(1<<i);k++){
				a[j+k]=buf[j+k];
			}
		}
	}
	for(int i=1;i<=t;i++){
		for(int j=0;j<(1<<t);j+=(1<<i)){
			for(int k=0;k<(1<<i-1);k++){
				buf[j+k*2]=a[j+k];
				buf[j+k*2+1]=a[j+k+(1<<i-1)];
			}
			for(int k=0;k<(1<<i);k++){
				a[j+k]=buf[j+k];
			}
		}
	}
}
long long pow_mod(long long num1,long long num2=mod-2){
	long long num3=1;
	while(num2){
		if(num2&1){
			num3=num3*num1%mod;
		}
		num1=num1*num1%mod;
		num2>>=1;
	}
	return num3;
}
long long fact[500010],invfact[500010],out[500010];
int main(){
	init();
	int n;
	scanf("%d",&n);
	fact[0]=invfact[0]=1;
	for(int i=1;i<=n;i++){
		scanf("%lld",&f[i]);
		fact[i]=fact[i-1]*i%mod;
		invfact[i]=invfact[i-1]*pow_mod(i)%mod;
	}
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++){
		char ch;
		cin>>ch;
		if(ch=='+'){
			cnt1++;
		}
		if(ch=='?'){
			cnt2++;
		}
	}
	long long tmp=pow_mod(pow_mod(2,cnt2));
	for(int i=0;i<=cnt2;i++){
		g[cnt1+i]=invfact[i]*invfact[cnt2-i]%mod*fact[cnt2]%mod*tmp%mod;
	}
	for(int i=0;i<=n;i++){
	}
	while((1<<t)<=2*n){
		t++;
	}
	NTT(f);
	NTT(g);
	for(int i=0;i<(1<<t);i++){
		h[i]=(long long)f[i]*g[i]%mod;
	}
	INTT(h);
	for(int i=0;i<=2*n;i++){
		out[i%(n+1)]+=h[i];
		out[i%(n+1)]%=mod;
	}
	for(int i=0;i<=n;i++){
		printf("%lld ",out[i]);
	}
	return 0;
}