【数位DP】【P4127】[AHOI2009]同类分布

Description

给出两个数 \(a,~b\) 求出 \([a~,b]\) 中各位数字之和能整除原数的数的个数。

Limitations

\(1 \leq a,~b \leq 10^{18}\)

Solution

考虑数位DP。

设数字 \(A = \sum_{i = 0}^k a_i \times 10^i\)，其数字和 \(B = \sum_{i = 0}^k a_i\)

那么 \(A\) 满足条件即为 \(A \equiv 0 \pmod B\)，根据同余的性质，可以将求和符号拆开：

\[\sum_{i = 0}^k (a_i \times 10^i \bmod B)~\equiv~0\pmod B
\]

考虑 \(B\) 事实上很小，在 \(18\) 位数字都是 \(9\) 的时候也不超过 \(200\)，因此可以枚举 \(B\)。

设 \(f_{i, j, k}\) 位考虑前 \(i\) 位，前 \(i\) 位对应模 \(B\) 的值为 \(j\)，且后面几位的数字和为 \(k\)，不顶上界的方案数，转移时枚举当前这一位是几即可。

Code

// luogu-judger-enable-o2

#include <cstdio>

#include <cstring>

const int maxn = 70;

const int maxm = 163;

const int maxt = 10;

int A[maxn], B[maxn];

ll frog[maxn][maxm][maxm];

int ReadNum(int *p);

ll calc(const int *const num, const int n);

int main() {

  freopen("1.in", "r", stdin);

  int x = ReadNum(A), y = ReadNum(B);

  ll _sum = 0, _val = 0, _ten = 1;

  for (int i = x - 1; ~i; --i) {

    _sum += A[i]; _val += A[i] * _ten;

    _ten *= 10;

  }

  qw(calc(B, y) - calc(A, x) + (!(_val % _sum)), '\n', true);

  return 0;

}

int ReadNum(int *p) {

  auto beg = p;

  do *p = IPT::GetChar() - '0'; while ((*p < 0) || (*p > 9));

  do *(++p) = IPT::GetChar() - '0'; while ((*p <= 9) && (*p >= 0));

  return p - beg;

}

ll calc(const int *const num, const int n) {

  int dn = n - 1;

  if (n <= 1) { return num[0]; }

  ll _ret = 0, _ten = 1;

  for (int i = 1; i < n; ++i) _ten *= 10;

  for (int p = 1; p < maxm; ++p) {

    memset(frog, 0, sizeof frog);

    ll ten = _ten; int tm = ten % p;

    int upc = num[0] * tm % p, left = p - num[0];

    for (int i = 1; i < num[0]; ++i) if (p >= i) {

      frog[0][i * tm % p][p - i] = 1;

    }

    for (int i = 1; i < n; ++i) {

      int di = i - 1;

      tm = (ten /= 10) % p;

      for (int j = 0; j < p; ++j) {

        for (int k = 0; k < p; ++k) {

          for (int h = 0; h < 10; ++h) if ((h + k) <= p) {

            int dh = h * tm % p, dj = j >= dh ? j - dh : j - dh + p;

            frog[i][j][k] += frog[di][dj][k + h];

          }

        }

      }

      for (int j = 1; j < 10; ++j) if (j <= p) {

        ++frog[i][j * tm % p][p - j];

      }

      for (int h = 0; h < num[i]; ++h) if (h <= left) {

        int dh = h * tm % p;

        ++frog[i][(upc + dh) % p][left - h];

      }

      upc = (upc + num[i] * tm) % p; left -= num[i];

    }

    _ret += frog[dn][0][0];

    if ((upc == 0) && (left == 0)) ++_ret;

  }

  return _ret;

}

Summary

逐字符读入 \(L\) 时，\(L - 1\) 并不方便处理，不如改成 \([1, R] - [1,L] + (L\)是否合法\()\)。

巴特西