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}}$ 。这个时候我们先简单看看现在这个式子，首先可以看出来如果 $2i-1 \ge MOD$ 那么就没有意义了。然后就是如果 $2i-1 < MOD$ 那么相当于 $2i \le MOD-1$，于是有 $\binom{N/MOD}{2i/MOD}=\binom{k}{0}=1$ 。最后我们可以发现要想让 $\binom{n}{2i\%MOD}$ 不是 $0$ ，那么一定有 $2i \le n$ 。所以我们可以得到一个很重要的东西就是 $f(n+k*MOD)=a^{k*MOD}*f(n)=a^{k}*f(n)$ 。

所以我们就相当于是只需要跑完模数范围内的递推就可以了，就是说在3s要跑1e9的递推，在加上循环展开后就通过了这个题。
CVBB ACM Team

用户工具

站点工具

页面工具
