This is a problem in CSAcademy Contest Romanian IOI 2017 Selection #3, Pitmutation, which basically is: Given two permutations *A*, *B* of length *N* with some positions fixed while some positions remains unknown, find the number of configurations such that there are exactly *S* positions *p*_{1}, *p*_{2}, ..., *p*_{S}, where *A*_{pi} > *B*_{pi}, both *N*, *S* ≤ 300.

I've already come up a solution when there are no fixed positions. For simplicity, we can consider *B* as identity permutation and later multiply the answer by *N*!. Then we decompose the permutation into cycles. Let *dp*[*i*][*j*] denote the number of configurations, when there are *i* elements remaining, and the needed number of *A*_{pi} > *B*_{pi} positions is *j*. Enumerate the length of cycle the smallest element is in for transferring, which involves precalculating another DP: *dp*2[*i*][*j*] denote the number of permutations *A* of length *i* that consists of one cycle such that there are *j* positions *x* where *A*_{x} > *A*_{(x + 1)%i}. This precomputation can be done in *O*(*N*^{2}). With the help of this array, the original can be calculated in *O*(*N*^{3}). Also can be optimized to using FFT. Furthermore, since we only concern the answer with *S* such positions, and every time we are multiplying the same polynomial, so we only need 2 times of DFT, and thus the complexity is *O*(*N*^{2}).

However, I can't generalize this solution to the case where there are fixed positions, and also I can't find an editorial for this problem. Is there anyone willing to share some insights? Thanks in advance!