#ABC158E. Divisible Substring

Divisible Substring

题目描述

Takahashi has a string SS of length NN consisting of digits from 0 through 9.

He loves the prime number PP. He wants to know how many non-empty (contiguous) substrings of SS - there are N×(N+1)/2N \times (N + 1) / 2 of them - are divisible by PP when regarded as integers written in base ten.

Here substrings starting with a 0 also count, and substrings originated from different positions in SS are distinguished, even if they are equal as strings or integers.

Compute this count to help Takahashi.

高桥有一个长度为 NN 的字符串 SS ,由从 09 的数字组成。

他喜欢质数 PP 。他想知道 SS 的非空(连续)子串 N×(N+1)/2N \times (N + 1) / 2 有多少个。- 有 N×(N+1)/2N \times (N + 1) / 2 个--如果看作以十为底数的整数,则可以被 PP 整除。

在这里,以 "0 "开头的子串也算数,而且从 SS 的不同位置开始的子串也要加以区分,即使它们作为字符串或整数是相等的。

计算这个计数来帮助高桥。

输入格式

输入内容按以下格式标准输入:

NN PP
SS

输出格式

打印 SS 的非空(连续)子串中,能被 PP 整除(以十为基数)的个数。

样例 #1

样例输入 #1

4 3
3543

样例输出 #1

样例 #2

样例输入 #2

4 2
2020

样例输出 #2

10

样例 #3

样例输入 #3

20 11
33883322005544116655

样例输出 #3

68

说明

数据规模与约定

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • SS 由数字组成。
  • S=N|S| = N
  • 2P100002 \leq P \leq 10000
  • PP 是质数。

样例 11 解释

此处 SS = 3543SS 有十个非空(连续)子串:

  • 3`:可被 33 整除。

  • 35`:不能被 33 整除。

  • 354`:能被 33 整除。

  • 3543`:可以被 33 整除。

  • 5`:不能被 33 整除。

  • 54`:能被 33 整除。

  • 543`:能被 33 整除。

  • 4`:不能被 33 整除。

  • 43`:不能被 33 整除。

  • 3`:不能被 33 整除。

其中 6 个能被 33 整除,因此打印 66

样例 22 解释

这里 SS = 2020SS 有 10 个非空(连续)子串,它们都能被 22 整除,因此打印 1010

请注意,以 "0 "开头的子串也算数。