## 题目描述：

LeetCode 634. Find the Derangement of An Array

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.

There's originally an array consisting of `n` integers from 1 to `n` in ascending order, you need to find the number of derangement it can generate.

Also, since the answer may be very large, you should return the output mod 109 + 7.

Example 1:

```Input: 3
Output: 2
Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].
```

Note:
`n` is in the range of [1, 106].

## 解题思路：

``````import operator

class Helper(object):
def __init__(self):
self.dmap = {}

def findDerangement(self, n):
"""
:type n: int
:rtype: int
"""
return self.solve(list(range(1, n + 1)), list(range(1, n + 1)))

def solve(self, n, p):
if len(set(n + p)) == len(n) * 2:
return reduce(operator.mul, range(1, len(n) + 1))
tn, tp = tuple(n), tuple(p)
if (tn, tp) in self.dmap: return self.dmap[(tn, tp)]
ans = 0
for x in range(len(n)):
if n[x] != p[0]:
ans += self.solve(n[:x] + n[x+1:], p[1:])
self.dmap[(tn, tp)] = ans
return ans

helper = Helper()
print map(helper.findDerangement, range(1, 11))
``````

`dp[n] = (dp[n - 1] + dp[n - 2]) * (n - 1)`

1. 第i个人选择第一顶帽子，则问题规模缩小为n - 2

```2, 3, 4, ..., i-1, i+1, ... n 人
2, 3, 4, ..., i-1, i+1, ... n 帽```

2. 第i个人不选第一顶帽子，则问题规模缩小为n - 1（相当于第i个人不能选择第1顶帽子）

```2, 3, 4, ..., i-1, i, i+1, ..., n 人
2, 3, 4, ..., i-1, 1, i+1, ..., n 帽```

## Python代码：

``````class Solution(object):
def findDerangement(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0, 1]
for x in range(2, n + 1):
dp.append(x * (dp[- 1] + dp[-2]) % (10**9 + 7))
return dp[n - 1]
``````

`d(n) = sigma( n! * (-1)^i / i! ) i∈[0, n]`

## Python代码：

``````class Solution(object):
def findDerangement(self, n):
"""
:type n: int
:rtype: int
"""
MOD = 10**9 + 7
mul, sig = 1, (-1) ** n
ans = 0
for x in range(n, -1, -1):
ans = (ans + mul * sig) % MOD
mul = (mul * x) % MOD
sig *= -1
return ans % MOD
``````

Pingbacks已关闭。