参考博客：https://blog.csdn.net/u013534123/article/details/98877628#commentsedit

题目：

解题思路：

 涉及到位运算，把A,B,C转化成二进制，记录每位上的值，最低位下标是1。

数位dp， 从高位开始处理，，stax(sta1,sta2)有3种状态：0-还存在满足条件x的可能性，1-已经确定满足条件x，2-已经确定不满足条件x，lim1，lim2表示x，ypos位前面的位上的数有没有达到限制。

剪枝+记忆化，注意返回值的判断条件，剩下的就和普通的数位dp差多了。

注意：题目要求x和y必须大于0，但是在数位dp的dfs里加大于0的判断稍微有点麻烦，可以在最后输出的时候处理一下。数位dp得到的结果是（0≤x≤A,0≤y≤B）对应的结果，应该减去（x=0，0≤y≤B）对应的结果，再减去（0≤x≤A，y=0）最后减去（x=0,y=0）的结果。（这里的字母符号和代码里的有点出入，莫事，小问题）

 

ac（？）代码：

没有账号，没法提交，枯了?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[35][4][4][2][2], pow2[40], vala[40], valb[40];
int a[40], b[40], c[40];
int x, y, z;
int init()
{
    memset(dp, -1, sizeof dp);
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    memset(c, 0, sizeof c);
    memset(vala, 0, sizeof vala);
    memset(valb, 0, sizeof valb);
    int X = x, Y = y, Z = z;
    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    while(X) a[++cnt1] = X&1, X >>= 1;
    while(Y) b[++cnt2] = Y&1, Y >>= 1;
    while(Z) c[++cnt3] = Z&1, Z >>= 1;
    int maxt = max(cnt1, max(cnt2, cnt3));
    for(int i = 1; i <= maxt; i++)
    {
        for(int j = i; j >= 1; j--) // i-1
        {
            vala[i] = vala[i] << 1 | a[j];
            valb[i] = valb[i] << 1 | b[j];
        }
    }
    return maxt;
}
void get_pow2()
{
    pow2[0] = 1;
    for(int i = 1; i <= 32; i++)
        pow2[i] = pow2[i - 1] * 2;
}
ll dfs(int pos, int sta1, int sta2, bool lim1, bool lim2) //stax = 0 还可能存在满足条件x的情况，= 1，满足条件x, = 2, 不满足条件x（<成>这种）
{
    if(pos == 0) return sta1 == 1 || sta2 == 1; // 满足条件之一就返回1
    if(sta1 == 2 && sta2 == 2) return 0;
    if(sta1 == 1 || sta2 == 1)
    {
        ll s1 = lim1 ? vala[pos] + 1 : pow2[pos]; // 如果pos前面的位上的数都已经达到了最大值
        ll s2 = lim2 ? valb[pos] + 1 : pow2[pos];
        return s1 * s2;
    }
    if(dp[pos][sta1][sta2][lim1][lim2] != -1) return dp[pos][sta1][sta2][lim1][lim2];
    int up1 = lim1 ? a[pos] : 1, up2 = lim2 ? b[pos] : 1;
    ll sum = 0;
    for(int i = 0; i <= up1; i++)
    {
        for(int j = 0; j <= up2; j++)
        {
            int v1 = i & j, v2 = i ^ j, sta11 = sta1, sta22 = sta2; // 应该v1 > C， v2 < C
            // 都不满足和至少有一个满足都处理了，只剩下00 ，02（20） 这种情况了
            if((v1 < c[pos] || sta1 == 2) && (v2 > c[pos] || sta2 == 2)) continue;
            if(sta1 == 0) // 上一位 x,y对应位上的值&后和z对应位上的值相同，还存在有解的可能性
            {
                if(v1 < c[pos]) sta11 = 2;
                else if(v1 > c[pos]) sta11 = 1;
                else sta11 = 0;
            }
            if(sta2 == 0)
            {
                if(v2 > c[pos]) sta22 = 2;
                else if (v2 < c[pos]) sta22 = 1;
                else sta22 = 0;
            }
            //回溯时还要用到原来的值
            sum += dfs(pos - 1, sta11, sta22, lim1 && i == a[pos], lim2 && j == b[pos]);
        }
    }
    dp[pos][sta1][sta2][lim1][lim2] = sum;
    return sum;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    get_pow2();
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d %d", &x, &y, &z);
        int len = init();
        printf("%lld\n", dfs(len, 0, 0, true, true) - min(x, z - 1) - min(y, z - 1) - 1);
    }
    return 0;
}