部分点 1 $(N \le 6)$

\(Q\) としてあり得るものは \(N!\) 通りであり、\(N \le 6\) の制約下においては \(720\) 通りしかありません。

よって、それぞれの \(Q\) を頂点と見たグラフで BFS をし、到達可能な頂点全ての \(Q\) に対して転倒数を求めてその総和を答えればよいです。計算量は \(\mathrm{O}(N! (N^2+M))\) です。

満点

解説において、以下のように複数の用語を定義します。また、表記の都合上順列の \(i\) 項目を \(P_i\) とも \(P(i)\) とも表記することがあります。

• 順列の集合 \(P\) に対してそれらを複数個合成して得られる順列の集合を \(F(P)\) と表す。

• \(F(P)\) の要素のうち前 \(i\) 項が \((1,2,\dots,i,\dots)\) となっているものからなる集合を \(F_i(P)\) と表す。ここで、\(F(P) = F_0(P)\) である。

• \(F_i(P) = F(P_i)\) を満たす順列の集合のうちいずれかを \(P_i\) と置く。ここで、\(P_0 = P\) である。（\(P\) の要素を指している訳ではないことに注意）

• 順列の集合 \(P,Q\) に対して多重集合 \(P \times Q\) を \(\lbrace pq | p \in P,q \in Q \rbrace\) で定義する。

さて、目標は順列の集合 \(N\) 個 \(Q_1,Q_2,\dots,Q_N\) として以下の条件を満たすものを得ることです。

• \(Q_i\) のサイズは \(N\) 以下
• \(Q' = Q_1 \times Q_2 \times \dots \times Q_N\) の要素に被りはなく更に \(Q' = f(P)\) が成立する。

もしこのような \(Q_1,Q_2,\dots,Q_N\) が得られた場合、「\(Q_1,Q_2,\dots,Q_k\) までから要素を選んだ時に \(q'_i < q'_j\) を満たす \(q'\) の個数」という動的計画法を行うことでこの問題を \(\mathrm{O}(N^4)\) で解くことが出来ます。以降、\(Q_1,Q_2,\dots,Q_N\) を得ることを考えます。

さて、\(P_k\) から \(P_{k+1}\) と \(Q_{k+1}\) を高速に得ることを考えます。これが達成できればこのステップを \(N\) 回行うことで目標を達成できます。まず、\(f(P_k)\) に属する順列の \(k+1\) 項目としてあり得る値を列挙します。これは、\(p_{k+1} = x,q_x = y\) である順列 \(p,q\) を用いると \(q_{p_{k+1}} = y\) のように \(k+1\) 項目が \(y\) である順列を得られるので BFS を行うことで \(\mathrm{O}(N |P_k|)\) で列挙が可能です。得られた値の集合を \(\mathrm{orbit}_k\) とし、\(k+1\) 項目が \(x\) であるような \(f(P_k)\) の要素を \(g_x\) とします。（以降、\(g_x\) の集合を \(G\) とします。）

さて、ここで \(P_{k+1} = \lbrace g_{s_u}^{-1} s g_u | u \in \mathrm{orbit}_k,s \in P_k \rbrace\) とすると実際に条件を満たすことを確認します。まず、\(P_{k+1}\) に属する要素は \(P_k\) に属する要素から作れるので \(f(P_{k+1}) \subset f(P_k)\) です。更に、\(P_{k+1}\) に属する要素は始めの \(k+1\) 項が \((1,2,\dots,k+1,\dots)\) となっていることが確認できます。あとは \(f(P_k)\) の要素のうち始めの \(k+1\) 項が \((1,2,\dots,k+1,\dots)\) となっているもの \(s' = s_1 s_2 \dots s_m(s_i \in P_k)\) を実際に \(P_{k+1}\) の要素でも表せることを示せばよいです。以降、\(r_i = s_i s_{i+1} \dots s_m\) とします。

\(s' = s_1 \left(g_{r_2(k+1)}g_{r_2(k+1)}^{-1}\right) s_2 \left(g_{r_3(k+1)}g_{r_3(k+1)}^{-1}\right) s_3 \dots \left(g_{r_m(k+1)}g_{r_m(k+1)}^{-1}\right) s_m = \left(g_i^{-1} s_1 g_{r_2(k+1)} \right) \left(g_{r_2(k+1)}^{-1} s_2 g_{r_3(k+1)} \right) \dots \left(g_{r_m(k+1)}^{-1} s_m g_i \right)\) と表せます。ここで \(r_i(k+1) = s_i(r_{i+1}(k+1))\) であることを利用すると最後の式の括弧内の要素は全て \(P_{k+1}\) に属しています。よって、\(P_{k+1}\) が条件を満たしていることが分かりました。

\(Q_{k+1}\) についても考えます。実は、\(Q_{k+1} = G\) とすればよいです。これを証明します。\(G \times f(P_{k+1}) = f(P_k)\) であることが証明出来ればよいです。まず、前者が後者に含まれることは簡単に分かります。さて、後者が前者に含まれることを示しましょう。\(f(P_k)\) の要素 \(s\) を適当に持ってきます。ここで、\(g_{s_k}^{-1} s\) は \(f(P_{k+1})\) に含まれます。この要素を \(t\) としましょう。今、\(g_{s_k}^{-1} s = t\) が言えました。よって、\(s = g_{s_k} t\) が成立し、\(f(P_k)\) の要素が \(G \times f(P_{k+1})\) に含まれることが証明出来ました。

上記を繰り返せば \(Q_1,Q_2,\dots,Q_N\) を得ることが出来ますが、問題として \(|P_{k+1}| = |P_k||\mathrm{orbit}|\) であるため \(P_{k+1}\) のサイズが指数的に増えてしまいます。そこで、\(S\) から \(f(S) = f(T)\) を満たす \(T\) であって、\(|T| \le N^2\) を満たす \(T\) を得る以下のアルゴリズムを適用すればよいです。

• \(N \times N\) の配列 \(d\) を用意する。始め、\(d\) の要素には何も入っていない。
• \(S\) の要素 \(s\) に対して以下を \(i=1,2,\dots,N\) の順に実行する。
  • \(d[i][s_i]\) が空なら \(d[i][s_i] = s\) として \(s\) 自体への操作を終える。
  • そうでないなら \(s\) を \(s^{-1} d[i][s_i]\) に置き換えて次の \(i\) に進む。
• 最終的な \(d\) を \(T\) として返す。

アルゴリズムとしては、\(s\) を前から順番に \(s_i = i\) としていきそれが出来なくなれば \(T\) に追加しています。このアルゴリズムは \(\mathrm{O}(|S| N^2)\) で動作します。

上記をまとめることで、この問題を \(\mathrm{O}(N^6)\) で解くことが出来ます。

参考：https://codeforces.com/blog/entry/111290