Find the Multiples#3464

Find the Multiples

5 секунди

32 мегабајти

Тешко

You are given a sequence $a_{0} a_{1} \dots a_{N - 1}$ a_0 a_1 \ldots a_{N-1} of digits and a prime number $Q$ . For each $i \leq j$ i \leq j with $a_{i} \neq = 0$ a_i \neq 0, the subsequence $a_{i} a_{i + 1} \dots a_{j}$ a_i a_{i+1} \ldots a_j can be read as a decimal representation of a positive integer. Subsequences with leading zeros are not considered. Your task is to count the number of pairs $(i, j)$ such that the corresponding subsequence is a multiple of $Q$ .

Влез

The input consists of at most $50$ datasets. Each dataset is represented by a line containing four integers $N$ , $S$ , $W$ , and $Q$ , separated by spaces, where $1 \leq N \leq 1 0^{5}$ 1 \leq N \leq 10^5, $1 \leq S \leq 1 0^{9}$ 1 \leq S \leq 10^9, $1 \leq W \leq 1 0^{9}$ 1 \leq W \leq 10^9, and $Q$ is a prime number less than $1 0^{8}$ 10^8. The sequence $a_{0} \dots a_{N - 1}$ a_0 \ldots a_{N-1} of length $N$ is generated by the following code, in which $a_{i}$ a_i is written as $a [i]$ .

Примери

Пример 1

Loading

a_{0} a_{1} \dots a_{N - 1}

i \leq j

a_{i} \neq = 0

a_{i} a_{i + 1} \dots a_{j}

1 \leq N \leq 1 0^{5}

1 \leq S \leq 1 0^{9}

1 \leq W \leq 1 0^{9}

1 0^{8}

a_{0} \dots a_{N - 1}

a_{i}