输入正整数A,B,C,统计满足1≤x≤A,1≤y≤B且至少满足下列条件之一:
①x and y > C
②x xor y < C
的对儿(x,y)有多少个.
数据范围:1≤A,B,C≤10⁹.

分析

10⁹的二进制数至多30位,所以我们在二进制下做数位dp.

至少满足①或②的对立面是既不满足①也不满足②,即(and条件)且(xor条件).我们转而统计这种对儿有多少个,因为这样做比较方便.

在设计dp之前,我们先思考一些简单的问题.

首先,我们考虑x和y的最高位,因为是最高位,所以仅就这1位而言它必然要同时满足and条件和xor条件,我们定义为"边界and条件",为"严格and条件",xor条件也做相同定义.那么最高位有这么4种可能:

①严格and,严格xor
那么后一位(次高位)就可以无视and和xor这两个条件了,因为无论如何都会满足的.
②边界and,严格xor
那么后一位可以无视xor这个条件了
③严格and,边界xor
那么后一位可以无视and这个条件了
④边界and,边界xor
那么nothing will happen

所以我们设计dp[i][and][xor]表示:考虑第i位,是/否满足and条件,是/否满足xor条件的方案数.如果最高位是30位,那么最终的答案是dp[30][1][1],后两个参数均为1表示满足and和xor条件.

但这样还有问题,就是我们没有考虑A,B对x,y的限制.
同样,从最高位的情况开始思考,对于x,y的最高位分别与A,B的关系我们有4种情况:

①x<A,y<B
那么后一位可以无视A,B的限制了
②x=A,y<B
那么后一位可以无视B的限制了
③x<A,y=B
那么后一位可以无视A的限制了
④x=A,y=B
那么nothing will happen

所以我们设计dp[i][and][xor][_A][_B],最后两个参数为1或0,表示是/否需要满足A和B的限制.如此我们最后的答案是dp[30][1][1][1][1].

然后我们考虑dp[i][and][xor][A][B]的转移.
枚举第i位x和y的值.

我们发现,各种条件可能会限制x和y的取值.具体来说,如果A,B,C的第i位分别是a,b,c的话(a,b,c=0或1),那么有:
x ≤ (_A?a:1)
y ≤ (_B?b:1)
x&y ≤ (and?c:1)
x^y ≥ (xor?c:0)
在确定了某一种x和y之后,我们就可以转移到后一位的dp了,后一位的4个限制条件转移如下:
newand = and&(x&y==c)
newxor = xor&(x^y==c)
new_A = _A&(x==a)
new_B = _B&(y==b)

然后就可以写出如下程序:

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;

ll A,B,C,dp[35][2][2][2][2];

ll dfs(int i,int And,int Xor,int _A,int _B){
    if(i==-1)return 1;
    ll& ans=dp[i][And][Xor][_A][_B];
    if(ans>=0)return ans;
    ans=0;
    int a=(A>>i)&1,
        b=(B>>i)&1,
        c=(C>>i)&1;
    for(int x=0;x<=1;x++)
    for(int y=0;y<=1;y++)
    if(x<=(_A?a:1)
        &&y<=(_B?b:1)
        &&(x&y)<=(And?c:1)
        &&(x^y)>=(Xor?c:0))
    {
        ans+=dfs(i-1,And&((x&y)==c),Xor&((x^y)==c),_A&(x==a),_B&(y==b));
    }
    return ans;
}

void solve(){
    scanf("%lld%lld%lld",&A,&B,&C);
    memset(dp,-1,sizeof dp);
    printf("%lld\n",A*B-(dfs(30,1,1,1,1)-max(B-C+1,0ll)-max(A-C+1,0ll)));
}

int main(){
    int T;scanf("%d",&T);
    while(T--)solve();
}