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₁, p₂, ..., 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: dp2[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²). With the help of this array, the original can be calculated in O(N³). 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²).

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!