题解：AT_abc226_f [ABC226F] Score of Permutations

__FL__ · 2025-08-13 11:18:50 · 题解

Solution

考虑每个人 i 向自己的 P_i 连边，由于 P 是一个排列，所以每个点入度为 1，出度为 1，也就是说图由若干个环组成。进一步地，每个环在变换它的大小的次数后会恢复原样，因此对于一个排列 P 连成的图，S(P) 等于所有环的大小的 \operatorname{lcm}。

对于计算答案，可以考虑枚举有一些什么样的环。更具体地，从大到小 dfs 枚举环的大小加入答案。当我们加入一个大小为 i 的环时，相当于从剩下的点里选 i 个，让它们组成圆排列，注意如果有若干个大小相同的环，还要减去这些环重复的情况。细节可结合代码理解。

由于我们是从大到小枚举环，dfs 的次数是不多的。经测试，当 n=50 时，一共进行了 1295971 次 dfs。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 55,M = 998244353;
int n,k,fac[N],ifac[N],ans;
int qpow(int a,int b)
{
    int ret = 1;
    while (b)
    {
        if (b&1) (ret *= a) %= M;
        (a *= a) %= M;
        b >>= 1;
    }
    return ret;
}
inline int inv(int a)
{
    return qpow(a,M-2);
}
inline int C(int a,int b)
{
    return fac[a]*ifac[b]%M*ifac[a-b]%M;
}
inline int cirA(int a,int b)
{
    return fac[a]*ifac[a-b]%M*inv(b)%M;
}
int gcd(int a,int b)
{
    if (!b) return a;
    return gcd(b,a%b);
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
void dfs(int u,int num,int sum,int p,int lc)
{
    if (!num)
    {
        (ans += sum*ifac[p]%M*qpow(lc,k)) %= M;
        return;
    }
    if (num >= u) dfs(u,num-u,sum*cirA(num,u)%M,p+1,lcm(lc,u));
    for (int i = 1; i <= min(u-1,num); i++)
        dfs(i,num-i,sum*cirA(num,i)%M*ifac[p]%M,1,lcm(lc,i));
}
signed main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i-1]*i%M,ifac[i] = inv(fac[i]);
    cin >> n >> k;
    dfs(n,n,1,0,1);
    cout << ans;
    return 0;
}