题目理解

我们有一个长度为 $N$ 的数字字符串 $S$，和一个素数 $P$。对于每个询问 $[fr, to]$，我们需要计算子串 $S[fr \ldots to]$ 中有多少个子串（连续）表示的数是 $P$ 的倍数。

关键观察：

• 子串 $S[l \ldots r]$ 表示的数字是 $\sum_{i=l}^r S[i] \times 10^{r-i}$
• 由于 $P$ 是素数，当 $P \neq 2, 5$ 时，$10$ 与 $P$ 互质，有乘法逆元
• 当 $P = 2$ 或 $P = 5$ 时，情况特殊，可以单独处理

问题分析

情况1：$P = 2$ 或 $P = 5$

这种情况下，一个数能被 $P$ 整除当且仅当最后一位能被 $P$ 整除。

解法：

• 预处理前缀和数组
• 对于询问 $[l, r]$，答案为 $\sum_{i=l}^r [S[i] \equiv 0 \pmod{P}] \times (i-l+1)$

情况2：$P \neq 2, 5$

这是本题的主要难点。

解法思路

关键转化

设 $f(i)$ 表示后缀 $S[i \ldots N]$ 表示的数字模 $P$ 的值：

$$f(i) = \left(\sum_{j=i}^N S[j] \times 10^{N-j}\right) \bmod P $$

那么子串 $S[l \ldots r]$ 表示的数字为：

$$\frac{f(l) - f(r+1)}{10^{N-r}} \bmod P$$

由于 $P \neq 2, 5$，$10$ 与 $P$ 互质，$10^{N-r}$ 有逆元，所以：

$$S[l \ldots r] \equiv 0 \pmod{P} \iff f(l) \equiv f(r+1) \pmod{P} $$

问题转化

对于询问 $[l, r]$，我们要求满足：

• $l \leq i \leq j \leq r$
• $f(i) \equiv f(j+1) \pmod{P}$

的子串 $S[i \ldots j]$ 的个数。

这等价于在区间 $[l, r+1]$ 中，有多少对 $(i, j)$ 满足 $f(i) = f(j)$ 且 $i < j$。

莫队算法

将问题转化为：有 $n+1$ 个位置（$f(1) \ldots f(n+1)$），每个位置有一个值，询问区间 $[l, r]$ 内相同值的对数。

使用莫队算法：

• 将询问按块排序
• 维护当前区间内每个值的出现次数
• 移动指针时更新答案

算法复杂度分析

特殊情况（$P = 2, 5$）

• 预处理：$O(n)$
• 每次查询：$O(1)$
• 总复杂度：$O(n + m)$

一般情况（$P \neq 2, 5$）

• 预处理：
  • 计算幂次：$O(n)$
  • 计算后缀值：$O(n)$
  • 离散化：$O(n \log n)$
• 莫队算法：$O(n \sqrt{m})$
• 总复杂度：$O(n \log n + n \sqrt{m})$

关键技巧总结

1. 数学转化：利用后缀表示将子串整除问题转化为值相等问题
2. 特殊情况处理：$P = 2, 5$ 时性质特殊，单独处理
3. 离散化：将大范围的模P值映射到小范围，便于计数
4. 莫队算法：高效处理区间内相同值对数的查询
5. 边界处理：注意f数组有$n+1$个值，询问区间要相应调整

正确性证明

对于子串 $S[i \ldots j]$：

• 其数值 = $\frac{f(i) - f(j+1)}{10^{N-j}} \bmod P$
• 由于 $10^{N-j}$ 与 $P$ 互质，该值为0当且仅当 $f(i) \equiv f(j+1) \pmod{P}$
• 因此统计区间 $[l, r+1]$ 内相同f值的对数即为答案

这种方法充分利用了数论性质和算法技巧，将复杂的子串统计问题转化为高效的区间查询问题。