JOIN
Get Time

   Problem Statement  

 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

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 176 Round 1 - Division I, Level Two