AtCoder Beginner Contest 127 E - Cell Distance 贡献

题目链接
大意：给你三个数 $n,m,k$n,m,k，让你在 $n\ast m$n∗m的矩阵中选择 $k$k个单元，计算 ${\sum }_i^{K-1}{\sum }_{j=i+1}^K(\mid x_i-x_j\mid +\mid y_i-y_j\mid )$∑iK−1​∑j=i+1K​(∣xi​−xj​∣+∣yi​−yj​∣)。
思路：很显然， $x,y$x,y坐标对答案的贡献是独立的。我们可以把他们拆开。
然后枚举横坐标的差值 $d$d
固定两个横坐标差值为 $d$d的两块，显然可以有 $(n-d)\ast m^2$(n−d)∗m2个，那么这两块的贡献就是 $(n-d)\ast m^2\ast d$(n−d)∗m2∗d
对于纵坐标一样讨论。
最后的还要乘一下 ${(}_{k-2}^{n\ast m-2})$(k−2n∗m−2​),（剩下的 $k-2$k−2块随便选），就是答案了。
细节见代码

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +511;
const LL mod=1e9+7;
LL fac[N],inv[N];
int n,m,k;
void P(){
	fac[0]=inv[0]=1;
	for(int i=1;i<=2e5;i++)fac[i]=fac[i-1]*i%mod;
	inv[200000]=powmod(fac[200000],mod-2,mod);
	for(int i=200000-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
LL get(int a,int b){
	if(b==0)return 1;
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int main(){
	ios::sync_with_stdio(false);
	P();
	cin>>n>>m>>k;
	LL ans=0;
	for(LL i=1;i<m;i++)ans=(ans+(m-i)*i%mod*n%mod*n%mod)%mod;//固定两个他们纵坐标的差为i，一共可以选（m-i）* n * n 个
	for(LL i=1;i<n;i++)ans=(ans+(n-i)*i%mod*m%mod*m%mod)%mod;
	ans=ans*get(n*m-2,k-2)%mod;
	cout<<ans<<endl;
	return 0;
}