[一本通提高数位动态规划]数字游戏：取模数题解

• • 1前言
  • 2问题
  • 3状态的设置
  • 4数位dp-part1预处理
  • 5数位dp-part2利用状态求解
  • 6代码
  • 7后记

1前言

本文为数字游戏：取模数的题解
需要读者对数位dp有基础的了解，建议先阅读
论数位dp–胎教级教学
B3883 [信息与未来 2015] 求回文数 数位dp题解
论进制类型的数位dp:胎教级教学

2问题

题目描述
定义一种取模数，满足各位数字之和 m o d N mod N modN为 0 0 0，指定一个整数闭区间 [ a , b ] [a,b] [a,b]，问这个区间内有多少个取模数。
输入格式
题目有多组测试数据。每组只含 3 3 3个数字 a , b , N ( 1 < = a , b < = 2 31 , 1 < = n < 100 ) a, b, N (1 <= a, b <= 2^{31},1 <= n < 100) a,b,N(1<=a,b<=231,1<=n<100)。
输出格式
每个测试用例输出一行，表示各位数字和 m o d N mod N modN为 0 0 0 的数的个数。
看这个 a , b a,b a,b的范围，直接可以确定是数位dp，但是该怎么dp？

3状态的设置

我们发现，假设现在 n = 9 n = 9 n=9，那么我们在一个取模数的最高位前面加上一位 9 9 9，这个数依旧是取模数
在一个各位数字和 m o d 9 = 1 mod 9 = 1 mod9=1的情况下，在最前面插入一个 8 8 8，也产生了取模数
我们可以把不同位数的的取模数个数看成子问题，子问题可以转化为更大的问题（方式如上），这就满足的dp的条件
有了子问题和可转移的性质，我们可以设 d p i , j , k dp_{i,j,k} dpi,j,k​为 i i i位 j j j开头，
各位之和 m o d n = k mod n = k modn=k的数的个数
属性显然为COUNT（加上子问题得到当前状态）

4数位dp-part1预处理

在 n n n固定的情况下， d p dp dp数组也是固定的，与 a , b a,b a,b无关
所以我们可以预处理 d p dp dp
首先，对于所有 d p i , j , k dp_{i,j,k} dpi,j,k​， i = 1 i = 1 i=1的情况下，如果 k = j m o d n k = j mod n k=jmodn
则 d p i , j , k = 1 dp_{i,j,k} = 1 dpi,j,k​=1，否则 d p i , j , k = 0 dp_{i,j,k} = 0 dpi,j,k​=0
接下来就可以枚举 i , j , k i,j,k i,j,k，此外再枚举 l l l为上一位数字的情况
利用模运算转移，得状态转移方程
d p i , j , k = d p i , j , k + d p i − 1 , l , m o d s ( k − j ) dp_{i,j,k} =dp_{i,j,k}+dp_{i-1,l,mods(k-j)} dpi,j,k​=dpi,j,k​+dpi−1,l,mods(k−j)​
其中 m o d s ( k − j ) mods(k-j) mods(k−j)等价于 ( ( k − j ) m o d n + n ) m o d n ((k-j)modn+n) mod n ((k−j)modn+n)modn，这样可以防止出现负数

5数位dp-part2利用状态求解

我们首先考虑一个数 23456 23456 23456
可以将其分解为 0 − 19999 0-19999 0−19999和 20000 − 23456 20000-23456 20000−23456两个区间
0 − 19999 0-19999 0−19999我们预处理过了，方案数等于
∑ d p 5 , j , 0 \sum dp_{5,j,0} ∑dp5,j,0​对于此处情况 0 < = j < = 1 0<=j<=1 0<=j<=1
普遍的，此处的 0 < = j < = s i 0<=j<=s_{i} 0<=j<=si​， s i s_{i} si​为原数 i i i位
然后呢，我们可以把 3456 3456 3456看做子问题
第一位必然为 2 2 2，不为 2 2 2的情况已经得出
这样的话我们就可以打个标记，将已经固定的位数求和
但是我们这样一直缩小问题规模，会产生一个问题，会忽略边界值
这个也好办，我们特判最后标记变量如果被 n n n整除，就可以取到边界，答案 + 1 +1 +1
算法完成了，但是看到这的你可能会有一些问题，我来解答
1.为什么不处理前导 0 0 0
答：前导 0 0 0是合法的，因为处理方式是加和，所以 0 0 0相当于空位
2.如果左边界为 1 1 1怎么办， 1 − 1 1-1 1−1之后传到函数里的参数为 0 0 0
答：特判， 0 0 0本身合法，返回 1 1 1

6代码

有了如上思想，你就可以写出代码
附作者的代码（c++）

#include using namespace std; long long a,b,n; long long dp[20][20][200]; int mods(int x){ 	return (x%n+n)%n; } void init(){ 	memset(dp,0,sizeof(dp)); 	for(int i = 0;i<=9;i++){ 		dp[1][i][i%n]++; 	} 	for(int i = 2;i<=12;i++){ 		for(int j = 0;j<=9;j++){ 			for(int k = 0;k 				for(int l = 0;l<=9;l++){ 					dp[i][j][k]+=dp[i-1][l][mods(k-j)]; 				} 			} 		} 	} } int solve(int x){ 	if(x==0){ 		return 1; 	} 	int h = x,s[1145],idx = 0,ans = 0,res = 0; 	while(h){ 		s[++idx] = h%10; 		h/=10; 	} 	for(int i = idx;i>=1;i--){ 		for(int j = 0;j 			ans+=dp[i][j][mods(n-res)]; 		} 		res+=s[i]; 		res%=n; 		if(i==1&&res%n==0){ 			ans++; 		} 	} 	return ans; } int main(){ 	while(cin>>a>>b>>n){ 		init(); 		int ans = solve(b)-solve(a-1); 		cout<