SmoothPermutations | Topcoder Archive

Problem Statement

A smooth permutation is a permutation of numbers 1 to N such that the largest element among the first K elements is at most equal to X.

You are given T separate test cases. For each of them, calculate the number of smooth permutations modulo a given M.

You are given the values of N, K and X for a few test cases. Use the pseudocode below to generate the rest of test cases.

A[0] = seed
for i = 1 to 3*T-1:
	A[i] = (A[i-1] * 1103515245 + 12345) modulo 2147483648

LEN = length(prefN)
for i = 0 to LEN-1:
	N[i] = prefN[i]
	K[i] = prefK[i]
	X[i] = prefX[i]
 
for i = LEN to T-1:
	N[i] = (A[i] modulo MX) + 1
	K[i] = (A[T+i] modulo N[i]) + 1
	X[i] = (A[2*T+i] modulo N[i]) + 1

Return the sum of answers across all test cases.

Definition

Class:: SmoothPermutations
Method:: countPermutations
Parameters:: int, int, int, int, int[], int[], int[]
Returns:: long
Method signature:: long countPermutations(int T, int M, int MX, int seed, int[] prefN, int[] prefK, int[] prefX)
(be sure your method is public)

Notes

Be careful with overflows.
The reference solution would correctly solve any case that matches the constraints. It does not depend on the properties of the pseudorandom generator.

Constraints

T will be between 1 and 200,000, inclusive.
M will be between 1 and 1,000,000,000, inclusive.
MX will be between 1 and 200,000, inclusive.
seed will be between 0 and 2,147,483,647, inclusive.
Number of elements in prefN, prefK, prefX will be equal and between 0 and min(500,T), inclusive.
Each element of prefN will be between 1 and MX, inclusive.
For each i, prefK[i] and prefX[i] will be between 1 and prefN[i], inclusive.

Examples

```
3
```
```
100
```
```
5
```
```
4
```
```
{5,4}
```
```
{3,2}
```
```
{5,2}
```
```
Returns: 24
```
The generated arrays will be: N = {5,4,4} K = {3,2,2} X = {5,2,1} Thus, we have the following test cases: permutations of 1..5 in which the largest among the first 3 elements is at most 5 permutations of 1..4 in which the largest among the first 2 elements is at most 2 permutations of 1..4 in which the largest among the first 2 elements is at most 1 The answers for these are as follows: In the first test case, all 5! permutations are smooth permutations, and 5! mod 100 = 120 mod 100 = 20. In the second test case, the following 4 permutations are smooth permutations: (1,2,3,4), (2,1,3,4), (1,2,4,3), and (2,1,4,3). In the third test case there are no smooth permutations. Hence, the correct return value is 20 + 4 + 0 = 24.
```
100
```
```
1
```
```
47
```
```
47
```
```
{}
```
```
{}
```
```
{}
```
```
Returns: 0
```
Anything modulo 1 is 0.
```
100
```
```
999999937
```
```
123456
```
```
47
```
```
{}
```
```
{}
```
```
{}
```
```
Returns: 24359438587
```
Note that the correct return value is just a plain sum of all test case answers. (It should not be taken modulo M.)

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)2024, Topcoder, Inc. All rights reserved.