【题目描述】
给出两个数$a,b$,求出$[a,b]$中各位数字之和能整除原数的数的个数。
【输入格式】
一行,两个整数$a$和$b$($a,b\le 10^{18}$)
【输出格式】
一个整数,表示答案
题解
数位DP的一般思想就是表示状态,然后记忆化搜索
由于整除这个操作不太好处理,而$10^{18}$以内的数的数字和是不会超过$9*18=162$的 所以可以先枚举最终的数字和
考虑子状态需要记录哪些信息以便进行记忆化搜索
假设现在枚举到的最终数字和为$m$从高到低按数位搜索
设当前枚举到数的前$k$位,数字和为$sum$,这个$k$位数模$m$余$r$。如果两个$k$位数的$sum,r$都相同,其实后面能填的数字也会是一样的,就可以进行记忆化。
举例来说,$m=20$,枚举到第3位
$163??$和$523??$
163和523模20同余,数字和也均为10
那么后两位能填的数也会一样 不需要再搜索$523??$而是只用返回$163??$的结果
枚举$m$子状态就是$dp[i][j][k]$表示枚举到前i位,数字和为j,这个i位数模m余k
最后用$1\sim r$的减掉$1\sim l-1$的即可
时间复杂度$O(162^3*数位个数)$
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| #include <bits/stdc++.h> using namespace std; typedef long long ll;
ll a, b, ans, ans2; ll num[20], len, mod; ll dp[20][200][200];
inline void getnum(ll x) { len = 0; while (x) { num[++len] = x % 10; x /= 10; } }
ll dfs(ll d, ll sum, ll m, ll lim) { if (d <= 0) { return (m == 0 && sum == mod ? 1 : 0); } if (!lim && ~dp[d][sum][m]) return dp[d][sum][m]; ll ret = 0, mx = lim ? num[d] : 9; for (int i = 0; i <= mx; i++) { ret += dfs(d-1, sum+i, (m*10+i)%mod, lim && i == mx); } if (!lim) dp[d][sum][m] = ret; return ret; }
ll work(ll x) { if (!x) return 0; getnum(x); ll ret = 0; for (int i = 1; i <= 9 * len; i++) { mod = i; memset(dp, -1, sizeof(dp)); ret += dfs(len, 0, 0, 1); } return ret; }
int main() { scanf("%lld %lld", &a, &b); ans = work(a-1); ans2 = work(b); printf("%lld\n", ans2 - ans); return 0; }
|