挑战赛#30 T2 题解

对于卡片对 $(i,j)$，有以下两种情况：

1. $a_i=i,a_j=j$；
2. $a_i=j,a_i=i$。

两种情况分开求即可。

对于第一种情况：
枚举满足 $a_i=i$ 的 $i$ 的数量，记为 $x$，答案为 $\large{C_x^2=\frac{x!}{2(x-2)!}=\frac{x(x-1)}{2}}$。

对于第二种情况：
只需枚举满足 $a_{a_i}=a_i\ (i<a_i)$ 的 $i$ 的数量即可。

注意两种情况不要重复计算。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int n,ans;
int a[N],vis[N];
signed main(){
	cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        if (a[i]==i){
            ans++;
            vis[i]=1;
        }
    }
    ans=ans*(ans-1)/2;
    for (int i=1;i<=n;i++){
        if (!vis[i]&&a[a[i]]==i&&i<a[i]){//vis[i] 避免两种情况重复计算
            ans++;
        }
    }
    cout<<ans;
	return 0;
}