1863G - Swaps - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int N = 1e6 + 100;
const ll MOD = 1e9 + 7;

int n, a[N], in[N], bio[N];

inline ll mul(ll x, ll y){
	return (x * y) % MOD;
}

inline ll add(ll x, ll y){
	if (x + y >= MOD) return (x + y - MOD);
	return (x + y);
}

inline ll diff(ll x, ll y){
	if (x < y) return (x - y + MOD);
	return (x - y);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; ++i){
		cin >> a[i]; ++in[a[i]];
	}
	
	vector<int> cycle; int cnt = 1;
	for (int i = 1; i <= n; ++i){
		if (bio[i] > 0) continue;
		int x = i;
		while (bio[x] == 0)
			bio[x] = cnt, x = a[x];
		if (bio[x] == cnt)
			cycle.pb(x);
		++cnt;
	}
	
	ll sol = 1; memset(bio, 0, sizeof(bio));
	for (int x: cycle){
		int y = x, deg_sum = 0;
		ll M = 1;
		while (!bio[y]){
			M = mul(M, in[y] + 1);
			deg_sum += in[y];
			bio[y] = 1; y = a[y];
		}
		sol = mul(sol, diff(M, deg_sum));
	}
	
	for (int i = 1; i <= n; ++i){
		if (!bio[i]) sol = mul(sol, in[i] + 1);
	}
	
	cout << sol;
	
	return 0;
}