4124 [CQOI2016] 手机号码

link

#include <bits/stdc++.h>
using namespace std;
#define int long long
long long l, r;
long long f[15];
long long dp[12][12][12][2][2][2][2];
long long dfs(int len, int pre1, int pre2, bool com, bool lim, bool lim8, bool lim4) {
	if(lim8 && lim4) return 0;
	if(!len) return com;
	if(dp[len][pre1][pre2][com][lim][lim8][lim4] != -1) return dp[len][pre1][pre2][com][lim][lim8][lim4];
	int maxn = lim ? f[len] : 9;
	long long tmp = 0;
	for(int i = 0; i <= maxn; i++) {
//		printf("%d\n", len);
		tmp += dfs(len - 1, i, pre1, com || (i == pre1 && i == pre2), (i == f[len]) && lim, lim8 || (i == 8), lim4 || (i == 4));
	}
	return dp[len][pre1][pre2][com][lim][lim8][lim4] = tmp;
}
long long solve(long long n, bool flag) {
	memset(dp, -1, sizeof dp);
	int cnt = 0;
	long long tmp = n;
	while(tmp) {
		cnt++;
		f[cnt] = tmp % 10;
		tmp /= 10;
	}
	tmp = 0;
//	printf("%lld\n", cnt);
	for(int i = 1; i <= f[cnt]; i++) tmp += dfs(cnt - 1, i, 12, 0, (i == f[cnt]), 0, 0);
	return tmp;
}
signed main() {
	scanf("%lld%lld", &l, &r);
	printf("%lld", solve(r, 0) - solve(l - 1, 1));
	return 0;
}