题解：P8143 [JRKSJ R4] Stirling

lailai0916 · 2022-02-12 13:45:28 · 题解

解题思路

对于任意一个排列的生成图，交换其中两个数的位置，会使环的数量增加或减少 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;
}