题解：AT_abc226_f [ABC226F] Score of Permutations

Solution

考虑每个人

i

向自己的

P_i

连边，由于

P

是一个排列，所以每个点入度为

1

，出度为

1

，也就是说图由若干个环组成。进一步地，每个环在变换它的大小的次数后会恢复原样，因此对于一个排列

P

连成的图，

S(P)

等于所有环的大小的

\operatorname{lcm}

。

对于计算答案，可以考虑枚举有一些什么样的环。更具体地，从大到小 dfs 枚举环的大小加入答案。当我们加入一个大小为

i

的环时，相当于从剩下的点里选

i

个，让它们组成圆排列，注意如果有若干个大小相同的环，还要减去这些环重复的情况。细节可结合代码理解。

由于我们是从大到小枚举环，dfs 的次数是不多的。经测试，当

n=50

时，一共进行了

1295971

次 dfs。

Code

CPP

#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;
}

题解：AT_abc226_f [ABC226F] Score of Permutations

文章操作

Solution

Code

相关推荐

评论

题解：AT_abc226_f [ABC226F] Score of Permutations