TopCoder SRM 602 Div2 Hard BlackBoxDiv2

Div1 Hardは見たとき絶望感しか感じなかったが、こちらはどうにかなる。
http://community.topcoder.com/stat?c=problem_statement&pm=12929

問題

グリッド上のいくつかのマスに黒いブロックが乗っているとする。
このグリッドを下から見た場合と左から見た場合、それぞれどの位置にブロックが見えるかという情報が与えられる。
この情報に合致するブロック配置の組み合わせ数を列挙せよ。

解法

まず、ブロックの見えない列や行は無視する。
残された列数をW、行数をHとすると、この問題は以下のように書き換えられる。
「H行W列のグリッドに、各行・各列に最低１個はブロックを置くような置き方の数を求めよ。」

最初「これ包除原理なんだろうな…」と思って色々こねくりかえしてみたけど、結局かなり単純な方法で解けた。
H行W列からi行j列を選ぶとその選び方はで、またi行j列のグリッドの埋め方は2^(i+j)通り。
後は(H-i)+(W-j)の偶奇によって、上記のを加減算すればよい。

ll mo=1000000007;
ll p2[2501];

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

class BlackBoxDiv2 {
	public:
	
	int count(string front, string side) {
		int F=0,S=0,i,j;
		FOR(i,front.size()) F += (front[i] == 'B');
		FOR(i,side.size()) S += (side[i] == 'B');
		
		p2[0]=1;
		FOR(i,2500) p2[i+1] = (p2[i]*2) % mo;
		
		ll ret = 0;
		FOR(i,F+1) FOR(j,S+1) {
			ll t=(comb(F,i)*comb(S,j))%mo;
			t = (t*p2[i*j]) % mo;
			if(((F-i)+(S-j))%2) t=mo-t;
			ret = (ret+t)%mo;
		}
		return ret;
	}
};

まとめ

包除原理は苦手だけど、以前のABC#003でも出てきたしこれで苦手意識を減らしたい。