Submission #62317283

---

Source Code Expand

#include <bits/stdc++.h>
//#define int long long 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
mt19937_64 rnd(time(0));

const int N = 2e3 + 50;
const int MOD = 998244353;

int n,m;
int a[N];
ll dp[N][N], dps[N][N]; // dp[i][j]表示结点i上的数字为j时的方案数

vector<int> G[N], G0[N];
bool st[N][N]; //避免对新图建重边
int din[N], dout[N]; // 新图上的点的入度和出度

int dfn[N],tim;//时间戳数组
int low[N];//low[u]表示从结点u出发，可以通过返祖边和横叉边回溯到的最小dfn
int stk[N],top;//栈，维护已经遍历过但还未被算进某个强联通分量内的结点
bool instk[N];//标记一个节点是否在当前栈中
int scc[N],cnt_scc;//scc[u]==x表示结点u在第x个强联通分量中,cnt表示当前强联通分量的个数
int siz[N];//siz[i]表示第i个强联通分量内点的个数

void Tarjan_scc(int u)
{
    dfn[u]=low[u]=++tim;
    stk[++top]=u;
    instk[u]=1;
    for(auto v:G[u]){
        if(!dfn[v]){ //若下一个点没有走过，则直接递归深搜这个点
            Tarjan_scc(v);
            low[u]=min(low[u],low[v]);//v能回溯到的点,u也一定能回溯到
        }
        else if(instk[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){//在当前点的所有出边遍历完后，判断dfn与low是否相等。若相等则说明找到了强联通分量的顶端，开始弹栈并统计该强联通分量
        cnt_scc++;
        int x;//表示栈顶元素，每次弹出的点均属于同一个强联通分量
        do{
            x=stk[top--];
            instk[x]=0;
            scc[x]=cnt_scc;
            siz[cnt_scc]++;
        }while(x!=u);
    }
}


void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        G[i].pb(a[i]);
    }
    
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) Tarjan_scc(i);
    }

    for(int u = 1; u <= n; u++){
        for(auto v : G[u]){
            if(scc[u] != scc[v]){
                st[scc[u]][scc[v]] = true;
                G0[scc[u]].pb(scc[v]);
                dout[scc[u]]++;
                din[scc[v]]++;
            }
        }
    }

    int n0 = cnt_scc;
    auto Topo = [&]() -> void{
        queue<int> q;
        for(int i = 1; i <= n0; i++){
            for(int j = 1; j <= m; j++){
                dp[i][j] = 1;
                dps[i][j] = dps[i][j - 1] + dp[i][j];
            }
            if(!din[i]){
                q.push(i);
            }
        }
        while(q.size()){
            int u = q.front();
            q.pop();
            for(auto v : G0[u]){
                for(int j = 1; j <= m; j++){
                    dp[v][j] = (dp[v][j] * dps[u][j]) % MOD;
                }
                din[v]--;
                if(din[v] == 0){
                    for(int j = 1; j <= m; j++){
                        dps[v][j] = (dps[v][j - 1] + dp[v][j]) % MOD;
                    }
                    q.push(v);
                }
            }
        }
    };

    Topo();

    ll ans = 1;
    for(int i = 1; i <= n0; i++){
        if(!dout[i]){
            ans = (ans * dps[i][m]) % MOD;
        }
    }

    cout << ans << endl;
}


signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1; //cin>>T;
    while(T--) solve();
    return 0;
}

Submission Info

Judge Result