题解：AT_abc387_f [ABC387F] Count Arrays

player_1_Z · 2025-01-12 10:33:47 · 题解

先来理解题目

atcoder 原题

思路

我们发现，既然 x_i \le x_{A_i} 那么不妨让 x_i 指向 x_{A_i}，这样就组成了基环树森林。然后开一个 dp 数组，dp^i_j 存以 i 点为根且数字为 j 时的子树造成的贡献。那么就可以从每个基环树的叶子节点往上传贡献直到环（这个过程中需要用前缀和把 i 点为每个数字时的总贡献统计在一起，不然会超时）。最后统计每个环的总贡献并输出。

代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long n,m,a[2035],dp[2035][2035],as[2035][2035],q;
long long k,on_huan[2035],shendu[2035],shuenxu_dp[2035],fa[2035];
vector<int> son[2035];
bool find_huan(int x){//找环 
    int g=fa[x];
    for(int i=0;i<=n;i++){
        if(g==x){
            ++k;
            for(int i=0;i<=n;i++){
                on_huan[g]=k;
                g=fa[g];
            }
            return 1;
        }
        g=fa[g];
    }
    return 0;
}
void find_shendu(int x,int shen=0){//找深度
    shendu[x]=shen;
    for(int j:son[x]) if(j!=fa[x]&&on_huan[j]==0) find_shendu(j,shen+1);
}
bool cmp(int x,int y){
    return shendu[x]>shendu[y];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>fa[i];
        son[fa[i]].push_back(i);
        shuenxu_dp[i]=i;
    }
    for(int i=1;i<=n;i++) if(on_huan[i]==0) find_huan(i);
    for(int i=1;i<=n;i++) if(on_huan[i]) find_shendu(i);//环不能找 
    sort(shuenxu_dp+1,shuenxu_dp+1+n,cmp);//按深度从大到小排序 
    //初始化
    for(int i=0;i<=2033;i++) for(int j=0;j<=2033;j++) as[i][j]=dp[i][j]=1; 
    for(int i=1;i<=n;i++){//dp转移（非环） 
        #define x shuenxu_dp[i]
        long long sum=0;
        if(on_huan[x]==0)
            for(int j=1;j<=m;j++)
                sum=(sum+dp[x][j])%mod,dp[fa[x]][j]=sum*dp[fa[x]][j]%mod;
        #undef x
    }
    for(int i=1;i<=n;i++){//dp转移（环） 
        if(on_huan[i]) 
            for(int j=1;j<=m;j++)
                as[on_huan[i]][j]=as[on_huan[i]][j]*dp[i][j]%mod;
    }
    long long ans=1;
    for(int i=1;i<=k;i++){//统计总数 
        long long sum=0;
        for(int j=1;j<=m;j++){
            sum+=as[i][j];
            sum%=mod;
        }
        ans*=sum;
        ans%=mod;
    }
    cout<<ans;
    return 0;
}