蓝桥杯2020年第十一届省赛真题-整数小拼接python解法应该怎么做？

Question

蓝桥杯2020年第十一届省赛真题-整数小拼接python解法应该怎么做？

给定一个长度为 n 的数组 A1,A2,.,An。

你可以从中选出两个数 Ai 和 Aj(i 不等于 j)，然后将 Ai 和 Aj 一前一后拼成一个新的整数。

例如 12 和 345 可以拼成 12345 或 34512。

注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法，即便是 Ai=Aj 时。

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

输入格式
第一行包含 2 个整数 n 和 K。

第二行包含 n 个整数 A1,A2,.,An。

输出格式
一个整数代表答案。

数据范围
1≤n≤105,
1≤K≤105,
1≤Ai≤109
输入样例：
4 2
1 2 3 4
输出样例：
6

Answer 1

引自免费微信小程序：皆我百晓生

为了实现蓝桥杯2020年第十一届省赛真题——整数小拼接的Python解法，我们可以按照以下步骤进行：

1. 读取输入数据

   • 读取第一行得到两个整数n和K。
   • 读取第二行得到长度为n的整数列表A。

2. 预处理数组

   • 对于数组中的每个元素Ai，将其转换成字符串并计算它对K的模余数。这样我们就可以快速判断一个数字前后拼接是否满足是K的倍数。

3. 统计结果

   • 使用哈希表（字典）存储每个模余数出现的次数。
   • 遍历哈希表，对于每一个模余数r，找到其互补模余数（K-r），如果存在互补模余数且次数大于0，则将结果累加（注意每一对贡献2种拼接方式）。

4. 输出答案

   • 输出统计结果作为最终答案。

下面是根据上述思路编写的完整Python代码：

def count_combinations(n, k, nums):
    # 预处理，记录每个余数出现的次数
    remainder_count = {i: 0 for i in range(k)}
    for num in nums:
        remainder = str(num) % k
        remainder_count[remainder] += 1

    # 统计满足条件的组合数量
    result = 0
    for remainder, count in remainder_count.items():
        complementary_remainder = (k - remainder) % k
        if complementary_remainder in remainder_count:
            # 每一对可以形成两种拼接方式
            result += count * remainder_count[complementary_remainder]

    return result


# 示例：读取输入数据
input_str = """
4 2
1 2 3 4
"""

lines = input_str.strip().split('\n')
n, k = map(int, lines[0].split())
nums = list(map(int, lines[1].split()))

# 调用函数计算答案
answer = count_combinations(n, k, nums)
print(answer)

# 根据题目示例，应该输出6

请确保你已经正确地将输入数据替换到input_str变量中。在实际提交或运行时，请使用标准输入流（如sys.stdin）来读取数据，以适应在线评测系统的要求。