在给定范围的数据中找到含有6的数据个数

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 2e5 + 5; //限定N变量为只读
LL a[20];
LL dp[20];
LL dfs(LL len,bool limit) {
    if(len == 0) return 1LL;  //longlong类型的1. 某个数*1LL是为了从int类型转成longlong类型
    if(!limit && dp[len]) return dp[len];    
    LL m = (limit) ? a[len] : 9;    //如果limit是真（是1或True），m=a【len】; 如果limit是假(是0或false），m=9
    LL cnt = 0;
    for(LL i=0;i<=m;i++) {
        if(i == 6) continue;
        cnt += dfs(len-1,limit && (i == m));
    }
    return dp[len] = cnt;
}
LL six(LL n) {
    memset(dp,0,sizeof(dp));
    LL k = 0;
    while(n) {
        a[++k] = n % 10;
        n /= 10;
    }
    return dfs(k,1);
}
int main() {
    LL l,r;
    scanf("%lld %lld",&l,&r);
    LL ans = (r - l + 1) - (six(r) - six(l-1));
    printf("%lld\n",ans);
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 25;
ll dp[N][10];
ll n,m;
void init(){
    for(int i = 1;i<=20;i++){
        for(int j=0;j<=9;j++){
            if(j!=6){
                for(int k=0;k<=9;k++)
                    dp[i][j]+=dp[i-1][k];
            }
            else{
                ll tmp = 1;
                for(int q=1;q<=i-1;q++)
                    tmp*=10;
                dp[i][j]=tmp;
            }
        }
    }
}
int v[N];
ll solve(ll di){
    ll res=0;
    v[0]=0;
    while(di){ // 将数字存入v数组,并且用v[0]记录位数
        v[++v[0]]=di%10;
        di/=10;
    }
    for(int i=v[0];i>=1;i--){ // 逐位排查
        for(int j=0;j<v[i];j++){ // 对此位的各种取值可能进行判断
            res+=dp[i][j];// 这里面加的dp,如果是含6就会加上所有含有6的那几千万种可能，可能是1000,1000000等
        }
// 也就是这个大佬的解题思路是   1.  加上各位是6的dp可能
                            //  2.  加上一个位置是6后的各种位置的花式取值
        if(v[i]==6){ // 本位的60000……的10000……种可能已经在前面加过了
            ll tmp = 0;
            for(int k=i-1;k>=1;k--){// 500 对应后面有 500种可能，就是先5 再 *10  再*10
                tmp=tmp*10+v[k];
            }
            res+=tmp;
            break;
        }
    }
    return res;
}
int main(){
    init();
    scanf("%lld%lld",&n,&m);
    ll res1 = solve(m+1);
    ll res2 = solve(n);
    printf("%lld\n",res1-res2);
}