算法
(dfs找环) $O(n)$
记 $C$ 为由函数 $f$ 构成的环的数量,由于环之间相互独立,所以本题的答案为 $2^C - 1$。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
const int mod = 998244353;
vector<int> st, f;
bool dfs(int v) {
if (st[v]) return st[v] == 1;
st[v] = 1;
bool res = dfs(f[v]);
st[v] = 2;
return res;
}
int main() {
int n;
cin >> n;
f.resize(n);
rep(i, n) cin >> f[i], --f[i];
st.resize(n);
int ans = 1;
rep(i, n) if (dfs(i)) (ans *= 2) %= mod;
ans -= 1;
cout << ans << '\n';
return 0;
}