数位 dp

数位 dp 就是处理和具体的数有关的 dp，一般和每个数位有关。

大多数的题目形式类似于：统计 $[l,r]$ 之间有多少整数满足某个性质。这个某性质往往是数位之间的性质。

比如有多少数包含 $49$，如 $1949$ 包含，而 $1994$ 不包含。$l$、$r$一般很大，如 $10^{100000}$。

算法复杂度往往和数的位数相关。一般数据范围不会真的这么大，比如 $10^9$，有时候可分段打表暴力拿分。

数位 dp 主要麻烦的地⽅在于前导零的处理、$\leq r$ 之类限制的处理。

例题1

题目

设 $dp_{i,j}$ 为第 $i$ 位为 $j$ 时的方案数。

所以边界是对于 $x\in[0,9]$，$dp_{1,x}=1$。

然后转移方程是 $dp_{i,j}=\sum\limits_{x=\max(j-2,0)}^{\min(j+2,9)}dp_{i-1,x}$。

记得取模 $\bmod$。

最后答案就是 $\sum\limits_{x=1}^9dp_{k,i}$。

为什么是 $x=1$，因为不能有前导 $0$。

但是单个 $0$ 可以，所以特判 $k=1$ 时输出 $10$。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int k,dp[1000001][10],sum;
const int mod = 1000000007;

signed main()
{
	scanf("%lld",&k);
	if(k == 1){printf("10");return 0;}//特判
	for(int i = 0;i <= 9;i++) dp[1][i] = 1;//边界
	for(int i = 1;i <= k;i++)
	for(int j = 0;j <= 9;j++)
	for(int x = max(j - 2,0ll);x <= min(j + 2,9ll);x++)
	dp[i][j] = (dp[i][j] + dp[i - 1][x]) % mod;//转移
	for(int i = 1;i <= 9;i++) sum = (sum + dp[k][i]) % mod;//累加
	printf("%lld",sum);
	return 0;
}

例题2

题目

给定两个正整数 $a$ 和 $b$，求在 $[a,b]$ 中的所有整数中，被自身数位和整除的数有多少个。

一般用记忆化搜索的形式写，而不用其他 dp 常用的递推。

从起点向下搜索，到最底层得到⽅案数，一层一层向上返回答案并累加，最后从搜索起点得到最终答案。

对于 $[l,r]$ 区间问题，一般转化为两次数位 $dp$，即找 $[0,r]$ 和 $[0,l−1]$ 两段，再将结果相减就得到了我们需要的 $[l,r]$。

即我们只需要考虑在 $[0,n]$ 下这一问题怎么解决。

先将 $n$ 进行数位拆分

比如 $654$ 会拆成 $4\ 5\ 6$，从左到右下标递增，$4$ 的下标为$0$

一般会设计 $𝑑𝑝_{i,0/1,0/1}$表示考虑前 $𝑖$ 位已经确定的情况下， 当前是否解除了枚举限制，当前是否有前导零（如果有其他限制 or 要求则增加更多状态即可，比如前一位或者前几位的状态）的⽅案数，一般数位 dp 的时间限制不高，多开几个状态也问题不⼤。

是否解除了枚举限制

什么是“考虑前 $𝑖$ 位已经确定的情况下，当前是否解除了枚举限制”？

由于我们要搜的数可能很长，所以我们从最高位开始搜起。

例如：我们在搜索 $[0,654]$ 的数时，显然最高位搜索范围是 $0\sim6$，而后面的位数的取值范围会根据上一位发生变化：

• 当最高位是 $0\sim5$ 时，第二位取值为 $[0,9]$；
• 当最高位是 $6$ 时，第二位取值为 $[0,5]$（再往上取就超出右端点范围了）

这一特点我们叫枚举限制，用 $𝑙𝑖𝑚𝑖𝑡$ 标记来记录。

• 如果当前 $𝑙𝑖𝑚𝑖𝑡=1$，且当前位取得最⼤数位，则下一位的 $𝑙𝑖𝑚𝑖𝑡=1$；
• 如果当前𝑙𝑖𝑚𝑖𝑡 =1，且当前位不是最⼤数位，则下一位的 $𝑙𝑖𝑚𝑖𝑡=0$；
• 如果当前 $𝑙𝑖𝑚𝑖𝑡=0$，则不论当前位取值，下一位的 $𝑙𝑖𝑚𝑖𝑡=0$。

简写：当前位能取的最⼤值为 $res$，则下一位的标记为 𝑖==𝑟𝑒𝑠&&𝑙𝑖𝑚𝑖t。

前导 0 标记

假设我们需要找 $[0,1000]$ 内找相邻数位差值小于等于 $2$ 的数的数量。

$45,75,645$ 是合法的，但是加上前导零 $0045,0075,0645$ 就不合法了。因此需要加一个前导零标记来避免这种误判

• 如果当前 $lead=1$，且当前位填 $0$，则下一位也是前导 $0$，$lead=1$；
• 如果当前 $lead=1$，但当前位不是 $0$，则本位作为当前数的最高位，下一位 $lead=0$。

不是所有问题都需要判前导零，有影响才需要，当然加了也不会产生多⼤时间开销，都加上也行。

记忆化搜索

使用 DP 数组保存已经搜索过的情况。

DP 数组中一般不会保存 $limit$ 和 $lead$，注意在当前 limit==0&&lead==0 的时候才能记录值。

解答

设 $dp_{i,sum,m,k}$ 表示在 $i$ 位数中数位和为 $sum$ 且数值 $\bmod\ k=m$ 的有几个。

例如 $dp_{2,12,3,7}=1$，因为 $00-99$ 中满足的有 $39,48,57,\color{red}66$$,75,84,93$。

那么 $dp_{3,16,4,9}$ 手算慢，如何转移？

设 $dp_{3,16,4,9}$ 由 $dp_{2,x,y,9}$ 转移得到。

对于 $a$，$a+x=16$，$(a\times10+y)\bmod9=4$。（$a$ 是枚举的变量）

• $a=0$ 时 $dp+=dp_{2,16,4,9}$；
• $a=5$ 时 $dp+=dp_{2,11,8,9}$。

所以 $dp_{i,sum,m,k}=\sum dp_{i-1,sum-a,\text{遍历},k}$

抽象死了，我觉得代码讲的比我好，让它来讲吧。

#include <bits/stdc++.h>
using namespace std;

int l,r,a[100],dp[12][100][100][100];

int dfs(int pos,int sum,int mod,int k,int limit)//记搜
{
	if(pos <= 0) return sum == 0 && mod == 0;//边界,数位和是sum且取模后为0
	if(dp[pos][sum][mod][k] != -1 && !limit) return dp[pos][sum][mod][k];//记录当前值,记忆化
	int ret = 0;//暂时记录当前方案数
	int res = limit?a[pos]:9;//res当前位能取到的最大值
	for(int i = 0;i <= res;i++) ret += dfs(pos - 1,sum - i,(mod * 10 + i) % k,k,i == res && limit);
	if(!limit) dp[pos][sum][mod][k] = ret;//当前状态方案数记录
	return ret;
}

int calc(int x)//把数按位拆分
{
	int len = 0;
	while(x) a[++len] = x % 10,x /= 10;
	int ans = 0;
	for(int k = 1;k <= 9 * len;k++) ans += dfs(len,k,0,k,1);//枚举数位和
	return ans;
}

signed main()
{
	memset(dp,-1,sizeof(dp));
	while(cin >> l >> r) printf("%d\n",calc(r) - calc(l - 1));
	return 0;
}

** 题老是 TLE，卡时限很好玩吗，若交上去超时就再交，即可 AC。（害得我 debug 好久）

例题3

题目

一

#include <bits/stdc++.h>
#define int long long
using namespace std;

int t,x,a[33],dp[33][2][2];//定义f[pos][n1][n2]表示准备搜索第pos位的数字,pos的前两位分别是n1,n2,其非魔鬼数数量

int dfs(int pos,bool n1,bool n2,bool flag)//深搜非魔鬼数的数量,记忆化搜索
{
	if(!pos) return 1;
	if(!flag && dp[pos][n1][n2] > -1) return dp[pos][n1][n2];
	int maxn = 9,ans = 0;
	if(flag) maxn = a[pos];
	for(int i = 0;i <= maxn;i++)
	{
		if(n1 && n2 && i == 6) continue;//是魔鬼数,跳过,要统计的是非魔鬼数的数量
		ans += dfs(pos - 1,n2,i == 6,flag && i == maxn);
	}
	if(!flag) dp[pos][n1][n2] = ans;
	return ans;
}

bool check(int mid)
{
	int n = 0,k = mid;
	while(mid){a[++n] = mid % 10;mid /= 10;}
	return (k + 1 - dfs(n,0,0,true)) >= x;//把0加上,减去非魔鬼数的数量=魔鬼数的数量
}

signed main()
{
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld",&x);
		memset(dp,-1,sizeof(dp));
		int l = 0,r = 1e11 + 5;
		while(l + 1 < r)//二分查找mid以内魔鬼的数量
		{
			int mid = l + r >> 1;
			if(check(mid)) r = mid;
			else l = mid;
		}
		printf("%lld\n",r);
	}
	return 0;
}

二

考虑先求出前 $i$ 位的魔鬼数的总数。

记 $f_{i,j}(0\le j\le2)$ 为前 $i$ 位从 $i$ 开始有连续 $j$ 个 $6$ 的非魔鬼数的数量， $f_{i,3}$ 为前 $i$ 位魔鬼数的总数。

对于 $f_{i,0}$ ，由于第 $i$ 位可以选除 $6$ 外的任意数字且没有其他限制，所以 $f_{i,0}=9*(f_{i-1,0}+f_{i-1,1}+f_{i-1,2})$ 。

对于 $f_{i,1}$ ，由于第 $i$ 位必须填 $6$ 且第 $i-1$ 位必须不为 $6$ ，所以 $f_{i,1}=f_{i-1,0}$ 。

对于 $f_{i,2}$ ，同 $f_{i,1}$ ，即 $f_{i,2}=f_{i,1}$ 。

对于 $f_{i,3}$ ，若其由前 $i-1$ 位的魔鬼数转移而来，则当前位可以填任意数；若其由前 $i-1$ 位的非魔鬼数转移而来，则必须保证该数的最高两位（第 $i-1$ 和 $i-2$ 位）必须是 $6$ ，且当前位必须填 $6$ 。所以 $f_{i,3}=10\times f_{i-1,3}+f_{i-1,2}$ 。

初始化 $f_{0,0}=1$ 。

求出 $f$ 数组后，我们便可以算出第 $n$ 大的魔鬼数的长度，记为 $len$ 。

接着，我们从高位到低位，依次确定每一位的值。用 $j$ 从 $0$ 到 $9$ 枚举第 $i$ 位的值，对于每个 $j$ ，我们用 $tot$ 统计在该位为 $j$ 且前 $len-i$ 位已经确定的情况下，魔鬼数的总数。如果 $n>tot$ ，那么直接让 $n-=tot$ ，那么现在的 $n$ 就表示在前 $len-i$ 位确定且第 $i$ 位为 $[j+1,9]$ 中的数时，第 $n$ 大的魔鬼数。否则如果 $n<=tot$ ，则当前 $j$ 就一定是第 $i$ 位的答案，因为 $j$ 是从 $0$ 开始一个一个枚举的。

那么现在问题就是如何求出 $tot$ ，首先 $tot$ 肯定是会加上 $f_{i-1,3}$ 的。

我们对位置 $i$ 时，记录一个数组 $cnt$ ，表示从最高位开始的连续 $6$ 的个数，如果在某一位断了且没达到 $3$ ，那么更改为 $0$ ，如果达到了 $3$ ，那么这个数一定是魔鬼数，就不变。

$tot$ 还会加上该位为 $j$ 时新增的魔鬼数，先将 $k$ 更新，如果 $k=3$ ，那么 $tot+=f_{i-1,0}+f_{i-1,1}+f_{i-1,2}$ ，如果 $k=2$ ，那么 $tot+=f_{i-1,0}+f_{i-1,1}$ ，如果 $k=1$ ，那么 $tot+=f_{i-1,0}$ ，具体实现看代码。

代码如下：

#include<cstdio>
#include<iostream>
using namespace std;
long long f[21][4]={1};
int t,n;
int main(){
	for(int i=1;i<=20;i++){
		f[i][0]=9*(f[i-1][0]+f[i-1][1]+f[i-1][2]);
		f[i][1]=f[i-1][0];
		f[i][2]=f[i-1][1];
		f[i][3]=10*f[i-1][3]+f[i-1][2];
	}
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		int len=3;
		while(f[len][3]<n)len++;
		for(int i=len,cnt=0;i;i--){
			for(int j=0;j<=9;j++){
				long long tot=f[i-1][3];
				if(j==6||cnt==3)for(int k=max(3-cnt-(j==6),0);k<3;k++)tot+=f[i-1][k];
				if(tot<n)n-=tot;
				else{
					if(cnt<3)j==6?cnt++:cnt=0;
					printf("%d",j);
					break;
				}
			}
		}
		printf("\n");
	}
}