TopCode SRM 601 Div1 Medium WinterAndSnowmen

問題

{1, 2, ..., N}の部分集合Aを選ぶ
{1, 2, ..., M}の部分集合Bを選ぶ。

このとき、AとBの積集合が空かつ、（Aの要素全てのxor）＜（Bの要素全てのxor）となる集合の選び方は何通りあるか。
mod 10^9 + 7で求めよ。

制約条件

N, M≦2000

方針

Aの集合のxorとBの集合のxorがはじめて異なる桁を固定する。これをkとする。

1から順に数字をAまたはBに割り振っていくメモ化再帰をする。
rec(いくつまで見たか, Aのk桁目のbit, Bのk桁目のbit, k桁より上の部分のbitのAとB全てのxor)
として計算すればいい。

自分がやったのはなんかセンスない方針。
桁を固定するのは同じなんだけど、1〜min(n, m)の部分とmin(n, m) + 1〜max(n, m)の部分に分けてDPするとかいうことをやってしまった。

ソースコード

const int mod = 1e9 + 7;

int calc(int dp[2][2][2048], int pos, int n){
	int cur = 0, next = 1;
	memset(dp, 0, sizeof(int)*2*2*2048);
	dp[0][0][0] = 1;
	
	for(int i = 1; i <= n; i++){
		memset(dp[next], 0, sizeof(int)*2*2048);
		rep(j, 2) rep(k, 2048) if(dp[cur][j][k]){
			
			if((i & k) >> pos & 1){
				if(k >> pos & 1){
					(dp[next][0][k ^ i] += dp[cur][j][k]) %= mod;
					(dp[next][1][k ^ i] += dp[cur][j][k]) %= mod;
				}
				else{
					(dp[next][0][k ^ i] += dp[cur][j][k] * 2 % mod) %= mod;
				}
			}
			else{
				(dp[next][j][k ^ i] += dp[cur][j][k] * 2 % mod) %= mod;
			}
			(dp[next][j][k] += dp[cur][j][k]) %= mod;
		}
		swap(cur, next);
	}
	return cur;
}

int solve(int n, int m){
	ll res = 0;
	int cur = 0, next = 1;
	static int dp[2][2048];
	static int dp2[2][2][2048];
	
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for(int i = min(n, m) + 1; i <= n || i <= m; i++){
		memset(dp[next], 0, sizeof(dp[next]));
		rep(j, 2048){
			(dp[next][j ^ i] += dp[cur][j]) %= mod;
			(dp[next][j] += dp[cur][j]) %= mod;
		}
		swap(cur, next);
	}
	
	rep(pos, 11){
		int p = calc(dp2, pos, min(n, m));
		
		rep(i, 2048) if(dp[cur][i]) rep(j, 2) rep(k, 2048) if(dp2[p][j][k]){
			
			if(!((i ^ k) >> pos & 1)) continue;
			if((i ^ k) >> pos + 1) continue;
			
			if(k >> pos & 1){
				res += dp2[p][j][k] * (ll)dp[cur][i] % mod * (mod / 2 + 1) % mod;
				res %= mod;
			} 
			else{
				if(j == (n < m)) continue;
				res += dp2[p][j][k] * (ll)dp[cur][i] % mod;
				res %= mod;
			}
		}
	}
	
	return res;
}

class WinterAndSnowmen {
	public:
	int getNumber(int N, int M) {
		
		return solve(N, M);
	}
};