题解 P8143 [JRKSJ R4] Stirling

· · 题解

题目分析

首先，不要去管题目前面的斯特林反演。

考虑一个比较容易想到的思路：对于任意一个排列的“生成图”，将排列中两个数调换一下位置，都会使环的个数增加或减少 1。换句话说，有偶数个环和有奇数个环的方案数是相同的。

于是我们就得到了答案为 \dfrac{n!}{2}。

代码实现

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

const int MOD = 998244353;

int main() {
    int n;
    long long f = 1;

    scanf("%d", &n);
    for(int i = 3; i <= n; i++) {
        f = f * i % MOD;
    }
    printf("%lld\n", f);

    return 0;
}