洛谷P2602 [ZJOI2010]数字计数 题解（数位dp）

description：

给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。

$a\le b\le 10^8$a≤b≤108

solution：

数位dp

$设f\left[i\right]\left[j\right]\left[k\right]表示一共有i位，最高位是j，k这个数字一共出现的次数$设f[i][j][k]表示一共有i位，最高位是j，k这个数字一共出现的次数

$易得f\left[i\right]\left[j\right]\left[p\right]={\sum }_{k=0}^{9}f[i-1]\left[k\right]\left[p\right]$易得f[i][j][p]=∑k=09​f[i−1][k][p]

然后就是板子了（按照最高位分类讨论）

code：

#include<cstdio>
#include<cstring>
using namespace std;
long long cheng(long long x,long long y)
{
	long long ans=1;
	for(long long i=1;i<=y;i++)
	{
		ans=ans*x;
	}
	return ans;
}
long long f[15][15][15];
void init()
{
	for(long long i=0;i<=9;i++)
	{
		f[1][i][i]=1;
	}
	for(long long i=2;i<=13;i++)
	{
		for(long long j=0;j<=9;j++)
		{
			for(long long k=0;k<=9;k++)
			{
				for(long long h=0;h<=9;h++)
				f[i][j][h]+=f[i-1][k][h];
			}
			f[i][j][j]+=cheng(10,i-1); 
		}
	}
	return ;
}
long long a[15];
long long ans[15][4];
void work(long long x,long long pd)
{
	memset(a,0,sizeof(a));
	long long cnt=0;
	while(x)
	{
		a[++cnt]=x%10;
		x=x/10;
	}
	for(long long i=1;i<cnt;i++)
	{
		for(long long j=1;j<=9;j++)
		{
			for(long long k=0;k<=9;k++)
			{
				ans[k][pd]+=f[i][j][k];
			}
		}
	}
	for(long long i=1;i<a[cnt];i++)
	{
		for(long long k=0;k<=9;k++)
		{
			ans[k][pd]+=f[cnt][i][k];
		}
	}
	for(long long i=cnt-1;i>=1;i--)
	{
		for(long long j=0;j<a[i];j++)
		{
			for(long long k=0;k<=9;k++)
			{
				ans[k][pd]+=f[i][j][k];
			}
		}
		for(long long p=cnt;p>i;p--)
		{
			ans[a[p]][pd]+=a[i]*cheng(10,i-1);
		}
	}
	return ;
} 
int main()
{
	init();
	long long A,B;
	scanf("%lld%lld",&A,&B);
	work(B+1,1);
	work(A,2);
	for(long long i=0;i<=9;i++)
	{
		printf("%lld ",ans[i][1]-ans[i][2]);
	}
	return 0;
}