这道题我想应该有数学公式吧（如我上次说的欧拉函数），但是像我这种蒟蒻还是算了。
反复思考后，我想到一种代码简单、原理简单、细节困难的方法。
（1）前缀和思想，即设p(k)是1-k中的答案，那么ans=p(b)-p(a-1)。
（2）预处理。我们把k拆开来储存在a数组里（如：3456，它在a数组中是3,4,5,6），并用g数组存储从前到后的数据大小（如：3456，它在g数组中是3,34,345,3456），f数组存储从后向前的数据大小（如：3456，它在f数组中是3456,456,56,6）。
（3）排列组合思想。我分别枚举0--9，每次枚举它们在每一数位上的个数。设a数组中数字是□□□□□p□□□□□，我们已枚举在p所在的这个数位i，且设我们处理的数字是q。
①设p>q，我们用乘法原理，ans[q]+=(g[p+1]+1)*10^(i-1)。为什么要加1呢？因为前面可以为0（即i是最高位）
②设p<q，与上面类似，只是少加了一。ans[q]+=(g[p+1])*10^(i-1)。
③设p=q，那么我们先把p后面的数字加一下（别忘了还要多加一），再进行②中的乘法原理。
即ans[q]+=f[i+1]+(g[p+1])*10^(i-1)
注意：0不能做最高位，0的情况需另判。
#include<stdio.h>
#include<cstring>
using namespace std;
long long f[2][15],g[2][15],ans[2][10],p[2],aa,bb;
long k[2],a[2][15],i,j;
long long pow(long a,long b)
{
long long temp=1;
for (long i=1;i<=b;i++)
temp*=a;
if (b==0) return 1;return temp;
}
void go(long o)
{
long i,j;long long temp;
for (i=0;i<10;i++)
{
for (j=1;j<=k[o];j++)
{
if (i==0&&j==k[o]) break;
if (a[o][j]==i) {ans[o][i]+=f[o][j-1]+1;temp=g[o][j+1];if (i==0) temp--;ans[o][i]+=temp*pow(10,j-1);}
else if (a[o][j]>i) {temp=g[o][j+1]+1;if (i==0) temp--;ans[o][i]+=temp*pow(10,j-1);}
else if (a[o][j]<i) {temp=g[o][j+1];if (i==0) temp--;ans[o][i]+=temp*pow(10,j-1);}
}
}
}
int main()
{
scanf("%lld %lld",&aa,&bb);aa--;
memset(a,0,sizeof(a));memset(g,0,sizeof(g));memset(f,0,sizeof(f));
p[0]=p[1]=1;k[0]=k[1]=0;
while (aa>0)
{
a[0][++k[0]]=aa%10;
aa=aa/10;//printf("%ld",p[1]);
f[0][k[0]]=f[0][k[0]-1]+a[0][k[0]]*p[0];
p[0]*=10;
}
p[1]=1;
while (bb>0)
{
a[1][++k[1]]=bb%10;
bb/=10;
f[1][k[1]]=f[1][k[1]-1]+a[1][k[1]]*p[1];
p[1]*=10;
}
for (i=k[0];i>0;i--) g[0][i]=g[0][i+1]*10+a[0][i];
for (i=k[1];i>0;i--) g[1][i]=g[1][i+1]*10+a[1][i];
for (i=0;i<2;i++) go(i);
for (i=0;i<9;i++)
printf("%lld ",ans[1][i]-ans[0][i]);
printf("%lld\n",ans[1][9]-ans[0][9]);
//scanf("%lld %lld",&aa,&bb);
return 0;
}bzoj 1833 [ZJOI2010] count 数字计数 题解
原文：http://blog.csdn.net/jiangshibiao/article/details/19768907