P8712 [蓝桥杯 2020 省 B1] 整数拼接

发表于 更新于 阅读次数：

1.题目描述

给定一个长度为 \(n\) 的数组 \(A_1,A_2,\cdots,A_n\)。你可以从中选出两个数 \(A_i\) 和 \(A_j\)（\(i\neq j\)），然后将 \(A_i\) 和 \(A_j\) 一前一后拼成一个新的整数。例如 12 和 345 可以拼成 12345 或 34512。注意交换 \(A_i\) 和 \(A_j\) 的顺序总是被视为 \(2\) 种拼法，即便是 \(A_i=A_j\) 时。

请你计算有多少种拼法满足拼出的整数是 \(K\) 的倍数。

原题链接：https://www.luogu.com.cn/problem/P8712

2.思路

由于 \(1 \le n \le 10^5\)，使用时间复杂度为 \(\mathcal O(n^2)\) 的算法枚举每种拼接显然不可行。面对这个问题，我们需要一种储存数组 \(A\) 中信息的方法，可以让我们在每次遍历 \(A_i\) 时以较少的时间复杂度得知能与 \(A_i\) 拼接的整数个数。

设数组中两个元素 \(A_j\) 和 \(A_i\) 的数字位数分别为 \(v\) 和 \(u\)，因为拼接后的数是 \(K\) 的倍数，所以有 \(A_j \cdot 10^u + A_i \equiv 0 \pmod K\)，即 \(A_j \cdot 10^u \equiv -A_i \pmod K\)。由于 \(A_i \le 10^9\)，即 \(A_i\) 最多有十位，我们可以开 \(10\) 个哈希表，对于第 \(p\) 个哈希表，存储 \(A_i \cdot 10^u \mod K\) 的每个值出现的次数。这样我们在遍历时就能用哈希表里的值进行快速相加了。

3.注意事项

  • 由于 \(K \le 10^5\)，我们把两个模 \(K\) 的余数相乘时会超出int的范围。此外拼接方法的总数在极限情况下也会超出int的范围。所以记得开long long。

  • 按以上方法计算会多算到自己与自己拼接的情况。所以当 \(A_i \cdot 10^u + A_i \equiv 0 \pmod K\) 时，要把答案减 \(1\)。

  • 可以用log10(x) + 1快速计算 \(x\) 的数字位数。

4.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
int n, k, a[N];
long long pw[11]; // 10^u % k
unordered_map<int, int> mp[11];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    pw[0] = 1;
    for (int i = 1; i <= 10; i++)
        pw[i] = (pw[i-1] * 10) % k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = 1; j <= 10; j++)
            mp[j][a[i] * pw[j] % k]++;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int len = log10(a[i]) + 1, mod = (k - a[i] % k) % k; // mod等价于数学上的-a[i] mod k
        ans += mp[len][mod];
        if (a[i] * pw[len] % k == mod)
            ans--;
    }
    cout << ans << endl;
    return 0;
}

5.复杂度分析

时间复杂度：\(\mathcal O(n \log_{10} \max A_i)\)

The End