CVBB ACM Team

一个作用在 $\{1,2,\dots,n \}$ 上的一一映射 $f$ 是好的，当且仅当其由不动点和二元置换组成，其权值为 $a^{不动点个数}$ （$a$ 是给定常数）。求所有好的映射的权值和。

时限:3s

数据范围:$n \le 5*10^9, 1 \le a \le 998244352$

我们考虑令 $f(n)$ 表示 $n$ 对应的答案。那么我们首先可以得到一个递推式为 $f(n)=a*f(n-1)+(n-1)*f(n-2)$ ，其含义就是我们可以选择 $n$ 是单独一个不动点还是和前面 $n-1$ 个数中的一个形成二元置换。

然后我们考虑直接写出 $f(n)$ 的表达式，就是 $f(n)=\sum_{i=0}^{n/2}{\binom{n}{2i}*\frac{(2i)!}{2^i*i!}*a^{n-2i}}$，就是说枚举二元置换个数，然后方案数就是选 $2i$ 个出来之后，先去排列一下，之后去掉相邻的两个交换和整体 $i$ 组之间的顺序。这个我们可以化简一下就是 $f(n)=\sum_{i=0}^{n/2}{\binom{n}{2i}*(2i-1)!!*a^{n-2i}}$ 。

我们考虑一下如果 $n<MOD$ 那么 $f(n+k*MOD)$ 和 $f(n)$ 之间会有什么关系。下面令 $N=n+k*MOD$，等号都是指模意义下相等。

$f(N)=\sum_{i=0}^{N/2}{\binom{N}{2i}*(2i-1)!!*a^{N-2i}}=\sum_{i=0}{N/2}{\binom{N/MOD}{2i/MOD}*\binom{n}{2i\%MOD}*(2i-1)!!*a^{N-2i}}$