AT_abc297_f [ABC297F] Minimum Bounding Box 2 题解

· · 题解

水。

题目就是说，给你一个 n \times m 的网格，现在有一个机器会将 k 个珠子随机撒进这个网格的 k 个互不相同的位置。你需要在机器随机撒放珠子后铺下一张任意大小的矩形的网，要求这张网可以罩住所有珠子并且面积最小。求这张网的面积的期望值，对 998244353 取模。

算期望，那么转换为算方案数。

容斥当然是最好的解决办法！

考虑枚举网格上的每个位置 (i,j)，计算出有多少张符合题目要求的网。

但是这东西看上去不大好求啊！

常规套路，正难则反呗。不能正着直接求，那咱就反过来，容斥。

所以现在需要计算的就是有多少张网完全不包含 (i,j) 这个位置！

让剩下 k-1 个珠子都在 (i,j) 的某一边，一共上下左右四个方向。多在草稿纸上画几张图就能推出式子：

\binom{(i-1) \times m}{k} + \binom{(n-i) \times m}{k} + \binom{(j-1) \times n}{k} + \binom{(m-j) \times n}{k}

令这个玩意儿为 A。

但是这样对……吗？

没错确实不对，因为会重复算啊！比方说左上角的，就会被上和左各算一次，这可不行！

因此就轮到咱们的容斥出场啦！

左上角、右上角、左下角、右下角都会重复算，画几张图摇一摇，又会出现下面的公式：

\binom{(i-1) \times (j-1)}{k} + \binom{(i-1) \times (m-j)}{k} + \binom{(n-i) \times (j-1)}{k} + \binom{(n-i) \times (m-j)}{k}

咱又令这家伙为 B。

那么 (i,j) 的真实贡献就可以算出来啦！

但在此之前还需要算一个 All = \dbinom{n \times m}{k}，就是所有的情况数。

所以最终 (i,j) 的贡献为 All-A+B。

说到这里，整个做法也就显而易见了。枚举每个 (i,j)，使用上面的公式依次计算就好了。记得一开始要预处理，因为组合数需要 O(1) 计算。然后别忘了取模。

时间复杂度 O(n \times m)，稳过好吧。

代码也是非常短的。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int K = 1e6+5;
const LL mod = 998244353;
LL n,m,k,p[K],v[K],All,ans;
LL QP(LL x,LL y){LL as=1;while(y){if(y&1)as=(as*x)%mod;x=(x*x)%mod,y>>=1;}return as;}
LL C(LL x,LL y){if(x<y)return 0;return ((p[x]*v[y])%mod*v[x-y])%mod;}
int main(){
    cin>>n>>m>>k;p[0]=1,v[0]=1,ans=0;
    for(LL i=1;i<=n*m;i++)p[i]=(p[i-1]*i)%mod,v[i]=QP(p[i],mod-2);All=C(n*m,k);
    for(LL i=1;i<=n;i++)for(LL j=1;j<=m;j++){
        LL add=(C((i-1)*m,k)+C((n-i)*m,k)+C((j-1)*n,k)+C((m-j)*n,k))%mod;
        LL div=(C((i-1)*(j-1),k)+C((n-i)*(j-1),k)+C((i-1)*(m-j),k)+C((n-i)*(m-j),k))%mod;
        LL now=(All-(add-div)+mod)%mod;ans=(ans+now)%mod;
    }
    cout<<(ans*QP(All,mod-2))%mod<<"\n";
    return 0;
}

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太谢谢啦！