数位dp——牛客多校H

/*

x[1,A]

y[1,B]

x^y<C 或 x&y>C

把ABC拆成二进制后按位进行数位dp

dp[pos][s1][s2][f1][f2]

表示从高到低第pos位，条件一状态为s1，条件2状态为s2，x在pos为的限制状态为f1,y在pos的限制状态为f2的方案数

条件状态s=0|1|2表示前pos位数运算结果<C前pos位数,=C前pos位数，>C前pos位数

dp时枚举下一位的所有可能情况，如果当前状态已经确定(满足或不满足)，那么下一位取什么都可以，即下一位的条件状态可以直接继承当前位

反之当前状态不确定，即前pos位的值和C相等，那么需要通过当前为来进行判断下一位的条件状态

终止条件：pos==30

    s1==2||s2==0，值为1，反之为0

考虑要减去的情况

    x=0,y=[1,min(C-1,B)]都可行

    y=0,x=[1,min(C-1,A)]都可行

     x=0,y=0也可行

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 35

#define ll long long

ll A,B,C,dp[maxn][][][][];

vector<int>v1,v2,v3;

ll dfs(int pos,int S1,int S2,int f1,int f2){

    ll &res=dp[pos][S1][S2][f1][f2];

    if(res!=-)return res;

    if(pos==){//边界条件

        if(S1==||S2==)return res=;

        else return res=;

    }

    res=;

    int newS1,newS2,lim1,lim2;

    lim1=f1?v1[pos]:;//x下一位的上界

    lim2=f2?v2[pos]:;//y下一位的上界

    for(int i=;i<=lim1;i++)//枚举xy的下一位

        for(int j=;j<=lim2;j++){

            int tmp1=i&j,tmp2=i^j;

            if(S1==){//先处理条件1

                 if(tmp1==v3[pos])newS1=;

                 else if(tmp1<v3[pos])newS1=;

                 else newS1=;

            }

            else newS1=S1;

            if(S2==){

                if(tmp2==v3[pos])newS2=;

                 else if(tmp2<v3[pos])newS2=;

                 else newS2=;

            }

            else newS2=S2;

            res=res+dfs(pos+,newS1,newS2,f1&&(i==lim1),f2&&(j==lim2));

        }

    return res;

}

void calc(ll x,vector<int> & v){

    v.clear();

    for(int i=;i>;i--){

        v.push_back(x&);

        x>>=;

    }

    reverse(v.begin(),v.end());//把数组倒置后就可以正常数位dp了

}

int main(){

    int t;cin>>t;

    while(t--){

        memset(dp,-,sizeof dp);

        cin>>A>>B>>C;

        calc(A,v1);calc(B,v2);calc(C,v3);

        ll res=dfs(,,,,);//进入搜索时的状态

        res-=min(C-,A)+min(C-,B)+;//0取不到，但数位dp时算了

        cout<<res<<'\n';

    }

}