2023-03-03
题目
翻译
难度&重要性(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\))
完成状态
已完成