abc297F - Minimum Bounding Box 2

abc297F - Minimum Bounding Box 2

题意：n*m的网格，在上面随机选k个不重复的点，问能够包含这k个点的最小的矩形的面积的期望值。

我们可以考虑每个点对和的贡献，直接算并不好算，我们可以考虑哪些矩形不会包含它，就是在四个方向上选k个点（比如在横坐标小于x的点中选k个），然后有四块区域的被算了两次，减去即可。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#include<set>
#include<unordered_map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
//typedef __int128 i128;
const int N=1e6+5;
const ll inf=1ll<<60;
const ll mo=998244353;
ll n,m,k,fac[N],inv[N],t,ans,tot;
ll power(ll a,ll b){
	ll t=1,y=a;
	while (b) {
		if (b&1) t=t*y%mo;
		y=y*y%mo;
		b/=2;
	}
	return t;
}
ll C(ll n,ll m){
	if (n<m) return 0;
	return fac[n]*inv[m]%mo*inv[n-m]%mo;
}
void add(ll &x,ll y){
	x=(x+y)%mo;
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	
	fac[0]=1;
	fo(i,1,N-1) fac[i]=fac[i-1]*i%mo;
	inv[N-1]=power(fac[N-1], mo-2);
	fd(i,N-2,0) inv[i]=inv[i+1]*(i+1ll)%mo;
	
	scanf("%lld %lld %lld",&n,&m,&k);
	
	tot=C(n*m,k);
	fo(i,1,n) fo(j,1,m) {
		t=C((i-1)*m, k)+C((n-i)*m, k)+C((j-1)*n, k)+C((m-j)*n, k);
		t-=C((i-1)*(j-1), k)+C((i-1)*(m-j),k)+C((n-i)*(j-1),k)+C((n-i)*(m-j),k);
		t=(tot-t+mo)%mo;
		
//		printf("%lld %lld %lld\n",i,j,t);
		ans=(ans+t)%mo;
	}
	
	ans=ans*power(tot, mo-2)%mo;
	printf("%lld",ans);
	return 0;
}