BZOJ1833: [ZJOI2010]count 数字计数

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 15
using namespace std;
int bit[MAXN];
long long A,B;
long long ans[MAXN][2],dp[MAXN][MAXN][MAXN];
inline long long read(){
	long long date=0,w=1;char c=0;
	while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
	while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
	return date*w;
}
long long mexp(long long a,long long b){
	long long s=1;
	while(b){
		if(b&1)s*=a;
		a*=a;
		b>>=1;
	}
	return s;
}
void solve(long long n,int d){
	int len=0;
	memset(dp,0,sizeof(dp));
	memset(bit,0,sizeof(bit));
	while(n){
		bit[++len]=n%10;
		n/=10;
	}
	for(int i=0;i<=9;i++)dp[1][i][i]=1;
	for(int i=2;i<=len;i++)
	for(int j=0;j<=9;j++){
		for(int k=0;k<=9;k++)
			for(int now=0;now<=9;now++)
				dp[i][j][now]+=dp[i-1][k][now];
		dp[i][j][j]+=mexp(10,i-1);
	}
	for(int i=1;i<len;i++)
		for(int j=1;j<=9;j++)
			for(int k=0;k<=9;k++)
				ans[k][d]+=dp[i][j][k];
	for(int i=1;i<bit[len];i++)
		for(int j=0;j<=9;j++)
			ans[j][d]+=dp[len][i][j];
	for(int i=len-1;i>=1;i--){
		for(int j=0;j<bit[i];j++)
			for(int k=0;k<=9;k++)
				ans[k][d]+=dp[i][j][k];
		for(int j=len;j>i;j--)ans[bit[j]][d]+=1LL*bit[i]*mexp(10,i-1);
	}
}
void work(){
	A=read();B=read();
	solve(B+1,0);solve(A,1);
	for(int i=0;i<=9;i++)printf("%lld ",ans[i][0]-ans[i][1]);
	printf("\n");
}
int main(){
	work();
    return 0;
}