## SPOJ BALNUM Balanced Numbers（数位DP + 状态压缩）

2018年10月12日 ⁄ 综合 ⁄ 共 1248字 ⁄ 字号 评论关闭

```#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef unsigned long long ll;

int t;
ll a, b;
int bit[25], bn;

ll get(ll x) {
bn = 0;
while (x) {
bit[bn++] = x % 10;
x /= 10;
}
for (int i = 0; i < bn / 2; i++)
swap(bit[i], bit[bn - i - 1]);
}

ll dp[25][60000][2];
int tmp[10];

int getnext(int s, int x) {
int ans = 0;
for (int i = 0; i < 10; i++) {
tmp[i] = s % 3;
s /= 3;
}
if (x == 0) {
int flag = 0;
for (int i = 0; i < 10; i++) {
if (tmp[i]) {
flag = 1;
break;
}
}
if (flag) {
if (tmp[x] == 0) tmp[x] = 1;
tmp[x] = 3 - tmp[x];
}
} else {
if (tmp[x] == 0) tmp[x] = 1;
tmp[x] = 3 - tmp[x];
}
for (int i = 9; i >= 0; i--)
ans = ans * 3 + tmp[i];
return ans;
}

bool judge(int s) {
for (int i = 0; i < 10; i++) {
tmp[i] = s % 3;
s /= 3;
if (tmp[i] == 0) continue;
if (i % 2 && tmp[i] == 2) return false;
if (i % 2 == 0 && tmp[i] == 1) return false;
}
return true;
}

ll dfs(int u, int s, int flag) {
ll &ans = dp[u][s][flag];
if (ans != -1) return ans;
int end = 9;
ans = 0;
if (u == bn) {
if (judge(s)) ans = 1;
else ans = 0;
return ans;
}
if (!flag) end = bit[u];
for (int i = 0; i <= end; i++) {
if (flag) ans += dfs(u + 1, getnext(s, i), 1);
else {
if (i < end) ans += dfs(u + 1, getnext(s, i), 1);
else ans += dfs(u + 1, getnext(s, i), 0);
}
}
return ans;
}

ll solve(ll x) {
if (x == 0) return 1;
get(x);
memset(dp, -1, sizeof(dp));
return dfs(0, 0, 0);
}

int main() {
scanf("%d", &t);
while (t--) {
scanf("%llu%llu", &a, &b);
printf("%llu\n", solve(b) - solve(a - 1));
}
return 0;
}```