持っている順列のうち、少なくとも \(1\) つの順列で swap が発生するような \((a_i, b_i)\) の組を 有効である と呼び、有効な組に関する swap を順列の組に作用させることを 有効な swap と呼びます。
次の事実が証明できます。

命題：\(M\) 回の操作の過程で、有効な swap は高々 \(N(N-1)/2\) 回しか発生しない。

(証明) 持っている順列の組に対して、有効でない整数対 \((a, b)\) の個数を \(X\) とします。はじめ \(X=0\) です。
\(X\) に関して次の補題が証明できます。

補題：有効な swap を作用させるごとに \(X\) は \(1\) 以上増加する。

(補題の証明) 順列の組に有効な \((a, b)\) を作用させると \((a, b)\) は有効でなくなるので \((a, b)\) の \(X\) に対する寄与が \(1\) 増えます。
それ以外の整数対の寄与のうち、swap 後に減少することが考えられる整数対は次の 2 通りです。

• \((c, a)\) が有効でなかったが \((a, b)\) swap を作用させた後に有効になった
• \((b, c)\) が有効でなかったが \((a, b)\) swap を作用させた後に有効になった

前者について考えます。 \((c, a)\) が有効でないということは、すべての順列 \(p\) について \(p_c \leq p_a\) が成り立つことをいいます。そして、\((a, b)\) swap を作用させることは \(p_a, p_b \gets \min(p_a, p_b), \max(p_a, p_b)\) に入れ替える操作なので、\(p_c \leq p_a \leq \max(p_a, p_b)\) より、操作後の順列を \(p'\) とすると \(p'_c \leq p'_b\) が成り立つので、操作後は \((c, b)\) は有効でないです。
また、「\((c, a)\) が有効でなかったが \((a, b)\) swap を作用させた後に有効になった」ならば、ある順列 \(p\) であって \((p_c, p_a, p_b) = (1, 1, 0)\) を満たすものが存在します。よってこのような場合、swap の前に \((c, b)\) は有効な swap です。
よって、 \((c, a)\) の \(X\) の寄与が減少する条件下では代わりに \((c, b)\) への寄与が \(1\) 増加するため \(X\) への負の寄与は打ち消されることが示せました。
後者についても同様の議論が回ります。よって有効な swap を作用させるごとに \(X\) は \(1\) 以上増加します。(補題の証明終わり)

全ての列がソートされた時点で \(X=N(N-1)/2\) なので、補題と合わせると、有効な swap は高々 \(N(N-1)/2\) 回であることがここから証明できました。(証明終わり)

この事実を利用すると、実は愚直な DP に適切な枝刈りを行えば高速に動作することがわかります。
詳しく説明します。ある時点での sorted な列の個数は (長さ \(N\) の 01 列であって, 現時点までの swap を作用させると sorted になる列の集合) がわかっていれば次の要領で計算できます。

• \(2 \times 2 \times \dots \times 2\) の \(N\) 次元グリッドがあり、swap を作用させるとsorted になる 01 列に対応する座標のマスは通行可能で、それ以外のマスは通行不可能である。このとき \((0,0, \dots ,0)\) から \((1,1, \dots,1)\) への経路の本数が sorted である順列の個数に対応する。

上の経路数 DP は \(\mathrm{O}(N 2^N)\) で動作するので、sorted になる列の集合の更新が \(\mathrm{O}(N^2)\) 回であることを合わせると、個数を計算する DP の部分は \(\mathrm{O}(2^N N^3)\) の計算量で抑えられます。

よって、長さ \(N\) の 01 列に swap を作用させていったときの状態を管理する DP を考えます。長さ \(2^N\) の配列 \(S\), \(N\times N\) の配列 \(C\) を次のように置きます。

• \(S[x]\) (ここで \(x\) は 01 列に対応する bit) \(:=\) (操作を行う前の状態が \(x\) で、それに \((a, b)\) を作用させたときの現在の状態)
• \(C[i][j]\) ： (\(S[x]\) の \(i\) bit 目が \(1\) で \(j\) bit 目が \(0\) であるような \(S[x]\) の個数, ただし \(i < j\))

\((i, j)\) 間の swap を作用させるときは、以下の手順を行います。

• \(C[i][j]\) が 非 \(0\) かどうかで\((i, j)\) swap が有効かどうかが \(\mathrm{O}(1)\) で判定できる。有効でない場合は手順を打ち切る。
• 必要な場合は \(S[x]\) をすべて走査して, \(S[x]\) の \(i\) bit 目と \(j\) bit 目が swap 可能なときに swap して \(S[x]\) の値を更新する。
  • それに応じて \(C[i][j]\) の値も同時に更新する。値を更新する必要があるので \(C[i][*], C[j][*], C[*][i], C[*][j]\) の部分のみなので \(\mathrm{O}(N)\) で計算できる。
  • また、\(S[x]\) が sorted になった場合は \(x\) に対応するマスを通行可能なマスにする。
• その後、経路数 DP をして答えを更新する。

このアルゴリズムは全体で \(\mathrm{O}(2^N N^3 + M)\) で動作して高速です。実装例
また、説明は省略しますが、上のアルゴリズムより実装が易しい \(\mathrm{O}(2^N N^4 + M)\) 解法もあり、定数倍の軽い書き方をすればこれでも AC するのに十分です。実装例

以上よりこの問題を \(\mathrm{O}(2^N N^3 + M)\) 程度で計算出来て、これは十分高速です。

(別解として、01 列の隣接 swap が全体で \(\mathrm{O}(2^N N^2)\) 回しか発生しないことを利用して、通行可能なマスが増えるごとに経路数 DP のテーブルを更新していく \(\mathrm{O}^\ast (3^N)\) 解法があります。)