BZOJ 1833 【ZJOI2010】 数字计数

题目链接：数字计数

　　没啥好说的，裸裸的数位(dp)。

　　先枚举当前是算数字(x)出现的次数，设(f_{i,j})表示从高位往低位(dp)，(dp)完了前(i)位之后(x)出现了(j)次的方案数。然后再加一维，表示当前这一位能否自由选数(也就是说之前是否是一路选最大值过来的)。转移分情况讨论一下就好了。

　　注意这种写法还有一点情况，就是算(0)出现的次数时需要减去区间内前导(0)的个数。

　　下面贴代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

using namespace std;
typedef long long llg;

llg l,r,f[21][21][2],mi[21];
int a[21],b[21],l1,l2;

void divide(llg x,int *s,int &len){
	llg y=x; while(y) len++,y/=10;
	for(int i=len;i;i--) s[i]=x%10,x/=10;
}

llg work(int *s,int n,int x){
	f[0][0][1]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=i;j++){
			f[i][j][0]=f[i-1][j][0]*9;
			if(j) f[i][j][0]+=f[i-1][j-1][0];
			if(s[i]>x){
				f[i][j][0]+=f[i-1][j][1]*(s[i]-1);
				if(j) f[i][j][0]+=f[i-1][j-1][1];
			}
			else f[i][j][0]+=f[i-1][j][1]*s[i];
			if(s[i]==x){
				if(j) f[i][j][1]=f[i-1][j-1][1];
				else f[i][j][1]=0;
			}
			else f[i][j][1]=f[i-1][j][1];
		}
	llg now=0;
	for(int i=1;i<=n;i++) now+=i*(f[n][i][0]+f[n][i][1]);
	if(!x){
		mi[0]=1; now-=n;
		for(int i=1;i<n;i++) mi[i]=mi[i-1]*10;
		for(int i=1;i<n;i++) now-=(mi[i]-mi[i-1])*(n-i);
	}
	return now;
}

int main(){
	File("a");
	scanf("%lld %lld",&l,&r); l--;
	divide(l,a,l1); divide(r,b,l2);
	for(int i=0;i<=9;i++){
		if(i) printf(" ");
		printf("%lld",work(b,l2,i)-work(a,l1,i));
	}
	return 0;
}