$AC$ 题解

如果 $(D,10)\not=1$，那么上面的性质就不再成立。

自然可以想到将 $D$ 分解为两部分：$D=D_1\cdot D_2$，其中 $(D_1,10)=1$，$D_2$ 的质因子只包含 $2,5$。

因为 $(D_1,D_2)=1$，根据数论性质，一个子串能被 $D$ 整除，等价于它同时能被 $D_1$ 和 $D_2$ 整除。

设 $D_2=2^a\times5^b$，令 $K=\max(a,b)$，那么 $10^K=2^K\times5^K$ 必然是 $D_2$ 的倍数。

这意味着，对于任何一个长度超过 $K$ 的数字，我们可以把它拆成两部分：前面的高位和最后的 $K$ 位。

由于 $10^K$ 可以被 $D_2$ 整除，高位部分在模 $D_2$ 意义下直接归零。所以一个数能否被 $D_2$ 整除，完全且仅仅取决于它的后 $K$ 位数字能否被 $D_2$ 整除。

那么对于 $S[j+1\dots i]$，只要这段的长度大于等于 $K$（即 $i-j\ge K$），我们根本不需要看 $j$ 具体在哪里，只需要看子串的最后 $K$ 位，也就是 $S[i-K+1\dots i]$ 能否被 $D_2$ 整除即可。如果不能整除，那么所有 $j\le i-K$ 对应的子串全部不合法。如果能整除，那 $D_2$ 这一关就过了。

在 $D\le10^6$ 的范围内，$2$ 的最大幂次是 $2^{19}=524288$（即 $a$ 最大为 $19$），$5$ 的最大幂次是 $5^8=390625$（即 $b$ 最大为 $8$）。

因此 $K$ 的理论最大值为 $19$，当计算 $i$ 时，只需验证一次长度为 $K$ 的后缀。如果合法，直接从 $suma[val[i]]$ 中读取前面所有合法 $j$ 带来的 $DP$ 总和，$O(1)$ 时间即可完成状态转移。对于距离 $i$ 小于 $K$ 的那几个 $j$，因为数量极少（最多 $19$ 个），直接用普通字符串取模暴力验证即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 1000005
#define M 1000000007
#define LL long long

LL n, d;
char s[N];
LL f[N][2];
LL suma[N], sumb[N];
LL val[N], pre[N];

// 扩展欧几里得求逆元
void exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

LL inv(LL a, LL m) {
    LL x, y;
    exgcd(a, m, x, y);
    return (x % m + m) % m;
}

int main() {
    scanf("%s %lld", s + 1, &d);
    n = strlen(s + 1);
    LL d1 = d, d2 = 1;
    int a = 0, b = 0;
    // 动态计算 d2 和 K
    while (d1 % 2 == 0) { d1 /= 2; d2 *= 2; a++; }
    while (d1 % 5 == 0) { d1 /= 5; d2 *= 5; b++; }
    // K 为满足 10^K % d2 == 0 的最小整数，保底为 1 以保证区间有效
    int k = max({1, a, b});
    LL inv10 = d1 > 1 ? inv(10, d1) : 0, now = 1;
    for (int i = 0; i <= n; i++) {
        if (i > 0) {
            pre[i] = (pre[i - 1] * 10 + (s[i] - '0')) % d1;
            now = (now * inv10) % d1;
        }
        val[i] = d1 > 1 ? (pre[i] * now) % d1 : 0;
    }
    f[0][1] = 1;
    f[0][0] = 0;
    LL sum = 1;
    for (int i = 1; i <= n; i++) {
        if (i >= k) {
            int j = i - k;
            suma[val[j]] = (suma[val[j]] + f[j][0] + f[j][1]) % M;
            sumb[val[j]] = (sumb[val[j]] + f[j][1]) % M;
        }
        LL sum1 = 0, sum2 = 0;
        // 处理相距较远的划分 (i - j >= k)
        if (i >= k) {
            LL lstk = 0, p10 = 1;
            for (int j = i; j > i - k; j--) {
                lstk = (lstk + (s[j] - '0') * p10) % d2;
                p10 = (p10 * 10) % d2;
            }
            if (!lstk) {
                sum1 = suma[val[i]];
                sum2 = sumb[val[i]];
            }
        }
        // 暴力匹配相距较近的划分 (i - j < k)
        int st = max(0, i - k + 1);
        LL now = 0, p10 = 1;
        for (int j = i - 1; j >= st; j--) {
            now = (now + (s[j + 1] - '0') * p10) % d;
            p10 = (p10 * 10) % d;
            if (now == 0) {
                sum1 = (sum1 + f[j][0] + f[j][1]) % M;
                sum2 = (sum2 + f[j][1]) % M;
            }
        }
        f[i][1] = sum1 % M;
        f[i][0] = (sum - sum2 + M) % M; // 总合法方案数减去好串后缀的方案数
        sum = (sum + f[i][1]) % M;
    }
    printf("%lld\n", (f[n][0] + f[n][1]) % M);
    return 0;
}

测试点 $4,5,6$ 题解

注意到特殊性质：$(D,10)=1$，不妨先考虑 $D$ 与 $10$ 互质的情况。

设 $pre[x]$ 表示字符串从第 $1$ 位到第 $x$ 位数字对 $D$ 取模的结果，那么子串 $S[j+1\dots i]$ 在数值上可以表示为：

$$S[j+1\dots i]=pre[i]-pre[j]\times10^{i-j}$$

要求这个子串能被 $D$ 整除，即：

$$pre[i]-pre[j]\times10^{i-j}\equiv0\pmod{D}$$ $$pre[i]\equiv pre[j]\times10^{i-j}\pmod{D}$$

为了把 $i$ 相关的项和与 $j$ 相关的项完全分离，在等式两边同时乘以 $10^{-i}$（即 $10^i$ 在模 $D$ 下的逆元）：

$$pre[i]\times10^{-i}\equiv pre[j]\times10^{-j}\pmod{D}$$

如果令 $val[x]=(pre[x]\times10^{-x})\pmod{D}$，那么判断条件就简化为 $val[i]==val[j]$。

因此，我们只需要用两个桶 $suma$ 和 $sumb$ 来记录相同 $val$ 值下的 $DP$ 累加和，就可以在 $O(1)$ 的时间内完成所有的状态转移，彻底去除了暴力枚举的内层循环。

// 特殊性质：测试点 4，5，6
#include <cstdio>
#include <cstring>
using namespace std;

#define N 500005
#define M 1000000007
#define LL long long

LL n, d;
char s[N];
LL f[N][2];
LL suma[N]; // 记录 val 相同的 f[j][0] + f[j][1] 的总和
LL sumb[N]; // 记录 val 相同的 f[j][1] 的总和
LL val[N];

// 扩展欧几里得求逆元
void exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

LL inv(LL a, LL m) {
    LL x, y;
    exgcd(a, m, x, y);
    return (x % m + m) % m;
}

int main() {
    scanf("%s %lld", s + 1, &d);
    n = strlen(s + 1);
    // 因为 (D, 10) = 1，直接求 10 在模 D 下的逆元
    LL inv10 = inv(10, d), now = 1, pre = 0;
    // 预处理所有前缀的映射值 val[i]
    for (int i = 0; i <= n; i++) {
        if (i > 0) {
            pre = (pre * 10 + (s[i] - '0')) % d;
            now = (now * inv10) % d;
        }
        val[i] = (pre * now) % d;
    }
    f[0][1] = 1;
    f[0][0] = 0;
    LL sum = 1; // 记录所有合法的 f[j][1] 历史总和
    for (int i = 1; i <= n; i++) {
        // 将 j = i - 1 的状态加入到对应的 val 桶中，供后续快速查询
        suma[val[i - 1]] = (suma[val[i - 1]] + f[i - 1][0] + f[i - 1][1]) % M;
        sumb[val[i - 1]] = (sumb[val[i - 1]] + f[i - 1][1]) % M;
        // 查表：如果 val[j] == val[i]，说明 S[j+1...i] 是好串，O(1) 获取总和
        f[i][1] = suma[val[i]];
        // 坏串情况：全集 (所有合法的接好串情况) 减去 好串情况
        f[i][0] = (sum - sumb[val[i]] + M) % M;
        sum = (sum + f[i][1]) % M;
    }
    printf("%lld\n", (f[n][0] + f[n][1]) % M);
    return 0;
}

暴力 $30pt$ 题解

根据题意，“不存在两个相邻的子串不能被 $D$ 整除” 的意思是：对于任意两个相邻的子串，至少有一个必须能被 $D$ 整除。

这就意味着，如果把不能被 $D$ 整除的子串叫「坏串」，能被 $D$ 整除的子串叫「好串」，那么划分方案中就不允许出现 “坏串-坏串” 的情况，必须是 “好串-好串”、“好串-坏串” 或 “坏串-好串”。

那么可以设计一个动态规划：

• $f[i][0]$ 表示前 $i$ 个字符的合法划分方案数，且最后一段是「坏串」。
• $f[i][1]$ 表示前 $i$ 个字符的合法划分方案数，且最后一段是「好串」。

设最后一段为 $S[j+1\dots i]$：

如果是好串（能被 $D$ 整除），它可以接在好串后面，也可以接在坏串后面：

$$f[i][1]=\sum_j(f[j][0]+f[j][1])$$

如果是坏串（不能被 $D$ 整除），它只能接在好串后面：

$$f[i][0]=\sum_jf[j][1]=(\sum_{j=0}^{i-1}f[j][1])-(\sum_{S[j+1\dots i]\equiv0\pmod{D}}f[j][1])$$

这样问题的核心就变成了：如何快速求出所有使得 $S[j+1\dots i]\equiv0\pmod{D}$ 的 $j$ 对应的 $DP$ 值之和。

直接暴力枚举 $j$ 的时间复杂度是 $O(n^2)$。可得 $30pt$。

// O(n^2) DP 30pt
#include <cstdio>
#include <cstring>
using namespace std;

#define N 500005
#define M 1000000007
#define LL long long

LL n, d;
char s[N];
LL f[N][2];

int main() {
    scanf("%s %lld", s + 1, &d);
    n = strlen(s + 1);
    // f[i][0] 表示前 i 个字符的合法划分，且最后一段是“坏串”（不能被 D 整除）
    // f[i][1] 表示前 i 个字符的合法划分，且最后一段是“好串”（能被 D 整除）
    // 初始化：空串算作“好串”，这是为了让字符串的第 1 段无论是好是坏，都能正常通过转移方程计算
    f[0][1] = 1;
    f[0][0] = 0;
    // 外层枚举当前处理到的字符串末尾 i
    for (int i = 1; i <= n; i++) {
        LL now = 0;
        LL p10 = 1; // 记录 10 的幂次对 D 取模的结果
        // 内层暴力枚举上一个切分点 j (从 i-1 倒推到 0)
        for (int j = i - 1; j >= 0; j--) {
            // 倒序计算子串 S[j+1...i] 对应的数值模 D 的结果
            now = (now + (s[j + 1] - '0') * p10) % d;
            p10 = (p10 * 10) % d;
            if (now == 0) {
                // 当前段 S[j+1...i] 是“好串”：可以接在“好串”或“坏串”后面
                f[i][1] = (f[i][1] + f[j][0] + f[j][1]) % M;
            } else {
                // 当前段 S[j+1...i] 是“坏串”：为了避免相邻都坏，只能接在“好串”后面
                f[i][0] = (f[i][0] + f[j][1]) % M;
            }
        }
    }
    // 最终答案为最后一段是好串和坏串的方案数之和
    printf("%lld\n", (f[n][0] + f[n][1]) % M);
    return 0;
}