q个询问: 区间[L,R]中的整数能异或出多少个不同的数? (1≤q≤100, 0≤L≤R≤10^18) 考试的时候只想到了暴力高斯消元......如果R-L > 10^5, 就在[L,R]中随机取10^5个数再做. 手动加入L,L+1,R-1,R.
但是......我CE了......因为Linux环境下已经typedef过uint, 而机房里的电脑装的是Windows XP.
XP本机测试的结果是不能AC. 但是交到雅礼校内OJ上A掉了......可能是rand函数的实现不同.
下面给出两种靠谱的做法.
出题人myy的做法是这样的: |
| 因此, [L,R]的异或空间 = { L, L xor (L+1), (L+1) xor (L+2), ..., (R-1) xor R } 的异或空间. |
x xor (x+1) 长啥样呢? 一串 1. 那么, 待求的是: 对于 k=1,2,...,60, 长度为 k 的一串 1 是否等于某个 x xor (x+1). 这也就是问, 是否存在 x∈(L,R], 其二进制末尾恰有 (k-1) 个 0. |
| 一个末尾恰有 (k-1) 个 0 的二进制数, 加上 2^k, 得到下一个末尾恰有 (k-1) 个 0 的二进制数. 先把 L 的末 k 位替换成 100..0 ((k-1) 个 0), 得到 t. 如果 t ≤ L, 就令 t += 2^k. 仅当 t ≤ R, 可以得到 k 个 1. |
| 假设得到 r 个长度不同的全 1 串. 如果 L 可以被它们线性表出, 则答案为 2^r, 否则答案为 2^(r+1). 只需要用这些全 1 串对 L 消元. |
学到另一个更简洁的方法: 当 R-L ≥ 2, 一定存在相邻两数, 它们异或可以得到 1. 用这个 1 去消其他数, 可以使最低位全 0, 于是就能递归下去啦 >_<
ans(L, L) = 2^[L>0]
ans(L, L+1) = 2^([L>0] + 1)
ans(L, R) = 2 * ans(L/2, R/2) (R-L >= 2)