EDCP-S「Digit Sum」 #C++

EDCP-S「Digit Sum」

解法

状態を考えるとdp[i桁目][未満フラグ][i桁目のmod Dを取った値]になる。これは桁DP知らないと思いつけないと思う。i桁目と未満フラグは桁DPのお決まり。そのあとは、桁DPの条件を書いていくのが定石になってる。
今回の条件は各桁の総和がDの倍数であること。この状態を保持するのは一見難しく感じる。
でも、(a + b + c) % mod = (a % mod) + (b % mod) + (c % mod)なので、各桁ごとにDのmodを取った総和を求めればいい。その結果が0になったら各桁の総和がDの倍数ということになる。
状態の持ち方がわかったので次は遷移を考える
頑張って遷移を考えるとこんな感じになる。僕は10分くらい考えないとできない。
dp[i][smaller][modD] → dp[i+1][smaller || その桁の未満フラグ][(modD + その桁) % D]
あとは実装するだけ（だけってこともないけど。割とめんどいので）
計算量は多分$O(|K| *D)$。$|K|$はKの桁数ね。メモ化再帰の計算量よくわかんねえ。

コード

メモ化再帰

メモ化再帰で書くとこんな感じ
rec(0, 0, 0)について、第1引数が0なのは文字列の最初のインデックスが0だから。第2引数が0なのは、最上位桁の上限値はその桁以下じゃないといけないから（これは再帰の中身見ればわかる。limの部分）。
modめんどいから別に関数作った。

#include <bits/stdc++.h>
using namespace std;

#define int long long

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

// ------------------------------------------------------------------------------------------

string K;
int D;
int dp[11111][2][111]; // dp[i桁目][未満フラグ][mod Dした値] = 総数

int rec(int digit, int smaller, int modD) {
  // 桁を超えたら終了
  if (digit >= K.size()) {
    return modD == 0;
  }

  // メモした値なら返す
  if (dp[digit][smaller][modD] != -1) {
    return dp[digit][smaller][modD];
  }

  int lim = (smaller ? 9 : K[digit] - '0'); // 上限値
  int ret = 0;
  for (int num = 0; num <= lim; num++) {
    int t = rec(digit + 1, smaller || (num < lim), (modD + num) % D);
    Add(ret, t);
  }

  return dp[digit][smaller][modD] = ret; // ここでメモ
}

signed main() {
  cin >> K >> D;

  // DPテーブルを初期化
  for (int i = 0; i < 11111; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 111; k++) {
        dp[i][j][k] = -1;
      }
    }
  }

  int ans = rec(0, 0, 0); // メモ化再帰に投げる
  Add(ans, -1LL); // 0になる場合の数を引く
  cout << ans << endl;

  return 0;
}

ループDP

これだけループ重ねるとわけわからんくなる。頭では追えない。頑張って遷移を考えてそれをコードに落とし込んだだけって感じ。
未満フラグが1→0になる遷移は存在しないので、それは弾く（この処理なくてもACなんだけどよくわからん。でもやるに越したことはないと思う）。

#include <bits/stdc++.h>
using namespace std;

#define int long long

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

// ------------------------------------------------------------------------------------------

string K;
int D;
int dp[11111][2][111]; // dp[i桁目][未満フラグ][mod Dした値] = 総数

signed main() {
  cin >> K >> D;

  dp[0][0][0] = 1; // 初期化
  // DP
  for (int digit = 0; digit < K.size(); digit++) {
    for (int smaller : {0, 1}) {
      for (int modD = 0; modD < D; modD++) {
        int lim = (smaller ? 9 : K[digit] - '0');
        for (int num = 0; num <= lim; num++) {
          int nSmaller = smaller || (num < lim);
          if (smaller == 1 && nSmaller == 0) continue;
          Add(dp[digit+1][nSmaller][(modD + num) % D], dp[digit][smaller][modD]);
        }
      }
    }
  }

  int ans = 0;
  for (int smaller : {0, 1}) {
    Add(ans, dp[K.size()][smaller][0]);
  }

  Add(ans, -1LL); // 0になる場合の数を引く
  cout << ans << endl;

  return 0;
}

メモ

負のMODがだるかった。言語によって仕様違うみたい。確認してないけど。
ループでDP書くと更新順序バグってないか心配になる。てんぷらさんとかは再帰で書いた方が直感的に書けるって言ってたから僕も書いてみた。悪くない