把数位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 而next,nextLcm是变量,上面的比较式的意义就是 在已知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[MOD+5]; 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 }