HDU 5803（2016多校第6场） 数位dp

题意：

You are given four integers A , B , C , D , there are many different (a,b,c,d) satisfy a+c>b+d && a+d≥b+c && 0≤a≤A && 0≤b≤B && 0≤c≤C && 0≤d≤D ?

做法：

可以将四个数都拆成2进制，用记忆化搜索来统计。记w1=a+c-b-d,w2=a+d-b-c,如果搜的过程中w1大于2其实可以把它变成2，对答案不影响，如果w1小于2则直接剪枝。w2也同理。

（比赛的时候完全没想到数位dp，看了huanzhizun的博客才会做）I good vegetable！a ！

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=64,mo=1e9+7;
ll A,B,C,D;
int a[N],b[N],c[N],d[N];
int f[N][2][2][2][2][5][5];
void add(int &x,int y)
{
	x=(x+y)%mo;
}
void cg(ll x,int *a)
{
	for (int i=0;i<N;i++) a[i]=0;
	int cnt=0;
	while(x) a[++cnt]=x%2,x/=2;
}
int dfs(int pos,bool u1,bool u2,bool u3,bool u4,int w1,int w2)
{
	if (pos==0) return w1>0&&w2>=0;
	int ret=f[pos][u1][u2][u3][u4][w1+2][w2+2];
	if (ret!=-1) return ret;
	ret=0;

	int d1=1,d2=1,d3=1,d4=1;
	if (u1) d1=a[pos];
	if (u2) d2=b[pos];
	if (u3) d3=c[pos];
	if (u4) d4=d[pos];

	for (int i1=0;i1<=d1;i1++)
	for (int i2=0;i2<=d2;i2++)
	for (int i3=0;i3<=d3;i3++)
	for (int i4=0;i4<=d4;i4++)
	{
		int ww1=w1*2+i1+i3-i2-i4;
		int ww2=w2*2+i1+i4-i2-i3;
		if (ww1>2) ww1=2;
		if (ww2>2) ww2=2;
		if (ww1<-2) continue;
		if (ww2<-2) continue;

		bool uu1=u1,uu2=u2,uu3=u3,uu4=u4;
		if (i1<a[pos]) uu1=0;
		if (i2<b[pos]) uu2=0;
		if (i3<c[pos]) uu3=0;
		if (i4<d[pos]) uu4=0;

		add(ret,dfs(pos-1,uu1,uu2,uu3,uu4,ww1,ww2));
	}
	return f[pos][u1][u2][u3][u4][w1+2][w2+2]=ret;
}
int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
		cg(A,a); cg(B,b); cg(C,c); cg(D,d);
		memset(f,-1,sizeof(f));
		printf("%d\n",dfs(63,1,1,1,1,0,0));
	}
}