問題文で与えられた条件は、次のどちらかが成り立つことと同値です。

• \(a_i = i\) かつ \(a_j = j\)
• \(a_i = j\) かつ \(a_j = i\)

前者が成り立つような組の総数は、\(a_k = k\) であるような \(k\) の個数を \(n\) として \(\frac{n(n - 1)}{2}\) です。

後者については、\(a_i = j\) より \(i\) を固定すると \(j\) は \(1\) 通りに定まるので、\(a_i \neq i\) であるような \(i\) を全て試すことで総数を求めることができます。

以上により、時間計算量 \(O (N)\) でこの問題を解くことができました。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int same = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] -= 1;
        if (a[i] == i) {
            same += 1;
        }
    }
    long long ans = (long long)same * (same - 1) / 2;
    for (int i = 0; i < n; ++i) {
        if (a[i] > i and a[a[i]] == i) {
            ans += 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

実装例 (Python)

n = int(input())
a = list(map(int, input().split()))

for i in range(n):
  a[i] -= 1

same = 0
for (i, x) in enumerate(a):
  if i == x:
    same += 1

ans = same * (same - 1) // 2
for (i, j) in enumerate(a):
  if i < j and a[j] == i:
    ans += 1

print(ans)