ARC150D Removing Gacha（组合）

ARC150D Removing Gacha

有一棵 \(N\) 个白点的树根为 \(1\)，每次等概率随机选一个到 \(1\) 的路径上有白点的点涂黑，问期望几次整棵树被涂黑。模 \(998244353\)。

CODE

首先手玩可以发现对于每个深度，每个此深度的点对答案的贡献是一样的。所以只需要求出每个深度的贡献，然后找规律（代码在底下）发现深度 \(i\)（根深度为 \(1\)）的贡献为 \(\sum_{j = 1} ^ i \frac{1}{j}\)。

CODE 找规律

#include <bits/stdc++.h>
#define R(i, n) for (int i = 0; i < (n); ++i)
#define L(i, n) for (int i = (n) - 1; i >= 0; --i)
#define N(a) int((a).size())
#define V(a) (a).begin(), (a).end()
#define X(a) cerr << #a << " = " << a
#define $ << ' '
#define E << '\n'
using namespace std;
using LS = long long;
template<typename U>
ostream& operator<<(ostream& ost, const vector<U>& a) {
	for (const U& x : a) ost << x $;
	return ost;
}
// constexpr int xN = 200000 + 7;
struct frac {
	LS x, y;
	constexpr frac() : x(), y(1) {}
	frac(const LS& _x) : x(_x), y(1) {}
	frac(const LS& _x, const LS& _y) : x(_x), y(_y) {
		LS g = __gcd(x, y);
		x /= g;
		y /= g;
	}
};
frac operator~(const frac& a) {
	assert(a.y);
	return frac(a.y, a.x);
}
frac operator+(const frac& a, const frac& b) {
	return frac(a.x * b.y + b.x * a.y, a.y * b.y);
}
frac operator-(const frac& a, const frac& b) {
	return frac(a.x * b.y - b.x * a.y, a.y * b.y);
}
frac operator*(const frac& a, const frac& b) {
	return frac(a.x * b.x, a.y * b.y);
}
frac operator/(const frac& a, const frac& b) {
	return a * ~b;
}
ostream& operator<<(ostream& ost, const frac& a) {
	return ost << a.x $ << '/' $ << a.y;
}
constexpr int xN = 10 + 7, xs = 1 << 10; 
int N, p[xN];
frac f[xs], res[xN];
bool vis[xs];
frac F(int s) {
	if (vis[s]) return f[s];
	vis[s] = true;
	frac& res = f[s] = frac();
	if (s == (1 << N) - 1) return res = frac();
	int c = 0, tot = 0, is_good = true;
	R(u, N) {
		is_good &= s >> u & 1;
		if (is_good) continue;
		tot += 1;
		if (s >> u & 1) c += 1;
		else res = res + F(s ^ 1 << u);
	}
	res = (res / tot + 1) / frac(tot - c, tot);
	return res;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for (N = 1; N <= 10; ++N) {
		R(s, 1 << N) vis[s] = false;
		X(N) $;
		res[N] = F(0);
		X(res[N]) E;
	}
	for (int i = 10; i >= 1; --i) res[i] = res[i] - res[i - 1];
	X(vector<frac>(res + 1, res + 11)) E;
	for (int i = 10; i >= 1; --i) res[i] = res[i] - res[i - 1];
	X(vector<frac>(res + 1, res + 11)) E;
	frac r = res[1] + res[2] * 2 + res[3];
	X(r) E;
	// cin >> N;
	// for (int u = 1; u < N; ++u) cin >> p[u], --p[u];
}