题解 P8143 【[JRKSJ R4] Stirling】

· · 题解

题目名称写了 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 数的组合意义（如果不知道这个组合意义建议也找博客学一下）知题意即求

\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);
}