算法

(枚举) $\ \ \mathcal O(n \log _ {10} n)$

首先考虑一下暴力，很容易写出暴力的代码：

for (int i = 0; i < n; i ++ )
    for (int j = 0; j < n; j ++ )
        if (check(a[i], a[j]))
            ans ++ ;

其中check(a[i], a[j])是判断a[i]与a[j]的拼接是否为k的倍数。ans存答案。

考虑优化。

首先最外面那层循环肯定是去不掉了，因为我们一定要枚举所有数字。

那就只能看能否去掉内层的循环，也就是考虑如何快速求出与a[i]拼接起来为k的倍数的数字

要与a[i]拼接起来是k的倍数，那首先要考虑a[i]和a[j]拼起来是个啥玩意。

观察到a[i]与a[j]拼起来的结果即为 $a[i] \times 10 ^ {\lfloor \log _ {10}{a[j]} \rfloor + 1} + a[j]$

那要$a[i] \times 10 ^ {\lfloor \log _ {10}{a[j]} \rfloor + 1} + a[j]$ 是 k 的倍数，也就是要 $a[i] \times 10 ^ {\lfloor \log _ {10}{a[j]} \rfloor + 1} \% k + a[j] \% k$ 是 k 的倍数。

然后注意到 $a[i] \times 10 ^ {\lfloor \log _ {10}{a[j]} \rfloor + 1} \% k$ 这个数字是小于k的，而k最大是 $10 ^ 5$。

也就是说，我们是可以将其储存起来的。

所以我们可以开一个cnt数组，其中cnt[i][j]记录在之前遍历过的所有数中，乘 $10 ^ i$ 后模 k 的结果为 j 的数的个数。

然后对于所有的a[i]，累加 $cnt[\lfloor \log _ {10} a[i] \rfloor + 1][(k − a[i] \% k) \% k]$ 即可。

但这只能求出所有 $i < j$ 的合法的 a[i] 与 a[j] 的个数。
从前往后跑一遍，从后往前再跑一遍就可以辣~

时间复杂度

循环一遍 $1 \sim n$，的时间复杂度是 $\mathcal O(n)$ 的，
循环里面求 $\log_{10}x$ 的时间复杂度 $\mathcal O(\log _ {10} n)$，
所以总的时间复杂度是 $\mathcal O(n \log _ {10} n)$。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;
const int N = 100010;

int n, mod;     // n 即题目中 n，mod 即上述 k
ll ans;         // ans 存答案，由于最多会有 n ^ 2 中情况，所以需要开 ll
int a[N];       // a 存输入数据
int cnt[11][N]; // cnt 即上述数组 cnt

int log_10(int x) // 返回 1 + log10(x)
{
    int res = 0;
    while (x) x /= 10, res ++ ;
    return res;
}

void work()     // 从前往后跑一遍
{
    for (int i = 0; i < n; i ++ )
    {
        ans += cnt[log_10(a[i])][(mod - a[i] % mod) % mod]; // 累加 cnt
        for (int j = 0, power = 1; j < 11; j ++ ) // 将 a[i] 的 0 ~ 10 次方 % mod 的结果计入 cnt
        {
            cnt[j][power * 1ll * a[i] % mod] ++ ;
            power = power * 10 % mod;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &mod);
    for (int i = 0; i < n; i ++ )
        scanf("%d", a + i);

    work();

    memset(cnt, 0, sizeof cnt); // 别忘了在第二次跑之前清空一下 cnt 数组
    // 其实并不需要从前往后，从后往前写两遍。
    // 只需要将数组反转一下，再从前往后跑一遍即可
    reverse(a, a + n);

    work();

    printf("%lld\n", ans);
    return 0;
}