yukicoder : No.3146 RE: Parentheses Counting

時間内に詰め切れず…。
https://yukicoder.me/problems/no/3146

問題

N文字の対応が取れた括弧列Tに対し、f(T)を以下のように定義する。
f(T) := 対応が付く括弧対の内側にある、"()"の個数の総和

Nが与えられるので、N文字の対応が取れたすべての括弧列Tにおけるf(T)の和を求めよ。

解法

g(n) := N=n*2の時の問題の解
とする。g(n-1)までがわかっている状態でg(n)を求めよう。
対応のついている括弧列Y,Zを用いて、Tが以下のように置けるとすると、
T="("+Y+")"+Z
f(T)をf(Y)とf(Z)と、あとはYにおける"()"の個数で表現できる。

T,Y,Zの全パターンを考えるとカタラン数C(i)を用いてとなる。

int N;
const ll mo=998244353;
const int NUM_=2400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll catalan(int n) {
	return fact[2*n]*factr[n]%mo*factr[n+1]%mo;
}
ll dp[1<<20];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
		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;
	
	ll dpS=0,cS=0;
	for(i=1;i<=1000000;i++) {
		(dp[i]=dpS*3+cS)%=mo;
		(dpS+=dp[i])%=mo;
		(cS+=catalan(i))%=mo;
	}
	
	int T;
	cin>>T;
	while(T--) {
		cin>>x;
		if(x%2) {
			cout<<0<<endl;
		}
		else {
			cout<<dp[x/2]<<endl;
		}
	}
	
	
}

まとめ

真ん中にある"()"の解への寄与を考えてしまったけど、先頭の開き括弧の対応を考えればよかったか。