Dp-digit

数位dp一般就是要统计一个区间[l,r]内满足一些条件数的个数。

题目来源: http://www.51nod.com/Challenge/Problem.html#problemId=1042

感谢优秀博客：https://www.cnblogs.com/y2823774827y/p/10301145.html
以上博客写的很详细，这里稍作总结
算法思想

  • 1.首先计算10^i内1-9出现的次数，下面简称为各数贡献值bj
    dp[i] = 10dp[i-1] + 10^(i-1)
    其实很好理解，如i=1,显然10以内1-9各数贡献值均为1;i=2,100以内各数贡献值10    1+10

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    typedef long long ll;
    ll a[25], digit[25], dp[25], countl[20], countr[20];
    void init()        //统计10^(i-1)内各数出现次数,dp[i]存储 
    {                //dp[i] = 10*dp[i-1] + 10^(i-1)
        digit[0] = 1;
        for(ll i = 1; i <= 20; ++i)
        {
            dp[i] = (dp[i-1]<<3) + (dp[i-1]<<1) + digit[i-1];
            digit[i] = (digit[i-1]<<3) + (digit[i-1]<<1);
        }
    }

  • 2.接着计算数n内各数贡献值
    如n=43102，遍历每一位数，遍历顺序从n到1，将其拆为{40000,3000,100,0,2}
    对于第i位，记录2项 1)拆分的第i位数贡献值(如i=1,为b[j]+=4*dp[5])
    2)第i位数的贡献值(如i=1,为b[j]+=(3102+1))

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void solve(int m, ll *b)
    {
        ll len = 0, ans = m;
        while(m)        //字符串存储m 
        {
            a[++len] = m % 10;
            m /= 10;
        }
        for(ll k = len; k>=1; --k)    
        {
            for(int i = 0; i < 10; ++i)
                b[i] += dp[k-1] * a[k];        //10^(k-1)内各数的贡献值 
            for(int i = 0; i < a[k]; ++i)
                b[i] += digit[k-1];        //第k位数的贡献值,不包含a[k] 
            ans -= a[k]*digit[k-1];    //m = m % ( 10^(k-1) ) 
            b[a[k]] += (ans + 1);        //a[k]的贡献值 
            b[0] -= digit[k-1];        //0的贡献值在之前加上的要删去 
        }
    }

  • 3.最后可以求[a,b]间各数的贡献值，算两次即可 solve(b) - solve[a-1]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int main()
    {
        init();
        ll m, n;
        scanf("%lld%lld", &m, &n);
        solve(m-1, countl);
        solve(n, countr);
        for(int i = 0; i < 10; ++i)
            printf("%lld ", countl[i]);
        printf("\n");
        for(int i = 0; i < 10; ++i)
            printf("%lld ", countr[i]);
        printf("\n");
        for(int i = 0; i < 10; ++i)
            printf("%lld ",countr[i] - countl[i]);
        return 0;
    }