[ABC127E] Cell Distance 题解
题意：
有一个 $n \times m$ 的矩形，你会从中选出 $k$ 个坐标为整数的位置 $(x_1,y_1),(x_2,y_2)\dots(x_{k},y_{k})$ 。
你定义一个选出 $k$ 个位置的方案的权值为$\textstyle \sum_{i=1}^{k-1}\sum_{j=i+1}^{k}(|x_{i}-x_{j}|+|y_{i}-y_{j}|)$
你需要求出，所有可能的选出 $k$ 个位置的方案的权值之和，答案对 $1000000007$ 取模。
输入格式：
一行三个整数 $n,m,k$ 。
输出格式：
一行一个整数，表示答案。
数据范围：
$2 \le k \le n \times m \le 200000$
考虑两个点满足 $x$ 的差为 $d$ 时的贡献 $(1 \le d \le n - 1)$ 。
显然当 $x_1$ 固定时，有 $m^2$ 个这样的点对。而当 $y_1=y_2$ 固定时， 有 $n-d$ 对这样的点。
同理，我们可以计算出 $y$ 相差为 $d$ 时的贡献。最后乘上一个组合数就好了。最终答案如下：
代码：（搬的）
#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r)>>1)
using namespace std;
const int mod=1e9+7;
int qp(int a,int b){
int ans=1;
while(b){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
int fac[10000005],inv[10000005];
void init(){
fac[0]=1;
for(int i=1;i<=10000000;i++) fac[i]=fac[i-1]*i%mod;
inv[10000000]=qp(fac[10000000],mod-2);
for(int i=9999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int i,int j){
if(i<0||j<0||i<j) return 0;
return fac[i]*inv[i-j]%mod*inv[j]%mod;
}
signed main(){
init();
int n,m,k,ans=0;
cin>>n>>m>>k;
for(int i=1;i<n;i++){
ans=(ans+(i*m%mod)*((n-i)*m%mod)%mod*C(n*m-2,k-2)%mod)%mod;
}
for(int i=1;i<m;i++){
ans=(ans+(i*n%mod)*((m-i)*n%mod)%mod*C(n*m-2,k-2)%mod)%mod;
}
cout<<ans;
return 0;
}参考文献：
[1] https://www.luogu.com.cn/blog/lyxtree/solution-at-abc127-e
