Divisible Substring

题目描述

Takahashi 有一个长度为 $N$ 的字符串 $S$，由数字 $0$ 到 $9$ 组成。 他很喜欢素数 $P$。他想知道将 $S$ 的多少个非空（连续）子字符串 —— 总共有 $N \times (N + 1) / 2$ 个 —— 当作十进制整数时能被 $P$ 整除。 这里以 $0$ 开头的子字符串也算数，并且来源于 $S$ 不同位置的子字符串即使作为字符串或整数相同也被区分。 计算这个计数以帮助 Takahashi。

输入格式

Input is given from Standard Input in the following format: $N$ $P$ $S$

输出格式

Print the number of non-empty (contiguous) substrings of $S$ that are divisible by $P$ when regarded as an integer written in base ten.

4 3
3543

6

4 2
2020

10

20 11
33883322005544116655

68

提示

$1 \leq N \leq 2 \times 10^5$ $S$ consists of digits. $|S| = N$ $2 \leq P \leq 10000$ $P$ is a prime number.这里 $S$ = $3543$。共有十个非空（连续）子字符串：

$3$：能被 $3$ 整除。

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

$354$：能被 $3$ 整除。

$3543$：能被 $3$ 整除。

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

$54$：能被 $3$ 整除。

$543$：能被 $3$ 整除。

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

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

$3$：能被 $3$ 整除。

其中六个能被 $3$ 整除，所以输出 $6$。
这里 $S$ = $2020$。共有十个非空（连续）子字符串，全部都能被 $2$ 整除，所以输出 $10$。 注意以 $0$ 开头的子字符串也算数。

标签: AtCoder|abc158E

来源

AtCoder|abc158E