ABC297F 题解

标签：return int 题解 ll ABC297F ans binom mod

容斥萌萌题

给你一个 \(H\times W\) 的棋盘，问在棋盘上随机撒 \(k\) 个点，能够围住这 \(k\) 个点的最小子矩形的期望面积

考虑枚举子矩形可以直接转成计数
问题转变为在 \(n\times m\) 的矩形中撒 \(k\) 个点，有多少种方案使得四条边上均至少有一个点
答案乘上矩形面积再除以所有撒点的方法数就是答案

考虑怎么算这个东西，对四条边分别容斥即可
所有撒点的方案有

\[\binom {nm}{k} \]

种
分别钦定四条边不撒，那么一共有

\[2\binom{(n-1)m}{k}+2\binom{n(m-1)}{k} \]

种方案
钦定两条边不撒，一共有

\[\binom{(n-2){m}}{k}+\binom{n(m-2)}{k}+4\binom{(n-1)(m-1)}{k} \]

种方案
钦定三条边就是

\[2\binom{(n-2)(m-1)}{k}+2\binom{(n-1)(m-2)}{k} \]

四条边就是

\[\binom{(n-2)(m-2)}{k} \]

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const ll mod = 998244353;

inline ll f_pow(ll x, int k = mod - 2) {
	ll base = 1;
	for(; k; k >>= 1, x = (x * x) % mod)
		if(k & 1)
			base = (base * x) % mod;
	return base;
}

ll n, m, k;
ll fac[N], ifac[N];

void factory() {
	fac[0] = 1;
	for(int i = 1; i < N; i++)
		fac[i] = fac[i-1] * i % mod;

	ifac[N-1] = f_pow(fac[N-1]);
	for(int i = N - 2; i >= 0; i--) {
		ifac[i] = ifac[i+1] * (i+1) % mod;
	}
}

ll Plus(ll a, ll b) {
	a += b;
	return a > mod ? a - mod : a;
}
ll Minu(ll a, ll b) {
	a -= b;
	return a < 0 ? a + mod : a;
}

ll binom(int a, int b) {
	if(a < b || a < 0 || b < 0)
		return 0;
	return fac[a] * ifac[a - b] % mod * ifac[b] % mod;
}

ll calc(int a, int b) {
	ll ans = binom(a * b, k);

	ll t;
	t = Plus(binom((a-1) * b, k) % mod, binom(a * (b-1), k) % mod);
	t = t * 2 % mod;
	ans = Minu(ans, t);

	ans = Plus(ans, binom((a-2) * b, k));
	ans = Plus(ans, binom(a * (b-2), k));
	ans = Plus(ans, (ll)4 * binom((a-1) * (b-1), k) % mod);

	ans = Minu(ans, (ll)2 * binom((a-2) * (b-1), k) % mod);
	ans = Minu(ans, (ll)2 * binom((a-1) * (b-2), k) % mod);

	ans = Plus(ans, binom((a-2) * (b-2), k));
	return ans;
}

int main() {
	factory();
	cin >> n >> m >> k;
	ll all = binom(n * m, k);

	if(k == 1) {
		printf("%d\n", 1);
		return 0;
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			ll t = calc(i, j) * i % mod * j % mod;
			t = t * (n - i + 1) % mod;
			t = t * (m - j + 1) % mod;
			ans = Plus(ans, t);
		}
	}
	printf("%lld\n", ans * f_pow(all) % mod);
	return 0;
}

标签：return,int,题解,ll,ABC297F,ans,binom,mod
From： https://www.cnblogs.com/lostintianyi/p/17378398.html