题目描述
给定一个 \(n\) 个点的环，初始时全为白色，每次有两种操作：
-
随机选一个点（可能为黑），把它变成黑色，代价为 \(1\)；
-
选一个点，若其在环上相邻两点都为黑色，则可把它变成黑色。
求把所有点变黑期望代价，对 \(998244353\) 取模。
\(2 \le n \le 10^5\)
题解
现场得分：0/10（写的拆分数暴力，结果 n = 2 WA 了，然后还打包……）
首先观察到 2 操作不受操作顺序影响，且可以无限操作，于是将问题转化成：
不存在两个白点相邻的期望代价
即
相邻两个黑点距离 \(< 2\) 的期望代价
考虑将代价转化一下：\(\sum_\limits{i=1} i * E_i = \sum_\limits{i=1}E'_i\)，\(E'_i\) 为代价 \(\ge i\) 的概率。
我们发现这个随机选点，选到了已经选过的黑点是没有用的，于是定义已经染色了 \(i\) 个点，现在去染第 \(i+1\) 个点的期望代价，显然为 \(\frac{n}{n - i}\)。
考虑如何计算 \(E'_i\)，考虑容斥，即 \(E'_i=1-\frac{f_i}{sum_i}\)，\(f_i\) 为 \(i\) 次成功染色且已经为结束态的方案数，\(sum_i\) 为 \(i\) 次成功染色的总方案数。
考虑计算 \(f_i\)，相当于是环上 \(i\) 个黑点中插入 \(n - i\) 个白点，且中间最多插 \(1\) 个。所以 \(f_i = C(i, n - i)\)。
考虑计算 \(sum_i\)， 由于是环，所以我们得避免算重，我们不妨钦定成功染色的 \(i\) 个点中包含第 \(1\) 个点，所以 \(sum_i = C(n - 1, i - 1)\)。
代码
#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
const int N = 1e5 + 10, MOD = 998244353;
int n, f[N];
int fac[N], ifac[N];
inline void init(int n) {
fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
F(i, 2, n) fac[i] = (ll) fac[i - 1] * i % MOD, ifac[i] = (ll) (MOD - MOD / i) * ifac[MOD % i] % MOD;
F(i, 2, n) ifac[i] = (ll) ifac[i] * ifac[i - 1] % MOD;
}
inline int C(int x, int y) {
if (x < y || y < 0) return 0;
return (ll) fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;
}
inline int Quickpow(int x, int y) {
int ans = 1;
for (; y; x = (ll) x * x % MOD,y >>= 1)
if (y & 1) ans = (ll) ans * x % MOD;
return ans;
}
int ans;
signed main() {
freopen("color.in", "r", stdin);
freopen("color.out", "w", stdout);
read(n);
init(1e5);
F(i, 1, n) ans = (ans + (1 - (ll) C(i, n - i) * Quickpow(C(n - 1, i - 1), MOD - 2) % MOD + MOD) * n % MOD * Quickpow(n - i, MOD - 2)) % MOD;
cout << (ans + 1) % MOD;
return 0;
}