TopCoder SRM 555 Div1 Medium XorBoard

問題

HxWのグリッドがあり、はじめ全てのグリッドは0である。
1行を自由に選んでその0, 1を反転する操作を合計Rcount回行い、
1列を自由に選んでその0, 1を反転する操作を合計Ccount回行う。

操作を行った後で、1の個数がS個になっているような、
操作の選び方は何通りあるか、mod 555555555で求めよ。
ただし、どの行、列が何回操作が行われたかのみを区別し、操作の順序は区別しないものとする。

制約条件

H, W≦1555
Rcount, Ccount≦1555
S≦H * W

方針

同じ行、列を2度選ぶと、操作は打ち消しあう。
なので、打ち消されていない操作を、a行、b列に対して行ったとき、
1の数はHb + Wa - ab個になる。

a, bは1500以下くらいなので、全部ループをまわしてよい。
Hの行の中からa個の行を選ぶ操作（残りは打ち消しあう）が何通りあるかが、速く計算できればよい。

Hの中からa行を選ぶ場合の数がC(H, a)通り。
Rcount - a個の操作は打ち消し合う。
打ち消し合う操作の選び方は、(Rcount - a) / 2個の区別しないものを、H個の箱に入れる場合の数
に等しい。
これは重複順列なので、C(物+箱-1, 物)通り。

ソースコード

多分本番中のやつか何かなので汚い。

const ll mod = 555555555;
ll null[1600][800]; //row, use
ll C[1600][1600];


class XorBoard {
	public:
	int count(int H, int W, int Rcount, int Ccount, int S) {
		
		rep(i, 1600) rep(j, 1600) C[i][j] = j == 0 || i == j ? 1 : (C[i - 1][j] + C[i - 1][j - 1]) % mod;
		
		memset(null, 0, sizeof(null));
		null[0][0] = 1;
		for(int i = 1; i < 1600; i++) rep(j, 800){
			null[i][j] = (null[i - 1][j] + (j ? null[i][j - 1] : 0)) % mod;
		}
		
		ll ans = 0;
		rep(tate, W + 1){
			if(W - 2 * tate == 0){
				if(S != H * tate) continue;
				
				rep(yoko, H + 1){
					if(Ccount < tate || Rcount < yoko) continue;
					if((Ccount - tate) % 2 || (Rcount - yoko) % 2) continue;
					
					ans += C[W][tate] * null[W][(Ccount - tate) / 2] % mod
					* (C[H][yoko] * null[H][(Rcount - yoko) / 2] % mod) % mod;
					ans %= mod;
				}
				continue;
			}
			if((S - tate * H) % (W - 2 * tate)) continue;
			
			int yoko = (S - tate * H) / (W - 2 * tate);
			
			if(yoko < 0 || yoko > H) continue;
			if(Ccount < tate || Rcount < yoko) continue;
			if((Ccount - tate) % 2 || (Rcount - yoko) % 2) continue;
			
			ans += C[W][tate] * null[W][(Ccount - tate) / 2] % mod
			* (C[H][yoko] * null[H][(Rcount - yoko) / 2] % mod) % mod;
			
			ans %= mod;
		}
		return ans;
	}
};