摘要
Title: 2068. 整数拼接
Tag: 哈希表、模拟
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

2068. 整数拼接

• 题意

  给定一个长度为 n 的数组 A1,A2,⋅⋅⋅,An。
  你可以从中选出两个数 Ai 和 Aj(i 不等于 j)，然后将 Ai 和 Aj 一前一后拼成一个新的整数。
  例如 12 和 345 可以拼成 12345 或 34512。
  注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法，即便是 Ai=Aj 时。
  请你计算有多少种拼法满足拼出的整数是 K 的倍数。

• 思路

  思路比较简单
  当遍历每个数时，去哈希表中找所有位数的数模k的余数，比如遍历到了12，在哈希表中找到了345（其实里面存的时345 % k），那么12需要乘345的位数，得到的结果模k，如果两者的模k结果加起来模k等于0，那么这就是一种方案。最后把12也放入对应位数的哈希表中（题目最多10位，所以开11个哈希表即可），即d[2][12 % k] += 1

  正序走一遍，每个数都当了前缀，所以需要逆序走一遍，让它们当一次后缀

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-04-07 19:15:23
  FilePath: \ACM\Acwing\2068.py
  LastEditTime: 2022-04-07 19:22:52
  '''
  from math import log10
  from collections import Counter
  
  d = [Counter() for _ in range(11)]
  
  n, k = map(int, input().split())
  a = list(map(int, input().split()))
  ans = 0
  #正序
  for i in a:
      for j in range(11):
          ans += d[j][(k - (i * (10**j) % k)) % k]
      d[int(log10(i) + 1)][i % k] += 1
  #逆序
  a = a[::-1]
  d = [Counter() for _ in range(11)]
  for i in a:
      for j in range(11):
          ans += d[j][(k - (i * (10**j) % k)) % k]
      d[int(log10(i) + 1)][i % k] += 1
  print(ans)