The Counting Problem

The Counting Problem

询问区间\([a,b]\)中\(1\sim 9\)出现的次数，0 < a, b < 100000000。

解

显然为数位递推，考虑试填法，现在关键是求出方案数，于是设\(A[i]\)表示i位以内数字中0出现的次数，不含前导0,\(B[i]\)为i位数字中\(0\sim 9\)出现的次数，可以含前导0，不难有(其中\(base[i]=10^i\))，显然有

\[B[i]=10\times B[i-1]+base[i-1]
\]

\[A[i]=A[i-1]+9B[i-1]
\]

边界：\(A[0]=B[0]=0\)

解释：对于\(B[i]\),显然与第i位填什么有关，只能填0~9(含前导0)，i-1位能够统计的数字个数翻10倍，然后对于第i位填上该个数字，剩下的数字自由组合有\(base[i-1]\)，对于\(A[i]\)，i-1位以内方案\(A[i-1]\)，i位的方案是\(9B[i-1]\)(只能填\(1\sim 9\))。

于是对于一个数位题目，当我们处理好含前导0i位数字方案（前面的数字已经填好统计方案）和不含前导0i位以内的方案（前面的数字没有填好，不允许含前导0）的方程时，该题基本完成一半，罗嗦几句，帮助理解，对于\(1\sim 9\)的数字而言只需要\(B[i]\)数组即可，因为含前导0有两重意思都是等价的，一是i位数字上的含前导0的数的数字出现次数，二是i位以内的不含前导0的数的出现的次数，而0没有这个特殊待遇，于是得在维护一个\(A[i]\)，剩下的照数位递推套路进行即可。

参考代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#define il inline

#define ri register

#define ll long long

#define swap(x,y) x^=y^=x^=y

using namespace std;

int num[9];

ll A[9],B[9],base[9],at[10],bt[10];

il void prepare();

il void ask(int n,ll[]);

int main(){

	int a,b;prepare();

	while(scanf("%d%d",&a,&b),a&&b){

		if(a>b)swap(a,b);

		ask(a-1,at),ask(b,bt);

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

			printf("%lld ",bt[i]-at[i]);

		putchar('\n');

	}

	return 0;

}

il void ask(int n,ll ans[]){++n,num[0]&=0;

	do num[++num[0]]=n%10,n/=10;while(n);

	ans[0]=0;

	for(int j(num[0]),k,l(0);j;--j){

		for(k=0;k<num[j];++k)

			ans[0]+=A[j-1]+base[j-1]*(l+!k);

		if(!num[j])++l;

	}ans[0]+=B[num[0]-1],ans[0]-=A[num[0]-1]+base[num[0]-1];

	if(num[0]==1)++ans[0];

	for(int i(1),j,k,l;i<10;++i)

		for(j=num[0],l=ans[i]=0;j;--j){

			for(k=0;k<num[j];++k){

				ans[i]+=A[j-1]+base[j-1]*(l+(k==i));

			}if(num[j]==i)++l;

		}

}

il void prepare(){base[0]=1;

	for(int i(1);i<9;++i)

		base[i]=base[i-1]*10,A[i]=A[i-1]*10+base[i-1];B[1]=1;

	for(int i(2);i<9;++i)B[i]=9*A[i-1]+B[i-1];

}

The Counting Problem的相关教程结束。