BZOJ 4714 - 旋转排列

题目精选 容斥原理 组合数学

---

---

相关链接

题目: http://www.lydsy.com/JudgeOnline/problem.php?id=4714
题解: https://zyqn.tech/?p=3158

题意

$1\le N\le 500000$

前置技能

环排列数

  我们定义 $q_n$ 为 $n$ 个数的环排列数.
  我门固定第一个位置不动, 所以 $q_n=(n-1)!$

错位排列数

定义

  我们定义 $d_n$ 为 $n$ 个数的错位排列数.

算法1: 递推

  枚举 $n$ 所在的连通块的大小, 进行使用递推的方法求解.

$$\begin{aligned}d_n&=\sum_{i=2}^n\binom{n-1}{i-1}q_id_{n-i}\\&=(n-1)!\sum_{i=2}^n\frac{d_{n-i}}{(n-i)!}\\&=(n-1)!\sum_{i=0}^{n-2}\frac{d_i}{i!}\end{aligned}$$
  这种计算的方法还是太麻烦啦, 我们考虑继续化简.
$$\begin{aligned}d_n&=(n-1)!\sum_{i=0}^{n-2}\frac{d_i}{i!}\\&=(n-1)(n-2)!\sum_{i=0}^{n-2}\frac{d_i}{i!}\\&=(n-1)[(n-2)!\sum_{i=0}^{n-3}\frac{d_i}{i!}+(n-2)!\frac{d_{n-2}}{(n-2)!}]\\&=(n-1)(d_{n-1}+d_{n-2})\end{aligned}$$
  边界: $d_0=1,d_1=0,d_2=1$

算法2: 二项式反演

  二项式反演:

$$f(n)=\sum_{k=0}^n\binom{n}{k}g(k)\Leftrightarrow g(n)=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}f(k)$$
  证明:
$$\sum_{k=0}^n(-1)^k\binom{n}{k}=[n=0]$$
$$\begin{aligned}g(n)&=\sum_{m=0}^n[n-m=0]\binom{n}{m}g(m)\\&=\sum_{m=0}^n\sum_{k=0}^{n-m}(-1)^k\binom{n-m}{k}\binom{n}{m}g(m)\\&=\sum_{m=0}^n\sum_{k=0}^{n-m}(-1)^k\binom{n}{k}\binom{n-k}{m}g(m)\\&=\sum_{k=0}^n(-1)^k\binom{n}{k}\sum_{m=0}^{n-k}\binom{n-k}{m}g(m)\\&=\sum_{k=0}^n(-1)^k\binom{n}{k}f(n-k)\\&=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}f(k)\end{aligned}$$

  我们考虑求解 $N$ 个元素的排列方案数.
  方法1: $n!$
  方法2: 枚举错位的个数, 其余在原本的位置上.

$$\sum_{k=0}^n\binom{n}{k}d_k$$
$$n!=\sum_{k=0}^n\binom{n}{k}d_k$$
$$\begin{aligned}d_k&=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k!\\&=n!\sum_{k=0}^n\frac{(-1)^{n-k}}{(n-k)!}\\&=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\end{aligned}$$

分析

  先分析一下两个条件分别是什么意思.
  条件1: 错位排列.
  条件2: 将一个排列 $P$ 看做一个置换, 那么要求置换存在一个循环节的大小为 $k$ .
  所以

$$ans_k=\sum_{P为错位排列}[P存在一个循环节的大小为k]$$

  考虑如何计算 $ans_k$ .
  我们可以使用容斥原理: 强制存在一个循环节的大小为 $k$ 的方案数, 减去强制两个循环节大小为 $k$ 的方案数, 加上强制存在三个循环节大小为 $k$ 的方案数,...,加(或减)上强制存在 $\frac{n}{k}$ 个循环节大小为 $k$ 的方案数.
  那么, 如果强制存在 $t$ 个循环节大小为 $k$ 的方案数能在 $O(1)$ 算出来, 就可以在 $\sum_{i=1}^n\frac{n}{i}=O(n\log n)$ 的复杂度内算出答案了.

  考虑强制存在 $t$ 个循环节大小为 $k$ 的方案数如何计算:

$$\binom{n}{kt}d_{n-kt}g_{t,k}$$
  $g_{t,k}$ 表示将 $tk$ 个数划分到 $t$ 个循环, 每个循环的大小为 $k$ 的方案数, 它可以递推处理:
$$g_{t,k}=\binom{tk-1}{k-1}g_{t-1,k}d_k$$

小结

  这道题我之所以没想到, 是因为不知道怎么求 $g_{i,k}$ , 始终想着用已有的结论来求, 没想到可以用陌生的东西求陌生的东西, 直接递推.