P8143 [JRKSJ R4] Stirling

解题思路

对于任意一个排列的生成图，交换其中两个数的位置，会使环的数量增加或减少 $1$。

证明：交换的两个数如果在同一个环中，这个环会分裂成两个环；如果不在同一个环中，两个环会合并成一个环。

这说明奇数个环和偶数个环的数量相同，因此答案为 $\frac{n!}{2}$。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int mod=998244353;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll n;
	cin>>n;
	ll ans=1;
	for(int i=3;i<=n;i++)ans=ans*i%mod;
	cout<<ans<<'\n';
	return 0;
}