题意：

T次询问，每次给出A,B,K,W，求满足下面条件的(x,y)对数：

1.x,y是整数

2. x ∈ [ 0 , A ] , y ∈ [ 0 , B ] x \in [0,A],y\in[0,B] x∈[0,A],y∈[0,B]

3. ∣ x − y ∣ ≤ K |x-y|\leq K ∣x−y∣≤K

4. x   x o r   y ≤ W x~ xor~ y\leq W x xor y≤W

A , B , K , W ≤ 1 0 9 , T ≤ 2000 A,B,K,W\leq10^9,T\leq2000 A,B,K,W≤109,T≤2000

Solution:

首先我们把条件3拆成两个条件: x + K ≥ y x+K\geq y x+K≥y和 y + K ≥ x y+K\geq x y+K≥x

然后我们考虑数位DP，因为有异或条件的限制，所以我们的每一位指的是二进制下的每一位，因为涉及到加法操作，只能从低位向高位DP，DP时记录有没有进位即可。

状态设为：

f [ l e n ] [ x ≤ A ] [ y ≤ B ] [ x + K ≥ y ] [ x 的 进 位 ] [ y + K ≥ x ] [ y 的 进 位 ] [ x   x o r   y ≤ W ] f[len][x\leq A][y\leq B][x+K\geq y][x的进位][y+K\geq x][y的进位][x~xor~y\leq W] f[len][x≤A][y≤B][x+K≥y][x的进位][y+K≥x][y的进位][x xor y≤W]

对于不等式的判断如何转移呢？

我们只需要记录只考虑当前位和低位时不等式是否成立即可，具体转移细节看代码，应该还是挺好懂的。

以前一直以为低位向高位无法转移，今天学会了一个新的姿势。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
long long f[40][2][2][2][2][2][2][2];
//bit x<=a y<=b x+k>=y 进位 y+k>=x 进位 x^y<=w 
int T,a,b,k,w;
long long dfs(int len,int xa,int xb,int xky,int addx,int ykx,int addy,int xyw)
{
	if (len==31)
	{
		if (xa&&xb&&(xky||(!xky&&addx))&&(ykx||(!ykx&&addy))&&xyw) return 1;
		return 0;
	}
	if (f[len][xa][xb][xky][addx][ykx][addy][xyw]!=-1) return f[len][xa][xb][xky][addx][ykx][addy][xyw];
	long long ans=0;
	int abit=(a>>len)&1,bbit=(b>>len)&1,kbit=(k>>len)&1,wbit=(w>>len)&1;
	for (int i=0;i<=1;i++)
		for (int j=0;j<=1;j++)
		{
			bool nxa=(xa&&i<=abit)||(!xa&&i<abit);
			bool nxb=(xb&&j<=bbit)||(!xb&&j<bbit);
			bool nxky=(xky&&((i+kbit+addx)&1)>=j)||(!xky&&((i+kbit+addx)&1)>j);
			bool nykx=(ykx&&((j+kbit+addy)&1)>=i)||(!ykx&&((j+kbit+addy)&1)>i);
			bool naddx=(i+kbit+addx)>>1;
			bool naddy=(j+kbit+addy)>>1;
			bool nxyw=(xyw&&(i^j)<=wbit)||(!xyw&&(i^j)<wbit);
			ans+=dfs(len+1,nxa,nxb,nxky,naddx,nykx,naddy,nxyw);
		}
	return f[len][xa][xb][xky][addx][ykx][addy][xyw]=ans;
}
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d%d%d",&a,&b,&k,&w);
		memset(f,-1,sizeof(f));
		dfs(0,1,1,1,0,1,0,1);
		printf("%lld\n",f[0][1][1][1][0][1][0][1]);
	}
}