【详细解释】数字计数 ZJOJ p2602 一道练习数位DP的好题
才刚刚考完noip老师就让我们开始了惨绝人寰的学习，不过为了明年的冲刺和省队，大家一起加油吧
数位DP整理链接
开始补之前没学的，落下的东西了2333，一开始就是我最不会的最玄学的DP。
首先让我们来看一下数位DP这玩意到底是啥，对于一些刚开始练的萌新（我）来说会比较好。
数位DP一般他对问题的求解都是与数字上的位数有关，比如统计数字出现个数，有多少个数字之类的，这类问题一般能用数位dp做的，都是可以从小数字推到大数字的。比如我们从第一位往后可以一层一层，逐渐推出我们需要的答案。
而解决这类问题其实不止DP（递推）还包括了记忆化搜索（模板），但是由于我不会也不喜欢敲记忆化所以大多我是用的递推，虽然我觉得递推更好理解但是也有人觉得记忆化更简单，如果是刚学，就自己都试试吧，不一定非要递推。在这里推荐给大家另几道题，如果你要练习数位DP的话，难度都差不多，反正我觉得比这题简单
* 【SCOI2009】windy数
* 【HDU2089】 不要62
* hdu 3652
如果你学数位dp上来就切这一题的话，我建议先去做做以上几题。
在这里我的写法参照了大奕哥这位dalao的题解，大家也可以看看，在这里我会针对我的理解来写。
那么我们首先看题，对于这道题我一开始以为很水，但是当我仔细去读题之后发现事情没那么简单。其中对于这道题（递推做法）最大的难点是难以找出递推式子（废话，你写递推就只有这点难了）。为啥，因为你很难想到怎样求出第几位它的数字又多少，因为不能有前导0。但是我们发现如果不考虑是否有前导0的话，那么这道题就似乎有递推公式。
f[i]代表在有i位数字的情况下，每个数字有多少个。如果不考虑前导0，你会发现对于每一个数，它的数量都是相等的，也就是f[i]=f[i-1]*10+10^(i-1);(这里我推荐使用打表+大眼观察法)
然而这个公式推出来后，你就会面临第二个难题，怎么推出我想要的答案？
我们先设数字为ABCD
看A000，如果我们要求出它所有数位之和，我们会怎么求？
鉴于我们其实已经求出了0~9,0~99,0~999。。。上所有数字个数（f[i],且没有考虑前导0）我们何不把这个A000看成0000~1000~2000...A000对于不考虑首位每一个式子的数字的出现个数为 A*f[3]。加上首位出现也就是小于A每一个数都出现了10^3次，再加上，我们就把A000处理完了。
这样你以为就把第一位处理完了？不不不，首位A还出现了BCD+1次呢，也就是从A000~ABCD，这个A还出现了BCD+1次，所以再加上这些才行呢。那么你发现，我们成功把首位代表的所有数字个数求出来了，剩下的求解与A完全没有任何关系，只是BCD的求解，于是我们发现我们已经把一个大问题，化成了一个个小问题，也即是，对于一个这样n位的数，把他一位位的分离开来。
当然你还需要处理前导0你会发现前导0一定是0001,0002。。。0012，0013。。。0101,0102.。。0999这样的数，一共出现了10*（i-1)+10*(i-2)+...10 (i表示数字位数），让0的统计减去这个值，那么恭喜你这道题做完了。
总结
对于DP这个东西，最重要的其实只有一点，推状态，状态又是什么？是大问题的子问题，对于这种题最重要的特点是，无后效性，问题可拆分，并且答案的求解具有一定的规律，这样的题应该就可以用DP做，数位DP最重要的就是把一整个数字拆分成一位一位的单独来看，那么对于数位DP，它的子问题也就一般是每一位上对于答案的求解，层层递进的这么一个思路。
最后粘代码，写的丑见谅
#include<bits/stdc++.h>
using namespace std;
long long a,b;
long long ten[20],f[20];
long long cnta[20],cntb[20];
void solve(long long x,long long *cnt)
{
long long num[20]={0};
int len=0;
while(x)
{
num[++len]=x%10;
x=x/10;
}
for(int i=len;i>=1;i--)
{
for(int j=0;j<=9;j++)
cnt[j]+=f[i-1]*num[i];
for(int j=0;j<num[i];j++)
cnt[j]+=ten[i-1];
long long num2=0;
for(int j=i-1;j>=1;j--)
{
num2=num2*10+num[j];
}
cnt[num[i]]+=num2+1;
cnt[0]-=ten[i-1];
}
}
int main()
{
scanf("%lld %lld",&a,&b);
ten[0]=1;
for(int i=1;i<=15;i++)
{
f[i]=f[i-1]*10+ten[i-1];
ten[i]=10*ten[i-1];
}
solve(a-1,cnta);
solve(b,cntb);
for(int i=0;i<=9;i++)
printf("%lld ",cntb[i]-cnta[i]);
}