设 \(f_{i,j,0/1}\) 表示考虑前 \(i\) 列，删去了 \(j\) 条边，目前上方和下方连不连通的方案数。
则有转移：
\[f_{i,j,1}=f_{i-1,j,1}+3\times f_{i-1,j-1,1}+f_{i-1,j,0} \]\[f_{i,j,0}=2\times f_{i-1,j-2,1}+f_{i-1,j-1,0} \]画个图就能懂了。
初值为 \(f_{1,1,0}=1,f_{i,0,1}=1\)。
最终答案就是 \(f_{n,i,1}\)。
时间复杂度 \(\mathcal O(n^2)\)。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3005;
int n, mod;
int f[N][N][2];
int main() {
scanf("%d%d", &n, &mod);
f[1][1][0] = 1;
for (int i = 1; i <= n; ++i) f[i][0][1] = 1;
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= i; ++j) {
f[i][j][1] = ((3ll * f[i - 1][j - 1][1] % mod + f[i - 1][j][1]) % mod + f[i - 1][j][0]) % mod;
f[i][j][0] = (2ll * f[i - 1][j - 2][1] % mod + f[i - 1][j - 1][0]) % mod;
}
for (int i = 1; i < n; ++i) printf("%d ", f[n][i][1]);
return 0;
}