题解 P2602 【[ZJOI2010]数字计数】

· · 题解

发现好像没有人和我写一样的数位dp

而且这还是个递推版的数位dp

我这个数位dp写的非常鬼畜

设dp[i][j][k]表示一个长度为i的数，其中最高位是j，k这个数码一共出现的次数

之后转移的话，我们需要枚举当前位数，当前最高位填什么数，次高位填什么数，之后转移一下就好了

显然有

dp[i][j][p]=\sum_{k=0}^9dp[i-1][k][p]

但是这就完了吗，显然不是啊

我们填上的最高位可是出现了很多次，但是一次都没有被记录进去

那也好办，我们让剩下的i-1为随意选择只考虑当前最高位上出现的数就好了（因为那些随意选择的数码已经被计入答案了）

于是根据乘法原理，还有

dp[i][j][j]+=10^{i-1}

之后就是数位dp的板子了

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define maxn 14
#define LL long long
LL dp[maxn][10][10];
LL L,R;
LL ans[10][2];
int a[maxn],num;
inline LL quick(LL a,LL b)
{
    LL s=1;
    while(b)
    {
        if(b&1) s*=a;
        b>>=1;
        a*=a;
    }
    return s;
}
inline void slove(LL x,int pd)
{
    memset(dp,0,sizeof(dp));
    num=0;
    memset(a,0,sizeof(a));
    while(x)
    {
        a[++num]=x%10;
        x/=10;
    }//分解数位 
    for(re int i=0;i<=9;i++) dp[1][i][i]=1;//初始化
    for(re int i=2;i<=num;i++)//枚举位数
        for(re int j=0;j<=9;j++)//当前最高位
        {
            for(re int k=0;k<=9;k++)//次高位
            {
                for(re int p=0;p<=9;p++)
                    dp[i][j][p]+=dp[i-1][k][p];
            }
            dp[i][j][j]+=quick(10,i-1);//乘法原理
        }
    for(re int i=1;i<num;i++)//位数比x小的，一定能够满足条件
        for(re int j=1;j<=9;j++)//不能有前导零
            for(re int k=0;k<=9;k++)
                ans[k][pd]+=dp[i][j][k];
    for(re int i=1;i<a[num];i++)//位数相同，但最高位比x小
        for(re int k=0;k<=9;k++)
            ans[k][pd]+=dp[num][i][k];
    for(re int i=num-1;i>=1;i--)//当前不同的那一位,[i+1,num]与x完全相同 
    {
        for(re int j=0;j<a[i];j++)//不同的这一位也必须必对应x位置上的数小
        {
            for(re int k=0;k<=9;k++)
                ans[k][pd]+=dp[i][j][k];
        }
        for(re int p=num;p>i;p--)
                ans[a[p]][pd]+=a[i]*quick(10,i-1);
        //由于我们保证[i+1,num]相同，那么这些数码也应该计入答案，于是还是一个乘法原理
    }
    //但是这个dp全程都不能处理出x是否满足条件
    //因为最后也只是判断第一位上的数比给定数的第一位小
    //所以slove(x)其实求得是[0,x)满足条件的数的个数
}
int main()
{
    scanf("%lld%lld",&L,&R);
    slove(R+1,0),slove(L,1);
    for(re int i=0;i<=9;i++)
        printf("%lld ",ans[i][0]-ans[i][1]);
    putchar(10);
    return 0;
}