[ABC297F] Minimum Bounding Box 2 题解

容斥真有趣。

有一个性质：

• 两个相同的子矩阵，对答案的贡献一定相同。

所以就只需要枚举矩阵大小即可。

我们设当前矩阵长 \(i\) 宽 \(j\)（对应的，\(H\) 为长，\(W\) 为宽），假如要给答案做出贡献，矩阵的四条边一定都有点，发现可以容斥了。

1. 至少 \(0\) 条边上有点的方案数为 \(a=C_{i\times j}^k\)。
2. 至少 \(1\) 条边上有点的方案数为 \(b=2\times C_{(i-1)\times j}^k+2\times C_{i\times(j-1)}^k\)。
3. 至少 \(2\) 条边上有点的方案数为 \(c=4\times C_{(i-1)\times(j-1)}^k+C_{(i-2)\times j}^k+C_{i\times(j-2)}^k\)。
4. 至少 \(3\) 条边上有点的方案数为 \(d=2\times C_{(i-1)\times(j-2)}^k+2\times C_{(i-2)\times(j-1)}^k\)。
5. 至少 \(4\) 条边上有点的方案数为 \(e=C_{(i-2)\times(j-2)}^k\)。

根据容斥，答案应为 \(a-b+c-d+e\)。

长 \(i\) 宽 \(j\) 的矩阵有 \((H-i+1)\times(W-j+1)\) 个，每个大小为 \(i\times j\)，所以贡献即为：

时间复杂度 \(O(HW)\)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=998244353;
const int N=1005;
ll qpow(ll x,int y){
    ll re=1;
    while(y){
        if(y&1) re=re*x%p;
        x=x*x%p;
        y>>=1;
    }return re;
}ll n,m,k,sum;
ll jc[N*N],inv[N*N];
void init(){
    jc[0]=inv[0]=1;
    for(ll i=1;i<=n*m;i++){
        jc[i]=jc[i-1]*i%p;
        inv[i]=qpow(jc[i],p-2);
    }
}ll C(int x,int y){
    if(x<y) return 0;
    if(!y||x==y) return 1;
    return jc[x]*inv[y]%p*inv[x-y]%p;
}int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    if(k==1){
        cout<<1;
        return 0;
    }init();
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=m;j++){
            if(i*j<k) continue;
            ll x=C(i*j,k);
            x=((x-2*C((i-1)*j,k)%p)%p+p)%p;
            x=((x-2*C((j-1)*i,k)%p)%p+p)%p;
            x=(x+4*C((i-1)*(j-1),k)%p)%p;
            x=(x+C((i-2)*j,k)+C((j-2)*i,k))%p;
            x=((x-2*C((i-1)*(j-2),k))%p+p)%p;
            x=((x-2*C((i-2)*(j-1),k))%p+p)%p;
            x=(x+C((i-2)*(j-2),k))%p;
            sum=(sum+(n-i+1)*(m-j+1)*i*j%p*x%p)%p;
        }
    cout<<sum*qpow(C(n*m,k),p-2)%p;
    return 0;
}