KEYENCE Programming Contest 2019 : F - Paper Cutting

これは考え方次第で一気にシンプルになるタイプの問題。
https://atcoder.jp/contests/keyence2019/tasks/keyence2019_f

問題

縦(H+1)、横(W+1)のグリッドがある。
このグリッドを、縦横いずれかの線に平行な直線で、マスの境界部分に切れ目を入れ切断していくことを考える。
線の入れ方は縦H箇所、横W箇所考えられる。

このうちK箇所に切れ目を入れていき、そのつど切断後のグリッドの個数の総和を取ることを考える。
切れ目の入れ方全通りに対し、上記総和の総和を求めよ。

解法

グリッドのマス目に(0,0)-(H,W)の座標を振る。例えば左上を(0,0)としよう。
i回目の切断後のタイミングで、マス(r,c)が切断後の各矩形の左上に来る確率をf(r,c,i)とする。
求める和は、切断の方法がP(H+W,K)通りあることを考えるととなる。

一見三重のsumが付いてびっくりするが、p(r,c,i)はr,cを変えても値のバリエーションがあまりないことを考えるとラクになる。

• f(0,0,*)は常に1である。
• f(0,c,i)やf(r,0,i)は、i回目以前に(c-1)列目とc列目、または(r-1)行目とr行目の間が切断されている確率と考えると、i/(H+W)である。
• f(r,c,i)は、i回目までに(c-1)列目とc列目、または(r-1)行目とr行目の間が切断されている確率と考えると、P(i,2)/P(H+W,2)である。

このため、rとcに関するsumはまとめて処理することができる。

int H,W,K;
ll mo=1000000007;

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	
	ll ret1=0,ret2=0;
	for(int t=1;t<=K;t++) {
		(ret1+=2LL*(t-1)*(K+1-t))%=mo;
		ret2+=K+1-t;
	}
	ret1=ret1*(1LL*H*W%mo)%mo*modpow(H+W)%mo*modpow(H+W-1)%mo;
	(ret1+=ret2+K)%=mo;
	
	for(i=H+W-K+1;i<=H+W;i++) ret1=ret1*i%mo;
	cout<<ret1<<endl;
	
}

まとめ

総和と期待値を互いに言い換えるテクは最近よく見かけるね。