CSAcademy Round #57 : E. Binary Flips

かなり手間取ってしまった。
https://csacademy.com/contest/round-57/task/binary-flips/

問題

H*Wの２次元グリッドがある。
初期状態では各セルに値0が振られている。

1つセルを選ぶと、その行および列に含まれるセルの値が0/1反転する。
選んだマス自体は行と列で２回反転するため、結果的に反転しない。

K回マスを選んだ場合、1になったマスがS個であるような選び順は何通りあるか。

解法

各列・行に対し、選択した回数の偶奇を考えると、奇数回選択した箇所のみ最終的な1のマスの数に影響する。
X列およびY行奇数回選択したマスがある場合、1となるマスの数はY*W+X*H-2*X*Yとなる。
よってX,Yを総当たりし、Y*W+X*H-2*X*Y==Sとなる(X,Y)を求めよう。

あとは、K回マスを選択した後、奇数回選択した列・行が(X,Y)となる組み合わせを求める。
これは行と列別々に求めればよい。
1回選択すると奇数回選択する箇所が1減るか1増え、かつ奇数回選択した箇所は負にならず幅・高さも超えない。
これはよくあるcorrect bracket sequenceの要領でO(HK+WK)で求めることができる。

行と列を別々に処理できることに気付けるかがカギ。そうでないとO(HWK)かかり間に合わない。

int T;
int H,W,K,S;
ll mo=1000000007;

ll DX[3030][3030];
ll DY[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W>>K>>S;
		ll ret=0;
		FOR(i,K+1) {
			FOR(y,H+1) DY[i][y]=0;
			FOR(x,W+1) DX[i][x]=0;
		}
		DX[0][0]=1;
		DY[0][0]=1;
		FOR(i,K) {
			FOR(y,H+1) {
				if(y) (DY[i+1][y-1]+=DY[i][y]*y)%=mo;
				if(y+1<=H) (DY[i+1][y+1]+=DY[i][y]*(H-y))%=mo;
			}
			FOR(x,W+1) {
				if(x) (DX[i+1][x-1]+=DX[i][x]*x)%=mo;
				if(x+1<=W) (DX[i+1][x+1]+=DX[i][x]*(W-x))%=mo;
			}
		}
		
		FOR(y,H+1) FOR(x,W+1) {
			if(y*W+x*H-2*y*x!=S) continue;
			(ret+=DX[K][x]*DY[K][y])%=mo;
		}
		
		cout<<ret%mo<<endl;
		
	}
}

まとめ

一応時間に解けて良かった。