AtCoder ABC #127 : E - Cell Distance

今回は速く解ききれたのでよかった。
https://atcoder.jp/contests/abc127/tasks/abc127_e

問題

N*MのグリッドのうちKマスに駒を置くことを考える。
2つの駒の対におけるマンハッタン距離の総和を考えるとき、駒の置き方全通りに対する距離の総和を求めよ。

解法

2つの駒の位置が決まった場合、それが何回分カウントされるかを考えると、他の駒の配置の組み合わせなので通りである。
よって2つの駒の位置の総和を全通り列挙し、前述の値を掛ければ解になる。
マンハッタン距離の和を考える問題はX軸とY軸を独立に考えるとよい。

ll N,M,K;

ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll modpow(ll a, ll n) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll comb(int P_,int Q_) {
	if(P_<0 || Q_<0 || Q_>P_) return 0;
	ll p=1,q=1;
	Q_=min(Q_,P_-Q_);
	for(int i=1;i<=Q_;i++) p=p*P_%mo, q=q*i%mo,P_--;
	
	return p*modpow(q,mo-2)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	
	ll ret=0;
	FOR(i,N) {
		ll d=1LL*i*(i+1)/2%mo;
		d=d*M%mo*M%mo;
		ret+=d;
	}
	FOR(i,M) {
		ll d=1LL*i*(i+1)/2%mo;
		d=d*N%mo*N%mo;
		ret+=d;
	}
	
	cout<<ret%mo*comb(N*M-2,K-2)%mo<<endl;
	
	
}

まとめ

N,Mが2*10^5だと思ってしまって、さらにそれだとTLEする解を出してしまったというグダグダ。
結果的に二重にミスしてうまくいってしまった。