数位 DP

数位 DP 是解决与数字有关相关的一类计数问题的一系列算法。

一般是给定一些限制条件，求满足条件 $P$ 的第 $k$ 个数是什么，或者问在区间 $[L,R]$ 中满足条件 $P$ 的数的权值总和。

这些题目给出的限制条件一般不是数的大小，而是数的位与位之间的关系。

常用思想和技巧

计数：将区间问题转化为前缀问题

将区间 $[L,R]$ 转化为区间 $[0,R]$（或 $[1,R]$）减去区间 $[0,L-1]$（或 $[1,L-1]$）。这样，DP 时只用考虑最大值的限制，而没有最小值的额外限制，更加简便。

区间划分

通过上面的简化，我们求解小于 $n$ 且满足条件 $P$ 的数的权值和。

对于一个小于 $n$ 的数，它从高到低必定出现某一位，使得这一位上的数字小于 $n$ 对应位置上的数字，并且这一位以前的数字都和 $n$ 中对应的位置相等，这一位之后的数字的选取没有限制。

一般地，我们定义 $f_{i,\mathrm{status},\mathrm{op}}$ 为目前考虑数字从高到低第 $i$ 位，当前前缀（前 $i-1$ 为）的“状态”为 $\mathrm{status}$，且当前考虑的数字与 $n$ 的大小关系为 $0$（小于）或 $1$（卡在最大值限制上）。

数位 DP 通用的状态转移方程：

$$f_{i,\mathrm{status},\mathrm{op}}=\sum\limits_{k=0}^dP(\mathrm{status},k)f_{i+1,\mathrm{status}',\mathrm{op} \land [k=d]}$$

其中 $k$ 是下一位的值，它的范围是 $[0,d]$。如果 $\mathrm{op}=1$（卡上限），则 $d$ 为 $n$ 对应位置上的数；否则，$d$ 为当前进制下的最大数位。$P(\mathrm{status},k)$ 表示当前位 $k$ 和前 $i-1$ 位的状态 $\mathrm{status}$ 是否满足条件 $P$。

与质因数有关的数位 DP

通常的切入口是质因数的个数，这往往很有限。比如，如果只允许以各位数字为质因数，可能的质因数只有 $2$、$3$、$5$ 和 $7$。

而且，给定可能的质因数，则只以它们作为质因数的数字非常离散。如果只考虑 $[1,n]$ 范围内的数，且只给定了 $k$ 个质因数，那么满足要求的数字个数为 $O((\log n)^k) \ll n$。

转换视角：$k$ 进制下的数 -> （假想的）$k$ 叉树

先考虑 $k=2$ 的情况。比如统计小于 $13$ 的自然数，$13=(1101)_2$，小于 $13$ 的自然数分成了 $3$ 棵满二叉树，根节点分别为 $00$、$010$ 和 $01100$，把小于 $13$ 的自然数划分为了 $3$ 个区间：$[(0000)_2,(0111)_2]$、$[(1000)_2,(1011)_2]$ 和 $[(1100)_2,(1100)_2]$。这 $3$ 棵满二叉树可以看作从根节点走到 $13$ 的路径，每次要“右转”时改为“左转”得到的。统计时，只用顺着走一遍，累加即可。

$k>2$ 时类似。

例题：数码出现次数，数位和，数位积，整除等问题

例题 1：URAL 1057

题目大意

求出区间 $[a,b]$ 中有多少个数能够写成 $K$ 个 $B$ 的 不同 幂次之和。

保证 $1 \le a \le b \le 2^{31}-1$，$1 \le k \le 20$，$2 \le B \le 10$。

做法 1

不妨按照二叉树的方式理解。向 $0$ 号子节点走（左），表示不选择 $K$ 的这一个幂；向 $1$ 号子节点走（右），表示选择 $K$ 的这一个幂。这里要求“恰好 $K$ 个”，于是用 $f_{i,j}$ 表示当前是第 $i$ 次幂，已经选了 $j$ 个的方案数，则 $f_{i,j}=f_{i-1,j-1}+f_{i-1,j}$，边界条件为 $f_{i,0}=1$，这正是组合数 $i \choose j$。

预处理组合数，并将区间 $[a,b]$ 变为 $[1,b]$ 和 $[1,a-1]$，注意将 $B$ 进制转化为二进制，通过走二叉树的方式求得答案即可。

提交记录（Virtual Judge） 备份

例题 2：ZJOI2010D1T1

题目大意

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

保证 $1 \le a \le b \le 10^{12}$。

做法 1

对每个数码分开处理。用 dfs(digit,limit,zero,cnt) 表示以下状态：从低到高第 $\mathrm{digit}$ 位，是否达到上界，是否有前导零，当前数码 $c$ 出现的次数。

对于 $\mathrm{limit}=\mathrm{zero}=0$ 的情况，可以记忆化。

提交记录（DarkBZOJ） 提交记录（Luogu） 备份

例题 3：Luogu P6218

题目大意

如果一个正整数的二进制表示中，$0$ 的数目不小于 $1$ 的数目，那么它就被称为「圆数」。请你计算，区间 $[l,r]$ 中有多少个「圆数」。

做法 1

状态设计：dfs(digit,diff,limit,zero) 表示当前考虑从低到高第 $\mathrm{digit}$ 位，$0$、$1$ 出现次数之差为 $\mathrm{diff}-32$（为了记忆化，将下标变为自然数），是否达到上限，是否有前导零。

核心代码：

for(int i=0;i<=d;i++)ans+=dfs(digit-1,diff+(i?-1:zero?0:1),limit&&d==i,zero&&i==0);

提交记录 备份

例题 4：BZOJ 3209

题目大意

设 $\mathrm{sum}(i)$ 表示 $i$ 的二进制表示中 $1$ 的个数。给出一个正整数 $n$，花神要问你 $\prod\limits_{i=1}^n\mathrm{sum}(i)$。

保证 $1 \le n \le 10^{15}$。对 $10000007$ 取模。

做法 1

显然 $\mathrm{sum}(i)$ 只有不到 $60$ 种取值，可以算出每一个取值的出现次数，再用快速幂乘起来。

求解 $1 \sim N$ 范围内的二进制表示中 $1$ 的个数为 $x$ 的数量，可以把这段区间划分成若干段 $[n \times 2^c,n \times 2^c+2^c-1]$（多算了 $0$，忽略它即可），这里面的二进制表示中 $1$ 的个数为 $x$ 的数量为 ${x-\operatorname{popcount}(n)} \choose c$。

可以预处理组合数，考虑到组合数要加到次数上去，组合数应该对 $\varphi(10000007)=9988440$ 取模。

提交记录（DarkBZOJ） 备份

例题 7：Luogu P3413

题目大意

定义满足“存在长度至少为 $2$ 的回文子串”的整数是 萌数。问在 $[l,r]$ 中有多少个萌数，答案对 $10^9+7$ 取模。保证 $l<r \le 10^{1000}$。

做法 1：数位 DP

结论：如果一个字符串 $S$ 有一个长度不小于 $2$ 的回文子串，那么 $S$ 一定有一个长度为 $2$ 或 $3$ 的回文子串，反之亦然。（证明：考虑回文串的中间的几个字符。）

因此，DP 状态除了 $\mathrm{digit}$ 数位、$\mathrm{limit}$ 是否卡上界和 $\mathrm{zero}$ 是否有前导零外，还要有最近的 $3$ 位数。注意前导零不能算作数位，可以用 $10$ 代替。

另外，如果懒得写高精度减法，可以特判 $l$ 是不是萌数。

提交记录 备份

做法 2：求解非萌数，使用数学方法

可以看这篇文章：题解 P3413 【SAC#1 - 萌数】 - sheep 的博客 - 洛谷博客

例题 8：AHOI2009D1T2

题目大意

给出 $a$、$b$，求出在 $[a,b]$ 中各位数字之和能整除原数的数的个数。

保证 $1 \le a \le b \le 10^{18}$。

做法 1

题目中已经暗含了 $4$ 个状态：从高到低的位数 $\mathrm{digit}$、$\mathrm{sum}$ 想要达到的位数和、$\mathrm{remainder}$ 模 $\mathrm{sum}$ 所得的余数和 $\mathrm{now}$ 已经确定的部分的数位和。另外，再加上一个 $\mathrm{flag}$ 表示是否顶到上界。

显然，$1 \le \mathrm{sum} \le 162$，完全可以枚举 $\mathrm{sum}$，对剩下的状态进行记忆化搜索。

两种小剪枝：当 $\mathrm{now}>\mathrm{sum}$ 或 $\mathrm{now}+(\mathrm{digit}+9)<\mathrm{sum}$ 时，直接返回 $0$。

提交记录（DarkBZOJ） 提交记录（Luogu，没有使用第二种剪枝） 备份

例题 10：CF55D

题目大意

认为一个数字 $x$ 是美丽的，当且仅当 $x \in \mathbb{Z^+}$ 并且对于 $x$ 的每一个非零位上的数 $y$，都有 $y|x$。算出在区间 $[l,r]$ 中有多少个数是美丽的。

共 $t$ 组数据，保证 $1 \le t \le 10$，$1 \le l \le r \le 9 \times 10^{18}$。

做法 1

数位 DP 的状态：$\mathrm{digit}$ 表示当前位数，$\mathrm{lcm}$ 表示已知的非 $0$ 的数位的最小公倍数，$\mathrm{num}$ 表示已知的数位 $\bmod 2520$，$\mathrm{lim}$ 表示是否顶上界。

提交记录 备份

例题 11：BZOJ 1183

题目大意

定义一个数的 digit-product 是它的各个位上的数字的乘积。定义一个数的 self-product 是它本身乘以它的 digit-product。求 self-product 在 $a$ 和 $b$ 之间的数的个数。

保证 $1 \le a \le b \le 10^{18}$。

做法 1

定义 $p(x)$ 为 $x$ 的 digit-product，则有 $p(x) \le x$。又因 $p(x) \times x \le b \le 10^{18}$，所以 $p(x) \le \sqrt b$。

根据 $p(x)$ 的定义，$p(x)$ 只能有 $2$、$3$、$5$、$7$ 这四种质因数，种类很少，打表可知只有 $5194$ 种。

将问题转化为：对于一个给定的正整数 $P=2^{x_1}3^{x_2}5^{x_3}7^{x_4}$，有多少在 $[\lceil \dfrac{a}{P} \rceil,\lfloor \dfrac{b}{P} \rfloor]$ 中的 $x$ 满足 $P=p(x)$。

可用 $f_{\mathrm{digit},p}$ 表示已经考虑了 $\mathrm{digit}$ 位，剩余部分的乘积应为 $p$ 时的方案数，可以通过记忆化搜索实现。

提交记录（DarkBZOJ） 备份

例题 12：SDOI2013R1D2T3

题目大意

有一个 $n \times n$ 的方格网，$X$ 轴、$Y$ 轴坐标范围均为 $[1,N]$ 内的正整数，初始时，所有的整数坐标点上均有一块金子。

一阵风吹过，金子的位置发生变化，点 $(i,j)$ 上的金子飘到了 $(f(i),f(j))$ 上。其中 $f(x)$ 表示 $x$ 各位数字的乘积，忽略前导零，但是中间的零要考虑。如果金子变化后的坐标不在 $1 \cdots N$ 的范围内，我们认为这块金子已经被移出游戏。同时可以发现，对于变化之后的游戏局面，某些坐标上的金子数量可能不止一块，而另外一些坐标上可能已经没有金子。

接着，玩家要选择 $K$ 个互不相同的位置采集金子。问最多可以采集到多少块金子，答案对 $10^9+7$ 取模。

做法 1

首先，可以发现 $f(x)$ 的取值非常有限，除去 $0$ 后，只能包含质因子 $2$、$3$、$5$、$7$，最多有 $8281$ 种。

为了方便计算，我们将数表示成 $x=2^{a_0} \times 3^{a_1} \times 5^{a_2} \times 7^{a_3}$ 的形式，在代码中以结构体的形式呈现。

我们先进行一次数位 DP 来求出所有可能的 $f(x)$ 的取值。

接下来，对于每一种取值，我们再通过一次数位 DP 来求出它的出现次数，具体来说，就是让 $f_{i,j}$ 表示最低的 $i$ 位，乘积应为 $x$ 时的方案数。由于 $x$ 可能很大且分布很稀疏，又有 $0 \le a_0 \le 36$、$0 \le a_1 \le 24$、$0 \le a_2,a_3 \le 12$，可以用 $\mathrm{hash}=((a_0 \times 25+a_1) \times 13+a_2) \times 13+a_3$ 来代替 $x$ 做为第二维下标。

最后，我们得到了一个 $\mathrm{cnt} \times \mathrm{cnt}$ 的方格网，其中第 $i$ 行、第 $j$ 列的值为 $\mathrm{num\_cnt}_i \times \mathrm{num\_cnt}_j$。将 $\mathrm{num\_cnt}$ 从大到小排序后，这个方格网显然满足左边比右边大，想取右边的必须先取完所有左边的这一性质。那么，我们可以用优先队列来维护这些信息，将每一行中最左边的未取用的元素放入队列，每次取出队列中值最大的元素，计入答案后放回它右边的元素（如果存在），一直到次数用完或队列为空为止。

提交记录 备份

例题：位运算的数位 DP

例题 1：BZOJ 5043

题目大意

给出一个长度为 $n$ 的数组 $b$，求最小的 $k$ 满足 $\sum\limits_{i=1}^nb_i \oplus k=m$，无解输出 -1。

保证 $1 \le n \le 10^5$，$0 \le m<2^{60}$，$0 \le b_i<2^{60}$。

做法 1

显然，对于位运算，数字的每一位是独立的。可以统计 $b_{1 \sim n}$ 的第 $i$ 位为 $j$ 的个数为 $\mathrm{cnt}_{i,j}$。如果 $k$ 的第 $i$ 位是 $0$ / $1$，对答案的贡献就是 $\mathrm{cnt}_{i,1} \times 2^i$ / $\mathrm{cnt}_{0,i} \times 2^i$。这就变成一个 0/1 背包问题了。

设 $f_{i,j}$ 为选到第 $i$ 位，贡献比 $m$ 对应位数小 $j \times 2^i$ 的最小答案。我们每次考虑下一位时，可以直接将系数乘 $2$ 来进行“退位”。

备份

例题 2：BZOJ 3329

题目大意

有 $T$ 组数据，每次给出一个正整数 $n$，问小于等于 $n$ / $2^n$ 的自然数中，有多少个数是方程 $x \oplus 3x=2x$ 的解，第二问的答案对 $10^9+7$ 取模。

做法 1

研究方程

先研究一下这个方程：

$$\because x \oplus 3x=2x$$

左右两边对 $x$ 作异或运算。

$$\therefore x \oplus (x \oplus 3x)=(x \oplus x) \oplus 3x=3x=x \oplus 2x$$

$$\therefore x+2x=x \oplus 2x$$

考虑到异或等同于对二进制数做不进位加法，$x$ 与 $2x$ 的同一位不能同时为 $1$。

又考虑到 $2x$ 就是在 $x$ 的末尾加一个 $0$ 得到的，$x$ 不能有相邻两位都为 $1$。

第一问

简单数位 DP，用 $f_{\mathrm{digit},\mathrm{last},\mathrm{lim}}$ 表示从低到高第 $\mathrm{digit}$ 位，上一位是 $\mathrm{last}$，是否卡到上界时的方案数。可以使用记忆化搜索实现。时间复杂度为 $O(\log n)$。

第二问

用 $f_{i,j}$ 表示一共有 $i$ 位，最后一位是 $j$ 且没有相邻两位是 $1$ 的方案数。

转移式：$f_{i,0}=f_{i-1,0}+f_{i-1,1}$，$f_{i,1}=f_{i-1,0}$。边界：$f_{0,0}=f_{1,0}=1$。

这正好是斐波那契数列，可以使用矩阵乘法快速幂优化，时间复杂度为 $O(\log n)$。

代码实现

提交记录（DarkBZOJ） 备份

例题 3：SDOI2016R1D1T1

题目大意

给 $n$、$m$、$k$、$p$，求 $\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1}\max((i \oplus j)-k,0) \bmod p$ 的值，其中 $\oplus$ 表示二进制意义下的异或。

保证 $n,m,k \le 10^{18}$，不多于 $5000$ 组数据。

做法 1

经典数位 DP。记 $f(i,a,b,c)$、$g(i,a,b,c)$ 表示从大到小考虑到第 $i$ 位，$a,b,c$ 表示当前的数是否顶 $n,m,k$ 的上界，对应的方案数和 $i \oplus j$ 之和。只统计 $i \oplus j \le k$ 的方案。转移时枚举当前位即可。时间复杂度 $O(\log n)$。

$$\begin{aligned} \sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1}\max((i \oplus j)-k,0) &= \sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1}(i \oplus j)-k \times f(61,1,1,1) \\ &= g(61,1,1,1)-k \times f(61,1,1,1) \end{aligned}$$

为什么要设置“是否顶上界”呢？题目中要求 $0 \le i \le n-1$ 且 $0 \le j \le m-1$，在枚举每一位时，都要控制 $i,j$ 的大小。在更新第 $i$ 位时，如果前 $i-1$ 位都顶上界，则第 $i$ 位不能超过 $n,m,k$ 这一位的上界；如果前 $i-1$ 位没有都顶上界，则第 $i$ 位没有限制。

举个例子：$n=1000110$，若 $i$ 的前 $5$ 位是 $00110$（即顶上界），则选取 $i$ 的第 $6$ 位只能是 $1$；若 $i$ 的前 $5$ 位是 $00100$（即没有顶上界），则选取 $i$ 的第 $6$ 位没有限制。

备份

例题 4：GYM 104053M

题目大意

给定 $A$、$B$、$n$，求满足以下条件的长度为 $n$ 的整数序列 $a$ 个数：

• $\sum\limits_{i=1}^n\sum\limits_{j=1}^i(a_i \oplus a_j)=A$
• $\forall 1 \le i \le n,0 \le a_i \le B$

保证 $0 \le A \le 10^{15}$，$0 \le B \le 10^{12}$，$1 \le n \le 40$。

做法 1

设 $f_{i,j,k}$ 表示需要 $j$ 个第 $i$ 位，现在有 $k$ 个数和 $B$ 相同（即顶着上界）的方案数，从高位到低位转移，枚举当前位有多少个 $0$。

时间复杂度为 $O(n^5 \log \max\{A,B\})$，能过。

提交记录（NFLSOJ） 提交记录（Codeforces） 备份

例题 5：NFLSOJ 1101

题目大意

找到一个长度为 $n$ 的，和为 $s$，异或和为 $x$ 的非负整数序列 $a_1,a_2,\cdots,a_n$。

你需要判断这样的序列是否存在，若存在，并求出其最大值的最小值。

有多组数据。

保证 $1 \le T \le 200$，$1 \le n<2^{60}$，$0 \le s,x<2^{60}$。

做法 1

zhouchenrui 做法详细阐述以及证明

b6e0 2023-10-13 8:28:04 2023-10-13 8:28:39

做法

我们把题面中的 $s,x$ 称作 $S,X$；称一个数 $x$ 二进制表示下的第 $i$ 位为 $x_i$，下标从 $0$ 开始。

我们令 $f_{w,s}$ 表示已经填完了 $>w$ 的位，并剩下 $s \cdot 2^{w+1}$ 的和要低位“偿还”。数组内是一个 pair，$\mathrm{first}$ 和 $\mathrm{second}$ 分别表示目前 $a_i$ 的最大值和最大值的个数，dp 值是这个 pair 的 $\min$（$\mathrm{first}$ 为第一关键字，$\mathrm{second}$ 为第二关键字）。显然取 pair 的 $\min$ 是最优的。

记 $c=2s+S_w$。朴素的转移是枚举当前位填 $j$ 个 $1$（$j$ 的奇偶性应该与 $X_w$ 相同），若 $\mathrm{second}+j \le n$ 则用 $\{\mathrm{first},\mathrm{second}\}$ 更新 $f_{w-1,c-j}$，否则用 $\{\mathrm{first}+2^w,\mathrm{second}+j-n\}$ 更新。

这个 $\mathrm{dp}$ 实际上更像是一个广搜，就是从高到底考虑每一位，将这一位填上，然后继续搜索下一位。$(w,s)$ 就是一个搜索的状态。

首先进行一个剪枝：若 $c \ge 2n$，那么即使下面全填满也无法达到，就不继续转移，直接跳过。

然后考虑优化转移。将转移分为两类：对当前位不产生贡献的，即 $\mathrm{second}+j \le n$；以及产生贡献的，即 $\mathrm{second}+j>n$。考虑分别优化。

第一类转移优化

记 $d$ 为最大可以填的 $1$ 的个数。我们先进行 $j=d$ 的转移；然后若 $c-d=0$，再进行 $j=d-2$ 的转移。不用进行更多转移。

要证明这是对的，只要证：

对于任意 $s_0>0$，令 $s_1=s_0+2$，若 $(w-1,s_1)$ 存在一组 $\{a_i\}$ 满足要求，那么一定可以将一些 $a_{i,j}$ 从 $1$ 变成 $0$ 得到 $(w-1,s_0)$ 的一组解。这蕴含着，若 $(w-1,s_1)$ 有解，那么 $(w-1,s_0)$ 有解。

令 $r$ 为 $S$ 中低于 $w$ 的位表示的数，即 $r=S \bmod 2^w$，那么有：

$$\sum\limits_{i=1}^n\sum\limits_{j=0}^{w-1}a_{i,j}2^j=r+s_1 \cdot 2^w$$

对于每个满足 $j<w$ 且 $X_j=1$ 的 $j$，我们选择一个满足 $a_{i,j}=1$ 的 $i$，先将这一位变为 $0$。记这些的位置组成的集合为 $C$。因为 $<w$ 的每一位最多只选择了一个数，而 $\sum\limits_{j=0}^{w-1}2^j=2^w-1$，所以此时有

$$\sum\limits_{i=1}^n\sum\limits_{j=0}^{w-1}a_{i,j}2^j \ge r+s_1 \cdot 2^w-2^w+1=r+1+(s_1-1) \cdot 2^w$$

此时，对于每个 $j<w$，满足 $a_{i,j}=1$ 的 $i$ 个数一定是偶数。我们现在只需要证明可以选出一些 $(i,j)$，满足对于所有 $j_0$，只有偶数个 $(i,j)$ 满足 $j=j_0$，且 $\sum 2^j=2^{w+1}$，然后将这些 $a_{i,j}$ 变为 $0$，最后将 $C$ 中的位置变回 $1$ 即可。

因为 $s_0>0$，所以 $s_1-1 \ge 2$，所以此时 $a_{i,j} 2^j$ 的总和显然大于 $2^{w+1}$。考虑将所有 $a_{i,j}=1$ 的 $(i,j)$ 分成两个集合 $A,B$，满足对于每个 $j$，有一半的 $i$ 在 $A$ 里，另一半在 $B$ 里，然后从 $A,B$ 中各选择一些位置满足 $\sum 2^j=2^w$ 即可。

引理：对于一个可重集 $A$，若其中 $2^j$ 的和 $\ge 2^x$，且其中 $j$ 的最大值 $\le x$，那么一定存在 $B \subseteq A$，使得 $\sum\limits_{j \in B} 2^j=2^x$。

采用反证法。若不存在和为 $2^x$ 的选择方法，取最小的和大于 $2^x$ 的选择方法，记选择的子集为 $T$，和为 $t$。取 $T$ 中最小的 $j$，记为 $j_0$，根据 $T,t$ 的最小性，$2^x<t<2^x+2^{j_0}$，又因为 $x \ge j_0$，所以 $2^{j_0} \nmid t$。又根据 $j_0$ 的最小性，$2^{j_0} \mid t$，矛盾。

集合 $A,B$ 里面 $2^j$ 的和都大于 $2^w$，且所有的 $j$ 都小于 $w$。根据引理，一定存在一种选择方法。于是得证。

第二类转移优化

与第一类几乎一样：记 $d$ 为最大可以填的 $1$ 的个数，我们先进行 $j=d$ 的转移；然后若 $c-d=0$ 或 $\mathrm{second}+d-n=n$，再进行 $j=d-2$ 的转移，不用进行更多转移。

证明也是运用调整法，考虑从 $s,\mathrm{second}$ 的一组最优的 $\{a_i\}$ 调整到 $s-2,\mathrm{second}+2$ 的一组不劣的 $\{a_i^{\prime}\}$，其中 $\mathrm{second}$ 要满足 $\mathrm{second}+2<n$，$c$ 要满足 $c>2$。

令 $t(j)$ 表示满足 $a_{i,j}=1$ 的 $i$ 的个数。

若存在一个 $j$ 满足 $t(j)>n-\mathrm{second}$，记这个 $j$ 为 $j_0$，可知 $t(j_0) \ge 4$。考察 $t(j_0+1)$，发现若 $t(j_0+1)<2$，那么可以删去 $j_0$ 处的四个 $1$，并在 $j_0+1$ 处添加两个 $1$，即将 $j_0$ 处的四个 $1$ 进位到 $j_0+1$ 处，可以得到一组更优的 $\{a_i\}$，与 $\{a_i\}$ 的最优性矛盾，所以 $t(j_0+1) \ge 2$。

接下来，我们运用归纳法，证明对于所有 $j_0<k<w$ 的 $k$，都有 $t(k) \ge 2$。设命题对于 $k<k_0$ 成立，若 $t(k_0)<2$，则可以从 $j_0$ 开始，每次将当前位的四个 $1$，进位到下一位的两个 $1$，最终 $k_0$ 得到了两个 $1$，并得到了一组更优的 $\{a_i\}$，与最优性矛盾。

有了这个性质，我们可以对于所有在 $(j_0,w)$ 中的位，删去两个 $1$，并删去 $j_0$ 处的四个 $1$，得到一组不劣的 $\{a_i^{\prime}\}$。

若不存在一个 $j$ 满足 $t(j)>n-\mathrm{second}$，此时即使每个 $j$ 都有 $n-\mathrm{second}$ 个 $a_{i,j}=1$，和也只是 $(n-\mathrm{second})(2^w-1)$，所以 $c<n-\mathrm{second}$。又因为 $c \ge 3$，所以 $n-\mathrm{second} \ge 4$，并且一定存在一个 $j_0$ 满足 $t(j_0) \ge 4$。之后，运用和上面存在的情况相同的方法，也可以得到一组不劣的 $\{a_i^{\prime}\}$。

于是得证。

复杂度证明

因为一个小细节搞不定，暂时分析不到 $\mathcal{O}(\log^2n)$，我搞不动了。

我们尝试证明，$w$ 减小 $1$ 时状态的个数只会增加 $\mathcal{O}(\log n)$，这蕴含着总复杂度为 $\mathcal{O}(\log^3n)$。

我们把状态分为三类：$0 \le s \le 2$，$s>2$ 且 $c<n$，$n \le c<2n$，分别分析它们对状态数增量的贡献。

我们不妨假定对于每个 $w$，都有 $s=0,1,2$ 三个状态，这样如果某个状态的某个后继的 $s=0,1,2$，我们不把它算在增量里。

注意到如果一个后继 $\ge n$，那么一定会被剪枝掉。

对于第一类状态，由于每个状态只有 $\mathcal{O}(1)$ 个后继，而这部分的状态数是 $\mathcal{O}(1)$ 的，所以增量是 $\mathcal{O}(1)$ 的。

对于第二类状态，第二类转移的后继一定是 $0,1,2$，所以每个状态只有一个有效后继，无增量。

对于第三类状态，我们可以证明，$n-\mathrm{second}=\mathcal{O}(\log n)$，具体懒得写，所以对于 $n \le c \le n+\mathcal{O}(\log n)$ 的状态，它们有 $\mathcal{O}(1)$ 个转移，对增量的贡献是 $\mathcal{O}(\log n)$（就是这部分我搞不定）；$\mathrm{second}=n$ 的状态只有至多一个，对增量的贡献是 $\mathcal{O}(1)$；其余每个状态只有一个后继，对增量无贡献。

所以复杂度有 $\mathcal{O}(\log^3n)$ 的上界。期待后人将其分析到 $\mathcal{O}(\log^2n)$ 或给出 hack 数据。

提交记录 备份

例题：复杂状态设计

例题 1：HDU 4352

题目大意

求在 $[L,R]$ 之内满足最长上升子序列长度为 $K$ 的数字有多少个。

保证 $0<L \le R<2^{63}-1$ 且 $1 \le K \le 10$，数据组数 $T \le 10000$。

做法 1

令 $\mathrm{dp}_{\mathrm{pos},\mathrm{state},k}$ 表示枚举到第 $\mathrm{pos}$ 位，满足状态为 $\mathrm{state}$，LIS 的长度为 $k$ 的数的数量。

本题最难的就是 $\mathrm{state}$ 的设计。

举例：将 $\mathrm{state}$ 按照数字 $13425$ 来更新。

1. 遇到 $1$，$\mathrm{state}=010000000$；
2. 遇到 $3$，$\mathrm{state}=010100000$；
3. 遇到 $4$，$\mathrm{state}=010110000$；
4. 遇到 $2$，$\mathrm{state}=011010000$；
   注意：因为第 $2$ 位后有一个 $1$（在第 $3$ 位），要把那一位的 $1$ 移过来。
5. 遇到 $5$，$\mathrm{state}=011011000$。

如果 $\mathrm{state}$ 的第 $a$ 位上为 $1$，并且之前（包括自己）有 $b$ 个 $1$，那么长度为 $b$ 的上升序列的末尾的最小值就是 $a$。

可以得出，$\mathrm{state}$ 中 $1$ 的个数就是 LIS 的长度。

另外，记得判断一下前导零，$l,r$ 范围大所以要开 long long。

备份

例题：同时存在上下界的数位 DP

例题 1：SGU 390

题目大意

有一位售票员给乘客售票，对于每位乘客，他会卖出多张连续的票，直到已卖出的票的编号的数位之和 $ \ge k$，然后他会按照相同的规则给下一位乘客售票。初始时，售票员持有的票是编号是 $[l,r]$ 的连续整数，请求出售票员可以售票给多少位乘客。

保证 $1 \le l \le r \le 10^{18}$，$1 \le k \le 1000$。

做法 1

参考资料：【sgu390】数位dp - 拦路雨偏似雪花 - 博客园。

这道题比较特殊，不能将答案变成 $[1,r]$ 减去 $[1,l-1]$，也就是说不存在区间可减性了。记忆化搜索的时候，要用两个变量 $\mathrm{lim1}$ 和 $\mathrm{lim2}$ 来表示是否压到了上限和下限。

用 $f_{\mathrm{cur},\mathrm{sum},\mathrm{rem}}$ 表示对于前 $\mathrm{cur}$ 位，已确定的高位的数字和为 $\mathrm{sum}$，这次分组剩余的数字和为 $\mathrm{rem}$ 时的分组数量和剩余数字和。

那么，对于 $\mathrm{cur}=0$ 的情况，若 $\mathrm{sum}+\mathrm{rem} \ge k$，那么答案为 $\{1,0\}$；否则，答案为 $\{0,\mathrm{sum}+\mathrm{rem}\}$。

对于 $\mathrm{cur}>0$ 的情况，只用枚举下一位是什么数。

时间复杂度为 $O(\log_dr \times (\log_dr \times d) \times k \times d)=O(\log^2_dr \times d^2 \times k)$，其中 $d=10$。

提交记录 备份

参考资料

• 数位 DP 小记 | Acc Robin's
• 【数位DP】CF55D BZOJ3329 HDU4352 SGU390 HDU5519