异或运算相关(坑)

(1)交换律$$p \oplus q = q \oplus p$$(2)结合律$$(p \oplus q) \oplus r = p \oplus (q \oplus r)$$(3)恒等率$$p \oplus 0 = p$$(4)归零率$$p \oplus p = 0$$性质(1), (2)使得异或的运算方式非常自由；

1. 按位异或：将两个数按二进制位异或；
2. 半加：将两个数做不进位的加法，并且因此有$$a + b = (a \ \mathrm{xor} \ b) + (a \ \mathrm{and} \ b) \times 2$$其中$a \ \mathrm{and} \ b$是进位的表示。进行这样的运算的逻辑运算单元被称为半加器；递归或者递推这个过程，可以通过$\mathrm{and}$和$\mathrm{xor}$完成加法；
3. $\mathbb{Z}_2$群的加减法：用群来描述(2)，即异或是$\mathbb{Z}_2$群的加法运算，同时也是减法运算（因为$\mathrm{xor}$是自己的逆运算）；
4. 存在性取反：将$b$存在的二进制位在$a$中取反；或者在集合运算中，将$b$集合在$a$集合中的存在性取反；
5. 对称差：集合运算中$a \oplus b$表示$a$与$b$集合的对称差。

变量交换

void swap(int &a, int &b) {
int c = a;
a = b;
b = c;
}

void swap(int &a, int &b) {
a = a + b; // a' = a + b, b' = b
b = a - b; // a' = a + b, b' = a + b - b = a
a = a - b; // a' = a + b - a = b, b' = a
}

void swap(int &a, int &b) {
a = a ^ b; // a' = a ^ b, b' = b
b = a ^ b; // a' = a ^ b, b' = a ^ b ^ b = a
a = a ^ b; // a' = a ^ b ^ a = b, b' = a
}
异或密码

int lastans = 0, op, l, r;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &op, &l, &r);
op ^= lastans, l ^= lastans, r ^= lastans;
printf("%d", lastans = answer(op, l, r));
}

ZOJ Will Come Back Soon

Sorry for the long downtime. On June 8th 2016, two disks in ZOJ’s RAID 5 system were corrupted. Unfortunately, serious data loss was resulted in this accident.

We will roll back ZOJ to some day in 2015, which means data in nearly a year will disappear. Registration and submission information during this period cannot be found. We grieve on the loss. Still, we will not stop trying to bring back the lost data.

Sorry again for all the inconvenience and loss resulted.

线性基

https://blog.sengxian.com/algorithms/linear-basis

（等我自以为能够拿得出手的时候，我就在这里放点例题和代码吧）

FWT

（坑）
{

Wikipedia：

Bilibili（雾）：

uestc郭大侠讲述fwt（虽然没证明

CSDN – Fast Walsh-Hadamard Transform (快速沃尔什变换)

}

其他

• 树上莫队

• (坑)

在一些脚本语言里居然可以这样写 (。・ω´・)