Consider the case with the fixed set \(S\) of \(i\) such that \(P_i > P_{i+1}\).

After applying the inclusion-exclusion principle, we need to solve the following problem.

• Find the sum of \(f(a) \times f(b)\) over all pairs \(a,b\) of subsets of \(S\), where \(f(x)\) is defined as follows.
  • Count permutations \(p\) that satisfy \(p_i<p_{i+1}\) for all \(i\) such that \(i \not \in x\). Let \(f(x)\) be this value multiplied by \((-1)^{|x|}\).

We want to let \(S\) move and then sum \(f(a) \times f(b)\) over all \(a,b \subset S\).

For a fixed pair \(a,b\), there are \(2^{N-1-|a|-|b|+w(a,b)}\) possible sets \(S\), where \(w(a,b)\) is the number of \(i\) such that \(i \in a\) and \(i \in b\).

If we ignore the term \(2^{w(a,b)}\), the counting is easy. The value to count can be decomposed as \(2^{N-1} \times (f(a)/2^{|a|}) \times (f(b)/2^{|b|})\), with a term only depending on \(a\) and a term only depending on \(b\), so we only have to find the product of \((\sum_{a}f(a)/2^{|a|})\) and \((\sum_{b}f(b)/2^{|b|})\). Here, let \(g(N)=(\sum_{a}f(a)/2^{|a|})^2/(N!)^2\).

Let us consider how to weight them with \(2^{w(a,b)}\). Since \(a \cap b\) has exactly \(2^{w(a,b)}\) subsets, the following method works.

• Find the following value for every subset \(c\) of \({1,2,\cdots,N-1}\), and sum the results.
  • The sum of \((f(a)/2^{|a|}) \times (f(b)/2^{|b|})\) over all \(a,b\) such that \(c \subset a\) and \(c \subset b\).

This can eventually be reduced to the following problem.

• Find the number of ways to get from \(0\) to \(N\). Here, the transition \(i \to j\) (\(0 \leq i < j \leq N\) has a weight of \(g(j-i)/4\).

One can find \(g(1),g(2),\cdots,g(N)\) by inv of polynomial or FFT + divide-and-conquer. Finding the answer from the information of \(g\) can also be done by inv of polynomial or FFT + divide-and-conquer.

The complexity is \(O(N \log N)\) or \(O(N \log^2 N)\).

Sample solution