2023-02-27

题目传送门

翻译

难度&重要性(1~10):4

题目来源

AtCoder

数学

先对整个序列求前缀和 \(sum_k=\sum_{i=1}^{k}a_i\)

题目求有多少对 \((l,r)\) 满足 \(sum_r-sum_l\equiv r-l \mod k\)

移项得 \(sum_r-r\equiv sum_l-l \mod k\)

那么使用一个 \(mp\) 存储 \(sum_l-l\) 的差，枚举右端点求和即可。

(\(mp[0]\) 要赋初值为 \(1\))

已完成