题目链接：https://ac.nowcoder.com/acm/contest/887/H
题意：给定A,B,C，求有多少对(x,y)满足x&y>C或者x^y<C，其中1<=x<=A,1<=y<=B。
思路：首先逆向考虑，求有多少对(x,y)满足x&y<=C且x^y>=C，然后用A*B去减它即可。然后就是数位dp模板题，用dp[pos][la][lb][land][lxor]表示到第pos位的个数，la位表示是否是A的上限，lb表示是否是B的上限，land表示 与 的上限是否是C，lxor表示 异或 的下限是否是C，因为该dp表示的值与输入的A,B,C有关，所以每次都要memset置-1。因为dfs存在x或y为0的情况，而x、y最小是1，所以要减掉x或y为0的情况。x为0的个数有max(0,B-C+0)，即y>=C;同理，y为0有max(0,A-C+0)种。
AC代码：
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; LL dp[35][2][2][2][2],A,B,C,ans; int T,a[35],b[35],c[35]; void init(){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); LL aa=A,bb=B,cc=C; int pos=0; while(aa){ a[pos++]=aa%2; aa/=2; } pos=0; while(bb){ b[pos++]=bb%2; bb/=2; } pos=0; while(cc){ c[pos++]=cc%2; cc/=2; } } LL dfs(int pos,int la,int lb,int land,int lxor){ if(pos<0) return 1; if(dp[pos][la][lb][land][lxor]!=-1) return dp[pos][la][lb][land][lxor]; LL res=0; int up1=1,up2=1,up3=1,up4=0; if(la) up1=a[pos]; if(lb) up2=b[pos]; if(land) up3=c[pos]; if(lxor) up4=c[pos]; for(int i=0;i<=up1;++i) for(int j=0;j<=up2;++j){ if((i&j)>up3) continue; if((i^j)<up4) continue; res+=dfs(pos-1,la&&(i==a[pos]),lb&&(j==b[pos]),land&&((i&j)==c[pos]),lxor&&((i^j)==c[pos])); } return dp[pos][la][lb][land][lxor]=res; } int main(){ scanf("%d",&T); while(T--){ memset(dp,-1,sizeof(dp)); scanf("%lld%lld%lld",&A,&B,&C); init(); ans=dfs(30,1,1,1,1); ans=ans-max(A-C+1,0LL)-max(B-C+1,0LL); printf("%lld ",A*B-ans); } return 0; }