自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:36:20，当前版本为作者最后更新于2022-02-15 13:42:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目名称写了 Stirling 你就用 Stirling 做嘛

事实上背景里给出的 Stirling 反演公式确实没啥用，但是有一个东西非常有用：

$$F_n(x)=\prod_{i=0}^{n-1}(x+i)=\sum_{m=1}^{n}\begin{bmatrix}n\\m\end{bmatrix}x^m. $$

这个式子在各种讲解 Stirling 数的博客（或者百度百科等地方）都有讲到，也有证明，在此不作赘述。建议自行搜索学习。

由第一类 Stirling 数的组合意义（如果不知道这个组合意义建议也找博客学一下）知题意即求

$$\begin{aligned} \sum_{1 \le m \le n,2 \mid m}\begin{bmatrix}n\\m\end{bmatrix}&=\dfrac{F_n(1)+F_n(-1)}{2}\\ &=\dfrac{n!-[n=1]}{2}. \end{aligned}$$

其中的 $-[n=1]$ 是因为 $F_1(-1)=-1$，$n>1$ 时 $F_n(-1)=0$，而 $F_n(1)=n!$ 对任意 $n$ 成立。

Code:

#include<cstdio>
#define ll long long
const int ntf=998244353;
int n;ll f;int main(){
	scanf(" %d",&n),f=n;while((--n)>2)f=f*n%ntf;
	return 0&printf("%lld\n",(n)?f:0);
}