AT681 【数】 题解

【\(description\)】

给定两个数 \(d\) , \(N\) ，求从 \(1\) ~ \(N\) 中有多少个数各个数位上的数码和是 \(d\) 的倍数，答案对 \(10 ^ 9 + 7\) 取模。

\(1 \leq N \leq 10 ^ {10000}\)

【\(solution\)】

这是一篇使用记忆化搜索来实现求解的题解。(记搜多么省事啊，背过模板就好了)

对于一个长度为 \(cnt\) 的数字，我们可以从高位向低位枚举数字，统计字符相加 \(\bmod \ \ d\) 的值。

• 我们枚举的位数是必须要记录的。 \((id)\)
• 其次，我们还要记录各个数位上的数 \(\bmod \ \ d\) 的值。 \((last)\)
• 还要记录是否上一位是否到达了边界。 \((limit)\)
• 记录是否有前导零。 \((zero)\)

上面四个参数就是我在记忆化搜索中用到的变量。

所以设 \(f[i][j][k][p]\) 为到达第 \(i\) 个数位，\(\bmod \ \ d\) 的余数为 \(j\) ，\(k\) 为是否到达上界（是则为 \(\text{true}\)，否则为 \(\text{false}\)）， \(p\) 为是否含有前导零（是则为 \(\text{true}\)，否则为 \(\text{false}\)）。

此外还要注意 \(N\) 很大，要用字符串读入，再转化为数组来储存，储存时要倒序储存。

最后献上主要代码。

【\(Code\)】

LL Dfs(int id,int last,int limit,int zero)
// 代表 进行到第几位，上一个数字，是否到边界，是否有前导 0
{
  if(!id) return !last ? 1 : 0;
  //当搜索完了最后一位，看看余数是否为 0 ， 为 0 则说明能够整除，答案 + 1;
  if(~f[id][last][limit][zero] && !limit && !zero) return (f[id][last][limit][zero] + mod) % mod;
  // 记忆化过程，如果以前已经搜到了这个位置，并且没有前导零，没到边界就可以返回，已经搜到的答案。
  int up = limit ? a[id] : 9;
   //从高位向低位枚举，所以如果之前一位的数码和最大的数码相同，这一位就只能从 0 枚举到 a[id]，防止越界。
    //否则如果之前一位比最大数的数码小，那这一位就可以从 0 ~ 9 枚举了，这样肯定不会越界。
  LL ans = 0;//统计答案
  for(int i = 0;i <= up;i ++) {
    int h = (last + i) % d;//计算各个数位上的和。
    if(zero && (i == 0)) ans += (Dfs(id - 1,h,limit && (i == up),1) + mod) % mod;
    // 当有前导 0 的时候分开来计算。
    else ans += (Dfs(id - 1,h,limit && (i == up),0) + mod) % mod;
  }
  if(!limit && !zero) f[id][last][limit][zero] = (ans + mod) % mod;
  //如果没到边界并且没有前导零，就可以记忆化。
  return (ans + mod) % mod;
  //别忘取模
}

AT681 【数】 题解

原文：https://www.cnblogs.com/Ti-despair/p/14472408.html