公開日 :
更新日 :
「\(N\) 以下の整数のうち、条件を満たすものの個数」を、上の桁から \(1\) 桁ずつ数字を決めながら数えるDP。
\(N\) が \(10^{500}\) のように巨大でも、計算量は「桁数 × 状態数 × \(10\)」 で済む。
上の桁から数字を決めていくとき、作っている数は2種類に分かれる。
| 意味 | 次の桁に置ける数字 | |
| tight(t=1) | ここまで N とまったく同じ数字を並べている | \(0 \sim N\) のその桁まで |
| 確定済み(t = 0) | どこかで N より小さい数字を置いた | \(0 \sim 9\) 何でもいい |
例 : \(N=1013\) で \(10\) まで来た(tight)。次の桁に置けるのは \(0\) か \(1\)。
| 決めること | 例 |
| 1. 最後に判定するために何を覚えていくか(状態) | 桁和 mod 3、使った数字の集合(ビットマスク) |
| 2. 数字 c を置いたとき、状態がどう変わるか | r → (r + c) % 3、 m → m | 1<<c |
| 3. 最後に、どの状態を答えに数えるか | 3 つの条件のうち満たす数がちょうど 1 |
1.の状態はできるだけ小さくする。
「数そのもの」は覚えられない(大きすぎる)ので、判定に必要な情報だけに絞る。
| 条件 | 覚えるもの | 大きさ |
| D の倍数 / 桁和が D の倍数 | 数 mod D / 桁和 mod D | D |
| 数字 3 を含む | 含んだかどうか | 2 |
| 使う数字の種類 | 使った数字の集合(ビットマップ) | 1024 |
| 0 でない数字の個数が K 個 | 個数(K を超えたらまとめる) | K + 2 |
| 隣の桁と違う | 直前の数字 | 10 |
string N; cin >> N;
// dp[t][s] : t = tight か、s = 状態
vector dp(2, vector<mint>(S));
dp[1][初期状態] = 1; // 何も置いていない数は N をなぞっている
rep(i, (int)N.size()) {
int d = N[i] - '0'; // ← '-' であって '=' ではない!
vector ndp(2, vector<mint>(S));
rep(t, 2) rep(s, S) {
if (dp[t][s] == 0) continue;
int lim = t ? d : 9; // tight なら N の桁まで
for (int c = 0; c <= lim; c++) {
int nt = (t && c == lim); // N の桁と同じ数字なら tight のまま
ndp[nt][次の状態(s, c)] += dp[t][s];
}
}
swap(dp, ndp);
}
// 答え = dp[0][OK な状態] + dp[1][OK な状態] (dp[1] は N 自身)N = 1013 のとき、「45」は「0045」として数えられている。
桁和や「mod D」なら先頭の 0 は影響しないので、気にしなくてよい。
気にする必要があるのは、0 という数字そのものが条件に関わるとき:
このときは状態に started(もう 0 でない数字を置いたか)を加える。
int ns = (s || c != 0); // 0 でない数字を置いたら始まる
int nm = ns ? (m | 1 << c) : 0; // 始まる前の 0 は集合に入れない最後は started = 1 の状態だけを数える(ついでに 0 も除かれる)。
K 以下の正整数で、桁和が D の倍数のものの個数 \((mod 10^{9}+7)\)。
string K; int D; cin >> K >> D;
vector dp(2, vector<mint>(D)); // dp[tight][桁和 mod D]
dp[1][0] = 1;
rep(i, (int)K.size()) {
int d = K[i] - '0';
vector ndp(2, vector<mint>(D));
rep(t, 2) rep(r, D) {
if (dp[t][r] == 0) continue;
int lim = t ? d : 9;
for (int c = 0; c <= lim; c++) {
int nt = (t && c == lim);
ndp[nt][(r + c) % D] += dp[t][r];
}
}
swap(dp, ndp);
}
mint ans = dp[0][0] + dp[1][0] - 1; // 0(桁和 0)を除く
cout << ans.val() << endl;\(1 \sim N\) で「3 の倍数」「数字 3 を含む」「数字がちょうど 3 種類」のちょうど 1 つを満たす数の個数。
\(N < 10^{500}\)。
// dp[tight][started][mask][r]
vector dp(2, vector(2, vector(1024, vector<mint>(3))));
dp[1][0][0][0] = 1;
rep(i, (int)N.size()) {
int d = N[i] - '0';
vector ndp(2, vector(2, vector(1024, vector<mint>(3))));
rep(t, 2) rep(s, 2) rep(m, 1024) rep(r, 3) {
mint v = dp[t][s][m][r];
if (v == 0) continue;
int lim = t ? d : 9;
for (int c = 0; c <= lim; c++) {
int nt = (t && c == lim);
int ns = (s || c != 0);
int nm = ns ? (m | 1 << c) : 0;
ndp[nt][ns][nm][(r + c) % 3] += v;
}
}
swap(dp, ndp);
}
mint ans = 0;
rep(t, 2) rep(m, 1024) rep(r, 3) {
int cnt = (r == 0) + ((m >> 3) & 1) + (__builtin_popcount(m) == 3);
if (cnt == 1) ans += dp[t][1][m][r]; // started = 1 だけ
}計算量 : 500 桁 × 状態 2 × 2 × 1024 × 3 × 10 ≒ 6 × 10^7。
tight な数は「N の先頭 i 桁」の1通りしかないので、配列にせず変数で持つ書き方もある。