T708004 G. 哈希表之线性探测 [Hello World 2026 蓝桥杯选拔赛]

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

typedef long long LL;
const int maxn = 200000 + 100;
const LL MOD = 998244353;
int n;
int num[maxn], son[maxn], fa[maxn], rt[maxn], deg[maxn];
bool vis[maxn];
LL dp[maxn], inv[maxn], pro[maxn], invpro[maxn];
vector<int> G[maxn];
queue<int> que;

void init() {
    inv[1] = 1;
    for(int i = 2; i < maxn; ++i) {
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    }
    pro[0] = invpro[0] = 1;
    for(int i = 1; i < maxn; ++i) {
        pro[i] = pro[i - 1] * i % MOD;
        invpro[i] = invpro[i - 1] * inv[i] % MOD;
    }
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
        rt[i] = i;
        vis[i] = false;
    }
}

LL C(int n, int m) {
    if(n < m) {
        return 0;
    }
    return pro[n] * invpro[m] % MOD * invpro[n - m] % MOD;
}

int Find(int *fa, int x) {
    return x == fa[x] ? x : fa[x] = Find(fa, fa[x]);
}

void unit(int *fa, int x, int y) {
    fa[Find(fa, x)] = Find(fa, y);
}

void dfs(int root, int fa) {
    dp[root] = 1;
    for (int pos : G[root]) {
        if (pos == fa) {
            continue;
        }
        dfs(pos, root);
        dp[root] = dp[root] * C(son[root] + son[pos], son[pos]) % MOD * dp[pos] % MOD;
        son[root] += son[pos];
    }
    ++son[root];
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n;
    assert(1 <= n && n <= 100000);
    init();
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        assert(-1 <= num[i] && num[i] <= 1000000000);
        if (num[i] != -1 && num[i] % n == i) {
            que.push(i);
            vis[i] = true;
        }
    }
    while (!que.empty()) {
        int tmp = que.front();
        que.pop();
        unit(fa, tmp, (tmp + 1) % n);
        int idx = Find(fa, tmp);
        if (vis[idx] || num[idx] == -1) {
            continue;
        }
        if (Find(fa, num[idx] % n) != idx) {
            continue;
        }
        vis[idx] = true;
        que.push(idx);
        int s = num[idx] % n;
        while ((s = Find(rt, s)) != idx) {
            G[idx].push_back(s);
            unit(rt, s, idx);
            ++deg[s];
            s = (s + 1) % n;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (num[i] != -1 && deg[i] == 0) {
            G[n].push_back(i);
        }
    }
    dfs(n, n);
    cout << dp[n] << endl;

    return 0;
}