====== 动态规划 1 ======

===== 数位DP =====

====  算法简介 ====

一般用于处理形如区间 $[l,r]$ 中满足条件的数有几个之类问题。

==== 算法思想 ====

首先考虑将区间 $[l,r]$ 拆分成 $[0,r]-[0,l]$。

考虑记忆化搜索，一般搜索函数为 $f(pos,s,eq,zero)$。

其中 $pos$ 表示当前搜索位置，$s$ 表示前缀状态，$eq$ 表示前缀是否与查询上界相等，$zero$ 表示是否有前导零。

==== 算法练习 ====

=== 习题一 ===

[[https://www.luogu.com.cn/problem/P2657|洛谷p2657]]

== 题意 ==

询问区间 $[l,r]$ 中满足相邻数位之差至少为 $2$ 的数的个数。

== 题解 ==

搜索函数中 $s$ 记录前一位状态即可。

<hidden 查看代码>
<code cpp>
int a[10],dp[10][10];
int dfs(int pos,int pre,bool eq,bool zero){
	if(!pos)return 1;
	if(!eq&&~dp[pos][pre])return dp[pos][pre];
	int ans=0,v=eq?a[pos]:9;
	_rep(i,0,v){
		if(!zero&&abs(i-pre)<2)
		continue;
		ans+=dfs(pos-1,i,eq&&i==a[pos],zero&&i==0);
	}
	if(!eq&&!zero)dp[pos][pre]=ans;
	return ans;
}
int solve(int n){
	int len=0;
	mem(dp,-1);
	while(n){
		a[++len]=n%10;
		n/=10;
	}
	return dfs(len,0,true,true);
}
int main()
{
	int a=read_int(),b=read_int();
	printf("%d",solve(b)-solve(a-1));
	return 0;
}
</code>
</hidden>

=== 习题二 ===

[[https://www.luogu.com.cn/problem/P2602|洛谷p2602]]

== 题意 ==

询问区间 $[l,r]$ 所有整数中 $0\sim 9$ 分别出现的次数。

== 题解 ==

依次计算 $0\sim 9$ 出现次数。每次把搜索函数中的 $s$ 当成当前前缀的贡献即可。

<hidden 查看代码>
<code cpp>
const int MAXL=15;
LL a[MAXL],dp[MAXL][MAXL];
int goal;
LL dfs(int pos,int pre,bool eq,bool zero){
	if(!pos)return pre;
	if(!eq&&~dp[pos][pre])return dp[pos][pre];
	int v=eq?a[pos]:9;LL ans=0;
	_rep(i,0,v){
		if(zero&&i==0)
		ans+=dfs(pos-1,pre,eq&&i==a[pos],true);
		else
		ans+=dfs(pos-1,pre+(i==goal),eq&&i==a[pos],false);
	}
	if(!eq&&!zero)dp[pos][pre]=ans;
	return ans;
}
LL solve(LL n){
	int len=0;
	mem(dp,-1);
	while(n){
		a[++len]=n%10;
		n/=10;
	}
	return dfs(len,0,true,true);
}
int main()
{
	LL a=read_LL(),b=read_LL();
	_rep(i,0,9){
		goal=i;
		printf("%lld ",solve(b)-solve(a-1));
	}
	return 0;
}
</code>
</hidden>

=== 习题三 ===

[[https://www.luogu.com.cn/problem/P4127|洛谷p4127]]

== 题意 ==

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

== 题解 ==

发现在各位数字之和不确定情况下难以判定最后结果是否被各位数字之和相当困难。

于是考虑枚举所有可能的各位数字之和 $\text{Mod}$。于是 $\text{dp}$ 过程中维护一下前面数位之和以及前缀模 $\text{Mod}$ 的结果。

于是每次可能状态共有 $18\ast(18\ast 9)^2$ 个，最坏计算次数 $18\ast(18\ast 9)^3\approx 8\times 10^7$。

当然每次合法状态数不可能达到上界。另外可以考虑在 $\text{dp}$ 过程中适当剪枝。

<hidden 查看代码>
<code cpp>
const int MAXL=20,MAXV=180;
LL a[MAXL],dp[MAXL][MAXV][MAXV];
int Mod;
LL dfs(int pos,int s,int mod,bool eq){
	if(s>Mod||s+pos*9<Mod)return 0;
	if(!pos)return mod==0;
	if(!eq&&~dp[pos][s][mod])return dp[pos][s][mod];
	int v=eq?a[pos]:9;LL ans=0;
	_rep(i,0,v)
	ans+=dfs(pos-1,s+i,(mod*10+i)%Mod,eq&&i==a[pos]);
	if(!eq)dp[pos][s][mod]=ans;
	return ans;
}
LL solve(LL n){
	int len=0;
	while(n){
		a[++len]=n%10;
		n/=10;
	}
	LL ans=0;
	_rep(i,1,len*9){
		mem(dp,-1);
		Mod=i;
		ans+=dfs(len,0,0,true);
	}
	return ans;
}
int main()
{
	LL a=read_LL(),b=read_LL();
	printf("%lld",solve(b)-solve(a-1));
	return 0;
}
</code>
</hidden>


=== 习题四 ===

[[https://www.luogu.com.cn/problem/P3413|洛谷p3413]]

== 题意 ==

如果某个数字按 $10$ 进位制表示的字串中含有长度至少为 $2$ 的连续回文子串，则称该数为萌数。询问区间 $[l,r]$ 中萌数的个数。

数据范围 $1\le l\le r\lt 10^{1000}$，输出结果对 $10^9+7$ 取模。

== 题解 ==

回文串信息难以维护，考虑计算不含回文字串的数字个数。

发现长度不小于 $2$ 的回文串一定含长度为 $2$ 或 $3$ 的回文串。

于是一个数不含长度至少为 $2$ 的回文串等价于一个数不含长度为 $2$ 或 $3$ 的回文串。

于是只需要维护一个数的前面两位，保证当前位不与前两位相同即可。

<hidden 查看代码>
<code cpp>
const int MAXL=1e3+5,Mod=1e9+7;
int a[MAXL],dp[MAXL][11][11];
int dfs(int pos,int pre1,int pre2,bool eq){
	if(!pos)return 1;
	if(!eq&&~dp[pos][pre1][pre2])return dp[pos][pre1][pre2];
	int ans=0,v=eq?a[pos]:9;
	_rep(i,0,v){
		if(i==pre1||i==pre2)continue;
		ans=(ans+dfs(pos-1,(i==0&&pre1==10)?10:i,pre1,eq&&i==a[pos]))%Mod;
	}
	if(!eq)dp[pos][pre1][pre2]=ans;
	return ans;
}
int solver(char *s){
	int len=strlen(s);
	_rep(i,1,len)
	a[i]=s[len-i]-'0';
	mem(dp,-1);
	return dfs(len,10,10,true);
}
char b[MAXL],c[MAXL];
int main()
{
	scanf("%s %s",b,c);
	LL ans=solver(c)-solver(b);
	int len_b=strlen(b),len_c=strlen(c),flag=1;
	_for(i,0,len_b){
		if(i+1<len_b&&b[i]==b[i+1]){
			flag=0;
			break;
		}
		if(i+2<len_b&&b[i]==b[i+2]){
			flag=0;
			break;
		}
	}
	ans+=flag;
	LL tot_b=0,tot_c=0;
	_for(i,0,len_b)tot_b=(tot_b*10+b[i]-'0')%Mod;
	_for(i,0,len_c)tot_c=(tot_c*10+c[i]-'0')%Mod;
	enter(((tot_c-tot_b+1-ans)%Mod+Mod)%Mod);
	return 0;
}
</code>
</hidden>

=== 习题五 ===

[[https://ac.nowcoder.com/acm/contest/5671/H|牛客暑期多校(第六场) H 题]]

== 题意 ==

求 $0\le A\le B\le N$ ,满足 $S(A)\gt S(B)$ 的 $(A,B)$ 个数，其中 $S(n)$ 代表 $n$ 的数码和。

== 题解 ==

搜索函数为 $f(pos,d,eq1,eq2)$。其中 $d$ 表示 $S(B)-S(A)$，$eq1$ 表示 $B$ 前缀是否与查询上界相等，$eq2$ 表示 $A$ 前缀是否与 $B$ 前缀相等。

接下来同时枚举 $B,A$ 在 $pos$ 位的数值即可，合法状态共 $O(18L^2)$ 个，每个状态递推时间复杂度 $O(100)$。

于是总时间复杂度 $O(1800L^2)$，其中 $L$ 表示 $N$ 的长度。需要注意搜索过程中需要对 $eq1,eq2$ 进行记忆化。

单个数搜索时不需要对 $eq$ 进行记忆化是因为单个数搜索时从 $eq=true$ 的状态只能走到下一个 $eq=true$ 的状态。

而两个数搜索时，从 $eq1=true,eq2=false$ 的状态可以走到 $10$ 个 $eq1=true,eq2=false$ 的状态。

所以存在某些 $eq1=true,eq2=false$ 的状态会被重复访问的可能，对 $eq1=false,eq2=true$ 的情况类似。

<hidden 查看代码>
<code cpp>
const int MAXL=105,MAXV=905,Mod=1e9+7;
int a[MAXL],dp[MAXL][MAXV<<1][2][2];
int dfs(int pos,int d,bool eq1,bool eq2){
	if(d>=MAXV+pos*9)return 0;
	if(!pos)return 1;
	if(~dp[pos][d][eq1][eq2])
	return dp[pos][d][eq1][eq2];
	int ans=0,v1=eq1?a[pos]:9,v2;
	_rep(i,0,v1){
		v2=eq2?i:9;
		_rep(j,0,v2)
		ans=(ans+dfs(pos-1,d+i-j,eq1&&i==v1,eq2&&j==v2))%Mod;
	}
	return dp[pos][d][eq1][eq2]=ans;
}
int solve(char *s){
	int len=strlen(s);
	mem(dp,-1);
	_rep(i,1,len)
	a[i]=s[len-i]-'0';
	return dfs(len,MAXV,true,true);
}
char buf[MAXL];
int main()
{
	scanf("%s",buf);
	enter(solve(buf));
	return 0;
}
</code>
</hidden>

=== 习题六 ===

[[https://cometoj.com/contest/71/problem/D?problem_id=4019|Comet OJ-Contest #12 D题]]

== 题意 ==

求满足 $0\le x\le A,0\le y\le B,x\oplus y=n,|x-y|\le m$ 的 $(x,y)$ 个数。

== 题解 ==

不难想到按二进制 $\text{dp}$。但 $|x-y|$ 在 $\text{dp}$ 过程中可能上升，也可能下降，不方便处理。

故不妨假设初始时 $x=0,y=n$，然后若 $n$ 的第 $i$ 位等于 $1$ 且将 $1$ 交给 $x$，则 $x-y$ 增加 $2^{i+1}$。这样可以保证 $x-y$ 在 $\text{dp}$ 过程中单增。

$|x-y|\le m$ 等价于增量 $n-m\le d\le n+m$，考虑计算出 $d\le n+m$ 的值减去 $d\le n-m-1$ 的值即可。

另外注意 $n-m\le 0$ 的情况需要特判防止 $\text{dp}$ 出错，由于 $|x-y|\le n$ 必成立，所以结果为 $0$。

搜索函数为 $f(pos,eq1,eq2,eq3)$。其中 $eq1$ 表示 $x$ 前缀是否与 $A$ 前缀相等，$eq2$ 表示 $y$ 前缀是否与 $B$ 前缀相等。

$eq3$ 表示 $d$ 前缀是否与上界相等，然后枚举每一位可能，使其满足约束 $x\oplus y=n$，直接转移即可。

<hidden 查看代码>
<code cpp>
const int MAXL=64;
int A[MAXL],B[MAXL],N[MAXL],M[MAXL];
LL dp[MAXL][2][2][2];
void cal(LL x,int *X){
	_for(i,1,MAXL)
	X[i]=0;
	int pos=0;
	while(x){
		X[++pos]=x&1;
		x>>=1;
	}
}
LL dfs(int pos,bool eq1,bool eq2,bool eq3){
	if(!pos)return 1;
	if(~dp[pos][eq1][eq2][eq3])return dp[pos][eq1][eq2][eq3];
	LL ans=0;
	_for(i,0,2){
		int x=i,y=i^N[pos];
		if((eq1&&x>A[pos])||(eq2&&y>B[pos])||(eq3&&((x>y)>M[pos+1])))
		continue;
		ans+=dfs(pos-1,eq1&&x==A[pos],eq2&&y==B[pos],eq3&&(x>y)==M[pos+1]);
	}
	return dp[pos][eq1][eq2][eq3]=ans;
}
LL solve(LL m){
	mem(dp,-1);
	cal(m,M);
	return dfs(62,true,true,true);
}
int main()
{
	int T=read_int();
	while(T--){
		LL a=read_LL(),b=read_LL(),n=read_LL(),m=read_LL();
		cal(a,A);
		cal(b,B);
		cal(n,N);
		enter(solve(n+m)-((n-m>0)?solve(n-m-1):0));
	}
	return 0;
}
</code>
</hidden>

=== 习题七 ===

[[https://www.luogu.com.cn/problem/CF908G|CF908G]]

== 题意 ==

定义 $S(x)$ 表示将 $x$ 的每个位从小到大重排后的值，例如 $S(3190)=0139,S(4312)=1234$。

给定 $1\le X\le 10^{700}$，求

$$
\sum_{i=1}^X S(i)
$$

== 题解 ==

考虑按贡献计算，设 $f(i,j)$ 表示 $1\sim X$ 中满足 $S(x)$ 的第 $j$ 位等于 $i$ 的 $x$ 的个数，$n=\text{len}(X)$，于是

$$
ans=\sum_{i=1}^9i\sum_{j=1}^n f(i,j)10^{j-1}=\sum_{i=1}^{9}i\sum_{j=1}^n (g(i,j)-g(i+1,j))10^{j-1}
$$

其中 $g(i,j)=\sum_{k=i}^9f(i,k)$ 表示 $1\sim X$ 中满足 $S(x)$ 的第 $j$ 位大于等于 $i$ 的 $x$ 的个数。

不难发现 $g(i,j)$ 也等于 $1\sim X$ 中满足 $x$ 中至少有 $j$ 位大于等于 $i$ 的 $x$ 的个数，于是

$$
g(i,j)=\sum_{k=j}^n \text{dp}(i,k)
$$

其中 $\text{dp}(i,j)$ 表示 $1\sim X$ 中满足 $x$ 中有 $j$ 位大于等于 $i$ 的 $x$ 的个数，显然该值通过数位 $\text{DP}$ 即可计算。

时间复杂度 $O(100n^2)$。

<hidden 查看代码>
<code cpp>
const int MAXL=705,Mod=1e9+7;
char s[MAXL];
int a[MAXL],dp[10][MAXL][MAXL][2],suf[11][MAXL];
int dfs(int v,int pos,int cnt,bool eq){
	if(!pos||cnt<0)return cnt==0;
	if(~dp[v][pos][cnt][eq])return dp[v][pos][cnt][eq];
	int ans=0,mv=eq?a[pos]:9;
	_rep(i,0,mv)
	ans=(ans+dfs(v,pos-1,cnt-(i>=v),eq&&(a[pos]==i)))%Mod;
	return dp[v][pos][cnt][eq]=ans;
}
int main()
{
	mem(dp,-1);
	scanf("%s",s+1);
	int len=strlen(s+1);
	for(int i=1,j=len;i<=len;i++,j--)a[i]=s[j]-'0';
	int ans=0;
	_for(i,1,10)for(int j=len;j>=1;j--)
	suf[i][j]=(suf[i][j+1]+dfs(i,len,j,true))%Mod;
	_for(i,1,10){
		int p=1;
		_rep(j,1,len){
			ans=(ans+1LL*i*p%Mod*(suf[i][j]-suf[i+1][j]+Mod)%Mod)%Mod;
			p=10LL*p%Mod;
		}
	}
	enter(ans);
	return 0;
}
</code>
</hidden>