[JRKSJ R4] Stirling

ID: 7147

远端评测题

1000ms

128MiB

难度: 3

上传者:

标签>

数学

2022

洛谷原创

题目背景

可能对您无用的提示：

f(n)=\sum_{i=0}^n \begin{Bmatrix} n\\i\end{Bmatrix}g(i) \leftrightarrow g(n)=\sum_{i=0}^n (-1)^{n-i} \begin{bmatrix} n\\i\end{bmatrix} f(i)

对于 $[1,n]$ 的排列 $p$ ，定义其“生成图”为：该图有 $n$ 个点，且 $\forall 1\le i\le n$ ，无向边 $(i,p_i)$ 存在且仅存在这些边。

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

一个整数 $n$ 。

一个整数，表示答案。答案对 $998244353$ 取模。

430461019

这些排列满足条件：

\{1,3,2\}

\{2,1,3\}

\{3,2,1\}

对于 $20\%$ 的数据， $n\le 10$ 。
对于 $50\%$ 的数据， $n\le 500$ 。
对于 $100\%$ 的数据， $1\le n\le 10^6$ 。