Finding the rank of permutation, modular inverse
Find the rank of the permutation Q in the set, containing all the strings that are obtained from the permutation P by cyclic shifts of the subsegments of P the length of K. If Q doesn’t belong S, output -1 instead.
How to get 10 points
Let’s solve subtask #2, where k = n.
Let’s find such x, that P1 = Qx. In other words, we need to find such x, that index 1 in the permutation P corresponds to the index x in the permutation Q. Note that if the index y in the permutation P corresponds to the index z in the permutation Q, then z mod n = (x+y+n-1) mod n holds. Using this fact, we can check whether Q can be obtained from P or not by iterating through all the indices from 1 to n and comparing the corresponding elements of the permutations.
If we figured out that P can be obtained from Q, then the answer is equal to Q1, because S will contain exactly n permutations, and all the first elements of these permutations will be distinct.
Making further insights
From now on, we will consider that k < n. Let’s consider two cases: when k is even and when k is odd
The first case: k < n, k is even
Let’s prove that we can obtain any permutation from the permutation P. It is easy to move the last n-k numbers to their places.
Now we need to figure out, how to swap the first two numbers of permutation P. If we can do this, we can swap any two consecutive numbers among the first k numbers and use the algorithm, similar to the bubble sort to place all these numbers to their places.
Let L denote cyclic shift of segment (P1,P2,…,Pk) and R denote the cyclic shift of the subsegment (P2,P3,…,P(k+1)). Applying there shifts consecutively - first L, and then then R moves elements Pk and P(k+1) to the first two places, saving their relative order and the relative order of the first k-1 elements. Using this combination several times, we get the permutation (P2,P3,…,P(k+1), P1,…). Finally, making the shift R we get the permutation (P2,P1,P3,P4,…).
Now we have swapped first two elements of the permutation.
Thus, we’ve showed that if k < n, k is even, any permutation can be obtained from P.
The second case: k < n, k is odd
Note that we can perform a cyclic shift of any k consecutive elements using k-1 swaps of the consecutive elements. Since k is odd, k-1 is even. It means that the parity of the permutation won’t change during operations. So, if parities of permutations P and Q aren’t equal, the answer is -1. Now let’s show that any other permutation belong to S, or, in other words, that S consists of all the permutations of the parity the same to the parity of P.
Now we can’t swap the first two elements like in the previous case, because it changes parity of the permutation. Instead of that we can cyclically shift the first three elements of the permutation. We do this in similar manner: using several LR-combinations to obtain the permutation (P3,P4,…,P(k+1),P1,P2,…) and make the RR-combination to get permutation (P3,P1,P2,P4,…).
Using this construction, we are able to place the first k-2 numbers to their places. The order of the remaining 2 numbers is determined by the parity of the initial permutation.
So, if the parities of the permutations P and Q are equal, these elements will go in the right order, so we can obtain the permutation Q from the permutation P.
Reformulating the problem
Now we need to solve the following problem:
- If k is even, find the rank of the permutation Q.
- If k is odd, find the rank of the permutation Q among all the permutations having the same parity with P.
Note that the permutations with the lexicographic indices 2i and 2i+1 (0-based) have distinct parities - we can prove this using induction by length of permutation. So, if lexicographic the index of the permutation Q is x, the 0-based answer will be equal to ⌊x/2⌋, and 1-based answer will be bigger by one.
Solving the reformulated problem
First of all, if k is odd, we need to check, whether the parities of Q and P coincide or not. The parity of the permutation is basically the parity of the number of the inversions in this permutation. Here is the detailed tutorial on finding the number of inversions in the permutation.
After the check is done, all that is left is to find the rank of the permutation Q (and then, if k is odd, to divide it by two using modular inverse).
Finding the rank of the permutation
The 0-based rank of the permutation will be equal to the number of the permutations that are lexicographically smaller than this permutation. In order to calculate it, let’s calculate the sum of the total number of permutations that have the first element smaller than the first element in the sought permutation, the total number of permutations that have the first element equal to the sought permutation but the second element smaller than the second element in the sought permutation, the total number of the permutations that have the first two elements equal to the first two elements of the sought permutation and the third element smaller than the third element in the sought permutation, and so on.
The number of the permutations where the first element is smaller than the first element of the sought permutation is (Q1-1)*((n-1)!) because the first element should be less than
Q1 and the rest can be chosen arbitrarily, so there are (n-1)! ways to do that.
Similarly, the number of permutations where the first element is equal to the first element of the sought permutation, but the second one is less than the second element of the sought permutation is Q2 - (1, if (Q1<Q2) and 0, otherwise)*((n-2)!) because after processing the first element, we can throw it away and consider a permutation of (n-1) integers.
All in all, we can write the pseudocode for calculating the rank of the permutation Q:
answer = 0
factorial = 1
for i = 1 to n do : factorial* = factorial[i - 1] * i mod (109+7)
for i = 1 to n do : isOccured* = 0
for i = 1 to n do :
elementsSmaller = 0
for j = 1 to Q*-1 : elementsSmaller = elementsSmaller + isOccured[j]
answer = (answer + elementsSmaller * factorial[n - i]) mod (109+7)
isOccured[Q*] = 1
The code above runs in O(n2), so if you use it without any changes, it will bring you at most 60 points. But now, we can notice that since all we do is the single element modification and finding the sum on the subsegment, it can be replaced with a fenwick tree or a segment tree, thus, reducing the complexity to O(n log n) and giving us the 100-point solution.
Can be found here
Can be found here