結果

問題 No.3099 Parentheses Decomposition
コンテスト
ユーザー shobonvip
提出日時 2025-01-13 00:49:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 23 ms / 2,000 ms
コード長 689 bytes
コンパイル時間 2,228 ms
コンパイル使用メモリ 196,988 KB
実行使用メモリ 7,600 KB
最終ジャッジ日時 2025-01-13 00:49:56
合計ジャッジ時間 3,345 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/modint>
typedef atcoder::modint998244353 mint;

int main() {
	int n; cin >> n;
	string s; cin >> s;
	int type = 0;
	if (s[1] == ')') type = 1;

	if (type == 0) {
		vector<mint> fact(n+1), factinv(n+1);
		fact[0] = 1;
		for (int i=1; i<=n; i++) fact[i] = fact[i-1] * i;
		factinv[n] = fact[n].inv();
		for (int i=n-1; i>=0; i--) factinv[i] = factinv[i+1] * (i+1);

		auto cmb = [&](int n, int k) -> mint {
			return fact[n] * factinv[k] * factinv[n-k];
		};

		mint ans = 0;
		for (int i=0; i<=n/2; i++) {
			ans += cmb(n/2,i) * cmb(n/2,i);
		}
		cout << ans.val() << endl;
	}else{
		cout << mint(2).pow(n/2).val() << endl;
	}
}
0