1 条题解
-
0
[S] Digit Sum(dp_s)题解
题意简述
求 ( 最多 )中十进制各位数字之和是 的倍数的整数个数,。
思路
数位 DP
有上万位,必须按位处理。设
f[s][tight]= 当前已填若干高位、数位和 、是否紧贴上界(tight)的方案数。
从最高位向最低位填:
- tight 时,本位最多填到 的对应数字;
- tight 时,本位可填 。
转移 每位,总 ,、 → 。
去掉 0
DP 统计的是 ,而 0 的数位和是 0(恒为 的倍数),所以要减去 1。
的验证
时答案就是 本身(所有数的数位和都是 1 的倍数),可以对拍验证"减 1"和取模是否正确。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <cstring> using namespace std; const long long MOD = 1000000007LL; int main() { static char ks[10005]; int d; scanf("%s %d", ks, &d); int L = strlen(ks); static long long f[2][100][2]; int cur = 0; f[cur][0][1] = 1; for (int pos = 0; pos < L; pos++) { int nxt = cur ^ 1; memset(f[nxt], 0, sizeof(f[nxt])); int digit = ks[pos] - '0'; for (int s = 0; s < d; s++) for (int t = 0; t < 2; t++) { long long w = f[cur][s][t]; if (!w) continue; int hi = t ? digit : 9; for (int c = 0; c <= hi; c++) { int nt = (t && c == digit); f[nxt][(s + c) % d][nt] = (f[nxt][(s + c) % d][nt] + w) % MOD; } } cur = nxt; } long long ans = ((f[cur][0][0] + f[cur][0][1]) % MOD - 1 + MOD) % MOD; printf("%lld\n", ans); return 0; }易错点
- 必须减掉 1(0 被算进去了),这是本题最常见的 WA。
- 用字符串读,不能用整数类型。
tight的传递:只有"当前 tight 且本位填满上界数字"才继续 tight。- 减法取模要
+MOD再取模。
数据说明
共 18 组:3 组官方样例;( 与 );;;18 位随机、100 个 9、、(全 9)、随机 10000 位()、(答案 ,可精确自检)、随机 10000 位 等。
- 1
信息
- ID
- 28
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者