移动手机网站建设,如何做网站地图视频,互联网行业 英文,昭通市有做网站的吗[一本通提高数位动态规划]数字游戏#xff1a;取模数题解 1前言2问题3状态的设置4数位dp-part1预处理5数位dp-part2利用状态求解6代码7后记 1前言
本文为数字游戏#xff1a;取模数的题解 需要读者对数位dp有基础的了解#xff0c;建议先阅读 论数位dp–胎教级教学 B3883 [… [一本通提高数位动态规划]数字游戏取模数题解 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(1a,b231,1n100)。 输出格式 每个测试用例输出一行表示各位数字和 m o d N mod N modN为 0 0 0 的数的个数。 看这个 a , b a,b a,b的范围直接可以确定是数位dp但是该怎么dp
3状态的设置
我们发现假设现在 n 9 n 9 n9那么我们在一个取模数的最高位前面加上一位 9 9 9这个数依旧是取模数 在一个各位数字和 m o d 9 1 mod 9 1 mod91的情况下在最前面插入一个 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 modnk的数的个数 属性显然为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 i1的情况下如果 k j m o d n k j mod n kjmodn 则 d p i , j , k 1 dp_{i,j,k} 1 dpi,j,k1否则 d p i , j , k 0 dp_{i,j,k} 0 dpi,j,k0 接下来就可以枚举 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,kdpi,j,kdpi−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)modnn) mod n ((k−j)modnn)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 0j1 0j1 普遍的此处的 0 j s i 0js_{i} 0jsi 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
#includebits/stdc.h
using namespace std;
long long a,b,n;
long long dp[20][20][200];
int mods(int x){return (x%nn)%n;
}
void init(){memset(dp,0,sizeof(dp));for(int i 0;i9;i){dp[1][i][i%n];}for(int i 2;i12;i){for(int j 0;j9;j){for(int k 0;kn;k){for(int l 0;l9;l){dp[i][j][k]dp[i-1][l][mods(k-j)];}}}}
}
int solve(int x){if(x0){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;i1;i--){for(int j 0;js[i];j){ansdp[i][j][mods(n-res)];}ress[i];res%n;if(i1res%n0){ans;}}return ans;
}
int main(){while(cinabn){init();int ans solve(b)-solve(a-1);coutansendl;}return 0;
}
7后记
本题很好地展现了数位dp的精髓 预处理部分情况分解子问题特判 本文作者是蒟蒻如有错误请各位神犇指点 森林古猿出品必属精品请认准CSDN森林古猿1
