学步园

蒟蒻只能想通简单题== 刷OJ太容易让人自我嫌弃了==

dp[i][j]表示i位的数，MOD10=k的个数。

预处理里面，是从低往高递推，包含的是0~9..9(i位)的整个范围的个数。

状态转移时，从高位往低位转移，并用pre记录i位前面（更高位）的各位数之和，因为每一位的数是枚举上界，在之前的枚举不会达到。

举个例子，2753

i=4： 0~1 [3位数0~999中%10=k的个数]

i=3： 2 0~6 [2位数0~99中%10=k的个数]

i=2：270~4 [1位数0~9中%10=k的个数]

i=1： 2750~2 [0位数中%10=k的个数]

这里的枚举不会到达2753，所以最后是solve(b+1)-solve(a)

然后初始状态dp[0][0]=1;我也不是很清楚为什么这样，不过举个例子可以看出，对于2而言，dp[1][0]=dp[0][k]，只能算1个（只有0符合条件），如果dp[0][i]=1 for all i，会算多了.

Plus，这里面按位数枚举是disjoint sample space，所以最后的ans要相加，而且ans只能在循环内相加，因为只有这里面的状态转移是合法的。

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
#include<map>
#include<time.h>
using namespace std;
//hdu 4722

int T;
long long A;
long long B;
long long dp[20][10];
int digit[20];
int len;
void initial()
{
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=0;i<=9;i++)
    {
        dp[1][i]=1;
    }
    for(int i=2;i<=19;i++)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                dp[i][(j+k)%10]+=dp[i-1][k];
            }
        }
    }
}
void toarray(long long a)
{
    len=0;
    memset(digit,0,sizeof(digit));
    while(a)
    {
        digit[++len]=a%10;
        a=a/10;
    }
}
long long solve(int len)
{
    int pre=0;
    long long ans=0;
    //cout<<len<<endl;
    for(int i=len;i>0;i--)
    {
        for(int x=0;x<digit[i];x++)
        {
            for(int k=0;k<=9;k++)
            {
               // dp[i][(pre+x+k)%10]+=dp[i-1][k]; 感觉不要相加，不过加了没影响，因为循环到后面不会用到加过的状态
                if((pre+x+k)%10==0)
                {
                    ans+=dp[i-1][k];//所以dp[0][0]=1, when number=1
                    //cout<<pre<<" "<<x<<endl;
                 //   cout<<ans<<" "<<i<<" "<<k<<" "<<dp[i-1][k]<<endl;
                }
            }
        }
        pre=(pre+digit[i])%10;//加上高位的数（之前的枚举上界） 之前写成了pre=(pre+x)%10; debug了半天。。
       // ans+=dp[i][0]; ans不能在最后再加，因为当dp[i][0]没有进入循环时，是不合法的，所以要在循环内累加
    }
    return ans;
}

int main()
{
    freopen("input.txt","r",stdin);
   //  freopen("data.txt","r",stdin);
    // freopen("out1.txt","w",stdout);
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        scanf("%I64d %I64d",&A,&B);
        initial();
        toarray(A);
        long long a=solve(len);
        initial();
        toarray(B+1);
        long long b=solve(len);
      //  cout<<b<<" "<<a<<endl;
        printf("Case #%d: %I64d\n",t,b-a);
    }

    return 0;
}