結果

問題 No.3370 AB → BA
コンテスト
ユーザー tute7627
提出日時 2025-11-17 21:03:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,000 ms / 2,000 ms
コード長 7,747 bytes
コンパイル時間 2,389 ms
コンパイル使用メモリ 215,560 KB
実行使用メモリ 27,040 KB
最終ジャッジ日時 2025-11-17 21:03:35
合計ジャッジ時間 10,635 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
//#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)

#define a first
#define b second

ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}

using pi=pair<int,int>;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

#define pb push_back
#define eb emplace_back
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int((x).size())
using vi=vc<int>;

template<class t>
void chmin(t&a,const t&b){if(a>b)a=b;}

using uint=unsigned;
using ull=unsigned long long;

struct modinfo{uint mod,root;};
template<modinfo const&ref>
struct modular{
	static constexpr uint const&mod=ref.mod;
	static modular root(){return modular(ref.root);}
	uint v;
	modular(ll vv=0){s(vv%mod+mod);}
	modular&s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	modular operator-()const{return modular()-*this;}
	modular&operator+=(const modular&rhs){return s(v+rhs.v);}
	modular&operator-=(const modular&rhs){return s(v+mod-rhs.v);}
	modular&operator*=(const modular&rhs){
		v=ull(v)*rhs.v%mod;
		return *this;
	}
	modular&operator/=(const modular&rhs){return *this*=rhs.inv();}
	modular operator+(const modular&rhs)const{return modular(*this)+=rhs;}
	modular operator-(const modular&rhs)const{return modular(*this)-=rhs;}
	modular operator*(const modular&rhs)const{return modular(*this)*=rhs;}
	modular operator/(const modular&rhs)const{return modular(*this)/=rhs;}
	modular pow(int n)const{
		modular res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modular inv()const{return pow(mod-2);}
};

//size of input must be a power of 2
//output of forward fmt is bit-reversed
//output elements are in the range [0,mod*4)
//input of inverse fmt should be bit-reversed
template<class mint>
void inplace_fmt(const int n,mint*const f,bool inv){
	static constexpr uint mod=mint::mod;
	static constexpr uint mod2=mod*2;
	static const int L=30;
	static mint g[L],ig[L],p2[L];
	if(g[0].v==0){
		rep(i,L){
			mint w=-mint::root().pow(((mod-1)>>(i+2))*3);
			g[i]=w;
			ig[i]=w.inv();
			p2[i]=mint(1<<i).inv();
		}
	}
	if(!inv){
		int b=n;
		if(b>>=1){//input:[0,mod)
			rep(i,b){
				uint x=f[i+b].v;
				f[i+b].v=f[i].v+mod-x;
				f[i].v+=x;
			}
		}
		if(b>>=1){//input:[0,mod*2)
			mint p=1;
			for(int i=0,k=0;i<n;i+=b*2){
				rng(j,i,i+b){
					uint x=(f[j+b]*p).v;
					f[j+b].v=f[j].v+mod-x;
					f[j].v+=x;
				}
				p*=g[__builtin_ctz(++k)];
			}
		}
		while(b){
			if(b>>=1){//input:[0,mod*3)
				mint p=1;
				for(int i=0,k=0;i<n;i+=b*2){
					rng(j,i,i+b){
						uint x=(f[j+b]*p).v;
						f[j+b].v=f[j].v+mod-x;
						f[j].v+=x;
					}
					p*=g[__builtin_ctz(++k)];
				}
			}
			if(b>>=1){//input:[0,mod*4)
				mint p=1;
				for(int i=0,k=0;i<n;i+=b*2){
					rng(j,i,i+b){
						uint x=(f[j+b]*p).v;
						f[j].v=(f[j].v<mod2?f[j].v:f[j].v-mod2);
						f[j+b].v=f[j].v+mod-x;
						f[j].v+=x;
					}
					p*=g[__builtin_ctz(++k)];
				}
			}
		}
	}else{
		int b=1;
		if(b<n/2){//input:[0,mod)
			mint p=1;
			for(int i=0,k=0;i<n;i+=b*2){
				rng(j,i,i+b){
					ull x=f[j].v+mod-f[j+b].v;
					f[j].v+=f[j+b].v;
					f[j+b].v=x*p.v%mod;
				}
				p*=ig[__builtin_ctz(++k)];
			}
			b<<=1;
		}
		for(;b<n/2;b<<=1){
			mint p=1;
			for(int i=0,k=0;i<n;i+=b*2){
				rng(j,i,i+b/2){//input:[0,mod*2)
					ull x=f[j].v+mod2-f[j+b].v;
					f[j].v+=f[j+b].v;
					f[j].v=(f[j].v)<mod2?f[j].v:f[j].v-mod2;
					f[j+b].v=x*p.v%mod;
				}
				rng(j,i+b/2,i+b){//input:[0,mod)
					ull x=f[j].v+mod-f[j+b].v;
					f[j].v+=f[j+b].v;
					f[j+b].v=x*p.v%mod;
				}
				p*=ig[__builtin_ctz(++k)];
			}
		}
		if(b<n){//input:[0,mod*2)
			rep(i,b){
				uint x=f[i+b].v;
				f[i+b].v=f[i].v+mod2-x;
				f[i].v+=x;
			}
		}
		mint z=p2[__lg(n)];
		rep(i,n)f[i]*=z;
	}
}

template<class mint>
void inplace_fmt(vector<mint>&f,bool inv){
	inplace_fmt(si(f),f.data(),inv);
}

template<class mint>
void half_fmt(const int n,mint*const f){
	static constexpr uint mod=mint::mod;
	static constexpr uint mod2=mod*2;
	static const int L=30;
	static mint g[L],h[L];
	if(g[0].v==0){
		rep(i,L){
			g[i]=-mint::root().pow(((mod-1)>>(i+2))*3);
			h[i]=mint::root().pow((mod-1)>>(i+2));
		}
	}
	int b=n;
	int lv=0;
	if(b>>=1){//input:[0,mod)
		mint p=h[lv++];
		for(int i=0,k=0;i<n;i+=b*2){
			rng(j,i,i+b){
				uint x=(f[j+b]*p).v;
				f[j+b].v=f[j].v+mod-x;
				f[j].v+=x;
			}
			p*=g[__builtin_ctz(++k)];
		}
	}
	if(b>>=1){//input:[0,mod*2)
		mint p=h[lv++];
		for(int i=0,k=0;i<n;i+=b*2){
			rng(j,i,i+b){
				uint x=(f[j+b]*p).v;
				f[j+b].v=f[j].v+mod-x;
				f[j].v+=x;
			}
			p*=g[__builtin_ctz(++k)];
		}
	}
	while(b){
		if(b>>=1){//input:[0,mod*3)
			mint p=h[lv++];
			for(int i=0,k=0;i<n;i+=b*2){
				rng(j,i,i+b){
					uint x=(f[j+b]*p).v;
					f[j+b].v=f[j].v+mod-x;
					f[j].v+=x;
				}
				p*=g[__builtin_ctz(++k)];
			}
		}
		if(b>>=1){//input:[0,mod*4)
			mint p=h[lv++];
			for(int i=0,k=0;i<n;i+=b*2){
				rng(j,i,i+b){
					uint x=(f[j+b]*p).v;
					f[j].v=(f[j].v<mod2?f[j].v:f[j].v-mod2);
					f[j+b].v=f[j].v+mod-x;
					f[j].v+=x;
				}
				p*=g[__builtin_ctz(++k)];
			}
		}
	}
}

template<class mint>
void half_fmt(vector<mint>&f){
	half_fmt(si(f),f.data());
}

template<class mint>
vc<mint> multiply(vc<mint> x,const vc<mint>&y,bool same=false){
	int n=si(x)+si(y)-1;
	int s=1;
	while(s<n)s*=2;
	x.resize(s);inplace_fmt(x,false);
	if(!same){
		vc<mint> z(s);
		rep(i,si(y))z[i]=y[i];
		inplace_fmt(z,false);
		rep(i,s)x[i]*=z[i];
	}else{
		rep(i,s)x[i]*=x[i];
	}
	inplace_fmt(x,true);x.resize(n);
	return x;
}

constexpr modinfo base{998244353,3};
using mint=modular<base>;

const int vmax=1000010;
mint fact[vmax],finv[vmax],invs[vmax];
void initfact(){
	fact[0]=1;
	rng(i,1,vmax)
		fact[i]=fact[i-1]*i;
	finv[vmax-1]=fact[vmax-1].inv();
	for(int i=vmax-2;i>=0;i--)
		finv[i]=finv[i+1]*(i+1);
	for(int i=vmax-1;i>=1;i--)
		invs[i]=finv[i]*fact[i-1];
}

mint binom(int a,int b){
	return fact[a+b]*finv[a]*finv[b];
}

vc<mint> hori(vc<mint>x,int h){
	int w=si(x)-1;
	vc<mint>y(w+1);
	rep(i,w+1)y[i]=binom(i,h);
	auto z=multiply(x,y);
	z.resize(w+1);
	return z;
}

vc<mint> vert(vc<mint>x,int h){
	int w=si(x)-1;
	rep(i,w+1)x[i]*=finv[w-i];
	vc<mint> y(fact,fact+(w+h+1));
	auto z=multiply(x,y);
	vc<mint> res(h+1);
	rep(i,h+1)res[i]=z[w+i]*finv[i];
	return res;
}

vc<mint> advance(vi a,int h,vc<mint> up){
	{
		int cnt=0;
		rep(i,si(a))if(a[i]<0)cnt++;else break;
		a.erase(a.bg,a.bg+cnt);
		up.erase(up.bg,up.bg+cnt);
	}
	int n=si(a);
	assert(si(up)==n+1);
	if(n<=250||h<=250){
		vc<mint> res(h+1);
		rep(i,h+1){
			rep(j,n)if(a[j]>=i){
				up[j+1]+=up[j];
			}
			res[i]=up[n];
		}
		return res;
	}
	int t=(n+h)/2;
	int x=0,y=0;
	while(x+y<t){
		if(x==n||y<a[x])y++;
		else x++;
	}
	vc<mint> res(h+1);
	vc<mint> nx(n-x+1);
	{
		auto ue=hori(vc<mint>(x+all(up)),y);
		rep(i,n-x+1)nx[i]=ue[i];
	}
	{
		auto migi=vert(vc<mint>(x+all(up)),y);
		rep(i,y+1)res[i]+=migi[i];
	}
	if(x){
		auto hidari=advance(vi(a.bg,a.bg+x-1),a[x-1],vc<mint>(up.bg,up.bg+x));
		hidari.resize(y+1);
		{
			auto ue=vert(hidari,n-x);
			rep(i,n-x+1)nx[i]+=ue[i];
		}
		{
			auto migi=hori(hidari,n-x);
			rep(i,y+1)res[i]+=migi[i];
		}
	}
	if(y<h){
		vi b(x+all(a));
		for(auto&v:b)v-=y+1;
		auto migi=advance(b,h-y-1,nx);
		rep(i,h-y)res[y+1+i]=migi[i];
	}
	return res;
}

void slv(){
	vi a;
  string s;cin>>s;
  int cnt=0;
  for(auto c:s){
    if(c=='B'){
      cnt++;
    }
    else{
      a.push_back(cnt);
    }
  }
	int n=a.size();
  if(n==0){
    cout<<1<<endl;
    return;
  }
	vc<mint> up(n+1);
	up[0]=1;
	auto ans=advance(a,a[n-1],up);
	cout<<ans[a[n-1]].v<<"\n";
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	initfact();
	
	int t=1;
	rep(_,t)slv();
}
0