2282.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//#define debug 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000
#define NMAX 52
__int64 a[10][10][10]={0};
int bit[12]={0};
void initbit()
{
	bit[1]=1;
	for(int i=2;i<=9;i++)
		bit[i]=10*bit[i-1];
}

int l,r;
__int64 lt[10],rt[10];
void total(int c,__int64 *p)
{
	int i,k;
	__int64 b[10]={0};
	if(c<=9)
	{
		p[0]=0;
		for(i=1;i<=c;i++)
			p[i]=1;
		return ;
	}
	
	int last=c%10;
	for(i=0;i<=last;i++)
	{
		b[i]=1;
	}
	c/=10;
	int t;
 	for(i=2;i<=9;i++)
	{
		
		t=c%10;
/*		if(!t)
		{
			c=c/10;
			continue;
		}
*/		for(k=0;k<=9;k++)
			p[k]=bit[i-1]*(i-1)*t+b[k];
		for(k=0;k<t;k++)
			p[k]+=bit[i];
		p[t]+=last+1;
		last+=t*bit[i];
		c/=10;
		if(c==0)
			break;
		memcpy(b,p,sizeof(b));
	}
	for(;i>=1;i--)
		p[0]-=bit[i];
}
void solve()
{
	memset(lt,0,sizeof(lt));
	memset(rt,0,sizeof(rt));
	if(l>r)
	{
		int t=l;
		l=r;
		r=t;
	}
	total(l-1,lt);
	total(r,rt);
	int i;
	for(i=0;i<=9;i++)
	{
		printf("%I64d",rt[i]-lt[i]);
		if(i<9)
			printf(" ");
	}
	printf("\n");
}
int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
//	init();
	initbit(); 
	while(1)
	{
		scanf("%d%d",&l,&r);
		if(!l)
			break;
		solve();
	}
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}