Codeforces #604 Div1 D2. Beautiful Bracket Sequence

この問題あんまり記憶にないなぁ。
https://codeforces.com/contest/1264/problem/D2

問題

括弧列をなす文字列が与えられる。
ただし一部の文字は未確定である。

未確定の文字を開きカッコ・閉じカッコのいずれにするかは、未確定の文字n個に対し2^n通り考えられる。
2^n通りの文字列に対し、部分列のなかで最もカッコがネストしている数を数え、その和を求めよ。

解法

開きカッコに対し、それが最もネストしたカッコ列の一部になるケースを数え上げることを考える。
自身の前に現れる開きカッコの数より、自身の後に現れる閉じカッコが多ければ条件を満たす。
この時、未確定の文字のある一定数が開きカッコまたは閉じカッコの指定された方になっていればいいので、Combinationの区間和になる。
事前にその和を求めておくとよい。

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

ll comb(ll N_, ll C_) {
	const int NUM_=1400001;
	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(int P_,int Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

int A[1010101],B[1010101];
int L[1010101],R[1010101];
ll pat[2][1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FOR(i,N) {
		A[i+1]=A[i], L[i+1]=L[i];
		if(S[i]=='(') A[i+1]++;
		if(S[i]=='?') L[i+1]++;
	}
	for(i=N-1;i>=0;i--) {
		B[i+1]=B[i+2];
		R[i+1]=R[i+2];
		if(S[i]==')') B[i+1]++;
		if(S[i]=='?') R[i+1]++;
	}
	
	for(i=L[N];i>=0;i--) pat[0][i]=(comb(L[N],i)+pat[0][i+1])%mo;
	for(i=L[N]-1;i>=0;i--) pat[1][i]=(comb(L[N]-1,i)+pat[1][i+1])%mo;
	
	ll ret=0;
	FOR(i,N-1) if(S[i]=='(' || S[i]=='?') {
		int X=1+A[i];
		int Y=B[i+2];
		int C=L[i];
		
		ret+=pat[S[i]=='?'][max(0,X-Y+C)];
	}
	
	cout<<ret%mo<<endl;
}

まとめ

なんでこの問題こんなに記憶にないんだろう。