Submission #29169532

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

int n, fac[305], ifac[305], ans;
char s[605];
int num[605][605], cost[605][605];

int add(int a, int b) {
	return a + b >= mod ? a + b - mod : a + b;
}
int dec(int a, int b) {
	return a - b < 0 ? a - b + mod : a - b; 
}
int mul(int a, int b) {
	return 1ll * a * b % mod;
}
int ksm(int a, int b = mod - 2) {
	int ret = 1;
	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) ret = mul(ret, a);
	return ret;
}

int binom(int a, int b) {
	if (a < 0 || b < 0 || a < b) return 0;
	return mul(fac[a], mul(ifac[b], ifac[a - b]));
} 

int main() {
	scanf("%d%s", &n, s + 1);
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = mul(fac[i - 1], i);
	ifac[n] = ksm(fac[n]);
	for (int i = n - 1; i; i--) ifac[i] = mul(ifac[i + 1], i + 1);
	for (int i = 1; i <= n; i++) s[n + i] = s[i];
	for (int i = 1; i < 2 * n; i++) num[i][i + 1] = 1;
	for (int len = 1; len < n; len++) {
		for (int i = 1; i + len < 2 * n; i++) {
			int j = i + len + 1;
			int c1 = (s[i] == 'R') + (s[j] == 'L');
			if (c1 == 0) continue;
			for (int k = i + 1; k < j; k++) {
				int c2 = (s[i] == 'R') * (k - i) + (s[j] == 'L') * (j - k);
				num[i][j] = add(num[i][j], mul(mul(num[i][k], num[k][j]), mul(c1, binom(len - 1, k - i - 1))));
				cost[i][j] = add(cost[i][j], mul(mul(num[i][k], num[k][j]), mul(c2, binom(len - 1, k - i - 1))));
				cost[i][j] = add(cost[i][j], mul(add(mul(cost[k][j], num[i][k]), mul(cost[i][k], num[k][j])), mul(c1, binom(len - 1, k - i - 1))));
			}
		}
	}
	for (int i = 1; i <= n; i++) ans = add(ans, cost[i][n + i]);
	printf("%d\n", mul(ans, ifac[n]));
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:32:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   32 |  scanf("%d%s", &n, s + 1);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~

Judge Result