yukicoder : No.1202 お菓子の食べ方

一つ勉強になりました。
https://yukicoder.me/problems/no/1202

問題

2次元の整数配列Aが与えられる。
同じ行なら左側、同じ列なら上側にある要素の方が小さいということはない。
この配列に対し、正の値を持つ要素が存在しなくなるまで以下を任意の順番で行う。

1. 全要素のうち正の値を持つものから1引く
2. 残された一番左の列を取り除く
3. 残された一番上の行を取り除く

手順は何通りか。

解法

残された要素のうち、常に左上が最大値を持つはずである。
そこで、最後の1手の直前A(r,c)がその左上に基底て正の値を持ち、最後の1手でこれが0になるまたは取り除かれるケースを列挙しよう。(r,cは0-index)
A(r,c)が左上に来る時点で、すでに処理2がr回、処理3がc回行われていることに留意。

• 最後の1手でA(r,c)=1が0になる
  • それまで、処理1が(A(r,c)-1)回あればよいので、通り。
• 最後の1手で処理2によってA(r,c)が取り除かれる。
  • A(r,c+1)がすでに0でなければこの状態は起きない。そこで事前に処理1がp回(A(r,c+1)≦p＜A(r,c))行われていなければならない。
  • よってその組み合わせは
  • このsumだが、を使えばpを0から一定数まで変化させたときの値を高速に求められるので、累積和の要領で(Combinationの事前前処理ありで)O(1)で求められる。
  • A(r+1,c)がすでに0でなければこの状態は起きない。これは上と同様。

int H,W;
int S[1010][1010];
const ll mo=1000000007;

ll comb(ll N_, ll C_) {
	const int NUM_=1400001;
	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;
}

void solve() {
	
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) {
		cin>>S[y][x];
	}
	ll ret=0;
	FOR(y,H) FOR(x,W) {
		//最後に-1
		ret+=comb(y+x,x)*comb(S[y][x]-1+y+x,y+x)%mo;
		//最後に縦
		// sum(Comb(0+m,0)～comb(n+m,n))=comb(n+m+1,n)を利用
		ll a=comb(S[y][x]-1+x+y+1,S[y][x]-1);
		ll b=comb(S[y+1][x]-1+x+y+1,S[y+1][x]-1);
		(ret+=(a-b)*comb(x+y,x))%=mo;
		ll c=comb(S[y][x+1]-1+x+y+1,S[y][x+1]-1);
		(ret+=(a-c)*comb(x+y,x))%=mo;
	}
	
	cout<<(ret%mo+mo)%mo<<endl;
	
}

まとめ

この二項係数の式は覚えておきたいな。