E - 可被整除的子串

得分：$500$ 分

问题描述

高桥有一个长度为 $N$ 的字符串 $S$，由数字 0 到 9 组成。

他特别喜欢质数 $P$。他想知道在将这些非空（连续）子串视为十进制整数时，有多少个子串可以被 $P$ 整除。

这里，以 0 开头的子串也要计算在内，并且来自 $S$ 的不同位置的子串是不同的，即使它们作为字符串或整数相等。

计算这个数量，帮助高桥。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $S$ 由数字组成。
• $|S| = N$
• $2 \leq P \leq 10000$
• $P$ 是一个质数。

输入

从标准输入中按以下格式给出：

$N$ $P$

$S$

输出

输出可以被 $P$ 整除的非空（连续）子串的数量，作为一个十进制整数。

4 3
3543

6

这里 $S$ = 3543。$S$ 有十个非空（连续）子串：

• 3：可以被 $3$ 整除。

• 35：不能被 $3$ 整除。

• 354：可以被 $3$ 整除。

• 3543：可以被 $3$ 整除。

• 5：不能被 $3$ 整除。

• 54：可以被 $3$ 整除。

• 543：可以被 $3$ 整除。

• 4：不能被 $3$ 整除。

• 43：不能被 $3$ 整除。

• 3：可以被 $3$ 整除。

其中六个可以被 $3$ 整除，所以输出 $6$。

4 2
2020

10

这里 $S$ = 2020。$S$ 有十个非空（连续）子串，所有这些子串都可以被 $2$ 整除，所以输出 $10$。

注意，以 0 开头的子串也要计算在内。

20 11
33883322005544116655

68