2016-10-08

HDU 5803 Zhu’s Math Problem【数位dp】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5803

题意：

给定四个数$A,B,C,D$，求满足$a+c>b+d，a+d\geq b+c$的四元组$(a,b,c,d)$的个数，其中$0\leq a\leq A,0\leq b \leq B,0\leq c \leq C,0\leq d \leq D$
数据范围:$0 \le A,B,C,D \le 10^{18}$

分析：

考虑数位DP，从高位到低位依次放数字即可，加上状态表示a+c-b-d,a+d-b-c即可。
比较直接的是$4$个数每一位$[0,9]$的枚举，然后记录当前$a+c-b-d,a+d-b-c$的值，再记录一下当前四个数的值是否为上限。下面考虑优化。
我们发现如果某位有$a+c-b-d \ge 2$，累积到下一位至少为$20$，那么下一位即使差了$2 \times 9=18$也不影响大小。同样如果$a+c-b-d \le -2$，那么下一位即使多了$18$也依然小于$0$。所以对于$a+c>b+d，a+d\geq b+c$的状态即可用$[-2,2]$表示。
接下来考虑每位的枚举，$10^4$的枚举肯定行不通，采用二进制优化，将数转化为二进制进行处理，每次的枚举就降到了$2^4$，而$a+c>b+d，a+d\geq b+c$同样满足刚才那个性质，可以用$[-2,2]$表示。
这样从高位到低位依次放数字，套个数位$dp$即可。
好劲的一道题，感觉最近总是在跟二进制的按位考虑打交道 = =

代码：

/*************************************************************************
    > File Name: 5803.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/10/8 13:54:55
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 18 + 5, mod = 1e9 + 7;
int dp[17][66][5][5];
int a[5][65];
int dfs(int pos, int s1, int s2, int top)
{
	if(pos < 0){
		return s1 > 0 && s2 >= 0;
	}
	if(dp[top][pos][s1 + 2][s2 + 2] != -1) return dp[top][pos][s1 + 2][s2 + 2];
	int up[4];
	for(int i = 0; i < 4; ++i){
		up[i] = (top >> i & 1)?1:a[i][pos];
	}
	int ans = 0;
	for(int a = 0; a <= up[0]; ++a){
		for(int b = 0; b <= up[1]; ++b){
			for(int c = 0; c <= up[2]; ++c){
				for(int d = 0; d <= up[3]; ++d){
					int ns1 = s1 * 2 + a + c - b - d;
                    int ns2 = s2 * 2 + a + d - b - c;
					ns1 = min(ns1, 2);
					ns2 = min(ns2, 2);
					if(ns1 <= -2 || ns2 <= -2) continue;
					int ntop = top;
					if(a != up[0]) ntop |= 1 << 0;
					if(b != up[1]) ntop |= 1 << 1;
					if(c != up[2]) ntop |= 1 << 2;
					if(d != up[3]) ntop |= 1 << 3;
					(ans += dfs(pos - 1, ns1, ns2, ntop)) %= mod;
				}
			}
		}
	}
	return dp[top][pos][s1 + 2][s2 + 2] = ans;
}
ll A, B, C, D;
int main (void)
{
	 int T;scanf("%d", &T);
	 while(T--){
		memset(dp, -1, sizeof(dp));
		scanf("%lld%lld%lld%lld", &A, &B, &C, &D);
		for(int i = 0; i <= 60; ++i){
			a[0][i] = A >> i & 1;
			a[1][i] = B >> i & 1;
			a[2][i] = C >> i & 1;
			a[3][i] = D >> i & 1;
		}
		printf("%d\n", dfs(60, 0, 0, 0));
	 }
	 return 0;
}