2012-09-07

SRM 555 Div1 555 XorBoard

00:34 |

0 or 1 が入る W x H のグリッドに 0 が書いてある。行と列すべての 0 1 を反転する回数がそれぞれ与えられる。
反転後 1 の数が S になるような反転のさせかたは何通りあるか。
各行/各列の反転回数どれかが違えば違うとする。
W, H ≦ 1555

（しばらくして）
行のうち反転回数が奇数になるものを ro, 同じく列のを co とすると
反転後の 1 の数は W*ro + H*co - 2*ro*co となる
こんな ro, co が何通りあるか数えればよさげ
ro を分解して H 個に振り分ける？分割数？
..........
奇数の場所は combination(H, ro) 通りあるな
そこから進まない
..........
おわり

（あとで）

行の場合
奇数の場所は combination(H, ro) 通りあって、それぞれについて
奇数のところから 1 を取ると→全部偶数になる
偶数ということは２コのペア (RC-ro)/2 を H 個に振り分ければいい（なるへそ）
これは combination((RC-ro)/2 + H-1, H-1) 通り
反転カード((RC-ro)/2 コ)または区切り棒(H-1)が置ける (RC-ro)/2 + H-1 個の置き場から H-1 個選んで区切り棒を置く。
列も同様。行と列は独立なのでかければいい
combination の表は combination(N, M) == combination(N-1, M-1) + combination(N-1, M) を使って DP

↓実装練習 (passed system test in practice room)

#define MOD 555555555

int comb[2500][2500];

class XorBoard {
	public:
	int count(int H, int W, int RC, int CC, int S) {
		// nCm = n-1Cm-1 + n-1Cm
		REP(n, 2500) comb[n][0] = 1;
		RANGE(n, 1, 2500) RANGE(m, 1, 2500) comb[n][m] = ((ll)comb[n-1][m-1] + comb[n-1][m]) % MOD;
		
		ll ans = 0;
		REP(ro, H+1) if(ro<=RC && (RC-ro)%2==0)
		REP(co, W+1) if(co<=CC && (CC-co)%2==0)
		if(W*ro+H*co-2*ro*co==S) {
			ll lans = (ll)comb[H][ro] * comb[W][co] % MOD * comb[(RC-ro)/2 + H-1][H-1] % MOD * comb[(CC-co)/2 + W-1][W-1] % MOD;
			ans = (ans + lans) % MOD;
		}
		return ans;
	}
};

kojingharangの日記

2012-09-07

SRM 555 Div1 555 XorBoard