[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;
}

https://atcoder.jp/contests/arc129/submissions/27425320