CF1029D.Concatenated Multiples

You are given an array $a$, consisting of $n$ positive integers.

Let's call a concatenation of numbers $x$ and $y$ the number that is obtained by writing down numbers $x$ and $y$ one right after another without changing the order. For example, a concatenation of numbers $12$ and $3456$ is a number $123456$.

Count the number of ordered pairs of positions $(i, j)$ ($i \neq j$) in array $a$ such that the concatenation of $a_i$ and $a_j$ is divisible by $k$.

给你一个由 $n$ 个正整数组成的数组 $a$。

我们将数字 $x$ 和 $y$ 的拼接（concatenation）定义为将 $x$ 和 $y$ 按照原有顺序依次写出所得到的数。例如，数字 $12$ 和 $3456$ 的拼接结果是 $123456$。

请统计数组 $a$ 中满足如下条件的有序位置对 $(i, j)$（其中 $i \neq j$）的个数：$a_i$ 与 $a_j$ 的拼接结果能被 $k$ 整除。

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $2 \le k \le 10^9$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$2 \le k \le 10^9$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

Print a single integer — the number of ordered pairs of positions $(i, j)$ ($i \neq j$) in array $a$ such that the concatenation of $a_i$ and $a_j$ is divisible by $k$.

输出一个整数——表示数组 $a$ 中满足 $a_i$ 与 $a_j$ 的拼接结果能被 $k$ 整除的有序位置对 $(i, j)$（其中 $i \neq j$）的个数。

In the first example pairs $(1, 2)$, $(1, 3)$, $(2, 3)$, $(3, 1)$, $(3, 4)$, $(4, 2)$, $(4, 3)$ suffice. They produce numbers $451$, $4510$, $110$, $1045$, $1012$, $121$, $1210$, respectively, each of them is divisible by $11$.

In the second example all $n(n - 1)$ pairs suffice.

In the third example no pair is sufficient.

在第一个例子中，数对 $(1, 2)$、$(1, 3)$、$(2, 3)$、$(3, 1)$、$(3, 4)$、$(4, 2)$、$(4, 3)$ 即可满足要求。它们分别生成数字 $451$、$4510$、$110$、$1045$、$1012$、$121$、$1210$，这些数均能被 $11$ 整除。

在第二个例子中，全部 $n(n - 1)$ 个数对均满足要求。

在第三个例子中，不存在满足要求的数对。