TopCoder problem "TwoSidedCards" used in SRM 472 (Division I Level Two)



Problem Statement

    There are N cards which are initially blank. First, Taro writes a distinct number between 1 and N, inclusive, on the front side of each card. The number he writes on the i-th card is taro[i]. Then, Hanako turns over all the cards and writes a distinct number between 1 and N, inclusive, on the back side of each card. The number she writes on the i-th card is hanako[i].



Now you must determine the number of distinct ways that the N cards can be arranged in a row. The cards can be placed in any order and each card can be oriented so that either its front side or back side is displayed. Two arrangements are considered distinct if the i-th card in the row shows a different number in one arrangement than it does it in the other. Return the number of distinct possible arrangements, modulo 1,000,000,007.
 

Definition

    
Class:TwoSidedCards
Method:theCount
Parameters:int[], int[]
Returns:int
Method signature:int theCount(int[] taro, int[] hanako)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 50, inclusive, where N is the number of elements in taro.
-Each element of taro will be between 1 and N, inclusive.
-taro will contain no duplicate elements.
-hanako will contain exactly N elements.
-Each element of hanako will be between 1 and N, inclusive.
-hanako will contain no duplicate elements.
 

Examples

0)
    
{1, 2, 3}
{1, 3, 2}
Returns: 12
If the front side of each card is displayed, the cards will be (1,2,3), and you can get (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) by changing the order.

If the back side of the second card is displayed, the cards will be (1,3,3), and you can get (1,3,3), (3,1,3), (3,3,1) by changing the order.

If the back side of the third card is displayed, the cards will be (1,2,2), and you can get (1,2,2), (2,1,2), (2,2,1) by changing the order.

If the back sides of both the second and third cards are displayed, the cards will be (1,3,2), and you can get (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) by changing the order.



In total, there are 12 possibilities: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1), (1,3,3), (3,1,3), (3,3,1), (1,2,2), (2,1,2), (2,2,1).
1)
    
{1, 2, 3}
{1, 2, 3}
Returns: 6
You can make 123, 132, 213, 231, 312, 321.
2)
    
{1, 2}
{2, 1}
Returns: 4
You can make 11, 12, 21, 22.
3)
    
{5, 8, 1, 2, 3, 4, 6, 7}
{1, 2, 3, 4, 5, 6, 7, 8}
Returns: 2177280
4)
    
{41, 22, 17, 36, 26, 15, 10, 23, 33, 48, 49, 9, 34, 6, 21, 2, 46, 16, 25, 3, 24, 13, 40, 37, 35,
50, 44, 42, 31, 12, 29, 7, 43, 18, 30, 19, 45, 32, 39, 14, 8, 27, 1, 5, 38, 11, 4, 20, 47, 28}
{19, 6, 23, 35, 17, 7, 50, 2, 33, 36, 12, 31, 46, 21, 30, 13, 47, 22, 44, 4, 25, 24, 3, 15, 20,
48, 10, 28, 26, 18, 5, 45, 49, 16, 40, 42, 43, 14, 1, 37, 29, 8, 41, 38, 9, 11, 34, 32, 39, 27}
Returns: 529165844

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10947

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14154&pm=10947

Writer:

rng_58

Testers:

PabloGilberto , ivan_metelsky , Chmel_Tolstiy

Problem categories:

Graph Theory, Math