\((1, \ldots, N)\) の順列は、左側頂点 \(1, \ldots, N\)、右側頂点 \(1', \ldots, N'\) を持つ完全二部グラフの完全マッチングと一対一対応します。具体的には、順列 \((r_1, \ldots, r_N)\) には、各 \(1 \leq i \leq N\) に対して辺 \((i, r_i')\) を採用するマッチングを対応させます。

この考え方を用いると、問題は次のように言い換えられます。

左側頂点 \(1, \ldots, N\)、右側頂点 \(1', \ldots, N'\) を持つ二部グラフ \(G\) には、各 \(1 \leq i \leq N\) に対して辺 \((i, p_i')\) および \((i, q_i')\) がある。\(G\) の補グラフ（完全二部グラフから \(G\) に含まれる辺を除いたグラフ）の最大マッチングの個数を求めよ。

包除原理から、\(G\) のサイズ \(k\) のマッチングの個数を \(a_k\) とすると、答えは \(\displaystyle \sum_{k=0}^N (-1)^k a_k (N-k)!\) となります。\(a_k\) を各 \(0 \leq k \leq N\) に対して求めることを考えましょう。

ここで重要な観察として、\(G\) の各連結成分はサイクルになっています。これは、各辺に \(i \to p_i'\) および \(i \leftarrow q_i'\) という向き付けをしてみると、各頂点の入次数・出次数がともに \(1\) となることからわかります。

この性質を利用すると、次のような動的計画法で答えが求まります。

• \(\mathrm{dp}(i, j) := i\) 個目の連結成分まで見て、マッチングに採用した辺の本数が \(j\) であるようなマッチングの個数

DP をするにあたって「頂点数 \(n\) のサイクルからサイズ \(k\) のマッチングを選ぶ方法の数」が必要になりますが、これは \(\displaystyle \binom{n-k}{k} + \binom{n-k-1}{k-1}\) という式で表せます（これがわからなくても、漸化式を立てる等して \(O(N^2)\) かけて前計算してもよいです）。\(2\) 頂点のサイクルが多重辺を含むコーナーである点には注意してください。計算量は自然な実装で \(O(N^2)\)、分割統治 FFT（任意 mod）を用いると \(O(N \log^2 N)\) です。

サイクルグラフのマッチングの個数について補足します。

• \(m_p(n, k) := n\) 頂点のパスグラフのサイズ \(k\) のマッチングの個数
• \(m_c(n, k) := n\) 頂点のサイクルグラフのサイズ \(k\) のマッチングの個数

と定めます（この解説だけの記号）。

\(\displaystyle m_p(n, k) = \binom{n-k}{k}\) となります。実際、「左右一列に並んだ \(n-k\) 個の無色の玉から \(k\) 個を選び、選んだ玉のうち \(i\) 個目のものについては色 \(i\) で塗った後にその右隣に色 \(i\) の玉を挿入する」という操作を考えると、得られる色の列が \(n\) 頂点パスグラフのサイズ \(k\) のマッチングに対応していることがわかります。（関連：典型 015）

\(m_c(n, k)\) については、次のような場合分けで求まります。（サイクルをなす頂点を順に \(1, 2, \ldots, n\) とします。）

• 辺 \((1, n)\) をマッチングに採用しない場合：その辺を除くと \(n\) 頂点のパスグラフになるので \(m_p(n, k)\) 通り
• 辺 \((1, n)\) をマッチングに採用する場合：頂点 \(1, n\) およびそれに隣接する辺を除くと \(n-2\) 頂点のパスグラフになるので \(m_p(n-2, k-1)\) 通り

これより \(\displaystyle m_c(n, k) = m_p(n, k) + m_p(n-2, k-1) = \binom{n-k}{k} + \binom{n-k-1}{k-1}\) を得ます。

なお、\(m_p(n, k), m_c(n, k)\) はそれぞれ、Fibonacci polynomials, Lucas polynomials と呼ばれる多項式の係数になっているようです（Wikipedia, Fibonacci polynomials の OEIS, Lucas polynomials の OEIS）。この性質を利用した高速化が何かないか考えましたがわかりませんでした。