补题记录：E. Phoenix and Computers

题意：有一列电脑，一开始是全关的。你一次只能开一台电脑，并且对于第i台电脑，如果第i - 1台和第i + 1台电脑开了，那么第i台电脑就会自动开，你是开不了它的。不同开电脑的顺序视为不同方案，问有几种方案可以让电脑全部开起来。
方法：DP
这题有点偏思维，首先我们想象一下，假如全部的电脑都开了，其中自动开的部分一定是这样分布的：1~i是手动开的，i + 1是自动开的，i + 2~j是手动开的…以此类推。
于是我们发现，某个状态可以表示为多个连续手动开机的连续状态的和
那我们先解决一个子问题：只手动开k个电脑的方案数
1、假如我们先开1，那么2, 3,4, …k都要依次手动开，否则就会出现自动开的部分，有$C_{k - 1}^{0}$种
2、假如我们先开2，那么3, 4, 5, …k都要依次手动开，并且我们可以把1传插其中，有$C_{k -1}^{1}$种
依次类推，把这些数加起来就行
$\sum_{i = 0}^{k - 1}C_{k - 1}^{i} = 2^{k - 1}$
接下来我们写状态表达和状态转移
状态表达：$dp[i][j]$表达前i台电脑中，有j台是手动开的方案数，接下来的第i + 1台是自动开的
状态转移：$dp[i][j] += dp[i - k - 1][j - k] \times 2 ^ {k - 1} \times C_{j}^{j - k}$
其中k表示的是之前的最后一段是连续k个手动插入。
其中$2 ^ {k - 1}$我们之前解释过了，而$C_{j}^{j - k}$表示我们后面的k个手动开的可以和之前我们j个手动开的穿插的进行，一共有$C_{j}^{j - k}$个方法。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 440;
inline int lc(int u) {return u << 1;}
inline int rc(int u) {return u << 1 | 1;}
inline int lowbit(int x) {return x & (-x);}
LL c[N][N], p[N];
LL dp[N][N];
inline void solve() {
    int n, m; cin >> n >> m;
    p[0] = 1;
    for (int i = 1; i <= 400; i ++ ) p[i] = p[i - 1] * 2 % m;
    for (int i = 0; i <= 400; i ++ ) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j ++ )
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % m;
    }
    for (int i = 1; i <= n; i ++ ) {
        dp[i][i] = p[i - 1] % m;
        for (int j = 0; j <= i; j ++ ) {
            for (int k = 1; k <= n; k ++ ) {
                if (i >= k + 1 && j >= k)
                    dp[i][j] = (dp[i][j] + dp[i - k - 1][j - k] * p[k - 1] % m * c[j][j - k] % m) % m;
            }
        }
    }
    LL res = 0;
    for (int i = 0; i <= n; i ++ )
        res = (res + dp[n][i]) % m;
    cout << res << endl;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
//    int t; cin >> t;
//    while (t -- )
        solve();
    return 0;
}