洛谷P2602 [ZJOI2010]数字计数

//左填法
#include <bits/stdc++.h>
using namespace std;
long long x;
long long f[11][15];
long long g[11][15];
char num0[15];int len=0;
long long dp[15];
void getans(long long moe){
	scanf("%lld",&x);
	if(moe==-1)x--;
	len=0;
	long long st=1;
	if(x==0)len=1;
	while(x)num0[++len]=x%10,x=x/10,st=st*10;
	st=st/10;
	for(int i=0;i<=9;i++){
		long long pst=0;
		long long st2=st;
		for(int j=len;j>=1;j--){
			long long num=num0[j];
			if(j==len&&len!=1)num--;
			dp[i]+=g[1][j-1]*num*moe;
			dp[i]+=pst*st2*num*moe;	
			if(i<num0[j]){
				if(i!=0||num==num0[j]){
					dp[i]+=st2*moe;
				}
			}
			st2=st2/10;
			if(num0[j]==i)pst++;
		}
	}
	for(int i=1;i<=len;i++)dp[num0[i]]+=moe;
	for(int i=0;i<=9;i++)dp[i]+=g[i!=0][len-1]*moe;
}
int main(){
	f[1][1]=f[0][1]=g[1][1]=1;
	f[0][2]=9;//g[0][2]=10;
	for(int i=0;i<=1;i++){
		long long tmp=1;
		for(int j=2;j<=12;j++,tmp=tmp*10){
			if(i==0&&j==2)continue;
			f[i][j]=f[i][j-1]*10+9*tmp;
			g[i][j]=g[i][j-1]+f[i][j];
		}
	}
	getans(-1);
	getans(1);
	for(int i=0;i<=9;i++)printf("%lld ",dp[i]);
}

//右填法
#include <bits/stdc++.h>
using namespace std;
long long x;
long long f[11][15];
char num0[15];int len=0;
long long dp[15];
void getans(long long moe){
	scanf("%lld",&x);
	if(moe==-1)x--;
	len=0;
	long long st=1;
	if(x==0)len=1;
	while(x)num0[++len]=x%10,x=x/10,st=st*10;
	st=st/10;
	for(int i=0;i<=9;i++){
		long long pst=0;
		long long st2=st;
		for(int j=len;j>=1;j--){
			if(j!=len&&num0[j+1]==i)pst++;
			for(int k=0;k<num0[j];k++){
				if(len==j&&k==0&&len!=1&&i==0){
					if(i==0)dp[i]+=moe;
					continue;
				}
				dp[i]+=f[i][j-1]*moe;
				if(i==k){
					dp[i]+=st2*moe;
				}
				dp[i]+=pst*st2*moe;	
			}
			st2=st2/10;
		}
	}
	for(int st=len;st>=3;st--){
		dp[0]+=moe*(9*f[0][st-2]);
	}
	for(int i=1;i<=len;i++)dp[num0[i]]+=moe;
}
int main(){
	for(int i=0;i<=9;i++)f[i][1]=1;
	for(int i=0;i<=9;i++){
		long long tmp=10;
		for(int j=2;j<=12;j++){
			f[i][j]=f[i][j-1]*10+tmp;
			tmp=tmp*10;
		}
	}
	getans(-1);
	getans(1);
	for(int i=0;i<=9;i++)printf("%lld ",dp[i]);
}