如何用dedecms做网站,a5站长网网站交易,营销方案推广,深圳单位名称和单位地址把数位dp写成记忆化搜索的形式#xff0c;方法很赞#xff0c;代码量少了很多。 下面为转载内容#xff1a; a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. 问一个区间内[l,r]有多少个Beautiful数字 范围9*…把数位dp写成记忆化搜索的形式方法很赞代码量少了很多。 下面为转载内容 a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. 问一个区间内[l,r]有多少个Beautiful数字 范围9*10^18 数位统计问题构造状态也挺难的我想不出我的思维局限在用递推去初始化状态而这里的状态定义也比较难 跟pre的具体数字有关 问了NotOnlySuccess的豁然开朗 Orz 一个数字要被它的所有非零位整除即被他们的LCM整除可以存已有数字的Mask但更好的方法是存它们的LCM{digit[i]} int MOD LCM{1,2,9} 5 * 7 * 8 * 9 2520 按照定义数字x为Beautiful x % LCM{digit[xi]} 0 即 x % MOD % LCM{digit[xi]} 0 所以可以只需存x % MOD范围缩小了 而在逐位统计时假设到了pre***pre指前面的一段已知的数字而*是任意变 ( preSum * 10^pos next ) % MOD % LCM(preLcm , nextLcm) ( preSum * 10 ^ pos % MOD next % MOD ) % LCM(preLcm , nextLcm) 0 而nextnextLcm是变量上面的比较式的意义就是 在已知pos , preSum , preLcm情况下有多少种(next,nextLcm)满足式子为0 而这个就是一个重复子问题所在的地方了需要记录下来用记忆化搜索 dfs(pos , preSum , preLcm , doing) 加一个标记为doing表示目前是在计算给定数字的上限还是没有上限即***类型的 这样就将初始化以及逐位统计写在一个dfs了好神奇 还有一点10以内的数字情况为2^3 , 3^2 , 5 , 7 所以最小公倍数组合的情况只有4*3*2*2 48 可以存起来我看NotOnlySuccess的写法是 for(int i 1 ; i MOD ; i ) { if(MOD % i 0) index[i] num; } 很棒 所以复杂度大概为19*2520*48*10状态数*决策数 我觉得这题状态的设计不能跟具体数字分开否则会很难设计吧 所以用记忆化搜索存起来 用具体数字去计算重复的子问题跟pre关系比较密切 有一个比较重要的切入点就是LCM还有%MOD缩小范围才能存储 还有优化到只需%252的更快 不过我觉得%2520比较好理解 代码 1 const int MOD 2520;2 3 LL dp[21][MOD][50];4 int digit[21];5 int indx[MOD5];6 7 void init() {8 int num 0;9 for(int i 1; i MOD; i) {
10 if(MOD%i 0) indx[i] num;
11 }
12 CL(dp, -1);
13 }
14
15 LL gcd(LL a, LL b) {
16 return b 0 ? a : gcd(b, a%b);
17 }
18
19 LL lcm(LL a, LL b) {
20 return a/gcd(a, b)*b;
21 }
22
23 LL dfs(int pos, int presum, int prelcm, bool edge) {
24 if(pos -1) return presum%prelcm 0;
25 if(!edge dp[pos][presum][indx[prelcm]] ! -1)
26 return dp[pos][presum][indx[prelcm]];
27 int ed edge ? digit[pos] : 9;
28 LL ans 0;
29 for(int i 0; i ed; i) {
30 int nowlcm prelcm;
31 int nowsum (presum*10 i)%MOD;
32 if(i) nowlcm lcm(prelcm, i);
33 ans dfs(pos - 1, nowsum, nowlcm, edge i ed);
34 }
35 if(!edge) dp[pos][presum][indx[prelcm]] ans;
36 return ans;
37 }
38
39 LL cal(LL x) {
40 CL(digit, 0);
41 int pos 0;
42 while(x) {
43 digit[pos] x%10;
44 x / 10;
45 }
46 return dfs(pos - 1, 0, 1, 1);
47 }
48
49 int main() {
50 //Read();
51
52 init();
53 int T;
54 LL a, b;
55 cin T;
56 while(T--) {
57 cin a b;
58 cout cal(b) - cal(a - 1) endl;
59 }
60 return 0;
61 }
