一道算法题，据同学说是某厂的笔试题

Question

天上共有n颗星星排成一排，小强坐在草地上数星星，但是直接一颗一颗数实在是太无聊了，因此小强规定自己数的第i颗星星不能是第a[i]颗，现在他想知道在他的限制之下还有多少数星星的方案。
0<n<10^7， 结果对10^9+7取模。

示例：
输入： n=3 array=[1,2,3]
输出： 2
说明：根据条件第一位不能为1，第二位不能为2，第三位不能为3，两种满足条件的排序为[2,3,1]和[3,1,2]
注意数组a可以包含重复的数字
如n=3 array=[1,1,1]的结果为0。
如n=3 array=[1,2,2]的结果为2。

从同学那听来的，自己想了好久想不出答案，求算法大佬来解答。

Answer 1

原作者改题了 ...
以下回答不适用于改过的题 ...

---

解释一下题吧。这个就是要求将 1~n 填入长为 n 的数组 a 里，要求对任意 i ， a[i] != i 。

这样的填写方式称作 derangement / 错位排序。

这个题是要求出对于某一个 n ，可能的错位排序的总数。我们将它记为 P(n) 的话，那么有:

P(n) = (n-1)*((P(n-1) + P(n-2))

P(1) = 0
P(2) = 1

可以搜索 derangement

拿掉一个(n)，n-1 个的 derangement 里，n 与其中任何一个交换，得到一个合法的 n 个的 derangement 。这种一共有 (n-1) * P(n-1) 个。
此时，n != a[a[n]]

拿掉两个(n,k) ，剩下是 n-2 的 derangement 。最后 n 与 k 互换，得到一个合法的 n 的 derangement 。k 一共有 n-1 中可能 . 这种一共有 (n-1) * P(n-2) 个。
此时，n == a[a[n]]

两种情况没有重复。n 的 derangment 必然为两种情况之一。