题解 P8143【[JRKSJ R4] Stirling】

qfpjm · 2022-02-16 13:59:11 · 题解

• 虽然赛时是猜结论的，但后来还是弄懂了。

题解

• 先给出结论：\frac{n!}{2}。

• 为什么？

• 因为，当我们改变排列 p 中的一个数时，环的数量也会随之改变，可以理解为奇数个环的情况和偶数个环的情况是成对出现的。

• 所以，我们只需要知道排列 p 的全排列。

• 问题就这样解决了，不过要注意，除法取模要用被除数乘以除数的逆元，2 的逆元为 499122177。

代码

#include <iostream>
#define int long long
using namespace std;
const int mod = 998244353;

int tot = 1,n;

signed main()
{
    cin >> n;
    for(int i = 1;i <= n;++i)
        tot = tot * i % mod;
    cout << tot * 499122177 % mod;
    return 0;
}