考虑固定 \(s\) 和每个格子的颜色,最终有多少个石子被染黑。
结论: 任何时刻只有不多于两个极大同色连通块。
证明: 设 \([x,y]\) 为当前的黑连通块,\([y+1,z]\) 为白连通块。如果下一次染 \(x-1\),若 \(x-1\) 为白,则 \([x-1,z]\) 都被染为白;否则 \(x-1\) 被染为黑。下一次染 \(z+1\) 同理。
下文令 \(0\) 为白,\(1\) 为黑,记 \(c_i\) 为第 \(i\) 个格子的颜色。
- 如果 \(c_1 = c_n = 0\),最终所有石子都会被染白;
- 如果 \(c_1 = c_n = n\),最终所有石子都会被染黑;
- 如果 \(c_1 \ne c_n\),不失一般性地,假设 \(c_1 = 1, c_n = 0\)。记 \(x\) 为最大的下标满足 \(\forall i \in [1,x], c_i = c_1\),\(y\) 为最小的下标满足 \(\forall i \in [y,n], c_i = c_n\)。若 \(x + 1 = y\),最终有 \(x\) 个石子被染黑;否则先手肯定要尽快使 \(x\) 被染为黑,后手要尽快使 \(y\) 被染为白,这样中间 \(y - x - 1\) 个石子肯定归某个人了。\([1,x]\) 最后肯定被染黑,\([y,n]\) 最后肯定被染白,如果先手先到 \(x\),即 \(s - x \ge y - s\),则 \([x+1,y-1]\) 归先手;否则归后手。
这样枚举 \(s,x,y\),就得到了一个 \(O(n^3)\) 的做法。
考虑如果 \(s - x \ne y - s\),把 \(c\) 黑白翻转后,最后的染色状态与翻转前互补,则配对后两个状态的答案的和为 \(n\);如果 \(s - x = y - s\),\([x + 1, y - 1]\) 归先手,配对后两个状态的答案和为 \(n + y - x - 1\)。
设 \(ans_s\) 为初始位置为 \(s\) 时不同状态染黑石子数量的总和,可得:
\[ans_s = n2^{n-1} + \sum\limits_{x=1}^n \sum\limits_{y=1}^n [x + y = 2s \land y - x - 3 \ge 0] (y - x - 1) 2^{y-x-3}
\]
这样是 \(O(n^2)\) 的。
考虑枚举 \(y - x = 2t\),则 \(x = s - t, y = s + t\),可得:
\[ans_s = n2^{n-1} + \sum\limits_{t=1}^n [1 \le s - t \land s + t \le n \land 2t - 3 \ge 0] (2t - 1) 2^{2t - 3}
\]
\(t\) 的范围可以算出是 \([2,\min(n-s,s-1)]\),所以:
\[ans_s = n2^{n-1} + \sum\limits_{t=2}^{\min(n-s,s-1)} (2t - 1) 2^{2t - 3}
\]
设 \(f_i = \sum\limits_{t=2}^i (2t - 1) 2^{2t - 3}\),\(f\) 可以前缀和 \(O(n)\) 求出,可得:
\[ans_s = n2^{n-1} + f_{\min(n-s,s-1)}
\]
最后乘 \(\frac{1}{2^n}\) 就是期望。
至此终于以 \(O(n)\) 的时间复杂度做完了本题。
code
// Problem: E - 1D Reversi Builder
// Contest: AtCoder - AtCoder Regular Contest 109
// URL: https://atcoder.jp/contests/arc109/tasks/arc109_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 long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
int n;
ll ans[maxn], pw[maxn], inv[maxn], f[maxn];
void solve() {
scanf("%d", &n);
pw[0] = inv[0] = 1;
for (int i = 1; i <= n; ++i) {
pw[i] = pw[i - 1] * 2 % mod;
inv[i] = inv[i - 1] * inv2 % mod;
}
for (int i = 1; i <= n; ++i) {
ans[i] = pw[n - 1] * n % mod;
}
for (int i = 2; i * 2 <= n; ++i) {
f[i] = (f[i - 1] + (i * 2 - 1) * pw[i * 2 - 3] % mod) % mod;
}
for (int i = 1; i <= n; ++i) {
ans[i] = (ans[i] + f[min(n - i, i - 1)]) % mod;
}
for (int i = 1; i <= n; ++i) {
printf("%lld\n", ans[i] * inv[n] % mod);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest Builder Reversiatcoder regular contest builder atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 164 subsegments atcoder regular contest disconnected atcoder regular contest