考虑最后往左走往右走的覆盖情况。
能发现肯定是有两个洞之间,或者是第一个洞左边,最后一个洞右边没有被覆盖,而左边的都被覆盖为向左,右边的都被覆盖为向右。
大致证明就是考虑左边这一部分,如果有向右的,那么其右边的洞肯定都需要走过才行,不然会被覆盖,那么这样就可以一次性走出左边,就不合法了,右边同理。
于是考虑设 \(f_i\) 为一边有 \(i\) 个洞的概率。
假设为左边来考虑,右边同理。
如果选到了最靠右的,其就只能向左边走,否则没有要求,就有 \(f_i = f_{i - 1}\times (1 - \frac{1}{2n})\)。
那么令一共有 \(p\) 个 .
,第 \(i\) 个 .
的位置是 \(w_i\)。
选到了第 \(i\) 和 \(i + 1\) 个洞,概率就是 \(f_i\times f_{p - i}\),对应的数量就是 \(w_i + \operatorname{count}(w_i + 1, w_{i + 1} - 1)\),\(\operatorname{count}(l, r)\) 代表 \([l, r]\) 中 (
的个数。
对于每种选取都选一遍求和即可。
时间复杂度 \(O(n)\)。
代码
#include<bits/stdc++.h>
using i64 = long long;
const i64 mod = 998244353;
const int maxn = 2e5 + 10;
i64 inv[maxn], f[maxn];
char s[maxn];
int sum[maxn];
int main() {
int n; scanf("%d%s", &n, s + 1);
inv[0] = inv[1] = 1;
for (int i = 2; i <= (n << 1); i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
f[0] = 1;
for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (mod + 1 - inv[i << 1]) % mod;
std::vector<int> w; int cnt = 0;
w.push_back(0);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] == '<'), s[i] == '.' && (w.push_back(i), cnt++);
w.push_back(n + 1);
i64 ans = 0;
for (int i = 0; i + 1 < w.size(); i++) {
i64 p = f[i] * f[cnt - i] % mod;
(ans += p * (sum[w[i + 1] - 1] - sum[w[i]] + w[i])) %= mod;
}
printf("%lld\n", ans);
return 0;
}