51nod 1042 数字0-9的数量 数位DP

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1042

题目：

给出一段区间a-b，统计这个区间内0-9出现的次数。比如 10-19，1出现11次（10,11,12,13,14,15,16,17,18,19,其中11包括2个1)，其余数字各出现1次。 Input

两个数a,b（1 <= a <= b <= 10^18)

Output

输出共10行，分别是0-9出现的次数

这题感觉挺麻烦的，纠结了好久。

我们用递归来考虑每一位。分成已经计算过的低位，当前位，还没计算的高位。

处理当前位时无非这几种情况：

1、当前位与低位的关系

2、高位与低位的关系

3、当前为与高位的关系

对三种情况进行处理即可。要注意0的特殊情况，例如 01 其实没有0。

#include <iostream>
#include<bits/stdc++.h>
#define ll long long
using namespace std;

void dfs(ll a,ll b,ll c[])
{
    ll n=a/10,m=a%10,t=n;
    for(int i=0;i<=m;i++)   c[i]+=b;//当前位对低位的影响
    for(int i=0;i<10;i++)   c[i]+=b*n;//高位对低位的影响
    c[0]-=b;//0特殊处理，将多算的0减去
    while(t)//当前位对高位的影响
    {
        c[t%10]+=b*(m+1);//加上0
        t/=10;
    }
    if(n)   dfs(n-1,b*10,c);//n已经处理过，所以要处理n-1
}

ll x[20],y[20];

int main()
{
    ll a,b;
    cin>>a>>b;
    dfs(a-1,1,x);
    dfs(b,1,y);
    for(int i=0;i<10;i++)   cout<<y[i]-x[i]<<endl;
}