群里有人问了这个问题

然后被attack秒了orz

考虑数位DP

预处理v[第几位][该位是否是目标数字][是否有目标数字]

显然数字除了0之外的求解过程是完全一致的

那么我们特判0就可以了

#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;long long L,R,val;long long v[19][2][2],pw[19],lis[19];long long dfs(long long x,int ct,bool fl){    if(!ct) return fl?x+1:x>=val;    int w=x/pw[ct];long long sum=0;    for(int i=0;i
    
     val) sum+=pw[ct];    return sum+dfs(x-pw[ct]*w,ct-1,fl||w==val);}long long slv(long long x){    if(x<10) return x>=val;    int ct=18;    while(pw[ct]>x) --ct;    int w=x/pw[ct];    long long sum=(val?v[ct-1][1][1]:lis[max(ct-2,0)]+1)+v[ct-1][0][1];    for(int i=1;i
     
      val) sum+=pw[ct];    return sum+dfs(x-pw[ct]*w,ct-1,w==val);}int main(){    pw[0]=1;v[0][1][1]=1,v[0][0][0]=9;    for(int i=1;i<=18;++i) pw[i]=pw[i-1]*10;    for(int i=1;i<=17;++i){        v[i][0][1]+=9*(v[i-1][1][1]+v[i-1][0][1]);        v[i][0][0]+=9*v[i-1][0][0];        v[i][1][1]+=v[i-1][1][1]+v[i-1][0][1]+v[i-1][0][0];        lis[i]=v[i][0][1]+lis[i-1];    }scanf("%lld%lld%d",&L,&R,&val);--L;    printf("%lld\n",slv(R)-slv(L));    return 0;}