1）
数位DP
数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：
要求统计满足一定条件的数的数量（即，最终目的为计数）；
这些条件经过转化后可以使用「数位」的思想去理解和判断；
输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
上界很大（比如 10^{18}），暴力枚举验证会超时。
数位 DP 的基本原理：
考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。
数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减（即 \mathit{ans}{[l, r]} = \mathit{ans}-\mathit{ans}_{[0, l - 1]}）
那么有了通用答案数组，接下来就是统计答案。统计答案可以选择记忆化搜索，也可以选择循环迭代递推。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，再考虑每一位都可以填哪些数字，最后利用通用答案数组统计答案。
例子 Luogu P2602 数字计数
代码：
点击查看代码
``` #includevoid solve(ll n, ll *ans) {
ll tmp = n;
int len = 0;
while (n) a[++len] = n % 10, n /= 10;
//将n拆分成每一位
for (int i = len; i >= 1; --i) {//从头到尾枚举
for (int j = 0; j < 10; j++) ans[j] += dp[i - 1] * a[i];
//对于没有顶到a[i]的数字，加上末几位的数字可能数
for (int j = 0; j < a[i]; j++) ans[j] += mi[i - 1];
// 还没有顶到i的后几位情况
tmp -= mi[i - 1] * a[i], ans[a[i]] += tmp + 1;
//对于顶到i的情况
ans[0] -= mi[i - 1];
//剔除前导0
}
}
int main() {
scanf("%lld%lld", &l, &r);
mi[0] = 1ll;
for (int i = 1; i <= 13; ++i) {
dp[i] = dp[i - 1] * 10 + mi[i - 1];
mi[i] = 10ll * mi[i - 1];
}
solve(r, ans1), solve(l - 1, ans2);
for (int i = 0; i < 10; ++i) printf("%lld ", ans1[i] - ans2[i]);
return 0;
}
</details>
特点：对于每一位从0—9进行枚举，中间对于进位特殊考虑。
未完待续...