【BZOJ1833】【ZJOI2010】数字计数 数位DP

链接：

#include <stdio.h>

int main()

{

    puts("转载请注明出处[辗转山河弋流歌 by 空灰冰魂]谢谢");

    puts("网址：blog.csdn.net/vmurder/article/details/46444975");

}

题解：

然而并没有DP。

[1。R]的答案减去[1,L]的答案。

对于一个数 X 。求 [1,X] 的答案。我是先处理出 [1,999……9] 的答案（那个999……9 < X）

然后按位往下扫。计算最高位为 i 的数有多少个、i在非最高位出现了多少次。

明明每天睡得非常多，为什么还是困呢Qwq

一定是蚊子有毒。剧毒。

代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

long long ans[10];

int main()

{

//  freopen("test.in","r",stdin);

    int i,j,k;

    long long t,y,l,r;

    scanf("%lld%lld",&l,&r),l--;

    if(l<0)ans[0]++,l=0;

    for(t=1,i=0,y=9;y<l;y=y*10+9,i++,t*=10)

    {

        ans[0]-=t*i*9/10;

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

        {

            ans[j]-=t*i*9/10;

            ans[j]-=t;

        }

    }

    for(t=1,i=0,y=9;y<r;y=y*10+9,i++,t*=10)

    {

        ans[0]+=t*i*9/10;

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

        {

            ans[j]+=t*i*9/10;

            ans[j]+=t;

        }

    }

    for(t=1e13,i=13;t>l;i--,t/=10);

    for(bool flag=1;i>=0;i--,t/=10)

    {

        for(j=0;j<10;j++)ans[j]-=t*i/10*(l/t-flag);

        if(flag)flag=0;else if(l/t)ans[0]-=t;

        for(j=1;j<l/t;j++)ans[j]-=t;

        ans[l/t]-=(l+1-l/t*t),l%=t;

    }

    for(t=1e13,i=13;t>r;i--,t/=10);

    for(bool flag=1;i>=0;i--,t/=10)

    {

        for(j=0;j<10;j++)ans[j]+=t*i/10*(r/t-flag);

        if(flag)flag=0;else if(r/t)ans[0]+=t;

        for(j=1;j<r/t;j++)ans[j]+=t;

        ans[r/t]+=(r+1-r/t*t),r%=t;

    }

    printf("%lld",ans[0]);for(i=1;i<10;i++)printf(" %lld",ans[i]);

    return 0;

}