Codeforces #313 Div1 C. Gerald and Giant Chess

先日のyukicoderのおかげで割とあっさり解けました。
http://codeforces.com/contest/559/problem/C

問題

大きさがH*Wの２次元グリッドがある。
左上角から右下角のセルまで、隣接する右セルまたは下セルを辿って移動したい。
ただ、途中いくつか通過できないセルが与えられる。

右下角セルに至る経路の組み合わせ数を求めよ。

解法

H*Wは大きいので、よくあるO(HW)のDPでは対応できない。
各通過不可セルと、右下角のセルについて、他の通過不可セルを通らずに到達できる組み合わせを考えてみる。

まず、各セルを左上角からのマンハッタン距離でソートする。
左上セルを(0,0)、各通過不可セルを(R[i],C[i])、右下角セルを(H-1,W-1)とする。
(R[N]=H-1,C[N]=W-1とすると他の通過不可セル同様に扱えて楽)

(0,0)から他の通過不可セルを経由せず(R[i],C[i])に到達する方法F(i)は、である。
そこから、他の通過不可セルを経由するケースを引こう。
(R[j],C[j])が矩形範囲(0,0)-(R[i],C[i])に含まれる場合、(R[j],C[j])を経由するケースを引くのでで更新していけば良い。
複数の通過不可セルを経由するケースは考慮しなくていいのか？と思うが、たとえばj番→k番→i番の順で通過不可セルをすべて経由する場合、F(k)の値はすでにF(j)分の影響を引いてあるので、F(i)からはF(j)の分とF(k)の分を両方引いても、F(j)の分が多重にひかれることはない。

ll mo=1000000007;

ll combi(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;
}

int H,W,N;
pair<int,int> P[2020];
ll dp[2020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>N;
	FOR(i,N) {
		cin>>y>>x;
		P[i]={x-1,y-1};
	}
	P[N]={W-1,H-1};
	sort(P,P+N+1);
	FOR(i,N+1) {
		dp[i]=combi(P[i].first+P[i].second,P[i].second);
		FOR(x,i) if(P[x].first<=P[i].first && P[x].second<=P[i].second) {
			dp[i] -= dp[x]*combi(P[i].first-P[x].first+P[i].second-P[x].second,P[i].second-P[x].second)%mo;
		}
		dp[i]=((dp[i]%mo)+mo)%mo;
	}
	
	cout<<dp[N]<<endl;
}

まとめ

一見O(2^N)に見えてO(N^2)に出来る包除原理、苦手意識があったけど今回自力回答できて少し自信回復。