题解 AGC015D【A or...or B Problem】

problem

从 \(\ge A\) 且 \(\le B\) 的整数中选择一个或多个，把这些整数按位或，求一共有多少种可能的结果。

\(1\le A\le B \le 2^{60}\)

solution

首先暴力怎么写呢？FWT。设序列 \(a_i=[L\leq i\leq R]\)，然后对它 FWT-or 之后自己乘几倍，再翻回去。然后输入几组样例，我们可以大概知道是什么东西了。建议输入样例 \(L=123,R=152\)。以下说说瞪出来的规律。

首先 \(L,R\) 的公共前缀是没有用的，不如删除，这样以后认为 \(R\) 的最高位是 \(1\)，\(L\) 的最高位是 \(0\)。然后答案显然需要先包括 \([L,R]\)，且因为 \(a|b\geq \max(a, b)\)，所以可能的结果只会更大。

考虑有了 \([L,R]\) 之后能构造 \(R+1\) 吗？需要看情况，例如：\(R=10001001_2\) 的时候，显然可以用 \(1000100\underline{0}_2\) 和 \(1000\underline{0}0\underline{10}_2\) 或一下，就是说我们可以去掉 \(R\) 的第二个 \(1\)，来获得 \(R+1\) 的没有第二个 \(1\) 的版本，然后或上第二个 \(1\) 后面全是零的一个数，构造出 \(R+1\)。那么就是说我们的 \(R\) 的第二个 \(1\) 后面可以全部放满一，不影响答案（如上面的例子可以将 \(R\) 直接改为 \(10001111_2\)）。再要更高的位，单靠 \(R\) 就无法做到。

考虑 \(L\)。举例 \(L=01011101_2,R=10001001\to 10001111_2\)，我们可以用 \([L,10000000_2)\) 中的数和 \(10000000_2\) 或一下，获得 \([L+10000000_2,11111111_2]\) 中的数。

除此之外没有别的数字，对 \([L,R']\) 和 \([L+10000000_2,11111111_2]\) 求并就是答案。

根据上面的构造，还可以发现这些可能的结果只需要两个数字或即可。所以 FWT 开平方就够了。

若认为高贵的 __builtin_clzll 是常数复杂度，则整个题的复杂度是常数。不用就是 \(O(\log R)\)。

code

#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define bitclz __builtin_clzll
typedef long long LL;
LL getBit(int k) { return 1ll << k; }
bool conBit(LL x, int k) { return x & getBit(k); }
LL L, R;
int main() {
    freopen("or.in", "r", stdin);
    freopen("or.out", "w", stdout);
    scanf("%lld%lld", &L, &R);
    if (L == R) return puts("1"), 0;
    int b = 63 - bitclz(L ^ R);
    assert(conBit(R, b) && !conBit(L, b));
    for (int i = b - 1; i >= 0; i--) if (conBit(R, i)) {
        R |= getBit(i) - 1;
        break;
    }
    LL U = (getBit(b) - 1) | (R >> b << b);
    LL D = L | (R >> b << b);
    if (R < D) printf("%lld\n", R - L + 1 + U - D + 1);
    else printf("%lld\n", U - L + 1);
    return 0;
}