SmoothPermutations

SRM 772 · 2019-12-10 · by misof

SRM 772 · 2019-12-10 · by misof · Math

Show categories

Class Name: SmoothPermutations

Return Type: long

Method Name: countPermutations

Arg Types: (int, int, int, int, vector<int>, vector<int>, vector<int>)

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.

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

200000
373416572
5
586135019
{}
{}
{}
Returns: 2292074

200000
284159665
28
2104362589
{}
{}
{}
Returns: 10522388292524

200000
603641977
13
1868932308
{}
{}
{}
Returns: 3598451238526

200000
761781896
51
1007685845
{}
{}
{}
Returns: 32130912337239

200000
867928711
71
1340110876
{}
{}
{}
Returns: 39331323581484

200)

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.

203)

100
1
47
47
{}
{}
{}
Returns: 0

Anything modulo 1 is 0.

204)

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.)

Submissions are judged against all 221 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SmoothPermutations with a public method long long countPermutations(int T, int M, int MX, int seed, vector<int> prefN, vector<int> prefK, vector<int> prefX) · 221 test cases · 2 s / 256 MB per case