\(1,\ldots,N\) を頂点とし、\((P_i,Q_i)\) に辺を張ったグラフ \(G\) を考えます。問題は「辺の部分集合 \(E\) であって、辺被覆となるものは何通りありますか？」と読み替えることができます。この問題は明らかに連結成分ごとに考えることができます。

\(P,Q\) はともに \((1,\ldots,N)\) の並び替えなので、\(G\) はどの頂点の次数も \(2\) であり、サイクルの集まりになることがわかります。したがって、サイクルの場合の問題が解ければ良いです。

あとで使うので、まずは次の問題を考えます。
「\(1,2,\ldots,M\) の中からいくつかの数を選びます。ただし、連続する \(2\) 数のどちらは必ず選ぶ必要があります。選び方は何通りありますか？」
この問題の答えを \(f(M)\) とすると、\(f(1)=2,f(2)=3,f(M)=f(M-1)+f(M-2)\) を満たすことがわかります。（\(M\) を選ぶか選ばないかで残りの選び方がどうなるか考えるとわかります）

本題に戻ります。
\(1,\ldots,M\) を頂点とする \(M\) 頂点のサイクルの辺の部分集合であって、辺被覆となるものは何通りあるでしょうか。これは「隣り合う辺のどちらかは必ず選ぶ必要があります。選び方は何通りありますか？」という先ほどとよく似た問題になります。この問題の答えを \(g(M)\) とします。辺 \((1,M)\) を選ぶか選ばないか場合分けすることで、答えは \(g(1)=1,g(2)=3,g(3)=4,g(M)=f(M-1)+f(M-3)\) を満たすことがわかります。

以上により、\(M\leq N\) の範囲の \(f(M),g(M)\) 全てを計算することが \(O(N)\) でできるので、この問題を\(O(N)\) で解くことができました。なお、式を整理すると \(g(N)=L_N\) となることが示せます。(\(L_N\) はリュカ数)