AGC015 D A or...or B Problem(智商题)

题意

给出$[a, b]$，求出$[a, b]$内任意数or起来能得到多少不同的值

sol

又是神仙题，考试的时候最怕这种题了qwq

设a,b二进制分解后第一个不同的位为i，那么显然i之前所有的数都是没用的(因为or出来的数都包含这些位)

考虑剩下的数形成的新的a和b能生成那些数

首先$b-a+1$这些数一定是能生成的

再考虑这些数or起来能得到哪些数

为了方便讨论，把ab分成两个集合

第一个是$s1 = [a, 2^r)$，另一个是$s2 = [2^r, b]$

s1内能生成的数有$[a, 2^r - 1]$

s2内能生成的数有$[2^r, 2^r + 2^{p+1} - 1]$

其中$p$表示b二进制分解后r位置往后下一个1的位置

两个集合or起来能生成的数有$[a + 2^r, 2^{r+1} - 1]$

最后一个边界我自己没有想出来，其实归纳证明一下是显然的

首先是最高位r，包含该位的元素一定可以通过2^r or s1得到

r - 1往后的都可以由s2得到

然后对ab二进制拆分后判断一下上面说的边界条件即可

#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
#define int long long  
using namespace std;
const int maxn = 2001;
inline ll read() {
    char c = getchar(); ll x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
ll a, b;
int a[maxn], b[maxn], n, m;
int get(int x, int *a) {
    int mx = 0;
    for(int i = 0; i <= 60; i++) {
        if(x & (1ll << i)) mx = i;
        a[i] = (bool)(x & (1ll << i));
    }
    return mx;
}
main() {
    a = read(); b = read();
    if(a == b) {puts("1"); return 0;}
    n = get(a, a); 
    m = get(b, b);
    //for(int i = 0; i <= m; i++) 
    //    printf("%d", b[i]);
    int r = 0, p = 0;
    for(int i = m; i >= 0; i--)
        if(a[i] != b[i]) {r = i; break;}
    for(int i = r -1; i >= 0; i--)
        if(b[i]) {p = i; break;}
    //printf("%d %d\n", r, p);
    a = 0; b = 0;
    for(int i = 0; i <= r; i++) {
        if(a[i]) a += (1ll << i);
        if(b[i]) b += (1ll << i);         
    }

    int al = a, ar = (1ll << r) + (1ll << (p + 1)) - 1;
    int ll = a + (1ll << r), rr = (1ll << (r + 1)) - 1;
    if(ar < ll) cout << ar - al + 1 + rr - ll + 1;
    else cout << rr - al + 1;
    return 0;
}