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

zyxjeek · 2025-01-13 21:15:31 · 题解

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 的倍数。

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.代码

#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