もうバグらせない桁dp

こんな感じで書けばいいと思うよ

//n = 桁数
//k = 状態数(余りか最後の桁が多い)
vector<mat<ll>> dp(n+1, mat<ll>(k, vl(2)));
dp[0][0][1] = 1;//0桁の時
rep(i, n)rep(j, k){
    rep(d, 10){
        dp[i+1][f(j ,d)][0] += dp[i][j][0];//前の状態がdp[i][j][0]でi+1桁目をdにする遷移
    }
    rep(d, m[i+1]){
        dp[i+1][f(j, d)][0]+=dp[i][j][1];//前の状態がdp[i][j][1]でi+1桁目をdにする遷移
    }
    dp[i+1][f(j, m[i])][1] += dp[i][j][1];
}

0でpaddingするとまずい問題は以下のようにするのがいいかも

mx = list(map(int, list(str(mid))))
mx = list(map(int, list(str(mid))))
n = len(mx)
dp = [[[0]*2 for i in range(s)] for j in range(n+1)]
//1桁目は手動で
for i in range(1, mx[0]):
    dp[1][i][0] = 1
dp[1][mx[0]][1] = 1

for i in range(1, n):
    for j in range(10):
        for d in range(10):
            if abs(j-d)<=1:
                dp[i+1][d][0]+=dp[i][j][0]
        for d in range(mx[i]):
            if abs(j-d)<=1:
                dp[i+1][d][0]+=dp[i][j][1]
        d = mx[i]
        if abs(j-d)<=1:
            dp[i+1][d][1]+=dp[i][j][1]
    //i+1桁目が最高位になる場合をたす
    for d in range(1, 10):
        dp[i+1][d][0]+=1