给定一个整数0到N的数组,有多少种方法来排列它,使得array [i]不能是i

Question

给定一个整数为0到N的数组,有多少种方法可以排列它,使得在数组的位置i,我们不能插入它？

例如,N = 2

以下安排有效:

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

因此,答案是2个安排

在O(1)时间里,我想不出一个非暴力方法来做这件事,任何人都可以帮助我吗？

Answer 1

这种排列称为紊乱.Wiki页面包含许多计算它们的公式.例如,重复:

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

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