答えを動的計画法で求めることを考えます。

辺について、

• \(1\leq i\leq N-1\) について、頂点 \(i\) と頂点 \(i+1\) を結んでいる辺を辺 \(a_i\),
• \(1\leq i\leq N-1\) について、頂点 \(N+i\) と頂点 \(N+i+1\) を結んでいる辺を辺 \(b_i\)
• \(0\leq i\leq N-1\) について、頂点 \(i+1\) と頂点 \(N+i+1\) を結んでいる辺を辺 \(c_i\)

とおきます。

ここで、各 \(k=0,1,\ldots,N-1\) について、\(i\leq k\) なる辺\(a_i\), \(b_i\), \(c_i\) を取り除くか決めた時の頂点 \(1,2,\ldots,k+1\)と \(N+1,N+2,\ldots,N+k+1\) の \((2k+2)\) 頂点からなる部分グラフ \(G_k\) について考えます。ここで、\(G=G_{N-1}\)　です。

ここで、もし \(G_k\) に頂点 \(k+1\) も \(N+k+1\) も含まない（空でない）連結成分が存在したとすると、もしこの後 \(i> k\) なる辺\(a_i\), \(b_i\), \(c_i\) をすべて残しても最終的にグラフが全体で連結となることはありません。よって、最終的に \(G\) が連結になるような 部分グラフ \(G_k\) の状態としてあり得るものは

• 状態 \(0\) : \(G_k\) は連結
• 状態 \(1\) : \(G_k\) は \(2\) つの連結成分に分かれており、一方には頂点 \(k+1\) 、もう一方には頂点 \(N+k+1\) が属している。

の \(2\) 種類しかありません。

そこで、 \(G_i\) において、\(x\leq i\) なる辺\(a_x\), \(b_x\), \(c_x\) のうちちょうど \(j\) 本 を取り除いて状態 \(k\) となっているようなグラフの個数を\(P\) で割ったあまりを \(dp[i][j][k]\) として、これを更新していく事を考えます。求めたいものは各 \(1\leq j\leq N-1\) についての \(dp[N-1][j][0]\) の値です。

まず、\(i=0\) の場合において、\(G_0\) は \(2\) 頂点のみからなり、 辺 \(c_0\) が存在するかどうかで \(dp[0][0][0]=dp[0][1][1]=1\) かつ その他において \(dp[0][j][k]=0\) です。

更新について、\(G_{i-1}\) から \(G_i\) になる時に新しく考慮する辺は辺 \(a_i\) , 辺 \(b_i\) , 辺 \(c_i\) の \(3\) 本です。状態 \(0\), \(1\) それぞれのグラフ \(G_{i-1}\) についてこれらを残すか取り除くかした時の \(G_i\) の状態について考えます。

• \(G_{i-1}\) が状態 \(0\) のとき

連結成分として、 \(G_{i-1}\), 頂点\(i+1\), 頂点 \(N+i+1\) の \(3\) つが存在し、\(G_{i-1}\) と頂点\(i+1\)の間を辺 \(a_i\) , \(G_{i-1}\) と頂点\(N+i+1\)の間を辺 \(b_i\) , 頂点\(i+1\) と頂点 \(N+i+1\) の間を辺 \(c_i\) が結んでいます。

まず、 辺 \(a_i\) と 辺 \(b_i\) がともに除かれてしまうと、 \(G_i\) において、 \(G_{i-1}\) は 頂点 \(i+1\) も頂点 \(N+i+1\) も属さない連結成分となってしまい、最終的に連結となることはありません。 逆にそうでない時、\(G_i\) は状態 \(0\) と 状態 \(1\) のいずれかとなります。さらに、辺 \(a_i\) , 辺 \(b_i\) , 辺 \(c_i\) のうち \(2\) 本以上が残されたとき、かつその時に限り \(G_i\) は全体で連結となり、状態 \(0\) となります。残りの場合が状態 \(1\) となります。

• \(G_{i-1}\) が状態 \(1\) のとき

連結成分として、\(G_{i-1}\) の頂点 \(i\) を含む連結成分 \(C_1\) , \(G_{i-1}\) の頂点 \(N+i\) を含む連結成分 \(C_2\) , 頂点\(i+1\), 頂点 \(N+i+1\) の \(4\) つが存在し、\(C_1\) と頂点\(i+1\)の間を辺 \(a_i\) , \(C_2\) と頂点\(N+i+1\)の間を辺 \(b_i\) , 頂点\(i+1\) と頂点 \(N+i+1\) の間を辺 \(c_i\) が結んでいます。

まず、 辺 \(a_i\) と 辺 \(b_i\) のうちどちらか一方でも除かれてしまうと、除かれた方の辺の端点を含む \(G_{i-1}\) 内の連結成分は、 \(G_i\) において頂点 \(i+1\) も頂点 \(N+i+1\) も属さない連結成分となってしまい、最終的に連結となることはありません。 逆にそうでない時、\(G_i\) は状態 \(0\) と 状態 \(1\) のいずれかとなります。このうち、辺 \(c_i\) も含めて \(3\) 本とも残されたとき \(G_i\) は全体で連結となり、状態 \(0\) となり、\(c_i\) が除かれたとき \(G_i\) は 状態 \(1\) となります。

これですべての遷移を確認することができました。 これは配る DP として、各 \(dp[i][j][k]\) に対して 更新を定数時間 \(O(1)\) で行うことができます。

よって、計算量は全体で \(O(N^2)\) であり、十分高速にこの問題を解くことができました。

なお、上記の遷移は多少工夫すれば人の手で行わずともコンピュータで求めることもできます。また、連結成分が全体で \(2\) 以下であることから, \(j\geq i+2\) ならばつねに \(dp[i][j][k]=0\) 等を用いるとより定数倍を軽くして計算することができます。

c++ による実装例 :

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  	int n, p;
	long long dp[2][3010][2];

	cin >> n >> p;

	for (int i = 0; i < 2; i++)for (int j = 0; j < n + 2; j++)for (int k = 0; k < 2; k++)dp[i][j][k] = 0;
	dp[0][0][0] = 1;
	dp[0][1][1] = 1;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < i + 2; j++) {
			for (int a = 0; a < 2; a++) {
				for (int b = 0; b < 2; b++) {
					for (int c = 0; c < 2; c++) {
						if ((a + b + c) <= 1)dp[1][j + a + b + c][0] += dp[0][j][0];
						else if ((a + b) <= 1)dp[1][j + a + b + c][1] += dp[0][j][0];
						if ((a + b + c) == 0)dp[1][j + a + b + c][0] += dp[0][j][1];
						else if ((a + b) == 0)dp[1][j + a + b + c][1] += dp[0][j][1];
					}
				}
			}
		}
		for (int j = 0; j < i + 3; j++) {
			for (int k = 0; k < 2; k++) {
				dp[0][j][k] = dp[1][j][k] % p;
				dp[1][j][k] = 0;
			}
		}
	}
  
	for (int j = 0; j < n - 2; j++)cout << dp[0][j + 1][0] << " ";
	cout << dp[0][n - 1][0] << endl;

	return 0;
}