Digit DP - sonning raqamlari bo'yicha DP
Digit DP quyidagi kabi masalalar uchun ishlatiladi:
Standart usul:
bu yerda = dagi yaroqli butun sonlar soni.
ning o‘nlik raqamlari s satrida saqlansin.
Quyidagi kabi DP holatini aniqlang:
Bu yerda:
pos = joriy raqam indeksitight = prefiks chegaraning prefiksiga tengmi (1) yoki allaqachon kichikmi (0)started = yetakchi nol bo‘lmagan raqamni allaqachon qo‘ydikmistate = masalaga xos ma’lumot (yig‘indi, qoldiq, soni, oxirgi raqam, maska, ...)O‘tish:
d raqamini 0 dan limit gacha sinab ko‘ringlimit = s[pos] agar tight=1 bo‘lsa, aks holda 9Masala: dagi raqamlar yig‘indisi ga bo‘linadigan sonlarni sanang
Quyidagini oling:
= pos gacha prefiksni qurish usullari soni, bu yerda rem — raqamlar yig‘indisining bo‘yicha moduli.
Biz faqat qoldiqni saqlaymiz (to‘liq yig‘indini emas), bu ancha yaxshi.
Agar d raqamini qo‘ysak, unda:
(Odatda started = 0 va d = 0 bo‘lsa ham ruxsat beramiz; bu shunchaki yetakchi nollar.
Oxirida nolni chiqarib tashlamoqchi bo‘lsangiz, 1 ni ayiring.)
Agar son uzunligi N bo‘lsa, murakkablik taxminan:
Agar faqat bo‘linuvchanlik muhim bo‘lsa, to‘liq raqamlar yig‘indisini saqlamang.
Quyidagini saqlang:
sum o‘rniga.
tight = 0 bo‘lganda memoizatsiya qilingKeng tarqalgan optimizatsiya:
tight = 0 bo‘lgan holatlar qayta ishlatiladitight = 1 bo‘lgan holatlar aniq chegara prefiksiga bog‘liqShuning uchun ko‘p yechimlar faqat bo‘sh holatlarni (tight = 0) memoizatsiya qiladi va xotirani tejaydi.
Yetakchi nollar Digit DP ning bir qismi va izchil tarzda qayta ishlanishi kerak.
Odatdagi tanlovlar:
started flagidan foydalanish#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;
}