数位 dp

首先看一道例题 

Example 01 [P2602 数字统计]
求 [l,r] 中每个数字出现了多少次
(1 <= l,r <= 1e12)

Solution 
这题直接 for 肯定会 TLE
我们思考用一个 dp 数组
dp[i][j][k] 表示搜到第 i 位,保证最高位为 j,数字 k 的出现次数
(比如 dp[2][1][1] 就表示 [0,19] 有多少个 1) 
显然区间比较难
我们借用前缀和思想
将 ans[l,r] 转化为 ans[1,r]-ans[1,l-1] 即可

首先得到一个方程 
dp[i][j][k] 是 [j...00~j...99]中 k 的次数
所以 dp[i][j][k] = 所有 j 中 k 出现次数 + [000000000~999999999] 中 k 出现次数
				 = 所有 j 中 k 出现次数 + sum(dp[i-1][iterator][k]) [0~9] 
				 
现在我们只差第一部分怎么求 
如果 j!=k 第一部分肯定是 0
否则就是   1e(i-1) 
所以完整版的转移方程即为

dp[i][j][k]={ sum(dp[i-1][iterator][k]) [0~9]              (j!=k)
			{ 1e(i-1) + sum(dp[i-1][iterator][k]) [0~9]    (j==k)

这个肯定是能求的
于是有如下 Code

const unsigned long long ten[16]={1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
unsigned long long number[16][11][11]; 
void _memset(){
	//明显如果只有 0 位,那么一定只有 0 个 
	for(int i=0;i<=9;i++)number[1][i][i]=1;//初始化状态 
	for(int i=2;i<=13;i++)for(int j=0;j<=9;j++)for(int k=1;k<=9;k++){//枚举 i,j,k 
		if(j==k)number[i][j][k]+=ten[i-1];		
		for(int it=0;it<=9;it++)number[i][j][k]+=number[i-1][it][k];
	} 
} 

这部分非常简单
接下来考虑如何求解
比如说 6187
首先我们拆开每一位,变成 6 0 8 7 (C++ 语法入门) 
接下来统计三种
# 01 位数与原数一样,高位较小的数 (for 循环使用) 
ans+=[1000,1999]+[2000,2999]+[3000,3999]+[4000,4999]+[5000,5999] 
# 02 位数较小,无前导零 (for 循环使用) 
ans+=[0]+...+[9]+[10,19]+[20,29]+....+[900,999] 

我们发现已经将 [0,5999] 的 ans 统计完了 
还差 [6000,6187] 
接下来我们直接将区间拆开
[6000,6099]
[6100,6109]+[6110,6119]+...+[6170,6179]
[6180]+[6181]+...+[6187]
我们再将每个区间劈开
k*[60]+[00,99]
k*[610]+[0,9]+k*[611]+[0,9].......
.....
(太抽象了)
一波玄学统计,然后就结束了
 
于是太离谱了,还是开码吧

Code