JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums TopCoder Cookbook Algorithm Competitions - New Recipes Counting permutations of certain type Revision History (1 edit)
Counting permutations of certain type
Hello,
This is my first post here and I really need some help with this.
I know this problem might be silly for many of you :) but I couldn't solve it, so need your help.

I am given 2 integers
1st one: N, I have to consider all permutations of numbers from 1 to N
2nd one: M, I have to count only those of the set of permutations in which no sum of adjacent numbers are dividable by M

Example:
Input: 3 3
Output: 2
The set of all permutations is
1. 1 2 3
2. 1 3 2
3. 2 1 3
4. 2 3 1
5. 3 1 2
6. 3 2 1
But I can take only 2 and 4 because all the others have adjacent numbers whose sum is dividable by 3. So the output is 2.

The maximum value of N is 14 and for M is 30
Is there any efficient way of doing this??
Please note that, I know how to generate all the permutations and get the result using bruteforce. But given the constraints, this will take hours if not days. But some teams solved it on a single attempt in a local contest and I'm really out of ideas here.
Please help..
Counting permutations of certain type
Hello,
This is my first post here and I really need some help with this.
I know this problem might be silly for many of you :) but I couldn't solve it, so need your help.

I am given 2 integers
1st one: N, I have to consider all permutations of numbers from 1 to N
2nd one: M, I have to count only those of the set of permutations in which no sum of adjacent numbers are dividable by M

Example:
Input: 3 3
Output: 2
The set of all permutations is
1. 1 2 3
2. 1 3 2
3. 2 1 3
4. 2 3 1
5. 3 1 2
6. 3 2 1
But I can take only 2 and 4 because all the others have adjacent numbers whose sum is dividable by 3. So the output is 2.

The maximum value of N is 14 and for M is 30
Is there any efficient way of doing this??

Please help..