考虑期望转计数,方案数显然是 \(n!\)(第 \(i\) 次操作有 \(n - i + 1\) 个人可供选择),所以问题转化为求所有方案的代价之和。
考虑倒着做,变成先放一个人,然后依次放 \(n - 1\) 个人,每次放的这个人可以让左边的人的 \(S\) 变成 R
,代价是他与他左边的人的距离,或让右边的人的 \(S\) 变成 L
,代价是他与他右边的人的距离。求 \(S\) 符合题面中给的 \(S\) 的前提下的代价之和。
考虑区间 dp,设 \(f_{i, j}\) 为在 \(i, j\) 都放好的前提下,把 \([i + 1, j - 1]\) 放好的代价和,\(g_{i, j}\) 为相应的方案数。枚举 \([i + 1, j - 1]\) 中第一个被放的人即可转移:
\[f_{i, j} \gets \binom{j - i - 2}{k - i - 1} \times (g_{i, k} \times g_{k, j} \times c2 + g_{i, k} \times c1 \times f_{k, j} + g_{k, j} \times c1 \times f_{i, k})
\]
\[g_{i, j} \gets \binom{j - i - 2}{k - i - 1} \times g_{i, k} \times g_{k, j} \times c1
\]
其中 \(c1 = [S_i = \texttt{R}] + [S_j = \texttt{L}]\),表示 \(k\) 有多少种选它左边或右边的人的选择;\(c2 = [S_i = \texttt{R}] \times (k - i) + [S_j = \texttt{L}] \times (j - k)\),表示对应的代价和。要合并 \([i, k]\) 和 \([k, j]\),先要合并操作序列,方案数为 \(\binom{j - i - 2}{k - i - 1}\);然后计算选择 \(k\) 的代价和 \(g_{i, k} \times g_{k, j} \times c2\),然后再把 \(f_{i, k}\) 和 \(f_{k, j}\) 乘上出现次数加到 \(f_{i, j}\)。
注意下标的处理,因为这是个环。
时间复杂度 \(O(n^3)\)。
code
// Problem: Ex - Removing People
// Contest: AtCoder - Monoxer Programming Contest 2022(AtCoder Beginner Contest 238)
// URL: https://atcoder.jp/contests/abc238/tasks/abc238_h
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 310;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, fac[maxn], ifac[maxn], f[maxn][maxn], g[maxn][maxn];
char s[maxn];
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%lld%s", &n, s + 1);
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
for (int i = 1; i < n; ++i) {
g[i][i + 1] = 1;
}
g[n][1] = 1;
for (int p = 3; p <= n + 1; ++p) {
for (int i = 1, j = p; i <= n; ++i, ++j) {
for (int k = i + 1; k < j; ++k) {
int nk = (k > n ? k - n : k), nj = (j > n ? j - n : j);
ll c1 = (s[i] == 'R') + (s[nj] == 'L'), c2 = (s[i] == 'R' ? k - i : 0) + (s[nj] == 'L' ? j - k : 0);
g[i][nj] = (g[i][nj] + g[i][nk] * g[nk][nj] % mod * c1 % mod * C(j - i - 2, k - i - 1) % mod) % mod;
f[i][nj] = (f[i][nj] + C(j - i - 2, k - i - 1) * (g[i][nk] * g[nk][nj] % mod * c2 % mod + g[i][nk] * c1 % mod * f[nk][nj] % mod + g[nk][nj] * c1 % mod * f[i][nk] % mod) % mod) % mod;
}
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans = (ans + f[i][i]) % mod;
}
printf("%lld\n", ans * ifac[n] % mod);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner Removing AtCoder Contest Peoplebeginner removing atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 310