提出 #64377729

---

ソースコード 拡げる

import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static final int MOD = 998244353;

	static int add(int a, int b) {
		int res = a + b;
		return res >= MOD ? res - MOD : res;
	}

	static int sub(int a, int b) {
		int res = a - b;
		return res < 0 ? res + MOD : res;
	}

	static int mul(int a, int b) {
		int res = (int) ((long) a * b % MOD);
		return res < 0 ? res + MOD : res;
	}

	static int pow(int a, int e) {
		if (e == 0) {
			return 1;
		}
		int r = a;
		for (int i = 30 - Integer.numberOfLeadingZeros(e); i >= 0; i--) {
			r = mul(r, r);
			if ((e & (1 << i)) != 0) {
				r = mul(r, a);
			}
		}
		return r;
	}

	static int inv(int a) {
		return pow(a, MOD - 2);
	}

	static void solve() throws Exception {
		int n = scanInt(), k = scanInt();
		String s = scanString();
		int facts[] = new int[n + 2];
		facts[0] = 1;
		for (int i = 1; i < facts.length; i++) {
			facts[i] = mul(facts[i - 1], i);
		}
		int factsInv[] = new int[facts.length];
		factsInv[facts.length - 1] = inv(facts[facts.length - 1]);
		for (int i = facts.length - 1; i > 0; i--) {
			factsInv[i - 1] = mul(factsInv[i], i);
		}
		int shortRuns = 0, longRuns = 0, sum = 0;
		for (int i = 0; i < k; i++) {
			if (s.charAt(i) == '(') {
				if (longRuns == 0) {
					if (sum == 0) {
						++shortRuns;
					} else {
						--shortRuns;
						++longRuns;
					}
				} else {
					if (sum == 0) {
						++longRuns;
					}
				}
				++sum;
			} else {
				--sum;
			}
		}
		int ans = 0;
		if (longRuns == 0) {
			for (int i = shortRuns; 2 * i <= n; i++) {
				ans = add(ans, mul(facts[n + 1], mul(factsInv[2 * i + 1], factsInv[n - 2 * i])));
			}
		} else {
			ans = mul(facts[n - k + 2 * shortRuns + longRuns + 1],
				mul(factsInv[2 * shortRuns + longRuns + 1], factsInv[n - k]));
			if (n > k) {
				ans = add(ans, mul(mul(facts[n - k + 2 * shortRuns + longRuns + 1],
					mul(factsInv[2 * shortRuns + longRuns + 2], factsInv[n - k - 1])), longRuns));
			}
		}
		out.println(ans);
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}

提出情報

ジャッジ結果