dynamic programming, matrix expontiation
Given two arrays X and V of length M and an integer N, count the number of permutations P of length N which satisfy all the following:
- There exist at least one pair (i,j) such that Pi > j and Pj > i
- for all j between 1 and M we have PXj = Vj
Let’s call a pair (i,j) good if it satisfy Pi > j and Pj > i, the problem asks us to count the number of permutations having at least one good pair and also satisfying second condition (i.e. for all j between 1 and M we have PXj = Vj).
instead of counting the number of permutations having at least one good pair we count the number of permutation having no good pairs then we subtract it from total number of permutations satisfying second condition.
Observation 1: All permutations which don’t have good pairs must satify Pi ≤ i+2 for all i between 1 and N
proof: Let’s assume Pi = i+3 or bigger then all Pj such that j < i+3 must have value less than i in order to prevent having a bad pair, but there are i+1 such elements to fill but only i different values available so this is impossible.
Observation 2: if Pi ≤ i+2 for some permutation then only consecutive elements can be good pair in that permutation.
proof: Let’s say elements with indices i and j are bad i < j then j < Pi but we have Pi ≤ i+2 so i < j < i+2 and that means j = i + 1
Special Case: arrays X and V are empty
This is can be solved by dynamic programming, let Fi,0 means the number of ways to fill first i elements of the permutation and the value of i-th element is NOT i+2, and Fi,1 means the number of ways to fill first i elements of the permutation and the value of i-th element is equal to i+2
now let’s think of transactions clearly all values of Fi should be computed using only Fi-1, so let’s think of four cases
- We want to set Pi = i+2 and Pi-1 = i-1+2: this will lead to have good pair so we should ignore this case.
- We want to set Pi = i+2 and Pi-1 != i-1+2: so we have this transaction Fi,1 += Fi-1,0
- We want to set Pi != i+2 and Pi-1 != i-1+2: note that we have exactly two ways to pick a value for Pi so Fi,0 += 2 * Fi-1,0
- We want to set Pi != i+2 and Pi-1 = i-1+2: we have exactly one way to pick a value for Pi, because there are exactly 3 values between 1 and i+2 not picked yet, one of them is i+2, and second one is i because if it was picked then (i-2,i-1) would be a good pair, and the last one is a value less than i, we don’t want to pick i+2 as we assumed Pi != i+2 from the beginning also we can’t pick i otherwise (i-1,i) would be a good pair, so the only option left is the value which is less than i, that’s why we have exactly one way to pick a value for Pi. so Fi,0 += Fi-1,1
so this will lead to O(N) solution which can be done in O(log n) using matrix exponentiation
in case X and V were empty we could use matrix exponentiation immediately because transformation matrix is fixed for all indices i. however, in case X and V are not empty then transformation matrix is not the same for all positions because coefficients of the transactions discussed above can be different and they depend on arrays X and V, so we need to divide the indices of the array P into ranges such that each range have a the same transformation matrix, in order to do so we create new array Q having those values:
- Xi-2, Xi-1, Xi, Xi+1 and Xi+2 for all i between 1 and M
- Vi-2, Vi-1, Vi, Vi+1 and Vi+2 for all i between 1 and M
- N-1 and N
after that we remove duplications from Q then sort it in increasing order, now it’s easy to see that transformation matrix on the range Q1…Q2 is the same and also it’s same for range Q2…Q3 and so on.
so we can apply matrix expontiation on each range alone and we would have complexity O(K log N) where K is the size of array Q, but K is O(M) so overall complexity is O(M log N) but it has very large constant factor (i.e. 8 from matrix multiplication and 10 from the size of Q)
Computing N factorial
We need to compute N! because as we said before we count the number of not required permutations then subtract them from total number of permutation, so to compute N! we can pre-compute the factorial for each N multiple of 107 on our own machine then paste the answers in the source code, now computing N! for any N will not take more than 107 operations
Will be uploaded soon.
Can be found here.