E - Divisible Substring Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

高橋君は 0 から 9 までの数字から成る長さ N の文字列 S を持っています。

素数 P が好きな高橋君は、S の空でない連続する部分文字列 N \times (N + 1) / 2 個のうち、十進表記の整数と見なした際に P で割り切れるものの個数を知りたくなりました。

ただし部分文字列は先頭が 0 であっても良いものとし、文字列として等しい場合や、整数と見なした際に等しい場合も、部分文字列の S 内の位置で区別します。

高橋君のためにこの個数を計算してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • S は数字から成る
  • |S| = N
  • 2 \leq P \leq 10000
  • P は素数である

入力

入力は以下の形式で標準入力から与えられる。

N P
S

出力

S の空でない連続する部分文字列であって、十進表記の整数と見なした際に P で割り切れるものの個数を出力せよ。

入力例 1

4 3
3543

出力例 1

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 を出力してください。

入力例 2

4 2
2020

出力例 2

10

S = 2020 です。S の空でない連続する部分文字列は 10 個ありますが、その全てが 2 で割り切れるので 10 を出力してください。

先頭が 0 である部分文字列も許容されることに注意してください。

入力例 3

20 11
33883322005544116655

出力例 3

68

Score : 500 points

Problem Statement

Takahashi has a string S of length N consisting of digits from 0 through 9.

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

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

Compute this count to help Takahashi.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • S consists of digits.
  • |S| = N
  • 2 \leq P \leq 10000
  • P is a prime number.

Input

Input is given from Standard Input in the following format:

N P
S

Output

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

Sample Input 1

4 3
3543

Sample Output 1

6

Here S = 3543. There are ten non-empty (contiguous) substrings of S:

  • 3: divisible by 3.

  • 35: not divisible by 3.

  • 354: divisible by 3.

  • 3543: divisible by 3.

  • 5: not divisible by 3.

  • 54: divisible by 3.

  • 543: divisible by 3.

  • 4: not divisible by 3.

  • 43: not divisible by 3.

  • 3: divisible by 3.

Six of these are divisible by 3, so print 6.

Sample Input 2

4 2
2020

Sample Output 2

10

Here S = 2020. There are ten non-empty (contiguous) substrings of S, all of which are divisible by 2, so print 10.

Note that substrings beginning with a 0 also count.

Sample Input 3

20 11
33883322005544116655

Sample Output 3

68