C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2022-08-06 03:23:17

#include <iostream>
#include <cstring>

using namespace std;

using i64 = long long;

const int N = 20;

i64 f[N][2][2][2][2][2][2];
int numl[N], numr[N];
int lenl, lenr;
int l, r;

i64 dfs(int pos, int l1, int r1, int l2, int r2, int l3, int r3) {
    if (!pos) return 1;
    i64& v = f[pos][l1][r1][l2][r2][l3][r3];
    if (~v) return v;
    int d1 = l1 ? numl[pos] : 0, d2 = l2 ? numl[pos] : 0, d3 = l3 ? numl[pos] : 0;
    int u1 = r1 ? numr[pos] : 1, u2 = r2 ? numr[pos] : 1, u3 = r3 ? numr[pos] : 1;
    i64 res = 0;
    for (int i = d1; i <= u1; i++)
        for (int j = d2; j <= u2; j++)
            for (int k = d3; k <= u3; k++)
                if ((i ^ j ^ k) == (i | j | k)) 
                    res += dfs(pos - 1, l1 & i == d1, r1 & i == u1, l2 & j == d2, r2 & j == u2, l3 & k == d3, r3 & k == u3);
    return v = res;
}

signed main() {
    cin >> l >> r;
    memset(f, -1, sizeof f);
    while (l) numl[++lenl] = (l & 1), l >>= 1;
    while (r) numr[++lenr] = (r & 1), r >>= 1;
    cout << dfs(lenr, 1, 1, 1, 1, 1, 1);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 412K, 提交时间: 2019-12-21 23:07:22

#include<bits/stdc++.h>
using namespace  std;

#define ll long long 
int numl[100],numr[100];
ll dp[20][2][2][2][2][2][2];
ll dfs(int len,bool sa,bool sb,bool sc,bool ta,bool tb,bool tc )
{
	if(len==0) return 1;
	if(dp[len][sa][sb][sc][ta][tb][tc]!=-1) return dp[len][sa][sb][sc][ta][tb][tc];
	ll ans=0;
	int al=sa?numl[len]:0,ar=ta?numr[len]:1;
	int bl=sb?numl[len]:0,br=tb?numr[len]:1;
	int cl=sc?numl[len]:0,cr=tc?numr[len]:1;
	for(int i=al;i<=ar;i++)
	{
		for(int j=bl;j<=br;j++)
		{
			for(int k=cl;k<=cr;k++)
			{
				if((i^j^k)==(i|j|k))
				 ans+=dfs(len-1,sa&&i==al,sb&&j==bl,sc&&k==cl,ta&&i==ar,tb&&j==br,tc&&k==cr);
			}
		}
	}
	dp[len][sa][sb][sc][ta][tb][tc]=ans;
	return ans;
}
ll solve(int l,int r)
{
	int p1=0;
	while(l)
	{
		numl[++p1]=l%2;
		l/=2;
	}
	int p2=0;
	while(r)
	{
		numr[++p2]=r%2;
		r/=2;
	}
	return dfs(max(p1,p2),1,1,1,1,1,1);
}
int main()
{
	int l,r;
	cin>>l>>r;
	memset(dp,-1,sizeof dp);
	cout<<solve(l,r)<<endl;
	return 0;
}

C++(clang++11) 解法, 执行用时: 5ms, 内存消耗: 476K, 提交时间: 2021-02-27 18:08:54

#include<bits/stdc++.h>
using namespace std;

bool num1[20],num2[20];
long long DP[20][2][2][2][2][2][2];
long long DFS(int L,bool a,bool b,bool c,bool x,bool y,bool z)
{
	if(!L)return 1;
	if(DP[L][a][b][c][x][y][z]!=-1)return DP[L][a][b][c][x][y][z];
	long long ans=0;
	int i,j,k,al,ar,bl,br,cl,cr;
	al=(a?num1[L]:0),ar=(x?num2[L]:1);
	bl=(b?num1[L]:0),br=(y?num2[L]:1);
	cl=(c?num1[L]:0),cr=(z?num2[L]:1);
	for(i=al;i<=ar;i++)
	    for(j=bl;j<=br;j++)
	        for(k=cl;k<=cr;k++)
	            if((i^j^k)==(i|j|k))
				    ans+=DFS(L-1,a&&i==al,b&&j==bl,c&&k==cl,x&&i==ar,y&&j==br,z&&k==cr);
	return DP[L][a][b][c][x][y][z]=ans;
}
int main()
{
    int l,r,a=0,b=0;
    scanf("%d%d",&l,&r);
    memset(DP,-1,sizeof(DP));
    for(;l;l>>=1)num1[++a]=l%2;
    for(;r;r>>=1)num2[++b]=r%2;
    printf("%lld\n",DFS(max(a,b),1,1,1,1,1,1));
}