BZOJ-1833: [ZJOI2010]count 数字计数

Description

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

数位DP。dp[i][j][k]表示i位数，以j开头，数码k的个数。统计答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll L,R,dp[20][10][10];//dp[i][j][k]表示i位数首位为j的数码k出现的次数
void initialize()
{
    for(int i=0;i!=10;++i) dp[1][i][i]=1;
    ll now=10;
    for(int i=2;i<=12;++i)
    {
        for(int j=0;j!=10;++j)
        {
            for(int k=0;k!=10;++k)
            {
                for(int t=0;t!=10;++t)
                    dp[i][j][k]+=dp[i-1][t][k];
            }
            dp[i][j][j]+=now;
        }
        now*=10;
    }
}
ll getans(ll x,int y)
{
    static int z[20]; int top=0; ll re=0;
    while(x) z[++top]=x%10,x/=10;
    for(int i=1;i<z[top];++i) re+=dp[top][i][y];
    for(int i=top-1;i;--i) for(int j=1;j<10;++j) re+=dp[i][j][y];
    for(int i=top-1;i;--i)
    {
        for(int j=0;j<z[i];++j) re+=dp[i][j][y];
        if(z[i+1]==y)
        {
            ll tmp=0;
            for(int j=i;j;--j) tmp=tmp*10+z[j];
            re+=tmp;
        }
    }
    return re;
}
int main()
{
    scanf("%lld%lld",&L,&R); initialize();
    for(int i=0;i<10;++i) printf("%lld%c",getans(R+1,i)-getans(L,i),i==9?'\n':' ');
    return 0;
}