Bitwise AND [yukicoder No.822] - はまやんはまやんはまやん

解説

よくよく考えると、(x,y)のペアは全探索ができる量である。
まず、xは[0,2^17)の範囲で考えればいい。
これは、2^17=131072であり、2進数表記すると1000000000000となる。
つまり18ビット目だけ1である訳であるが、ANDを取ってNになるためには最低でも18ビット目を0にする必要がある。
このためにはyの18ビット目を0にする必要があり、そのためには+2^17は最低でも必要ということになる。
これは絶対Kの最大値の300では達成できないので、xはそれより小さいということがわかる。
K≦300なので、yも各xについて高々300なので、十分全探索が可能になる。
　
さて、問題はINFとなる場合であるが、これはサンプルを見てみよう。

N=0, K=1

3 011
4 100
-------
   000

15 01111
16 10000
----------
     00000

これを見ると繰り上がりでうまく上位ビットが0になるおかげで無限に作れているみたい。
xは全部11111である繰り上がり寸前と考えると、y=x+1で最上位ビットだけ1になっているので、この時点でANDは0。
ここからyの値を増やしていくと、xが全部11111なので、ANDで増やした分は全部ANDで出てくることになる。
つまり、結論としては、N+1≦Kならば無限に作れる。

int N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	
	if (N + 1 <= K) {
		cout << "INF" << endl;
		return;
	}

	int ans = 0;
	rep(x, 0, 1 << 17) rep(k, 0, K + 1) {
		int y = x + k;
		if ((x & y) == N) ans++;
	}
	cout << ans << endl;
}