結果

問題 No.3138 Minimum Bracket Subsequence
ユーザー 👑 potato167
提出日時 2025-04-27 19:05:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 1,015 bytes
コンパイル時間 993 ms
コンパイル使用メモリ 76,324 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2025-04-27 19:07:19
合計ジャッジ時間 2,362 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/modint>
using mint = atcoder::modint998244353;
#include <iostream>
#include <string>
#include <vector>

mint solve(long long N, long long K, std::string S){
	int C = 0;
	for (int i = 0; i < K; i++){
		if (S[i] == ')') break;
		C++;
	}
	for (int i = K - 1; i >= 0; i--){
		if (S[i] == '(') break;
		C++;
	}
	long long R = N - K;
	if (C != K){
		mint A = 1, B = 1;
		for (int i = 1; i <= C + 1; i++){
			A *= R + i;
			B *= i;
		}
		return A * B.inv();
	}
	std::vector<mint> fact(K, 1), inv_fact(K);
	for (int i = 1; i < K; i++){
		fact[i] = fact[i - 1] * i;
	}
	inv_fact[K - 1] = fact[K - 1].inv();
	for (int i = K - 1; i > 0; i--){
		inv_fact[i - 1] = inv_fact[i] * i;
	}
	mint ans = (mint(2)).pow(N);
	mint A = 1;
	for (int i = 0; i < K; i++){
		ans -= A * inv_fact[i];
		A *= (N - i);
	}
	return ans;
}

int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

	long long N, K;
	std::cin >> N >> K;
	std::string S;
	std::cin >> S;
	std::cout << solve(N, K, S).val() << "\n";
}
0