位数统计DP

· · 个人记录

一、定义

与数字相关的一类计数问题。

二、常见思路

用DP预处理求出位数，再用试填法拼凑每位

三、经典模型

第k个数：

  1. 找位数：

既然要求第k个数，而这个数的分布又是不定的，那么就应该依照这个数的特性，用DP先选出这个数的位数（也就是当前位数下满足要求的数的个数，允许存在前导0）。

  1. 填数字

在确定位数之后，我们就应该去填每一位。一般从大到小枚举位数，从小到大枚举数字。累加每个数字下的数个数，直到选定。

例： 启示录

区间个数：

区间个数应该用前缀相减。并且与找第k个数不同，他的数值不会太大，一般在int范围内（毕竟题目能把数字输入）。

同类分布(月之谜）