给你一个由 \(n\) 个正整数组成的数组 \(a\) 。
我们把数字 \(x\) 和 \(y\) 的并集称为数字 \(x\) 和 \(y\) 的并集,即把数字 \(x\) 和 \(y\) 在不改变顺序的情况下一个接一个地写下所得到的数字。例如,数字 \(12\) 和 \(3456\) 的并集就是数字 \(123456\) 。
计算数组 \((i, j)\) ( \(i \neq j\) )中位置 \((i, j)\) ( \(i \neq j\) )的有序数对的个数。( \(i \neq j\) ),使得数组 \(a\) 中的 \(a_i\) 和 \(a_j\) 的连集能被 \(k\) 整除。
( \(1 \le n \le 2 \cdot 10^5\) 、 \(2 \le k \le 10^9\) )
\(n^2\)显然是不行的
然后我们通过观察可以发现 ,当拼起来的俩数都是 \(k\)的倍数的时候 这个拼起来的数一定是 k的倍数
假设后面的\(X\)长度为\(l\), \(X\%k=t\)
那么 $前面的数*10^l\ %k $ 可以\(O(n)\)的枚举
与之对应的可以枚举 位数,然后就可以得到对应的模数
然后我们用前缀和对应的思想 将这些模数的个数离线存储起来
便可以用 \(O(10nlogn)\)的复杂度解决了