\(P_i > P_{i+1}\) となる \(i\) の集合 \(S\) を決め打った場合を考えます．

包除原理を考えると，次のような問題を解けばよいです．

• \(S\) の部分集合のペア \(a,b\) すべてについて，\(f(a) \times f(b)\) を計算し総和を取れ．ただし \(f(x)\) は以下のように定義される値である．
  • \(i \not \in x\) なる \(i\) すべてについて \(p_i<p_{i+1}\) を満たす順列 \(p\) の個数を数える．この値に \((-1)^{|x|}\) をかけて，\(f(x)\) とする．

\(S\) を動かし，さらに \(a,b \subset S\) すべてについて \(f(a) \times f(b)\) の和を取るのが目標です．

\(a,b\) のペアを一つ固定したとき，\(i \in a\) かつ \(i \in b\) を満たす \(i\) の個数を \(w(a,b)\) と置くと，ありうる \(S\) の個数は \(2^{N-1-|a|-|b|+w(a,b)}\) となります．

\(2^{w(a,b)}\) の項を無視した場合の数え上げは簡単です． 数えたい値が \(2^{N-1} \times (f(a)/2^{|a|}) \times (f(b)/2^{|b|})\) のように \(a\) のみに依存する項と \(b\) のみに依存する項に分解できるので，\((\sum_{a}f(a)/2^{|a|})\) と \((\sum_{b}f(b)/2^{|b|})\) の積を求めるだけになります． ここで，\(g(N)=(\sum_{a}f(a)/2^{|a|})^2/(N!)^2\) と置くことにします．

\(2^{w(a,b)}\) の重みをつける方法を考えます． \(a \cap b\) の部分集合の個数がちょうど \(2^{w(a,b)}\) なので，以下の方法で目標の重みをつけることができます．

• \({1,2,\cdots,N-1}\) の部分集合 \(c\) 全てについて以下の値を求め，その総和を求める．
  • \(c \subset a\) かつ \(c \subset b\) なる \(a,b\) すべてについての \((f(a)/2^{|a|}) \times (f(b)/2^{|b|})\) の総和を取る．

これは結局，次のような問題に帰着されます．

• \(0\) から \(N\) まで至る方法が何通りあるか求めよ．ここで，\(i \to j\) (\(0 \leq i < j \leq N\)) という遷移の重みは \(g(j-i)/4\) とする．

\(g(1),g(2),\cdots,g(N)\) を求めるのは多項式の inv もしくは FFT+分割統治で行えます． また \(g\) の情報から答えを求めるのも同様に多項式の inv か FFT+分割統治で行えます．

計算量は \(O(N \log N)\) または \(O(N \log^2 N)\) です．

解答例