题解 P8143 【[JRKSJ R4] Stirling】

· · 题解

无耻地推销个人博客 qwq

题目传送门

update on 2024/9/15： 修复了关于 n = 1 的情况。

题意

对于给定的 n ，求有多少个 [1,n] 的排列满足其生成图恰有偶数个环（自环同样计入）。

其中一个排列生成图指的是对于每个该排列中的第 i 个元素（令其为 p_i ），连接一条从 i 到 p_i 的无向边，最后得到的无向图为原排列的生成图。

解法

作为一道公开赛的T1，由经验出发其十有八九是一道结论题（大雾

因此，我们从 n = 2 开始手玩几项，发现其对应关系如下：

n 2 3 4 5 6 7 8
ans 1 3 12 60 360 2520 20160

当然手玩一般到 n = 5 就是极限了

简单分析一下，可以看出 ans = \frac{n!}{2} 。

当然，仅仅靠猜是不够的，所以我们接下来通过递推来对其给出一个严格的证明：

为了方便表示，不妨令 p_{i} \rightarrow i 的映射为 h(x) ，并令 f(n), g(n) 分别为对于 [1,n] 的排列 p ，其环个数为偶数和奇数的生成图个数，

则易得 f(2) = g(2) = 1 （分别是 \{1, 2\} 与 \{2, 1\} ），

且有 f(n) + g(n) = n! （总生成图个数等于排列个数）。

现在假设对于 \forall x < n ，其对应的 f(x), g(x) 皆已求出，考虑当 x = n 时 f(x), g(x) 的值。 此时，对于新加入的 p_{n} ，有如下两种情况：

  1. p_{n} = n

此时相当于在原来的情况下增加了一个自环，故环的个数加一，奇偶性发生变化，原先所有环的个数为奇数的情况变为环的个数为偶数，偶数变奇数，

故有 \left\{\begin{matrix}f(x) = g(x - 1)\\ g(x) = f(x - 1)\end{matrix}\right.

  1. p_{n} \neq n

不妨令 p_{n} = \alpha ，则实际上发生的操作为 p_{n} = \alpha, p_{h(\alpha)} = n （实际上可以类比为链表的插入），此时相当于在原来的情况下将其中一个环的规模扩大，故环的个数不变，奇偶性不发生变化，原先所有环的个数为奇数的情况仍为奇数，偶数仍为偶数，又因为对于 先前 x = n - 1 的每一种情况而言， p_{n} = 1, 2, 3, \cdots, n - 1 都是满足假设的，

故有 \left\{\begin{matrix}f(x) = (x - 1)f(x - 1)\\ g(x) = (x - 1)g(x - 1)\end{matrix}\right.

故由加法原理得到最终的递推公式为 \left\{\begin{matrix}f(x) = g(x) + (x - 1)f(x - 1)\\ g(x) = f(x) + (x - 1)g(x - 1)\end{matrix}\right.

结合最初的两个式子，最终可以推出通项为 f(x) = g(x) = \frac{x!}{2} 。

所以题目背景中给出的公式在题目中完全用不上（大雾

不过需要注意的是，在求余这一操作下，除法应转化为乘上对应的乘法逆元，当然你也可以直接上下把2约掉，这样更方便，就像我代码里一样。

另外，当 n = 1 时，显然有答案为 0，特判一下即可。

最后代码如下：

#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
unsigned long long n, ans = 1;
int main(){
    cin >> n;
    if (n == 1) ans = 0;
    for(unsigned long long i = 1; i <= n; ++i) if(i != 2) ans = (ans % mod) * (i % mod);
    cout<< ans % mod << endl;
    return 0;
}

至此，愉快 AC，完结撒花 0v0