## Algorithm

Problem Statement for Deranged

### Problem Statement

A derangement of n numbers is a permutation of those numbers in which none of the numbers appears in its original place. For example, the numbers {1,2,3} can be deranged into {2,3,1} and {3,1,2}. We can modify this slightly for n numbers that are not necessarily distinct by saying that no number in the derangement can be in the place that a number of the same value was in in the original ordering. So the numbers {1,1,2,2,3} could be deranged into {2,2,1,3,1}, {2,2,3,1,1}, {2,3,1,1,2}, and {3,2,1,1,2}. Create a class Deranged with a function numDerangements that takes a int[] nums and return the number of derangements of nums.

### Definition

 Class: Deranged Method: numDerangements Parameters: int[] Returns: long Method signature: long numDerangements(int[] nums) (be sure your method is public)

### Notes

- The return value will fit in a 64-bit unsigned integer.

### Constraints

- nums will contain between 1 and 15 elements, inclusive.
- nums will only contain values between 0 and the number of elements in nums - 1, inclusive.

### Examples

0)

 `{1,1,2,2,3}`
`Returns: 4`
 The example from above.
1)

 `{0,0,0,1,1,1}`
`Returns: 1`
 The only derangement is {1,1,1,0,0,0}.
2)

 `{0,0,0,1,1,1,1}`
`Returns: 0`
 There is no way to arrange the numbers such that no 1 is where a 1 was originally.
3)

 `{0,0,0,0,0,0,0,1,1,1,1,1,1,1,2}`
`Returns: 14`

4)

 ```{0,5,4,2,3,6,6} ```
`Returns: 640`

5)

 `{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}`
`Returns: 481066515734`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;

class Deranged {
public:
static long long dp[(1 << 16)][16];

long long numDerangements(vector <int> nums) {
sort(nums.begin(), nums.end());
memset(dp, -1, sizeof dp);
long long ret = rec(0, 0, nums);

int fr[16] = {0};
for(int i = 0; i < nums.size(); ++i)
++fr[nums[i]];

for(int i = 0; i < 16; ++i)
ret /= fact(fr[i]);

return ret;
}

long long rec(int idx, int msk, vector<int>&nums) {
if(__builtin_popcount(msk) == int(nums.size()))
return 1;

long long &ret = dp[msk][idx];
if(ret != -1)
return ret;
ret = 0;

for(int i = 0; i < nums.size(); ++i)
if(((msk >> i) & 1) == 0 && nums[idx] != nums[i])
ret += rec(idx + 1, msk | (1 << i), nums);

return ret;
}

long long fact(int x) {
long long f = 1;
for(int i = 2; i <= x; ++i)
f *= i;
return f;
}
};

long long Deranged::dp[][16] = {0};``````
Copy The Code &

Input

cmd
{1,1,2,2,3}

Output

cmd
4