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$即可。
好劲的一道题,感觉最近总是在跟二进制的按位考虑打交道 = =

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*************************************************************************
> 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;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: