AtCoder Beginner Contest 248-F- Keep Connect（线性dp）

题目链接：F - Keep Connect (atcoder.jp)

题意，给定一个2*n如图所示的图，在去掉某些边后，图依然连通，请输出n-1个数，分别代表去掉1，2，3..., n-1条边后，图依然连通的方案数

题解：使用动态规划，定义f[i, j, k] 表示前i列，删去j条边，k = 1代表上下两行连通，k = 0 代表上下两行不连通。递推式如图所示

#include 

using namespace std;

typedef long long ll;

ll f[3010][3010][2]; //k = 1代表上下两行连通，k = 0 代表上下两行不连通

int main() {
	int n, P;
	cin >> n >> P;
	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] = ((f[i-1][j][1] + 3*f[i-1][j-1][1] % P) % P + f[i-1][j][0]) % P;
			  f[i][j][0] = (2*f[i-1][j-2][1] % P + f[i-1][j-1][0]) % P;
		}
	for(int i=1; i<=n-1; i++) cout << f[n][i][1] << ' ';

	return 0;
}