题目描述

Description

给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

Input

输入文件中仅包含一行两个整数a、b，含义如上所述。

Output

输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。

Sample Input

1 99

Sample Output

9 20 20 20 20 20 20 20 20 20

HINT

30%的数据中，a<=b<=10^6；
100%的数据中，a<=b<=10^12。

题目分析

数位DP
预处理出i位 以j开头的数 数字k出现了多少次
然后就正常DP即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long po[20];
long long dp[20][10][10];
void init()
{
    po[0]=1;
    for(int i=1;i<=13;i++) po[i]=po[i-1]*10; 
    for(int i=0;i<=9;i++) dp[1][i][i]=1;
    for(int i=2;i<=13;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<=9;k++)
            {
                if(j==k) dp[i][j][k]+=po[i-1];
                for(int z=0;z<=9;z++) dp[i][j][k]+=dp[i-1][z][k];
            }
}
int sta[100];
long long tmp[10],ans[10];
void slove(long long x)
{
    if(!x) return ;
    memset(tmp,0,sizeof tmp);
    sta[0]=0;
    long long nmp=x;
    while(x) sta[++sta[0]]=x%10,x/=10;
    for(int i=1;i<=sta[0]-1;i++)
        for(int j=1;j<=9;j++)
            for(int k=0;k<=9;k++) tmp[k]+=dp[i][j][k];
    for(int i=sta[0];i>=1;i--)
    {
        for(int j=(i==sta[0]);j<sta[i];j++) 
            for(int k=0;k<=9;k++) tmp[k]+=dp[i][j][k];
        tmp[sta[i]]+=nmp%po[i-1];
    }
}
int main()
{   
    long long a,b;
    init();
    scanf("%lld%lld",&a,&b);
    slove(b+1);
    for(int i=0;i<=9;i++) ans[i]=tmp[i];
    slove(a);
    for(int i=0;i<=9;i++)
        printf("%lld%c",ans[i]-tmp[i],i==9?'\n':' ');
    return 0;
}