TopCoder SRM 564 Div1 Hard

問題

xor b[i] = nとなるような数列b[i]は何通りあるか求めよ。
（ただし、b[i]はそれぞれ0≦b[i]≦cards[i]を満たす整数）

制約条件

cardsの要素の数≦50
n≦10^9
b[i]≦10^9

方針

cards[i]が一番大きなiの、b[i]の最上位ビットをどうするかで場合分けする。
一番大きな数の最上位ビットがそもそもnの最上位ビットよりも小さかったら0通り。

最上位ビット(= xとする）を1にするとき、これは、
b[i] = b[i] - x、n = n ^ xとおいたときの元の問題に等しいため、再帰すればいい。
再帰1回につき1のビットが1個減るので、この再帰はN * log(N)回程度で終了する。

最上位ビット(= k番目とする）を0にするとき、
一番大きな数のb[i]を調節すれば、k番目未満のビットは自由に変えられる。

なので、一番大きな数のカード以外で、k番目のビットのxorが、nのk番目のビットに等しくなる場合の数をDPで数えればよい。

ソースコード

const int mod = (int)1e9 + 7;
int msb(int n){
	int i = 0;
	for(; n; i++) n /= 2;
	return i - 1;
}
int dp[60][2];
class DefectiveAddition {
	public:
	int count(vector <int> cards, int n) {
		sort(all(cards));
		int m = cards.size();
		if(cards[m - 1] == 0) return n == 0;
		
		int a = msb(cards[m - 1]), b = msb(n);
		if(b > a) return 0;
		
		cards[m - 1] -= 1 << a;
		int ans = count(cards, n ^ (1 << a));
		cards[m - 1] += 1 << a;
		
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		rep(i, m - 1) rep(j, 2) if(dp[i][j]){
			int c = msb(cards[i]);
			if(c == a){
				(dp[i + 1][j ^ 1] += dp[i][j] * (cards[i] - (1 << c) + 1ll) % mod) %= mod;
				(dp[i + 1][j] += dp[i][j] * (1ll << c) % mod) %= mod;
			}
			else
				(dp[i + 1][j] += dp[i][j] * (cards[i] + 1ll) % mod) %= mod;
		}
		ans = (ans + dp[m - 1][a == b]) % mod;
		return ans;
	}
};