dh的帽子

思路：

官方的题解：

没想过加下界，加上下界确实很简单。
枚举的上下界，状态为：

写出状态后发现复杂度其实很低的，只要确保状态没问题就行了。

MyCode:

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll dp[20][2][2][2][2][2][2];
bool num1[20],num2[20];
ll dfs(int len,bool limit1,bool limit2,bool limit3,bool rimit1,bool rimit2,bool rimit3) {
    if(len==-1)
        return 1;
    if(~dp[len][limit1][limit2][limit3][rimit1][rimit2][rimit3])
        return dp[len][limit1][limit2][limit3][rimit1][rimit2][rimit3];
    int ln1=limit1?num1[len]:0;
    int ln2=limit2?num1[len]:0;
    int ln3=limit3?num1[len]:0;
    int rn1=rimit1?num2[len]:1;
    int rn2=rimit2?num2[len]:1;
    int rn3=rimit3?num2[len]:1;
    ll ans=0;
    for(int i=ln1; i<=rn1; ++i)
        for(int j=ln2; j<=rn2; ++j)
            for(int k=ln3; k<=rn3; ++k) {
                if((i^j^k)==(i|j|k))
                    ans+=dfs(len-1,limit1&&i==ln1,limit2&&j==ln2,limit3&&k==ln3,rimit1&&i==rn1,rimit2&&j==rn2,rimit3&&k==rn3);
            }
    return dp[len][limit1][limit2][limit3][rimit1][rimit2][rimit3]=ans;
}
int main() {
    int L=read(),R=read();
    memset(dp,-1,sizeof dp);
    for(int i=0,tmp=1; i<20; ++i) {
        num1[i]=L&tmp;
        num2[i]=R&tmp;
        tmp<<=1;
    }
    printf("%lld\n",dfs(19,true,true,true,true,true,true));
}