错排小记

· · 个人记录

错排好像可以在求解组合问题时突然蹦出来，那要是不会就 GG 了啊，那就记下板子吧。

错排的定义

### 解法 #### 递推 显然可以容斥，不过递推更常用。 一般递推求出，设 $f_i$ 表示 $n$ 个数的错排数量，首先有 $f_0=1,f_1=0

考虑 f_i，理解为在 i-1 排列末尾插入 i 元素，通过交换 i,j 一次来得到错排。

显然：i-1 排列中至多有 1 个位置满足 a_j=j，否则无法通过上述操作得到 i 错排。

分类讨论：

综上：

f_i=(f_{i-1} +f_{i-2})*(i-1)

容斥

定义性质 A_i 表示 n 排列中，满足 a_i=i 的排列集合，Q 表示错排集合，A 表示排列集合。

有

Q = (-A_1\cap-A_2...-A_n) =A-(A_1\cup A_2...A_n)

前半部分：

=n!

考虑容斥求解后半部分：

=\sum \limits_{i=1}^{n}A_i-\sum \limits_{i=1}^{n}\sum \limits_{j=i+1}^{n} A_i\cap A_j+...

显然 |A_{b_1}\cap A_{b_2}...A_{b_p}| = (n-p)!

（面对不关心 b_i 具体取值的容斥，可以快速求出其值而不用二进制枚举）

上式带入上上式：

=\sum \limits_{i=1}^{n} (-1)^{i-1}C_{n}^{i}(n-i)!

最后回到开始的式子：

|Q|=n!-\sum \limits_{i=1}^{n} (-1)^{i-1}C_{n}^{i}(n-i)!

也可以写成：

|Q|=\sum\limits_{i=0}^{n} (-1)^{i}C_{n}^{i}(n-i)!

代码

两种都放上。

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, ans, jc[N], jcinv[N], awa[N];

inline int qstp(int a, int b) {int s = 1; for(; b;a = a * a % mod, b >>= 1) if(b & 1) s = s * a % mod; return s;}
inline int C(int n, int m) {return jc[n] * jcinv[m] % mod * jcinv[n - m] % mod;}
signed main(){
    jc[0] = jcinv[0] = awa[0] = 1;
    for(int i = 1; i <= 1e6;++i){
        jcinv[i] = qstp(jc[i] = jc[i - 1] * i % mod, mod - 2);
        awa[i] = i == 1 ? 0 : (awa[i - 1] + awa[i - 2]) * (i - 1) % mod;
    }
    cin >> n;
    for(int i = 0, p = 1; i <= n;++i, p *= -1){
        ans = ((ans + p * C(n, i) % mod * jc[n - i] % mod) % mod + mod) % mod;
    }
    cout << ans << "\n" << awa[n];
    return 0;
}