容斥萌萌题
给你一个 \(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;
}