数位 dp
前置知识：
-
五大基础 dp
概念：
数位 dp，就是一个用来计数的动态规划，将一个长数分解为一个一个数位上的数进行统计。
例如：求 \(a-b\) 区间不包含 \(c\) 的数的个数，保证 \(0\leq a\leq b\leq 2\times 10^9\)。
空间限制 256MiB，时间限制 1000ms。
这个范围一眼暴力 TLE，等死。
直接动态规划记录数字？MLE 等着你。
所以有个东西叫数位 dp，它一般应用于：
-
求给定区间 \([a,b]\) 之内的符合条件的数的个数，即结果是计数，有左右边界。
-
条件与数的大小无关，与各数位上的数有关。、
-
上界较大，如（\(10^{18}\)）。
实现：
从左边界 \(l\) 数到右边界 \(r\)，过程中拥有非常多的重复部分，如：\(l=309\) 数到 \(r=831\)，之中有非常相似的过程：从 \(400\) 数到 \(499\)，从 \(500\) 数到 \(599\)，诸如此类后两位从 \(00\) 变为 \(99\) 的计数，这样的过程产生的计数答案可以放入一个通用的数组，对于这样的数组我们设计转移状态，进行动态规划。
有时也会用到一些计数技巧：
\[ \begin{aligned} ans_{l,r}=ans{0,r}-ans{0,l-1} \end{aligned} \]对于统计答案，往往采用记忆化搜索或是递推。
就伴着第一道例题讲实现吧：
[ZJOI2010] 数字计数
[ZJOI2010] 数字计数
题目描述
给定两个正整数 \(a\) 和 \(b\)，求在 \([a,b]\) 中的所有整数中，每个数码(digit)各出现了多少次。
输入格式
仅包含一行两个整数 \(a,b\)，含义如上所述。
输出格式
包含一行十个整数，分别表示 \(0\sim 9\) 在 \([a,b]\) 中出现了多少次。
样例 #1
样例输入 #1
1 99
样例输出 #1
9 20 20 20 20 20 20 20 20 20
提示
数据规模与约定
- 对于 \(30\%\) 的数据，保证 \(a\le b\le10^6\)；
- 对于 \(100\%\) 的数据，保证 \(1\le a\le b\le 10^{12}\)。
求给出的边界 \([a,b]\) 中，每个数码(\(0-9\))出现了多少次。
对于满 \(i\) 位（指第 \(i\) 位可以从 \(0\) 枚举到 \(9\)）的数，所有数字出现次数相同。
设 \(f_i\) 是满 \(i\) 位的数每个数字出现的次数，有 \(1-i\) 位的贡献=\(1-(i-1)\)位置的贡献\(\times 10+10^{i-1}\)：
\[ \begin{aligned} f_i=10\times f_{i-1}+10^{i-1} \end{aligned} \](\(10^{i-1}\) 是因为在第 \(i\) 位置产生贡献的情况下忽略第 \(i\) 位置，\(1-(i-1)\) 位置从全是 \(0\) 枚举到全是 \(9\) 共 \(10^{i-1}\) 的贡献由第 \(i\) 位产生）
考虑统计答案，将上界按位分开，从高到低枚举防漏，\(a_i\) 表示在第 \(i\) 位置的数，分着考虑：
-
\(1-(i-1)\) 位置的贡献，为 \(f_{i-1}\times a_i\)
-
第 \(i\) 位置的数不是 \(a_i\) 时，不管后面什么数。贡献为 \(fac_{i-1}.\)（\(10\) 的阶乘）
-
第 \(i\) 位置上的数是 \(a_i\) 时，其贡献是后面的数加上 \(1\) （后面的数全是 \(0\) 也行）
-
前导 \(0\)。第 \(i\) 位是前道 \(0\) 时，第 \(1-(i-1)\) 位都是 \(0\)，减去重复计数答案。
如果还不太明白就看代码注释，自己拿一个数字推一下，我就不推了：
（由于这道题明显递推更加简单所以选择递推）
Miku'sCode
#include<bits/stdc++.h>
using namespace std;
typedef long double llf;
typedef long long intx;
const int maxn=15;
int a[maxn];
intx l,r,f[maxn],fac[maxn];
//fac是10的阶乘,数据小于1e12故到13
intx ans1[maxn],ans2[maxn];
void input(){
scanf("%lld %lld",&l,&r);
}
void pre(){
//预处理
fac[0]=1;
for(int i=1;i<=13;++i){
f[i]=f[i-1]*10+fac[i-1];
fac[i]=(intx)10*fac[i-1];
cout<<"###"<<i<<' '<<f[i]<<endl;
}
}
void work(intx n,intx *ans){
//求1-n所有数的数码计数和,放入ans数组
intx tmp=n;
int len=0;
while(n) a[++len]=n%10,n=n/10;
for(int i=len;i>=1;--i){
//从高位向低位模拟
for(int j=0;j<=9;++j) ans[j]=ans[j]+f[i-1]*a[i];
//不贴近上界,随便取值
/*
简单来说:1-(i-1)位置从0000到9999的某个数的计数是f[i-1]
到a[i]算是贴近上界,这里加的是 1-(i-1)位置的数
*/
for(int j=0;j<a[i];++j) ans[j]=ans[j]+fac[i-1];
//贴近上界,取0到上界
/*
简单来说
就是把在第i位从0到上界-1的数的贡献加起来了。
*/
tmp=tmp-fac[i-1]*a[i];
ans[a[i]]=ans[a[i]]+tmp+1;
//将最后的上界上的数贡献加起来
ans[0]=ans[0]-fac[i-1];
//若第i位置是前导0,减去重复计数
}
}
int main(){
pre();
input();
work(r,ans1);
work(l-1,ans2);
for(int i=0;i<=9;++i){
//计数原理[1-r]-[1-(l-1)]=[l-r]
printf("%lld ",(intx)ans1[i]-ans2[i]);
}
return 0;
}