C++ – P4124 数位 DP

dfs(数的最后若干位,各种限制条件,当前第几位)
    if 最后一位
        return 各种限制条件下的返回值
    局部变量 ct=当前位的数字
    局部变量 sum=0;
    for i=0 to ct-1
        sum+=当前位取i时一定无无限制的合法状态数
        sum+=当前位取i时满足当前限制的合法状态数
    根据ct更新限制条件 不再满足则return sum
    return sum+dfs(当前位后的若干位,更新后的限制条件,下一位)

slv(当前数)
    if(只有一位) return 对应的贡献
    局部变量 ct;
    for ct=可能最高位 to 1
        if 当前位有数字 break
    局部变量 nw=当前位数字
    局部变量 sum=0
    for i=1 to nw-1
        sum+=当前位取i后合法情况任意取的贡献
    for i=1 to ct-1
        for j=1 to 9
            sum+=第i位取j后合法情况任意取的贡献
    sum+=dfs(去掉第一位后的若干位,限制条件,第二位)
    return sum

main
    预处理当前位取i的各种条件各种限制的贡献
    读入 L R
    --L
    输出 slv(R)-slv(L)
    return 0

#include <cstdio>
#include <cstring>
using namespace std;
int num[11];
long long dp[11][11][11][2][2][2][2];
long long fs(int p, int a, int b, bool c, bool d, bool _4, bool _8) {
    if(~dp[p][a][b][c][d][_4][_8]) return dp[p][a][b][c][d][_4][_8];
    if(_4 && _8) return dp[p][a][b][c][d][_4][_8] = 0;
    if(p <= 0) return dp[p][a][b][c][d][_4][_8] = c;
    long long res = 0;
    int lim = !d ? num[p - 1] : 9;
    for(int i = 0; i <= lim; i++)
        res += fs(p - 1, i, a, c || (i == b && i == a), d || (i < lim), _4 || (i == 4), _8 || (i == 8));
    return dp[p][a][b][c][d][_4][_8] = res;
}
long long solve(long long x) {
    if(x < 1e10) return 0;
    memset(dp, -1, sizeof dp);
    for(int i = 0; i < 11; i++) {
        num[i] = x % 10;
        x /= 10;
    }
    long long res = 0;
    for(int i = 1; i <= num[10]; i++) 
        res += fs(10, i, 0, false, i < num[10], i == 4, i == 8);
    return res;
}
int main() {
    long long l, r;
    scanf("%lld %lld", &l, &r);
    printf("%lld", solve(r) - solve(l - 1));
    return 0;
}