\(3 \leq n\) に対して、問題の条件に加えて「円周上で隣接している頂点間の辺を選ばない」という条件を課した際の \(m\) 辺の選び方の数を \(a_{n,m}\) とし、形式的べき級数 \(f_n = \sum_{m=0}^{\infty} a_{n+3,m} y^m, F = \sum_{n=0}^{\infty} f_{n} x^n\) を考えます。円周上で隣接する頂点間の辺はほかの辺の選択に影響しないことから、問題の条件を満たす辺の選び方の数は \([y^M](1+y)^N f_{N-2}\) であることに注意します。

\(n+3\) 頂点ある場合において問題の条件を満たす \(m\) 辺の選び方について、頂点 \(1\) を端点とする辺のうち、もう一つの端点の頂点番号の最小値を考えると以下の \(5\) つに場合分けできます。

• 頂点 \(1\) を端点とする辺を \(1\) つも選ばない場合
• 選んだ辺のうち頂点 \(1\) を端点とする辺のもう一つの端点の頂点番号の最小値が \(2\) である場合
• 選んだ辺のうち頂点 \(1\) を端点とする辺のもう一つの端点の頂点番号の最小値が \(3\) である場合
• 選んだ辺のうち頂点 \(1\) を端点とする辺のもう一つの端点の頂点番号の最小値が \(n+3\) である場合
• 選んだ辺のうち頂点 \(1\) を端点とする辺のもう一つの端点の頂点番号の最小値が \(i (4 \leq i \leq n+2)\) である場合

例えば最後のパターンについて、辺を選ぶ方法の数は

• 頂点 \(2,3,\dots,i\) の \(i-1\) 頂点内の辺を選ぶ
• 頂点 \(1,i,i+1,\dots,n+3\) の \(n+3-i+2\) 頂点内の辺を選ぶ。ただし、頂点 \(1,i\) 間の辺は必ず選ぶ

と考えることで \([y^m] (1+y)^{i-1}f_{i-4} \times y(1+y)^{n+3-i+1}f_{n+3-i-1} \) と求められます。

その他の場合についても同様の考え方により、以下の式が成り立つことがわかります。

\[(1+y)^{n+3} f_{n} = (1+y)^{n+2} f_{n-1} + y(1+y)^{n+2} f_n + y (1+y)^{n+2} f_{n-1} + y(1+y)^{n+2}f_{n-1} + \sum_{i=0}^{n-2} y(1+y)^{n+3} f_i f_{n-2-i}\]

整理すると

\[f_{n} = (1+2y) f_{n-1} + \sum_{i=0}^{n-2} y(1+y) f_i f_{n-2-i}\]

よって

\[F-1 = x(1+2y)F + y(1+y)x^2 F^2 \]

が成り立ちます。これを \(F\) についての二次方程式として \([x^0]F = 1\) という条件と合わせて解くと

\[\displaystyle F = \frac{-(x+2xy-1)-(1-x)\sqrt{1-\frac{4xy}{(1-x)^2}}}{2xy(1+y)}\]

となります。

さて、求めるべき答えは \([x^{N-2}][y^M] (1+y)^{N}F\) であるため、 \([x^n][y^m] F\) が \(O(1)\) 時間で求まれば \(O(N)\) 時間で求めることができます。

これは結局 \([x^n][y^m] \sqrt{1-\frac{4xy}{(1-x)^2}} \) を求めることができればよく、これは \([x^n] \frac{x^m}{(1-x)^{2m}} \times [y^m] \sqrt{1-4y}\) です。いずれも二項係数を用いて表せることから、階乗などの前計算のもと \(O(1)\) 時間で求められます。

以上より問題の答えを \(O(N)\) 時間で求めることができます。