感觉挺 educational 的。
观察最终形态,发现根据洞分段,有且只有一段没被覆盖,并且左端是向左的脚印,右端是向右的脚印。
最终状态就这几种了,直接枚举,概率乘贡献即可。
发现左端和右端不影响到对方是对称的,直接求出一边的概率。
设 \(f_i\) 为 \(i\) 个洞,填满往左走的脚印,不影响到右边的洞的方案数。
那么每次实际上只用规定选到最左的洞,不往右走即可。有转移:
\[f_i = (1 - \frac{1}{2i}) f_{i-1}
\]
最后直接计算即可。
时间复杂度 \(O(n)\)。
code
// Problem: E - Paw
// Contest: AtCoder - AtCoder Regular Contest 132
// URL: https://atcoder.jp/contests/arc132/tasks/arc132_e
// Memory Limit: 1024 MB
// Time Limit: 2000 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 = 1000100;
const int N = 1000000;
const ll mod = 998244353;
ll n, a[maxn], m, inv[maxn], f[maxn], b[maxn];
char s[maxn];
void init() {
inv[1] = 1;
for (int i = 2; i <= N; ++i) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
}
void solve() {
scanf("%lld%s", &n, s + 1);
a[++m] = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] == '.') {
a[++m] = i;
}
b[i] = b[i - 1] + (s[i] == '<');
}
a[++m] = n + 1;
f[0] = 1;
for (int i = 1; i <= n; ++i) {
f[i] = f[i - 1] * (mod + 1 - inv[i * 2]) % mod;
}
ll ans = 0;
for (int i = 1; i < m; ++i) {
ans = (ans + (b[a[i + 1] - 1] - b[a[i]] + a[i]) * f[i - 1] % mod * f[m - i - 1] % mod) % mod;
}
printf("%lld\n", ans);
}
int main() {
init();
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest 132 Pawatcoder regular contest 132 132e arc paw atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest 167 atcoder regular contest builder