Codeforces Round 984 (Div. 3) F.XORificator 3000 题解

2024 年 11 月 09 日

407 次浏览

1072字数

# 题目描述

多年来，爱丽丝一直在给鲍勃送礼物，她知道他最喜欢的是执行有趣整数的[按位异或运算](http://tiny.cc/xor_wiki_eng)。鲍勃认为一个正整数 $x$ 是有趣的，如果它满足 $x \not\equiv k (\bmod 2^i)$。因此，为了他的生日，她送给了他一台超强大的“XORificator 3000”，最新款式。

鲍勃对这份礼物非常高兴，因为它让他能够立即计算出从 $l$ 到 $r$ 范围内所有有趣整数的异或值。毕竟，一个人还需要什么来获得幸福呢？不幸的是，这个设备如此强大，以至于有一次它与自身执行了异或运算并消失了。鲍勃非常沮丧，为了让他振作起来，爱丽丝请你写出你的版本的“XORificator”。

# 输入

输入的第一行包含一个整数 $t$ $(1 \leq t \leq 10^4)$ — 表示在该段上的XOR查询数量。接下来的 $t$ 行包含查询，每个查询由整数 $l$, $r$, $i$, $k$ 组成 $(1 \leq l \leq r \leq 10^{18}$, $0 \leq i \leq 30$, $0 \leq k \leq 2^i)$。

# 输出

对于每个查询，在范围$[l, r]$内所有满足$x \not\equiv k \mod 2^i$的整数$x$的异或值，输出一个整数。

# 前缀异或和

区间$[0, l]$的异或和有一定的规律， 可以通过打表看出：

```cpp
int tmp = 0;
    for(int i = 0; i < 20; i ++)
    {
        if(i % 4 == 0) cout << endl;
        tmp = tmp ^ i;
        cout << tmp  << " ";
    }
```

结果如下：

```
0 1 3 0 
4 1 7 0 
8 1 11 0 
12 1 15 0 
16 1 19 0
```

可以看到， 连续四个自然数的异或和为0, 而且这四个数的二进制表示除了第两位不同，其余相同， 因此存在时间复杂度为$O(1)$的计算算法：

$$
f(n)=\begin{cases}
n, \quad n\%4 = 0\\
1, \quad n\%4 = 1\\
n+1, \quad n \%4 = 2\\
0, \quad n \% 4 = 3
\end{cases}
$$

代码如下:

```cpp
LL f(LL x)
{
    if(x % 4 == 0) return x;
    else if(x % 4 == 1) return 1;
    else if(x % 4 == 2) return x + 1;
    else return 0;
}
```

# 解题思路

首先可以根据异或的性质$a^a = 0$， 可以将求所有与$k$不同余的$x$的异或和，转换为所有$x$的异或和**异或上**所有与$k$同余的$x$的异或和

由于所有$x$的异或和很好求， 所以接下来只需要求所有与$k$同余的$x$的异或和

观察当$i=3$, $k=7$时候与$k$同余的$x$的二进制表示：

```
i = 3
k = 7
7        000111
15       001111
23       010111
31       011111
39       100111
```

可以看到：

- 最后$i$位都相同
- 除去最后$i$位的异或和同样可以用前缀异或和的方式得到

因此只需要将$l$和$r$右移$i$位再次使用前缀异或和后,和最后$i$位拼接即可

> 注意， 这里的$l$和$r$需要保证分别是**第一个满足与$k$同余的x**和**最后一个满足与$k$同余的$x$**

# 实现代码

```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
int t;
int i, k;
LL l, r;
LL f(LL x)
{
    if(x % 4 == 0) return x;
    else if(x % 4 == 1) return 1;
    else if(x % 4 == 2) return x + 1;
    else return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin >> t;
    while(t --)
    {
        cin >> l >> r >> i >> k;
        LL tmp = 1;
        for(int j = 0; j < i; j ++) tmp *= 2;
        LL rec = f(r) ^ f(l - 1);
        if(l % tmp > k) l += tmp; 
        if(r % tmp < k) r = r - tmp; 
        l = l >> i;
        r = r >> i;
        LL res = f(r) ^ f(l - 1);
        res = res << i;
        if((r - l + 1) % 2) res += k;
        cout << (rec ^ res) << endl;
    }
}
```

最后修改：2025 年 03 月 07 日