数字计数

题意：问[a,b]中0-9的数码各出现了多少次。a,b≤10¹²

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long 
using namespace std;

inline LL read()
{
    LL f=1,x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

LL l,r;
LL dp[15][15][2][2];
int a[15],q;

LL dfs(int pos,int sum,bool flag,bool done)
{
    if(pos==0)
        return sum;
    if(!done && dp[pos][sum][flag][done]!=-1)
        return dp[pos][sum][flag][done];
    int r=done ? a[pos] : 9;
    LL res=0;
    for(int i=0;i<=r;i++)
    {
        res+=dfs(pos-1,sum+((!flag || i) && i==q),flag && i==0,done && i==a[pos]);
    }
    if(dp[pos][sum][flag][done]=-1)
        dp[pos][sum][flag][done]=res;
    return res;
}

LL init(LL x)
{
    memset(dp,-1,sizeof(dp));
    int cnt=0;
    while(x>0)
    {
        a[++cnt]=x%10;
        x/=10;
    }
    return dfs(cnt,0,1,1);
}

int main()
{
    l=read(); r=read();
    for(int i=0;i<=9;i++)
    {
        q=i;
        printf("%lld ",init(r)-init(l-1));
    }
    return 0;
}