[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\) 时的贡献。最后乘上一个组合数就好了。最终答案如下： \[ \left(\sum_{d=1}^{n-1} d \times(n-d) \times m^2+\sum_{d=1}^{m-1} d \times(m-d) \times n^2\right) \times \dbinom{n\times m - 2}{k-2} \] 代码：（搬的）
#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
