P8143 Stirling 题解

· · 题解

题意：

给你一个 n ，要你求出由 n 个点和 n 条边组成的图，点的度数为 2 并且图中恰好含有偶数个环的方案数。

思路：

可以发现改变排列中的某一个数的时候，环的数量也会随之改变。一个偶数环排列交换某两项后变成了一个奇数环排列，一个奇数环排列交换某两项后变成了一个偶数环排列，说明两个排列之间构成了双射。

证明：

如果两项在两个环中，将会把两个环裂开并且把两个裂开的环的头尾相连导致两个环变为一个，环数将会减一。

如果两项在一个环中，将会把环断成两个环并将每个环的头尾相连导致一个环变成两个，环数将会加一。

综上所述，在任何情况下环的奇偶性都会改变。

因为偶数环数量加上奇数环数量等于所有排列，奇偶环的数量又是相同的，所以得出结论：答案等于 \frac{n!}{2} 。

注意：除法取模要用被除数乘以除数的逆元，所以要乘以 2 的逆元。

代码：

#include <bits/stdc++.h>
const int MOD=998244353;
using namespace std;
long long n,ans=1;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)ans=ans*i%MOD;
    cout<<ans*499122177%MOD;
    return 0;
}