BISHI24　谐距下标对¶

入门通过率 30.61%python3样例通过牛客 AC排序

一句话

统计满足 i < j 且 a_j - a_i = j - i 的下标对数量。

解题思路¶

这题考什么¶

移项，把「一对下标之间的关系」改写成「同一个量相等」：

a_j - a_i = j - i   <=>   a_j - j = a_i - i

令 b_i = a_i - i，条件就退化成 b_i = b_j，与 i、j 谁大谁小无关。于是答案不再需要枚举下标对，而是「每一种 b 值内部两两配对」的总数：

答案 = Σ C(c, 2) = Σ c * (c - 1) / 2，其中 c 是该 b 值出现的次数。

「把成对条件改写成单点特征，再用计数代替枚举」是计数类问题的通用手法，桶计数与离散化见 41-桶计数与离散化。

数据规模与复杂度¶

n <= 1e5。两重循环枚举 (i, j) 要做 n*(n-1)/2 ≈ 5e9 次判断，必然超时；改成计数后只遍历一遍，O(n) 时间、O(n) 空间。

坑在哪¶

b_i = a_i - i 可能是负数（a_i >= 1，而 i 最大到 1e5），所以用哈希表计数，而不是拿它当数组下标——那样会索引到负值区间。
下标从 0 还是从 1 开始都不影响答案：整体平移 b 不改变「哪些 b 相等」。代码里 enumerate 默认从 0 起算，正是利用了这一点，不必再做 +1 校正。
配对数写 c * (c - 1) // 2，用整除。写成 / 2 会变成浮点， c 接近 1e5 时结果约 5e9，既有精度风险，输出还会多出 .0。
答案量级最大 C(1e5, 2) ≈ 5e9，超出 32 位；C/C++ 要开 long long， Python 的整数无上限，不用管。

样例复核¶

a = [1,2,3,4,5,6]，b_i = a_i - i 恒等于同一个值，6 个下标全同组，答案 C(6,2) = 15，与样例一致。

参考实现¶

solutions/BISHI24.py
import sys
from collections import Counter

data = sys.stdin.buffer.read().split()
n = int(data[0])
# b = a_i - i：把「a_j - a_i = j - i」化为「b 值相同」，再按 b 值分桶计数
cnt = Counter(int(v) - i for i, v in enumerate(data[1:n + 1]))
# 同一个 b 值出现 c 次就贡献 C(c, 2) 对，累加即为答案
print(sum(c * (c - 1) // 2 for c in cnt.values()))

BISHI24 谐距下标对¶