DP-и рақамӣ
Digit DP барои масъалаҳое истифода мешавад, мисли:
Ҳиллаи стандартӣ ин аст:
ки дар он = шумораи ададҳои дуруст дар .
Бигзор рақамҳои даҳии дар сатри s нигоҳ дошта шаванд.
Ҳолати DP-ро чунин муайян кунед:
Ки дар он:
pos = индекси рақами ҷорӣtight = оё префикс ба префикси ҳад баробар аст (1) ё аллакай хурдтар аст (0)started = оё мо аллакай рақами ғайри сифри пешсафро гузоштемstate = маълумоти махсуси масъала (ҷамъ, боқимонда, шумор, рақами охирин, маска, ...)Гузариш:
d-ро аз 0 то limit санҷедlimit = s[pos] агар tight=1, вагарна 9Масъала: Шумориши ададҳо дар бо ҷамъбасти рақамҳо, ки ба тақсим мешавад
Бигзор:
= шумораи роҳҳо барои сохтани префикс то pos, ки дар он rem ҷамъбасти рақамҳо боқимонда аз рӯи аст.
Мо танҳо боқимондаро нигоҳ медорем (на ҷамъбасти пурра), ки хеле беҳтар аст.
Агар мо рақами d-ро гузорем, пас:
(Одатан агар started = 0 ва d = 0, мо ҳанӯз иҷозат медиҳем; ин танҳо сифрҳои пешсафанд.
Дар охир, 1-ро тарҳ кунед, агар хоҳед сифрро истисно кунед.)
Агар дарозии адад N бошад, мураккабӣ тақрибан чунин аст:
Ҷамъбасти пурраи рақамҳоро нигоҳ надоред, агар танҳо тақсимшавӣ муҳим бошад.
Нигоҳ доред:
ба ҷои sum.
tight = 0Як оптимизатсияи маъмул:
tight = 0 аз нав истифода мешавандtight = 1 аз префикси дақиқи ҳад вобастаандПас бисёр ҳалҳо танҳо ҳолатҳои озодро мемоизатсия мекунанд (tight = 0) ва хотираро сарфа мекунанд.
Сифрҳои пешсаф қисми Digit DP мебошанд ва бояд пайваста коркард шаванд.
Интихобҳои маъмул:
started#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string s;
int D;
ll memo[20][2][2][105];
bool vis[20][2][2][105];
ll dfs(int pos, int tight, int started, int rem) {
if (pos == (int)s.size()) {
// exclude 0 by requiring started == 1
return (started && rem == 0) ? 1 : 0;
}
if (vis[pos][tight][started][rem]) return memo[pos][tight][started][rem];
vis[pos][tight][started][rem] = true;
int lim = tight ? (s[pos] - '0') : 9;
ll ans = 0;
for (int d = 0; d <= lim; d++) {
int ntight = (tight && d == lim);
int nstarted = started || (d != 0);
int nrem = rem;
if (nstarted) nrem = (rem + d) % D;
ans += dfs(pos + 1, ntight, nstarted, nrem);
}
return memo[pos][tight][started][rem] = ans;
}
ll solve(long long x, int modD) {
if (x < 0) return 0;
s = to_string(x);
D = modD;
memset(vis, 0, sizeof(vis));
return dfs(0, 1, 0, 0);
}
int main() {
long long L, R;
cin >> L >> R >> D;
cout << solve(R, D) - solve(L - 1, D) << "\n";
return 0;
}