SEAPERM3 question

So, the solution for M=0 is made up from cycles of consecutive numbers. For example a permutation from [1,8] can be made up from some permutation cycle of [1,3] then cycle [4,6] and cycle [7,8]. The number of those cycles as a solution for M=0 can be found by N!-F(N) where F(N) is found by recurrence F(N)=2*F(N-1)+F(N-2). Then it can be shown that the solution for any M is a product of some constants(2,3,4) and F(i) where i are some lengths between segments. This was too hard for me to implement all cases for all constants, i.e. it took me a lot of time to solve for all types of pairs (X,V) where V>=X, and (X,V) where V<=X, but i couldn’t merge those 2 types of pairs, so i ended up typing nothing. Is there any easy way to merge these, or the problem should be approached differently such as with some DP knowing that you can jump forward by 1 or 2, i.e. if p(a)=b and b>a, b can be only a+1 or a+2?

So what you have here is a O(N*3) DP right?
Notice that the transition of states where the value is not fixed remains technically the same. So, we can use matrix exponentiation to jump from some value of DP to another. Where the value is fixed, we can simply do our original DP. This is O(3^3 \cdot log N \cdot M+M). I couldn’t code this myself but others had implemented this. Also, to solve last subtask, you need to cache and hard code the factorial values.

Not O(N^3), that what u said O(3^3*logN*M+M) is what i had in mind, but there were a lot of cases…

Umm, the operations required for jumping for 1 test case would be about 8.6 * 10^6. 10 tests make that 8.6*10^7+10^5. Calculating (n-m)! however, is O(n-m), which wont work for last subtask. To fix that, just hardcode values of factorial at some intervals.

P.S. I wrote N multiplied by 3. Not n^3.

Can you explain how you got the recurrence?

The answer for n=1 to 8 and m=0 are 0,0,1,12,91,650,4871,39912

@anupam_datta you can only jump one or two forwards, or you can end cycle and return, by ending cycle you continue from next step, then as with Fibonnaci reccurence you can look at this as filling the tile nx1 with tiles of length 2x1, green tile with length 1x1, and blue tile with length 1x1, there’s where reccurence comes from.

@nibnalin yes yes, sorry, anyway too many cases for me even for 65 pts this way.

@anupam_datta And sorry, this is the number of bad permutations, you substract this from (N-M)! !!!

@nidzulandz can you explain the cycle part?

@anupam_datta Consider you are jumping 1->3->5, and you choose to end cycle, it will and as 5->4->2->1, that is uniquely determined, and then you continue from 6, that is the same as if you jumped immidietly to 6 in reccurence.

//