学步园

思路：状态压缩，dp[i][s]表示第i位数时，数字状态为s的数量，状态s要用三进制数来表示，0表示不存在，1表示偶数，2表示奇数，这样状态设计出来，进行数位DP转移即可

代码：

#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;
}