可整除子串

题目描述

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

喜欢素数 $P$ 的高桥君想知道,在 $S$ 的非空连续子串共 $N \times (N + 1) / 2$ 个中,把它们看作十进制表示的整数时,能被 $P$ 整除的有多少个。

但是,子串开头可以是 0,并且即使字符串相同或看作整数时相同,只要在 $S$ 中的位置不同就视为不同的子串。

请帮高桥君计算这个个数。

输入格式

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

$N$ $P$
$S$

输出格式

输出 $S$ 的非空连续子串中,看作十进制表示的整数时能被 $P$ 整除的个数。

样例

4 3
3543

6

$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$。

4 2
2020

10

$S$ = 2020。$S$ 的非空连续子串有 $10$ 个,它们都能被 $2$ 整除,因此输出 $10$。

注意开头为 0 的子串也是允许的。

20 11
33883322005544116655

68

数据范围

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