}
计数过程处理前导零的常用思路:先处理所有$i(i<len)$位数的答案,这个在上一篇说过
计数过程比较重要的两个边界,一个是最终边界注意提前$+1$,这样可以考虑最后一位,**还有一个是:每次逼近完一位需要先确定这一位(让他和边界的这一位相等),再考虑下一位,注意确定这一位的过程要考虑对答案的影响,因为之前逼近过程没有计算,这里很容易出错**
举个例子:$12xxx$,第二高位会逼近到$1$,直接到下一位,但是$2$忽略了,因此要加入$2$的答案,也就是$12xxx%1000+1$
更多细节看代码吧
#$Code$
include
include
include
include
define re register
define ll long long
using namespace std;
inline ll read()
{
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch'-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x10+ch-'0';ch=getchar();}
return xf;
}
ll a,b,pow[20],dp[20][12][12];//dp[i][j][k]表示当前是第i位,当前位是j,后面任意贡献的k有多少个
ll tmp[20],ans[20],sums[20],cnt=0;
void pre()
{
pow[0]=1;
for(re int i=1;i<=12;++i) pow[i]=pow[i-1]*10;
for(re int i=0;i<=9;++i) dp[1][i][i]=1,sums[i]=1;
for(re int i=2;i<=12;++i)
{
for(re int j=0;j<=9;++j)
for(re int k=0;k<=9;++k)
{
dp[i][j][k]+=sums[k];
if(jk) dp[i][j][k]+=pow[i-1];
}
for(re int j=0;j<=9;++j) sums[j]=0;//一开始写的sum[j]=0,挂掉了
for(re int j=0;j<=9;++j)
for(re int k=0;k<=9;++k)
sums[k]+=dp[i][j][k];//降低一点常数
}
}
void ask(ll x)
{
memset(tmp,0,sizeof(tmp));
cnt=0;
if(x==0)
{
tmp[0]=1;
return;
}
ll t=x,now=0,last;
while(t){t/=10;cnt++;}
for(re int i=1;i<=cnt-1;++i)//处理前导零
for(re int j=1;j<=9;++j)
for(re int k=0;k<=9;++k)
tmp[k]+=dp[i][j][k];
now=x/pow[cnt-1];
for(re int j=1;j<now;++j)
for(re int k=0;k<=9;++k)
tmp[k]+=dp[cnt][j][k];
last=now;
x%=pow[cnt-1];
for(re int i=cnt-1;i>=1;--i)
{
tmp[last]+=x;//这里要特别判断边界,到了12xxx的第一个x要把前面2统计上,个数就是12xxx%1000+1
//又因为我们边界预先加了一,所以个数就是12xxx%1000,比如199会处理成200,如果计算2后有多少数会计算1个,但实际这个数是不存在的,因此不用%后+1
now=x/pow[i-1];
for(re int j=0;j<now;++j)
for(re int k=0;k<=9;++k)
tmp[k]+=dp[i][j][k];
x%=pow[i-1];
last=now;//更新
}
}
int main()
{
a=read(),b=read();
pre();
ask(b+1);
for(re int i=0;i<=9;++i) ans[i]=tmp[i];
ask(a);
for(re int i=0;i<=9;++i)
{
ans[i]-=tmp[i];
printf("%lld ",ans[i]);
}
return 0;
}