ABC226F Score of Permutations

Statement

F - Score of Permutations (atcoder.jp)

Solution

我们可以想到连边 \(i\to p_i\)

那么每一个点有出度 \(1\) ，最后显然会形成若干个环

于是，容易知道一个环的答案是它的长度，总的答案就是这若干个环长的 \(lcm\)

暴力枚举排列显然会炸掉，考虑 DP

设 \(dp[i][j]\) 表示使用 \(i\) 个点，现在形成的若干个环的 \(lcm=j\) ，的方案数，那么

\[dp[i+j][lcm^{\prime}=Lcm(lcm,j)]=\sum dp[i][lcm]*(j-1)!*\binom{n-i-1}{j-1} \]

即已经有 \(i\) 个点，新加入了一个 \(j\) 个点的环，对于环内的第一个点，下一个点有 \(j-1\) 种选择，\(\dots\) 。

那为什么是 \(\binom{n-i-1}{j-1}\) 而不是 \(\binom{n-i}{j}\) ？ 考虑以下两种选法：

橙色表示先选，蓝色后选，但是实际上两者是一样的

所以我们每次选环的时候强制让起点是当前最小的一个点，即提前拿出一个点作为起点，所以需要 \(-1\)

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;

int read(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}

map<int,int>dp[55];
int jc[55];
int n,k,ans;

int ksm(int a,int b){
    int res=1;
    while(b)((b&1)&&(res=res*a%mod,1)),a=a*a%mod,b>>=1;
    return res;
}
int C(int n,int m){
    return jc[n]*ksm(jc[m],mod-2)%mod*ksm(jc[n-m],mod-2)%mod;
}
int gcd(int n,int m){return m?gcd(m,n%m):n;}
int lcm(int n,int m){return n/gcd(n,m)*m;}

signed main(){
    n=read(),k=read();
    for(int i=jc[0]=1;i<=n;++i)
        jc[i]=jc[i-1]*i%mod;
    dp[0][1]=1;
    for(int i=0;i<n;++i)
        for(int j=1;i+j<=n;++j)
            for(auto v:dp[i])
                (dp[i+j][lcm(v.first,j)]+=v.second*jc[j-1]%mod*C(n-i-1,j-1)%mod)%=mod;
    for(auto v:dp[n])
        (ans+=v.second*ksm(v.first,k)%mod)%=mod;
    printf("%lld\n",ans);
    return 0;
}