题解 | 谐距下标对

C++ 一方面暴力枚举易超时，另一方面计算下标对要用 (unsigned) long long 才够用

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a;
    while (n--) {
        int ai;
        cin >> ai;
        a.push_back(ai);
    }
    // aj-ai==j-i ==> aj-j==ai-i
    // 即 新数组 b = [a1-1, a2-2, ..., an-n] 中，满足 i<j 且 bi=bj 
    // 统计 bi=bj=k 出现的次数 m 其下标对数为 C(m,2)=m*(m-1)/2
    map<int, unsigned long long> b;
    for (int i=0; i<a.size(); i++) {
        // cout << a[i]-i << endl;
        b[a[i]-i]++;
    }
    unsigned long long cnt=0;
    for (auto i : b) {
        if (i.second>1) {
            cnt += i.second*(i.second-1)/2;
        }        
    }
    cout << cnt;
}
// 64 位输出请用 printf("%lld")