526互联

ABC297F AtCoder Beginner Contest 297 F - Minimum Bounding Box 2

发布时间 2023-04-17 19:36:15作者: zrzring

https://atcoder.jp/contests/abc297/tasks/abc297_f

在 \(n \times m\) 的棋盘上放置 \(k\) 个棋子，记矩形 A 为能覆盖所有 \(k\) 个棋子的最小的矩形，求 A 的面积的期望

将问题反过来考虑，枚举每种矩形有多少种放置棋子的方案，对于一个 \(n \times m\) 的矩形，我们可以用容斥的方法求出正好覆盖它的方案数

image-20230417192721406

即总方案数减去没有达到任意一条边界的方案数，其中有重复计算的贡献，容斥四层即可消除重复贡献，具体详见代码。

const int N = 1e6 + 10, mod = 998244353;

int mul[N];

int qpow(int a, int x) {
	int res = 1;
	while (x) {
		if (x & 1) res = 1ll * res * a % mod; a = 1ll * a * a % mod; x >>= 1;
	}
	return res;
}

void MOD(i64 &x) {
	x = (x % mod + mod) % mod;
}

int main() {
	int n = read(), m = read(), k = read(), mul[n * m + 1], C[n + 1][m + 1] = {0};
	mul[0] = 1;
	for (int i = 1; i <= n * m; i++) mul[i] = 1ll * mul[i - 1] * i % mod;
	auto _C = [&](int n, int m) -> int {
		if (n < m) return 0;
		return 1ll * mul[n] * qpow(mul[m], mod - 2) % mod * qpow(mul[n - m], mod - 2) % mod;
	};
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			C[i][j] = _C(i * j, k);
		}
	}
	i64 ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (i * j < k) continue; i64 res = 0;
			MOD(res += C[i][j]);
			if (i > 1) MOD(res -= 2ll * C[i - 1][j] % mod);
			if (j > 1) MOD(res -= 2ll * C[i][j - 1] % mod);
			if (i > 2) MOD(res += C[i - 2][j] % mod);
			if (j > 2) MOD(res += C[i][j - 2] % mod);
			if (i > 1 && j > 1) MOD(res += 4ll * C[i - 1][j - 1]);
			if (i > 2 && j > 1) MOD(res -= 2ll * C[i - 2][j - 1] % mod);
			if (i > 1 && j > 2) MOD(res -= 2ll * C[i - 1][j - 2] % mod);
			if (i > 2 && j > 2) MOD(res += C[i - 2][j - 2]);
			// printf("%d ", res);
			MOD(ans += res * (i * j) % mod * ((n - i + 1) * (m - j + 1)) % mod);
		}
		// puts("");
	}
	printf("%lld", ans * qpow(_C(n * m, k), mod - 2) % mod);
	return 0;
}