[ARC129] A - Smaller XOR
[Q] https://atcoder.jp/contests/arc129/tasks/arc129_a
1. 範囲[10, 20]の答えは、20以下の範囲から、9以下の範囲を引けばいい。
2. Nのbitを考察する。Nのbitが立っている箇所にxのbitをたてれば、それより下のbit桁を自由に選択できる。
Q. 例2
10 2 19
1. 19 以下の答えを全部出した後、1 以下の答えを引くことを考える。
ans = solve(19) - solve(1)
なるsolveをつくろうと思う。
2. N のbitを考察する。
10 = 1010(bit)
N = 00001010 について
x = 10000000 を考える。
---- xor ----
100.... <= この時点で N を上回ってしまう。
・N の bit が立っていない箇所にxを立てられない。
N = 00001010 について
x = 00001000 を考える。
---- xor ----
00000zzz <= zに何をいれても、Nを上回ることはない。
・N の bit が立っている箇所にbitを立てれば、それより下の桁が自由におけるとわかる。
00000zzz
下 3 桁が自由なので、
ans += 2^3 = 8
N = 00001010
x = 0000001z
下 1桁が自由なので、
ans += 2^1 = 10
3. R の上限値を考慮する。
N = 00001010 について
x = 00001zzz を考える。
これを満たすのは、
1000 // 8
1001 // 9
1010 // 10
1011
1100
1101
1110
1111 // 15
の 8~15 の 8 種類。種類数は、
15 - 7 = 8 で求めている。
15 = 1<<5 - 1
7 = 1<<4 - 1
R は、上限の 15 について考慮すればいいので、
min(R, 15) - low
で種類数を求められる。
負になる場合もあるので、
max(0LL, min(R, 15) - low)
で0以上をとればよさそう。実装
bool is_pop(ll hash, ll d){ return (hash>>d)&1; }
ll N, L, R;
ll solve(ll n){
ll ret = 0;
for(ll i=62; i>=0; --i){
if (is_pop(N, i)){
ll high = (1LL << (i + 1)) - 1;
ll low = (1LL << i) - 1;
ll add = max(0LL, min(high, n) - low);
ret += add;
}
}
return ret;
}
int main(){
cincout();
cin >> N >> L >> R;
ll ans = solve(R) - solve(L - 1);
cout << ans << endl;
}