1 条题解

  • 0
    @ 2026-11-12 21:58:07

    [S] Digit Sum(dp_s)题解

    题意简述

    求 1∼K1 \sim K(KK 最多 101000010^{10000})中十进制各位数字之和是 DD 的倍数的整数个数, mod 109+7\bmod 10^9+7。

    思路

    数位 DP

    KK 有上万位,必须按位处理。设

    • f[s][tight] = 当前已填若干高位、数位和  mod D=s\bmod D = s、是否紧贴上界(tight)的方案数。

    从最高位向最低位填:

    • tight =1=1 时,本位最多填到 KK 的对应数字;
    • tight =0=0 时,本位可填 0∼90 \sim 9。

    转移 O(D⋅10)O(D \cdot 10) 每位,总 O(L⋅D⋅10)O(L \cdot D \cdot 10),L≤10000L \le 10000、D≤100D \le 100 → 10710^7。

    去掉 0

    DP 统计的是 [0,K][0, K],而 0 的数位和是 0(恒为 DD 的倍数),所以要减去 1。

    D=1D=1 的验证

    D=1D=1 时答案就是 KK 本身(所有数的数位和都是 1 的倍数),可以对拍验证"减 1"和取模是否正确。

    复杂度

    时间 O(L⋅D⋅10)O(L \cdot D \cdot 10),空间 O(D)O(D)。

    参考代码

    #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. 必须减掉 1(0 被算进去了),这是本题最常见的 WA。
    2. KK 用字符串读,不能用整数类型。
    3. tight 的传递:只有"当前 tight 且本位填满上界数字"才继续 tight。
    4. 减法取模要 +MOD 再取模。

    数据说明

    共 18 组:3 组官方样例;K=1/2/10K=1/2/10(D=1D=1 与 D>1D>1);K=999,D=9K=999, D=9;K=123456789,D=7K=123456789, D=7;18 位随机、100 个 9、10999910^{9999}、1010000−110^{10000}-1(全 9)、随机 10000 位(D=50D=50)、D=1D=1(答案 =K mod p=K \bmod p,可精确自检)、随机 10000 位 D=37D=37 等。

    • 1

    信息

    ID
    28
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者