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

1前言

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

2问题

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

3状态的设置

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

4数位dp-part1预处理

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

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

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

6代码

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

#include<bits/stdc++.h>
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<n;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<s[i];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<<ans<<endl;}return 0;
}

7后记

本题很好地展现了数位dp的精髓
预处理部分情况+分解子问题+特判
本文作者是蒟蒻，如有错误请各位神犇指点
森林古猿出品，必属精品，请认准CSDN森林古猿1！