TopCoder problem "PSequence" used in SRM 427 (Division I Level Three)



Problem Statement

    You are given a int[] S containing a set of distinct integers. A sequence is called a p-sequence of S if it satisfies both of the following conditions:



1. It contains each element of S exactly once.

2. For each pair of consecutive sequence elements s1 and s2, (s1 - s2) is not divisible by p.



Return the number of p-sequences of S, modulo 1234567891.
 

Definition

    
Class:PSequence
Method:count
Parameters:int[], int
Returns:int
Method signature:int count(int[] S, int p)
(be sure your method is public)
    
 

Constraints

-S will contain between 1 and 30 elements, inclusive.
-All elements of S will be distinct.
-Each element of S will be between -1,000,000 and 1,000,000, inclusive.
-p will be between 1 and 1,000, inclusive.
 

Examples

0)
    
{-1,0,1,2,3}
10
Returns: 120
All permutations of numbers are valid, so we have 5! = 120 sequences.
1)
    
{6,2}
4
Returns: 0
Both numbers have the same remainder modulo 4 and so we cannot create a valid 4-sequence from them.
2)
    
{1,2,3,4}
3
Returns: 12
3)
    
{4,6,8,-3,7}
2
Returns: 12

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13518&pm=8785

Writer:

rasto6sk

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, Recursion