今天比赛做得一个数位dp。

首先声明这个题目在数位dp中间绝对是赤裸裸的水题。毫无技巧可言。

题目的意思是个你a和b，要求出在a和b中间有多少个数满足数位上各个数字的和为10的倍数。

显然定义一个二维数组f，f[i][j]表示i位任意的数组合所有数位对10取模后余数为j的种类。

这样直接枚举1-10就可以得出i和i+1的递推关系了呢。简单了吧。

在求答案的时候不是直接求的，用的是数位dp最最经典的答案求法：

　　那就是定义一个count（x）函数表示不大于x满足的个数，这样，所求的答案就等于count（b）-count（a）了

下面的问题就是如何求得count这个函数值了。

首先我们把数x进行分解，用数组中的一个元素表示x的相对位数的数字。

这样对于从低位开始数起的第i位，如果数位的数值为a[i]，那么我们可以任取0~a[i]-1（想想为什么？这是典型的数位dp的求法），同时保存前面的和并且把a[i]加到和中并取模。

这样如此下去直到求出所有的，同时就是等于x本身的数没有考虑，我们可以直接特判一下就OK了。

代码：

#include 
     
      #include 
      
       #include 
       
        #define ll long longusing namespace std;ll f[19][29],sum[29],t,A,B,n,a[29],ans,tep;ll count(ll x){
         if (x<0) return 0;    if (x<10) return 1;    n=ans=tep=0;    while (x) a[++n]=x%10,x/=10;    for (ll i=n; i>1; i--)    {
             for (ll k=0; k
        
         >t;    for (ll cas=1; cas<=t; cas++)    {
             cin>>A>>B;        if (A>B)        {
                 cout<<"Case #"<
         
          <<": "<<0<