题解 | #小红的部分不同字符串#

假设每个条件都是 $i$ 向 $a_i$ 连接一条边, 那么最终构成的是基环树森林

对于一个 $n$ 元环, 假设有 $k$ 个颜色, 求染色方案数, 首先将环展开为链, 那么方案数为 $k \times (k - 1) ^ {n - 1}$

最后一个位置还需要和第一个位置链接起来

假设 $n$ 元环的染色方案记为 $f_n$

假设 $n - 1$ 位置颜色和 $1$ 位置不同, 那么 $n$ 位置的颜色, 那么就是前 $n - 1$ 个位置染色, 方案数是 $f_{n - 1} \times (k - 2)$
假设 $n - 1$ 位置颜色和 $1$ 位置相同, 那么就是前 $n - 2$ 个位置染色, 方案数是 $f_{n - 2} \times (k - 1)$

得到递推式 $f_n = f_{n - 1} \times (k - 2) + f_{n - 2} \times (k - 1)$

然后通过拓扑排序找出环

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 2e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream& operator>>(istream& is, i128& val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char& c : str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream& operator<<(ostream& os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

LL qpow(LL a, LL b) {
    LL ans = 1;
    a %= MOD;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

struct EDSU {
    int n;
    vector<int> p;
    vector<int> sz;
    EDSU(int _n) : n(_n), p(_n), sz(_n) {
        for (int i = 0; i < _n; ++i) {
            p[i] = i;
            sz[i] = 1;
        }
    };

    int find(int x) {
        if (p[x] != x) return p[x] = find(p[x]);
        return p[x];
    }

    void merge(int x, int y) {
        int fa1 = find(x), fa2 = find(y);
        if (fa1 == fa2) return;
        p[fa2] = fa1;
        sz[fa1] += sz[fa2];
    }
};
void solve() {
    int n;
    cin >> n;
    EDSU d(n + 1);
    vector<int> a(n + 1);

    vector<int> ideg(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ideg[a[i]]++;
        d.merge(i, a[i]);
    }

    vector<LL> f(n + 1);
    f[1] = 0;
    f[2] = 650;
    for (int i = 3; i <= n; ++i) f[i] = (f[i - 1] * 24ll % MOD + f[i - 2] * 25ll % MOD) % MOD;

    queue<int> q;
    vector<int> inc(n + 1, 1);
    for (int i = 1; i <= n; ++i) {
        if (!ideg[i]) {
            q.push(i);
        }
    }

    while (q.size()) {
        int u = q.front();
        q.pop();
        inc[u] = 0;

        int v = a[u];
        if (--ideg[v] == 0) q.push(v);
    }

    vector<int> sz(n + 1);
    for (int i = 1; i <= n; ++i) {
        if (inc[i]) {
            int fa = d.find(i);
            sz[fa]++;
        }
    }

    LL ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (i != d.find(i)) continue;
        LL cur = qpow(25ll, d.sz[i] - sz[i]) * f[sz[i]] % MOD;
        ans = ans * cur % MOD;
    }

    cout << ans << '\n';

/**/ #ifdef LOCAL
    cout << flush;
/**/ #endif
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}