传送门

描述

由于科协里最近真的很流行数字游戏。

某人又命名了一种取模数，这种数字必须满足各位数字之和 mod N 为 0。

现在大家又要玩游戏了，指定一个整数闭区间 [a.b]，问这个区间内有多少个取模数。

输入格式

输入包含多组测试数据，每组数据占一行。

每组数据包含三个整数 a,b,N。

输出格式

对于每个测试数据输出一行结果，表示区间内各位数字和 mod N 为 0 的数的个数。

数据范围

$$\begin{gathered} 1\le a,b\le 2^{31}-1 \\ 1\le N<100 \end{gathered}$$

输入样例：

1 19 9

输出样例：

2

对于这道题，因为要求模数为0的情况，所以我们存的就是模数为0有多少种，但是模数为0是和前面所有数字都有关系的

所以我们把二维的含义设置为前面所有数字的和，这样就保证我们的记忆化是有效果的，具体还是看代码吧

#include<bits/stdc++.h>
#define int long long
using namespace std;
int digit[10],dp[32][110];
int a,b,p;
int dfs(int len,bool up,int sum) {
if(!len)	return sum%p==0?1:0;
if(!up&&dp[len][sum]!=-1)	return dp[len][sum];
int ret=0,upmax=up?digit[len]:9;
for(int i=0; i<=upmax; i++) {
ret+=dfs(len-1,i==upmax&&up,sum+i%p);
}
return up?ret:dp[len][sum]=ret;
}
int count(int x) {
int len=0;
while(x) {
digit[++len]=x%10;
x/=10;
}
return dfs(len,true,0);
}
signed main() {
while(cin>>a>>b>>p) {
memset(dp,-1,sizeof dp);
cout<<count(b)-count(a-1)<<'n';
}
return 0;
}

最后

以上就是喜悦小蝴蝶为你收集整理的1084. 数字游戏 II（数位dp）传送门的全部内容，希望文章能够帮你解决1084. 数字游戏 II（数位dp）传送门所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。