bzoj1833 [ZJOI2010]count 数字计数（数位）

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

Input
输入文件中仅包含一行两个整数a、b，含义如上所述。

Output
输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。

Sample Input
1 99

Sample Output
9 20 20 20 20 20 20 20 20 20

HINT
30%的数据中，a<=b<=10^6；
100%的数据中，a<=b<=10^12。

Source
Day1

分析：
数位dp

以前做的数位dp只有一道题 windy数
我一直对这种dp的理解是把一个大数分成很多部分
分部分解决
但是我发现如果我这么想的话，在做题的时候就很tomato难受
所以我们就把数位dp看成是一种一位一位递推的dp
这样想方程会简单一点

一开始我的方程是这样的
f[i][j][0/1] 第i位填j，是否卡边界
但是这样我dp的答案会有错

看了一下网上的题解
给出的状态是这样的：
f[i][j][k][0/1][0/1]
枚举t：0~9
表示第i为填数字j,1~i位中t出现的次数为k,是否卡上限，1~i位是否为前导零。
ans=Σf[l][i][j][0/1][0/1]*j

tip

两个数字我都处理成了右对齐
所以在doit的时候
数组的长度一定是max(l1,l2)

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long

using namespace std;

ll f[15][15][15][2][2];
char s1[20],s2[20];
int a[20],b[20],l1,l2;
ll ans[20];

void doit(int *a,int l,int flag)
{
    int i,t,j,k,o,p,c;
    for (t=0;t<=9;t++)
    {
        memset(f,0,sizeof(f));
        for (i=0;i<=a[1];i++) 
            f[1][i][i==t&&(t!=0 ? 1:0)][i==a[1] ? 1:0][i==0 ? 1:0]=1;
        for (i=1;i<l;i++)
            for (j=0;j<=9;j++)
                for (k=0;k<=i;k++)
                    for (p=0;p<=1;p++)
                        for (o=0;o<=1;o++)
                        if (f[i][j][k][p][o])
                        {
                            int tt=9;
                            if (p) tt=a[i+1];
                            for (c=0;c<=tt;c++)
                                if (!o||c!=0)
                                    f[i+1][c][k+(c==t ? 1:0)][p&(c==a[i+1])][o&(c==0)]+=f[i][j][k][p][o];
                                else f[i+1][c][0][p&(c==a[i+1])][o&(c==0)]+=f[i][j][k][p][o];  //有前导零
                        }
        for (i=0;i<=9;i++)
            for (j=1;j<=l;j++)
                for (k=0;k<=1;k++)
                    for (p=0;p<=1;p++)
                        ans[t]+=((ll)f[l][i][j][k][p]*(ll)j*(ll)flag);
    }
}

int main()
{
    scanf("%s%s",&s1,&s2);
    l1=strlen(s1); l2=strlen(s2);
    for (int i=0;i<l2;i++) b[i+1]=s2[i]-'0';
    for (int i=0;i<l1;i++) a[i+l2-l1+1]=s1[i]-'0';
    l1=l2;
    int j=l2;
    while (!a[j])
    {
        a[j]=9;
        j--;
    }
    a[j]--;
    doit(b,l2,1);
    doit(a,l1,-1);
    for (int i=0;i<9;i++) printf("%lld ",ans[i]);
    printf("%lld
",ans[9]);
    return 0;
}