Codeforces #732 Div1 : B. AquaMoon and Chess

Bまでは良かったけど、そこからいまいちだった回。
https://codeforces.com/contest/1545/problem/B

問題

01で構成される文字列Sが与えられる。
S中の部分文字列で"110"と"011"を任意に置換できるとき、Sが取れる値は何通りか。

解法

"11"と連続した並びが1つあると、1をS中で任意に動かせることになる。
"11"の数をn個、"0"の数をm個とすると、重複組み合わせの要領で自由に動かせる1を0の間のどこに置くかでH(n,m+1)通りの選択肢が取れる。

int T,N;
string S;
const ll mo=998244353;

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		vector<pair<int,int>> V;
		FORR(c,S) {
			if(V.size()&&V.back().first==c-'0') {
				V.back().second++;
			}
			else {
				if(c=='0' && V.size()>=2&&V.back().second%2==0) {
					V[V.size()-2].second++;
				}
				else {
					V.push_back({c-'0',1});
				}
			}
		}
		
		int span=1;
		int num=0;
		FORR2(c,a,V) {
			if(c==0) span+=a;
			else num+=a/2;
		}
		cout<<hcomb(span,num)<<endl;
	}
}

まとめ

気付くとシンプル。