摘要
Title: 1230. K倍区间
Tag: 前缀和
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1230. K倍区间

• 题意

  给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
  你能求出数列中总共有多少个 K 倍区间吗？

• 思路

  枚举右端点i，用前缀和优化，也就是问对于此右端点i，有多少对$(i, j)$满足$(s[i] - s[j]) \% k == 0 (j\in[0, i - 1])$
  已知

  $$[(s[i] - s[j]) \% k == 0 ]\equiv [s[i] \% k - s[j] \% k == 0]$$

  那么题目就转化为了，求$s[i]$前面多少个数，和$s[i]$模$k$同余
  那么就可以用哈希表来动态记录即可，复杂度$O(n)$

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-23 10:51:14
  FilePath: \ACM\Acwing\1230.py
  LastEditTime: 2022-03-23 10:51:14
  '''
  N = int(1e5 + 10)
  
  from collections import Counter
  
  s = [0] * N
  d = Counter()
  
  n, k = map(int, input().split())
  ans = 0
  d[0] = 1
  for i in range(n):
      s[i] = int(input())
      s[i] += s[i - 1]
      ans += d[s[i] % k]
      d[s[i] % k] += 1
  
  print(ans)