keep-connect.cpp

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

const int maxn = 3000 + 1;

const int connected = 0;
const int two_connected = 1;
const int hopeless = 2;

const int take = 1;
const int leave = 0;

long long dp[maxn][maxn][3];

int determine_state(int prev_state, int top, int bot, int mid) {
    if (prev_state == connected) {
        if (top + bot == 0) {
            return hopeless;
        }
        if (top + bot + mid >= 2) {
            return connected;
        } else {
            return two_connected;
        }
    }
    else if (prev_state == two_connected) {
        if (top + bot != 2) {
            return hopeless;
        }
        if (top + bot + mid == 3) {
            return connected;
        } else {
            return two_connected;
        }
    }
    return hopeless;
}

void solve(int n, int mod) {
    memset(dp, sizeof(dp), 0);
    dp[0][0][0] = 1;
    dp[0][1][1] = 1;

    for(int now = 1; now < n; now++) {
        for(int j = 0; j < n; j++) {
            for(int prev_state : {connected, two_connected}) {
                for(int top : {take, leave}) {
                    for(int bot : {take, leave}) {
                        for(int mid : {take, leave}) {
                            int dropped_cnt = 3 - (top + bot + mid);
                            int state_now = determine_state(prev_state, top, bot, mid);
                            if (j >= dropped_cnt) {
                                dp[now][j][state_now] += dp[now - 1][j - dropped_cnt][prev_state];
                                dp[now][j][state_now] %= mod;
                            }
                        }
                    }
                }
            }
        }
    }

    for(int j = 1; j < n; j++) {
        cout << dp[n - 1][j][connected] << " ";
    }
    cout << endl;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, mod;
    cin >> n >> mod;
    solve(n, mod);
    return 0;
}