数位dp-526互联

数位dp的一般套路

问题形式

给你一个条件 $A$ ,然后询问值大小在 $[L,R]$ 中有多少满足条件的数

这个问题暴力去做一般是 $\mathcal{O}(R)$ 的时间复杂度,但是通过数位dp我们可以把这个东西优化到 $\mathcal{O}(\log_{10}R)$

求解过程

首先我们将区间 $[L,R]$ 的限制利用前缀和拆开,这样我们的问题就变成了求 $[1,R]$ 中满足要求的数的个数

每一位作为dp的阶段,设计状态,一般采用记忆化搜索的方法

我们要从高位向低位枚举,因为如果我们确定的高位之后才可以确定低位的范围

比如说一个数 $1230$

如果我们前两位分别选的是 $1,2$ ,那么第三位的取值范围就是 $[0,3]$

如果我们前两位分别选的是 $1,1$ ,那么第三位的取值范围就是 $[0,9]$

也就是我们在记忆化搜索的过程中记一个变量 $lim$ 表示前几位是否和最大数一样

具体的代码实现看下面的这一道题目

P4127 [AHOI2009]同类分布（经典数位dp）

题目

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

$1 \le a \le b\le 10^{18}$

代码实现如下,细节都在注释里

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return x*f;
}
const int N=25,M=210;
int n,a[N],f[N][M][M],mod;
inline int F(int u,int sum,int st,bool lim)
{
	if(u>n&&sum==0) return 0;//模数为0是无意义的 
	if(u>n) return st==0&&sum==mod?1:0;//如果模数恰好为1,那么就是一个合法的解 
	if(!lim&&f[u][sum][st]!=-1) return f[u][sum][st];//记忆化搜索 
	int ret=0,res=lim?a[u]:9;//lim判断当前位是否能随便取 
	for(int i=0;i<=res;++i) 
		ret+=F(u+1,sum+i,(10*st+i)%mod,i==res&&lim); 
	return f[u][sum][st]=ret;
}
inline int solve(int x)
{
	n=0;
	while(x) a[++n]=x%10,x/=10;
	reverse(a+1,a+1+n);//从高位到低位枚举 
	int ret=0;
	for(mod=1;mod<=9*n;++mod)//枚举当前模数 
	{
		memset(f,-1,sizeof(f));
		ret+=F(1,0,0,1);
	}
	return ret;
}
int l,r;
signed main()
{
	l=read();r=read();
	printf("%lld\n",solve(r)-solve(l-1));
	return 0;
}

HDU 3709 Balanced Number（普通数位dp）

题目

求区间 $[L,R]$ 里面满足平衡数的数的个数,$1 \le L\le R\le 1\times 10^{18}$

平衡数定义：可以通过找一个平衡数位，该数位左边的数位乘以偏移距离的和等于右边的数位乘以偏移距离的和。

比如 $4139$ ，平衡数位为 $3$ ,$4\times 2+1=9$,因此该数是平衡数

题解

显然的是,每个数最多只能有一个平衡数位(毕竟没有物体是有两个重心的)

那么我们仿照上一题枚举模数的做法,这一题我们枚举平衡数位

假设我们将一个数的各位存到 $a$ 数组中,枚举到的平衡数位是 $k$ ,那么一个有 $\text{len}$ 位的数答案可以按照如下的方式统计

\[\text{nw}=\sum_{i=1}^{\text{len}} (i-k)\times a[i] \]

当 $i=\text{len}$ 且 $\text{nw}=0$ 的时候,就意味着当前数是平衡数位为 $k$ 的平衡数

通过上面的方式统计出答案即可

HDU 4507 吉哥系列故事——恨7不成妻（平方和的处理）

题目

如果一个数跟 $7$ 有关,那么我们就说它满足以下三条性质

整数中的某一位是 $7$
整数的每一位上的数加起来是 $7$ 的倍数
整数是 $7$ 的倍数

询问 $[L,R]$ 当中与 $7$ 无关的数的平方和 $1\le L\le R\le 1\times 10^{18}$

题解

首先可以通过所有的数的平方和减去与 $7$ 有关的数的平方和来得到答案

我们的状态按照下面的思路定义

整数中的某一位是 $7$ $\Rightarrow$ 一维状态 $a$ 表示是否有 $7$ 出现
整数的每一位上的数加起来是 $7$ 的倍数 $\Rightarrow$ 一维状态 $b$ 表示各数位的和模 $7$ 的值
整数是 $7$ 的倍数 $\Rightarrow$ 一维状态 $c$ 表示当前这个数模 $7$ 的值

于是我们就设出了状态 $f[u][a][b][c]$

如果是要求个数,那么这个问题与上面两个问题是没有区别的,可是这里是要我们求平方和

所以考虑一个我们在期望dp那里也用过的套路,为了转移,我们需要维护 $3$ 个值:

$\text{cnt}$ 表示与 $7$ 有关的数的个数
$\text{sum}$ 表示与 $7$ 有关的数的和
$\text{sqr}$ 表示与 $7$ 有关的数的平方和

考虑转移,假设我们记忆化搜索回溯上来的数为 $x$ ,当前是第 $u$ 位,上面的数为 $k$ 。那么我们知道,算上这一位后再回溯这个数就会变为 $x+k\times 10^{u-1}$,为了方便表示,我们设 $d=k\times 10^{u-1}$ ,考虑我们形成的新数 $x+d$ 与 $7$ 有关的数的平方和应该怎么计算

它的平方对答案的贡献为 $(x+d)^2=x^2+2dx+d^2$ ,考虑如何计算这个贡献和,假设有 $n$ 个合法的数分别为 $x_1,x_2,\cdots ,x_n$ ,那么对答案的贡献如下

\[\sum_{i=1}^n (x_i+d)^2=n\times d^2+2d\times (x_1+x_2+\cdots+x_n)+(x_1^2+x_2^2+\cdots+x_n^2) \]

假设我们当前状态是 $f$ ,回溯过来的状态是 $g$ ,那么转移方程如下

\[f.\text{cnt}\leftarrow g.\text{cnt} f.\text{sum}\leftarrow g.\text{sum}+d\times g.text{cnt} f.\text{sqr}\leftarrow g.\text{cnt}\times d^2+2d\times g.\text{sum}+g.\text{sqr} \]

这样就做完了