Codeforces 55D Beautiful Number （数位统计）

左手的ㄟ右手 2022-08-09 12:54 143阅读 0赞

把数位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,![Codeforces 55D Beautiful Number （数位统计） - AcBoy - AcBoy的博客][Codeforces 55D Beautiful Number _ - AcBoy - AcBoy]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 }

[Codeforces 55D Beautiful Number _ - AcBoy - AcBoy]: /images/20220731/57f539658aa7431b88dd5498ba87867d.png