0634. Find the Derangement of An Array

https://leetcode.com/problems/find-the-derangement-of-an-array

Description

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

You are given an integer n. There is originally an array consisting of n integers from 1 to n in ascending order, return the number of derangements it can generate. Since the answer may be huge, return it modulo 109 + 7.

Example 1:

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

Example 2:

**Input:** n = 2
**Output:** 1

Constraints:

• 1 <= n <= 106

ac

class Solution {
    public int findDerangement(int n) {
        int mod = 1000000007;
        long[] dp = new long[n+1];
        dp[0] = 1;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = ((i - 1) * ((dp[i-2] + dp[i-1]) % mod)) % mod;
        }
        return (int)dp[n];
    }
}

/*
for i, it has 2 option: 1) j-th take i-value, i take j-value, then we have dp[n-1] possible; 2) j-th take i-value, i dont' take j-value, we have dp[n-1] possible; 3) we have (i-1) j-th position, so dp[i] = (i-1) * (dp[i-1] + dp[i-2]);
*/