各 \(0 \leq k \leq N\) に対し、\(k\) 個の添字について \(r_i = p_i\) または \(r_i = q_i\) となるような順列の総数を求めることができれば、包除原理によって答えを計算することができます。

「\(r_i = p_i\) または \(r_i = q_i\) となる」と決めた添字を \(i_1, i_2 ,\dots, i_k\) とします。これらの添字について \(r_i\) に異なる値を割り当てる方法の総数を求めましょう。

\(i = i_1, \dots, i_k\) について、 \((p_i, q_i)\) を \(N\) 頂点のグラフの辺とみなします。このグラフの各辺にその端点のうち一方を割り当てる方法であって、どの異なる二辺についても割り当てられた頂点が異なるようなものの総数を求めればよいです。

孤立点や自己ループを除いた連結成分ごとに考えます。グラフの最大次数は \(2\) 以下であるため、次の二通りが考えられます。

• 連結成分が一つのサイクルからなるとき、\(2\) 通り。
• 連結成分が一つのパスからなるとき、その頂点数を \(L\) として、\(L\) 通り。

これらの総積を取ればよいです。

さて、全ての \(i_1, i_2 ,\dots, i_k\) の組み合わせについて上記の値を合計したものを求める必要があります。全ての \((p_i, q_i)\) を追加したグラフを考え、その連結成分ごとにいくつの辺を選ぶか決めていきましょう。連結成分のサイズを \(K\) としたとき、各 \(0 \leq k \leq K\) についてその連結成分から \(k\) 個の辺を選んだ場合の \(r_i\) の割り当て方の総数が計算できていれば、簡単な動的計画法によって必要な値が求められます。以下では、グラフが一つのサイクルであるである場合のみ考慮します。

全ての辺を選ぶとき、前述の議論より \(2\) 通りとなります。 そうでないとき、パスと孤立点の集合となるので、それぞれの大きさを掛け合わせた値となります。これは、辺を選んだあと、選んだ辺からなるグラフの各連結成分から一点ずつ選んで印をつける方法の総数と言い換えることができるため、二項係数の和によって表すことができます。選ばない辺のうち、もっとも番号が小さいものを固定しながら数え上げることで、サイクルを切り開いてパスとみなして計算することができます。

実装例 (C++)