[ABC127E] Cell Distance

_lyx111 · 2023-01-10 14:08:33 · 题解

[ABC127E] Cell Distance

link

分析

转换一下，先考虑 x 坐标的贡献。

考虑两个点间 x 坐标相差为 d\ ( 1\le d\le n-1) 时的贡献（ d=0 的时候没有贡献所以这里不考虑）。设这两个点的坐标为 (x_1,y_1),(x_2,y_2)，那么就有 x_1-x_2=d,1\le x_1,x_2\le n,1\le y_1,y_2\le m。

则可行的 x_1,x_2 有 n-d 对（(1,d+1),(2,d+2),\cdots,(n-d,n)），y_1,y_2 各有 m 种取法。所以像这样的点对共有 (n-d)\times m^2 对，每一对的贡献为 d，总的贡献就是 d\times (n-d)\times m^2。

每一个点对出现在选出的 k 个点中的方案数共有 C_{n\times m-2}^{k-2} （除去这两个点之外，剩下 n\times m-2 个点中，选出 k-2 个点，与这两个点组成要选出的 k 个点），那么总的贡献就是 d\times (n-d)\times m^2 \times C_{n\times m-2}^{k-2}。

同理可以计算 y 坐标的贡献，得到最终答案为：

那么就做完了。

代码

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,k;
int ans;
int ksm(int u,int v)
{
    int res=1;
    while(v)
    {
        if(v&1) res=1ll*res*u%mod;
        u=1ll*u*u%mod; v>>=1;
    }
    return res;
}
int C(int p,int q)
{
    int s=1,t=1; //s：分子，t：分母 
    for(int i=p;i>=p-q+1;i--)
        s=1ll*s*i%mod;
    for(int i=1;i<=q;i++)
        t=1ll*t*i%mod;
    return 1ll*s*ksm(t,mod-2)%mod;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int d=1;d<n;d++)
        ans=(ans+1ll*d*(n-d)%mod*m%mod*m%mod)%mod;
    for(int d=1;d<m;d++)
        ans=(ans+1ll*d*(m-d)%mod*n%mod*n%mod)%mod;
    ans=1ll*ans*C(n*m-2,k-2)%mod;
    printf("%d\n",ans);
    return 0;
}

AC记录

写在最后

蒟蒻很菜，如果写的有不清楚或不对的地方望读者私信我指出，我会及时修正。