自动搬运

查看原文

来自洛谷，原作者为

	qiuqiuyaq 一枚蒟蒻的红题选手

搬运于2025-08-24 22:41:42，当前版本为作者最后更新于2023-03-08 21:51:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述

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

注意

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

时间复杂度分析

$n$ 为 $10^5$ 时间复杂度要控制在 $\mathcal{O}(n \log n )$ 以内。

实现思路

考虑枚举加优化。

我们可以枚举后面这个数 $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;
}