Submission #61393739

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 5505, M = 3*N;
const int mod = 998244353;

int n, m;
int a[N];
vector<int> e[N], g[N];
vector<pair<int,int>> v[N];

int head[M],to[M],nxt[M],etot=1;
bool cut[M];
int dft,low[N],dfn[N];

int cnt, f[N];
int bel[N];

void add(int x,int y){
    to[++etot]=y;
    nxt[etot]=head[x];
    head[x]=etot;
}

void tarjan(int x,int lst){
    dfn[x]=low[x]=++dft;
    for(int i=head[x];i;i=nxt[i]) if(i!=lst) {
        int y=to[i];
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[y]){
                cut[i]=cut[i^1]=1;
            }
        }else{
            low[x]=min(low[x],dfn[y]);
        }
    }   
}

void dfs1(int x, int beg){
    bel[x] = beg;
    f[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(!cut[i] && !f[y]) {
            dfs1(y, beg); 
        }
    }
}


int vis2[N];
ll dp[N][N], sm[N][N];

void dfs(int now, int fa) {
    vis2[now] = 1;
    for (auto i : v[now]) if (i.first != fa) dfs(i.first, now);
    for (int i = 1; i <= m; i++) {
        dp[now][i] = 1;
        for (auto tt : v[now]) {
            int j = tt.first, tp = tt.second;
            if (j == fa) continue;
            if (tp == 0) (dp[now][i] *= sm[j][i]) %= mod;
            else (dp[now][i] *= (sm[j][m] - sm[j][i-1] + mod) % mod) %= mod;
        }
        (sm[now][i] = sm[now][i - 1] + dp[now][i]) %= mod;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i]), add(a[i], i);
        e[a[i]].push_back(i);
        e[i].push_back(a[i]);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i, 0);
        }
    }

    for(int i=1;i<=n;i++){
        if(!f[i]){
            dfs1(i, (++cnt));
        }
    }

    // for (int i = 1; i <= n; i++) cout << bel[i] << ' '; cout << '\n';

    for (int i = 1; i <= n; i++) {
        if (bel[i] == bel[a[i]]) continue;
        g[bel[a[i]]].push_back(bel[i]);
        v[bel[a[i]]].push_back({bel[i], 0});
        v[bel[i]].push_back({bel[a[i]], 1});
    }


    ll ans = 1;

    for (int i = 1; i <= cnt; i++) {
        if (!vis2[i]) {
            dfs(i, 0);
            (ans *= sm[i][m]) %= mod;
        }
    }
    cout << ans;


    
    
    
    return 0;
}

Submission Info

Judge Result