AT_abc158_e [ABC158E] Divisible Substring

高桥君有一个由数字 $0$ 到 $9$ 组成、长度为 $N$ 的字符串 $S$。 高桥君喜欢素数 $P$，他想知道，在 $S$ 的所有 $N \times (N + 1) / 2$ 个非空连续子串中，有多少个子串在视为十进制整数时能够被 $P$ 整除。 注意，子串可以以 $0$ 开头；即使作为字符串或整数相等，只要在 $S$ 中的位置不同，也要分别计数。 请你帮高桥君计算这个数量。

输入以以下格式从标准输入读入。 > $N$ $P$ $S$

输出 $S$ 的所有非空连续子串中，能被 $P$ 整除的子串的个数。

## 限制条件 - $1 \leq N \leq 2 \times 10^5$ - $S$ 只包含数字 - $|S| = N$ - $2 \leq P \leq 10000$ - $P$ 是素数 ## 样例解释 1 $S = 3543$。$S$ 的所有非空连续子串共有 $10$ 个，如下所示： - `3` 可以被 $3$ 整除。 - `35` 不能被 $3$ 整除。 - `354` 可以被 $3$ 整除。 - `3543` 可以被 $3$ 整除。 - `5` 不能被 $3$ 整除。 - `54` 可以被 $3$ 整除。 - `543` 可以被 $3$ 整除。 - `4` 不能被 $3$ 整除。 - `43` 不能被 $3$ 整除。 - `3` 可以被 $3$ 整除。 其中能被 $3$ 整除的有 $6$ 个，所以输出 $6$。 ## 样例解释 2 $S = 2020$。$S$ 的所有非空连续子串共有 $10$ 个，并且全部都能被 $2$ 整除，所以输出 $10$。注意允许以 $0$ 开头的子串。 由 ChatGPT 4.1 翻译