https://en.wikipedia.org/wiki/Derangement
错排问题
n=0
f[0] = 1
n=1
f[1] = 0
n = 2
2 1
f[2] = 1
n = 3
2 3 1
3 1 2
f[3] = 2
f[4] = 9
f[5] = 44
1 0 1 2 9 44
0 1 2 3 4 5
f[1] = f[0] * 1 - 1
f[2] = f[1] * 2 + 1
f[3] = f[2] * 3 - 1
f[4] = f[3] * 4 + 1
f[5] = f[4] * 5 - 1
f[n] = f[n - 1] * n + (n & 1 ? -1 : 1)
f[n] = (n-1) * (f[n-1] + f[n-2])
2 1
2 3 1
3 1 2
n=0 1
n=1 0
n=2 1
n=3 2
n=4 9
n=5 44
n=6 265
非线性递推
f[n] = (f[n-1] + f[n-2])*(n-1)
f[n] = f[n-1]*n + (-1)^n
C(n, m) * derangement[n-m]
C(n, m)
n, m <= 1e6
mod prime