PSequence
SRM 427 · 2008-11-25 · by rasto6sk
SRM 427 · 2008-11-25 · by rasto6sk · Dynamic Programming, Recursion
Problem Statement
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.
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.
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
4)
{0,-5,1,2,3,4,5,6,7,8,9,10,12,213,123,122,21,2136,4534,2312,12312,34543,2765,56756,462346,46434,4235,2353,352342,23433}
4
Returns: 681816692
Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PSequence with a public method int count(vector<int> S, int p) · 70 test cases · 2 s / 256 MB per case