公式不一样，但是差不多：

就算以下右下点对和左下点对的贡献减去同行同列就行了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,P=1e9+7;
int fac[N];
int qpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;}
int c(int n,int m){if(n<m)return 0;return fac[n]*qpow(fac[m],P-2)%P*qpow(fac[n-m],P-2)%P;}
int calc(int n,int m){return (n*(n-1)/2%P*m%P+m*(m-1)/2%P*n%P)%P;}
signed main()
{
	int n,m,k;cin>>n>>m>>k;
	fac[0]=1;for(int i=1;i<=N-10;i++)fac[i]=fac[i-1]*i%P;
	int ans=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans=(ans+calc(n-i+1,m-j+1)*2)%P;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans=((ans-i*(i-1)/2-j*(j-1)/2)%P+P)%P;
	ans=ans*c(n*m-2,k-2)%P;
	cout<<ans;
	return 0; 
}

[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$ 坐标的贡献，得到最终答案为：

$$(\sum_{d=1}^{n-1} d\times (n-d)\times m^2+\sum_{d=1}^{m-1} d\times (m-d)\times n^2)\times C_{n\times m-2}^{k-2}$$

那么就做完了。

代码

#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记录

写在最后

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