Pair

思路：

我入门时写的数位都是求一个区间内满足某个要求的数有多少个，也就是通常要跑两遍，这题比较特殊的地方在于要求是满足条件的二元关系的数量()。

按照传统的思路，我们更喜欢用二进制来表示，比较二进制数的大小从高位开始，高位大的数一定大，后面就不用比较了。

从集合的高位开始判断当前二进制位上的两个数的异或与当前二进制位的关系，如果小于，那么后面的二进制位上的数不管是多少，组成的二进制数都是符合条件的()；如果大于，那么后面的二进制位上的数不管是多少，组成的二进制数都是不符合条件的；如果等于就继续比较，直到出现上述两种情况，或者每一位都相等，即，这也是不符合条件的。(判断的方法同上)。

表示二进制数第位组成的值，代表当的二进制位第位确定后，还有几种取值，表示二进制数第位组成的值，代表当的二进制位第位确定后，还有几种取。当第i位满足条件时，由上述可知剩下取值的组合都是满足条件的，假设这些组合的数量是，那么。

数位的状态显然就是，表示枚举到第几位，表示高位和的结果，取值为表示相等、表示符合条件，表示不符合条件，表示是否到集合的边界(的缩写)。

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 mi[37],dp[37][3][3][2][2];
int num1[37],num2[37],num3[37],n1[37],n2[37];
ll dfs(int len,int c1,int c2,bool lt1,bool lt2) {
    if(~dp[len][c1][c2][lt1][lt2]) return dp[len][c1][c2][lt1][lt2];
    if(c1==2&&c2==2) return dp[len][c1][c2][lt1][lt2]=0;
    if(c1==1||c2==1) {
        ll x=mi[len],y=mi[len];
        if(lt1) x=n1[len]+1;
        if(lt2) y=n2[len]+1;
        return dp[len][c1][c2][lt1][lt2]=x*y;
    }
    if(!len) return dp[len][c1][c2][lt1][lt2]=0;
    int end1=lt1?num1[len]:1,end2=lt2?num2[len]:1;
    ll ans=0;
    for(int i=0,j,x,y,nc1,nc2;i<=end1;++i) {
        for(j=0;j<=end2;++j) {
            x=i&j,y=i^j;
            nc1=c1,nc2=c2;
            if(!nc1) if(x>num3[len]) nc1=1; else if(x<num3[len]) nc1=2;
            if(!nc2) if(y<num3[len]) nc2=1; else if(y>num3[len]) nc2=2;
            ans+=dfs(len-1,nc1,nc2,lt1&&i==end1,lt2&&j==end2);
        }
    }
    return dp[len][c1][c2][lt1][lt2]=ans;
}
ll solve(int A,int B,int C) {
    int t1(0),t2(0),t3(0),t;
    while(A) num1[++t1]=A&1,A>>=1;
    while(B) num2[++t2]=B&1,B>>=1;
    while(C) num3[++t3]=C&1,C>>=1;
    t=max(t1,max(t2,t3));
    for(int i=1,j;i<=t;++i) {
        n1[i]=n2[i]=0;
        for(j=i;j;--j) {
            n1[i]=n1[i]<<1|num1[j];
            n2[i]=n2[i]<<1|num2[j];
        }
    }
    return dfs(t,0,0,true,true);
}
int main() {
    int A,B,C,t=read();
    mi[0]=1;
    for(int i=1;i<=32;++i) mi[i]=mi[i-1]<<1;
    while(t--) {
        A=read(),B=read(),C=read();
        memset(dp,-1,sizeof dp);
        memset(num1,0,sizeof num1);
        memset(num2,0,sizeof num2);
        memset(num3,0,sizeof num3);
        printf("%lld\n",solve(A,B,C)-min(A,C-1)-min(B,C-1)-1LL);
    }
}