這回只有 D 比較難而已，但是 D 真的很漂亮。

D - XOR World

XOR 性質題或是規律題

AC Code 1

你會發現最右邊的那位數是每兩個數字循環一次，右邊數來第二位數是每四個數字循環一次，依此類推。

所以你可以用規律去做！

對於每一位數，去看看他 $[0, x]$ 每一個位數的累計 1 個數。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int dp[40] = {0};

ll f(ll x)
{
    if (x <= 0)
        return 0;
    // 2^40 > 10^12
    ll acc[40] = {0};
    for (int i = 0; i < 40; i++) {
        ll mod = (1LL << (i + 1));

        acc[i] += x / mod * mod / 2;
        ll rem = x % mod - (mod / 2 - 1);
        if (rem > 0)
            acc[i] += rem;
    }

    ll ans = 0;
    for (int i = 0; i < 40; i++)
        if (acc[i] % 2 == 1)
            ans |= (1LL << i);
    return ans;
}

int main()
{
    ll a, b;
    scanf("%lld %lld", &a, &b);

    printf("%lld\n", f(b) ^ f(a - 1));

    return 0;
}

AC Code 2

題解的XOR觀察

$0 \oplus 1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 …$ = $(0 \oplus 1) \oplus (2 \oplus 3) \oplus (4 \oplus 5) …$ = $1 \oplus 1 \oplus 1 …$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    ll a, b;
    scanf("%lld %lld", &a, &b);

    ll ans = 0;
    if (a % 2 == 0 && b % 2 == 0)
        ans = b;
    else if (a % 2 == 1 && b % 2 == 0)
        ans = a ^ b;
    else if (a % 2 == 0 && b % 2 == 1)
        ans = 0;
    else
        ans = a;

    if (a % 2 == 1)
        a++;
    if (b % 2 == 0)
        b--;
    if (a <= b)
        ans ^= ((b - a + 1) / 2 % 2);
    printf("%lld\n", ans);
    return 0;
}