DP雑記③

桁DPの基本形

auto digit = [](long long n, int x) {
  while (x - 1) n /= 10, x--;
  return n % 10;
};

dp[0][0][0] = 1;
rep(i, 20) rep(j, 2) rep(k, 2) rep(d, 10) {
  if (j == 0 && d > digit(N, 20 - i)) continue;

  int _i = i + 1;
  int _j = j == 0 && d == digit(N, 20 - i) ? 0 : 1;
  int _k = k == 0 && d == 0 ? 0 : 1;

  dp[_i][_j][_k] += dp[i][j][k];
}

様々な問題

問題

1以上N未満の整数のうち、12345で割り切れる整数はいくつあるか。

解答

0～12344の12345個の状態を持つDPを定義する。遷移前の状態をl、遷移後の状態を_kとおくと、遷移は_k = (l * 10 + d) % 12345となる。これをコードで書くと次のようになる。

rep(l, 12345) rep(d, 10) {
  int _l = (l * 10 + d) % 12345;
  dp[_l] += dp[l];
}

桁DPの基本形のコードとマージすれば完成。digit()の定義は省略。

dp[0][0][0][0] = 1;
rep(i, 20) rep(j, 2) rep(k, 2) rep(l, 12345) rep(d, 10) {
  if (j == 0 && d > digit(N, 20 - i)) continue;

  int _i = i + 1;
  int _j = j == 0 && d == digit(N, 20 - i) ? 0 : 1;
  int _k = k == 0 && d == 0 ? 0 : 1;
  int _l = (l * 10 + d) % 12345;

  dp[_i][_j][_k][_l] += dp[i][j][k][l];
}

long long ans = dp[20][1][1][0];
cout << ans << endl;

N = 10^18のときは81004455245038個ある。

問題

1以上N未満の整数のうち、すべての数字の出現回数が偶数のものはいくつあるか。

解答

偶奇のみが重要。各数字は偶数と奇数の2つの状態を持つので、合計2¹⁰の状態を持つ。よって2¹⁰の状態を持つDPを定義する。遷移前の状態をl、遷移後の状態を_lとおいたとき、遷移は_l = _k == 1 ? l ^ (1 << d) : lとなる。これをコードで表すと次のようになる。

rep(l, 1 << 10) rep(d, 10) {
  int _l = _k == 1 ? l ^ (1 << d) : 0;
  dp[_l] += dp[l];
}

このコードと桁DPのコードをマージすれば完成。

N 10^18のときは2105532412794693個ある。

問題

1以上N未満の整数のうち、3の出現回数が全体の2/3以上のものはいくつあるか。

解答

2つの状態が必要。ひとつは桁数、もうひとつは3の出現回数。桁数をl、3の出現回数をmとおくと、遷移は_l = _k == 1 ? l + 1 : l、_m = d == 3 ? m + 1 : mとなる。答えはl * 2 <= m * 3を満たすdp[20][1][1][l][m]の和である。

N = 10^18のときは10835627321個ある。