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

· · 题解

题意简述

给出 n 个整数 a_1 ∼ a_n，需要从中挑下标不同的两个数，例如挑选 12 和 345 可以拼接为 12345 或者 34512 ，问一共有多少种拼接方式使得拼接之后的数是 k 的倍数？

注意

拼接的顺序不同算不同的方案，即使 A_i 等于 A_j。

时间复杂度分析

#### 实现思路 考虑枚举加优化。 我们可以枚举后面这个数 $A_i$，枚举完 $A_i$ 之后，$A_i$ 就固定了，然后再枚举一下前面有多少种不同的选法，使得 $A_jA_i$ 这个数是 $k$ 的倍数。 用 $k_i$ 表示 $A_i$ 的位数，例如 $123$ $=$ $12$ $\times$ $10$ $+$ $3$，$A_i$ 的位数为 $1$ 位。 当我们枚举 $i$ 之后，$k_i$ 与 $A_i$ 都是固定的，变量就只剩下 $j$，相当于问有多少个 $j$ 使得 $A_j \times 10^{k_i} + A_i$ 恰好能够整除 $k$？ 可以用哈希表或者数组存储 ，所有数的范围是从 $1$ 到 $10^9$，位数最多是 $10$ 位。 开 $11$ 个哈希表，第 $u$ 个哈希表存储 $A_j \times 10^u \bmod k$，$u∈ (0,10)$ 的余数出现的次数。 预处理的时间复杂度为 $A_j$ 的个数 $n$ $\times$ $11$。 #### 公式推导 由 $A_i \times 10^{k_i} + A_i \equiv 0 \pmod k

得

A_j \times 10^{k_i} \equiv -A_i \pmod k

在第 ki 个哈希表中查找有多少个 A_j \times 10^{ki} \bmod k 的余数等于 -A_i，查询哈希表的时间复杂度为 O(1)。

本题步骤

  1. 枚举整体数组来预处理 s 数组。

  2. 再依次枚举这个数组中的每个数 A_i。然后在上述预处理之后的数组中找出一个或多个数字，这一个或多个数字 A_j 满足 A_j \times 10^ {k_i} == -A_i \bmod k。

  3. 其中每次算结果的时候需要判重。因为之前在计算预处理数组时候一定会枚举到自身，并将自身 \times 10 的 j 次方 \bmod k 存入到 s 数组中。因此在这次计算结果的时候一定就要判断有无自己，有则结果减 1。

一些细节

利用 res += s[len][(k - t) % k] 得到数学中的余数，例如在 C++ 中 -5 \bmod 3 = -2，而在数学中答案应该是 1

如果我们想得到余数 1，可以用 (k - t) % k，实现 (3 - (5 \bmod 3)) \bmod 3 = 1

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

using namespace std;

typedef long long LL;
const int N = 100010;

int n, m;
//用a数组存储每个数 k只有10^5 开一个数组当作哈希表即可
int a[N], s[11][N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    //枚举每个数 预处理哈希表
    for (int i = 0; i < n; i ++ )
    {
        LL t = a[i] % m;
        //枚举当前数在每种指数下%k的余数是多少
        for (int j = 0; j < 11; j ++ )
        {
            //第j个哈希表的余数是t
            s[j][t] ++ ;
            //幂次*10
            t = t * 10 % m;
        }
    }

    LL res = 0;
    for (int i = 0; i < n; i ++ )
    {
        LL t = a[i] % m;
        //求出ai的位数
        int len = to_string(a[i]).size();
        //位数为len 在第len个哈希表中查找有多少个 Aj 满足 Aj × 10^ki % k 的余数等于 -Ai
        res += s[len][(m - t) % m];
        //余数为(m - t) % m
        LL r = t;
        //判断Ai本身是否也在统计的范围内-> 计算 Ai × 10^ki % k 是否等于 Ai
        while (len -- ) r = r * 10 % m;
        //满足说明计算重复需要-1
        if (r == (m - t) % m) res -- ;
    }

    printf("%lld\n", res);

    return 0;
}