kuangbin专题十五：数位DP

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int maxn = 12;

int dp[maxn][15];
vector<int> v;

int dfs(int pos, int st, int sig){
    if(!pos) return st != 4;
    if(!sig && ~dp[pos][st]) return dp[pos][st];

    int maxx = sig ? v[pos] : 9, res = 0;
    for(int i = 0; i <= maxx; i++){
        if(i == 4) continue;
        if(st == 6 && i == 2) continue;

        if(st == 10 && i == 0)
            res += dfs(pos-1, 10, sig&(i==maxx));
        else
            res += dfs(pos-1, i, sig&(i==maxx));
    }
    if(!sig) dp[pos][st] = res;
    return res;
}

int solve(int n){
    memset(dp, -1, sizeof(dp));
    v.clear();
    v.push_back(-1);
    while(n){
        v.push_back(n % 10);
        n /= 10;
    }
    return dfs(v.size()-1, 10, 1);
}

int main(){
    int n, m;
    while(cin >> n >> m && m){
        cout << solve(m) - solve(n-1) << endl;
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int maxn = 20;

unsigned long long dp[maxn][15];
int v[maxn];

unsigned long long dfs(int pos, int st, int sig){
    if(pos < 0) return 1;
    if(!sig && ~dp[pos][st]) return dp[pos][st];
    int maxx = sig ? v[pos] : 9;
    unsigned long long res = 0;
    for(int i = 0; i <= maxx; i++){
        if(st == 4 && i == 9) continue;
        if(st == 10 && i == 0)
            res += dfs(pos-1, 10, sig & (i==maxx));
        else
            res += dfs(pos-1, i, sig & (i==maxx));
    }
    if(!sig) dp[pos][st] = res;
    return res;
}

unsigned long long solve(unsigned long long n){
    int len = 0;
    while(n){
        v[len++] = n % 10;
        n /= 10;
    }
    return dfs(len-1, 10, 1);
}

int main(){
    memset(dp, -1, sizeof(dp));
    unsigned long long T, n;
    cin >> T;
    while(T--){
        cin >> n;
        cout << n + 1 - solve(n) << endl;
    }
    return 0;
}