状態をまとめて DP． 連結しているかどうかが重要．
今 i番目の コ の字の部分を決めようとしているとする． つまり，左側は既に決まっているとする． 上の頂点と下の頂点が，左側において連結しているかどうかだけが， 今後に影響する．
\(dp_{i,k} := \) \(i \in 2\) は左側でつながっているときに1, それ以外は0, 既に \(k\) 本取り除いたときの場合の数
とすればよい．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,p;
cin >> n >> p;
auto add = [&](ll &a, ll b) -> void {
a = (a+b)%p;
};
vvll dp(2, vll(n+5));
dp[0][1] = 1;
dp[1][0] = 1;
rep(i,n-1) {
// 1: connected
vvll old(2, vll(n+5));
swap(dp, old);
rep(k,n){
{
// top and bottom
ll now = old[0][k];
add(dp[0][k+1], now);
// top and bottom and vert
add(dp[1][k], now);
}
{
ll now = old[1][k];
// up only or botoom only
add(dp[0][k+2], now*2);
// (up and bottom) or
// (up and vert) or
// (bottom and vert)
add(dp[1][k+1], now*3);
// all
add(dp[1][k], now);
}
}
}
rep1(k,n-1){
cout << dp[1][k] << " ";
}
return 0;
}
