[ZJOI2010]count 数字计数

BZOJ1833..
 
好累...我真的再也不想做数位DP了...
啊,要统计[l,r]以内0~9出现的次数,减一减然后这道题就变成了求(0,k)以内各个数位出现的次数
[1,9]都是一样的,0比较特(e)殊(xin),一会儿再说,先说怎么处理[1,9]的情况
先假设当前要处理的数位为j(1 <= j <= 9),可以DP得到f[i][j]为i位以内(即(0,10^i)以内)j出现的次数
然后就是讨论3种情况:
(设k十进制共l位,从低到高第p位为b(p))
①首位为0 (f[l - 1][j])
②首位为[1,b(l) - 1] ((b(l) - 1) * f[l - 1[j] ,若b(l) >= j则再加上10^(l - 1))
③首位为b(l),这个情况比较复杂,不过仔细思考一下还是能得出的(具体的看代码吧..)
 
然后是待求数位为0的情况,首先需要维护两个数组:f[i][0]和h[i],其中f[i][0]的含义和前面一样,h[i]表示算上前缀0,刚好i位的数中0出现次数,这两个都可以DP求(吧...)(反正我是用组合求的...)
然后还是讨论上面三种情况,公式基本不变(还是有些变动,不过都是很好推的,具体看代码吧...),但是有些地方f[i][j]要换成h[i]
 
注意有些地方区间的开闭,还有精度啊啥啥的,基本上这道题就可以A了...
 

完整代码如下:


#include <stdio.h>

#include <iostream>

#include <string.h>

 

typedef long long Long;

 

Long f[20][20];

Long h[20][1]; 

Long p[20];

 

Long pow(Long a,int b)

{

    int m = (1 << 30);

    Long r = 1LL;

    while(m)

    {

        r *= r;

        if(m & b)

            r *= a;

        m >>= 1;

    }

    return r;

}

 

Long yh[100][100];

Long C(int a,int b)

{

    if(yh[a][b])

        return yh[a][b];

    if(b == 0 || b == a)

        return yh[a][b] = 1LL;

    if(b > a)

        return 0LL;

    return yh[a][b] = C(a - 1,b) + C(a - 1,b - 1);

}

 

void init()

{

    for(int j = 1;j < 10;j++)

    {

        f[1][j] = 1;

    }

     

    Long e = 1;

    for(int i = 2;i < 20;i++)

    {

        e *= 10;

        for(int j = 1;j < 10;j++)

        {

            f[i][j] = e + 10 * f[i - 1][j];

        }

    }

     

    h[1][0] = 1;

    //f[1][0] = 1;

    for(int i = 2;i < 20;i++)//要!算!前!导!零!!! 

    {

        f[i][0] += f[i - 1][0];

        for(int j = 1;j <= i;j++)

        {

            h[i][0] += j * pow(9,i - j) * C(i,j);

            if(j <= i - 1)

                f[i][0] += j * pow(9,i - j) * C(i - 1,j);

        }

    //  std::cerr<<i<<" (f) "<<f[i][0]<<std::endl;

    //  std::cerr<<i<<" (h) "<<h[i][0]<<std::endl;

    //  std::cerr<<i<<" (hs) "<<hs[i][0]<<std::endl;

    }

}

 

int len = 0;

int bit[20];

Long get_res_0(Long k)

{

    memset(bit,0,sizeof(bit));

    len = 0;

 

    Long q = k;

 

    while(q)

    {

        bit[++len] = q % 10;

        q /= 10;

    }

 

    Long result = 0LL;

 

    result += f[len - 1][0];

 

    result += 1LL * (bit[len] - 1) * h[len - 1][0];

     

    Long T = 0;

    for(int i = len - 1;i >= 1;i--)

    {

        if(bit[i + 1] == 0)

            T ++;

        for(int p = 0;p < bit[i];p++)

        {

            result += T * pow(10,i - 1);

            result += h[i - 1][0];

            if(p == 0)

                result += pow(10,i - 1);

        }

    }

    return result;

}

Long get_res(Long k,int j)

{

    /*

    if(k < 10)

    {

        if(k > j)

            return 1;

        return 0; 

    }

*/

    if(j == 0)

        return get_res_0(k);

 

    memset(bit,0,sizeof(bit));

    len = 0;

 

    Long q = k;

 

    while(q)

    {

        bit[++len] = q % 10;

        q /= 10;

    }

 

    Long result = 0LL;

 

    result += f[len - 1][j];

 

    result += 1LL * (bit[len] - 1) * f[len - 1][j] + (j <= (bit[len] - 1) ? (pow(10,len - 1)) : 0);

     

    Long T = 0;

    for(int i = len - 1;i >= 1;i--)

    {

        if(bit[i + 1] == j)

            T ++;

        for(int p = 0;p < bit[i];p++)

        {

            result += T * pow(10,i - 1);

            result += f[i - 1][j];

            if(p == j)

                result += pow(10,i - 1);

        }

    }

    return result;

}

 

int main()

{

     

    init();

     

    Long a = 0;

    Long b = 0;

 

    std::cin>>a>>b;

     

    Long res = 0;

     

    for(int i = 0;i < 10;i++)

    {

        res = get_res(b + 1,i) - get_res(a,i);

        /*

        if(i == 0)

        {

            if(a == 0)

                res ++;

        }

        */

        if(i != 9)

            std::cout<<res<<" ";

        else std::cout<<res<<std::endl;

    }

 

    return 0;

}