arrays - 给定一个整数为 0 到 N 的数组，有多少种排列方式使得 array[i] 不能是 i

Question

给定一个 0 到 N 的整数数组，有多少种排列方式使得在数组的位置 i 不能插入 i？

例如，N = 2

以下安排有效:

• 1,2,0
• 2,0,1

因此，答案是2种安排

我想不出在 O(1) 时间内完成此操作的非蛮力方法，有人可以帮我吗？

Answer 1

这种排列称为紊乱。 Wiki page包含很多计算它们的公式。例如，重复:

!n=(n-1)(!(n-1)+!(n-2))

其中 !n，称为子因子，表示紊乱的数量，起始值为 !0 = 1 和 !1 = 0