Description
鱼王青鱼的 AI 不愿意进行 996 的工作，于是要求青鱼先和它玩一个游戏。
AI 生成了 \(n\) 道题，编号为 \(1, 2, \dots, n\)。现在 AI 心里选择了其中一道题，但青鱼不知道这是哪一题。
青鱼可以向 AI 询问若干个问题，每个问题形如：给定 \(l, r\) 满足 \(1 \le l \le r \le n\)，询问这道题的编号是否在 \([l, r]\) 中。
如果青鱼能够通过同时询问这些问题唯一确定这道题的编号，那么青鱼就赢了。否则 AI 就赢了。
显然，身为鱼王，青鱼的智商不输 AI。因此，你可以认为青鱼和 AI 都是绝顶聪明的。
现在青鱼抓住了你，并要求你计算出青鱼有多少种问问题的方案使得他一定能赢。其中两种方案不同，当且仅当存在一个区间 \([l, r]\) 在其中一种方案中被询问，而在另一种方案中没有。
另外，青鱼施行仁政，所以他不会太为难你，只需要你给出答案对大质数 \(P\) 取模的结果。
\(1\leq n\leq 300\)。
Solution
首先直接是不好计算的，考虑容斥，即钦定一些等价类，求使得每个等价类内部的的编号被覆盖的区间集合相等的方案数。
设 \(b_i\) 表示 \(i\) 所在的等价类编号，如果存在 \(i<j<k<l\)，且 \(b_i=b_k,b_j=b_l\)，则所有包含 \(i\) 的区间也包含 \(k\)，也就包含 \(j\) 和 \(l\)，所以 \(i,j,k,l\) 的实际覆盖集合也相同，把它们的等价类合并后方案数也一样。
由于直接钦定等价类大小后容斥系数并不是 \((-1)^{size-1}\)，就无法用到上面的结论了。
考虑将钦定等价类改成钦定若干条边 \((i,j)\)，让 \(i\) 和 \(j\) 被覆盖的区间集合相同。容斥系数是 \((-1)^{边数}\)。
那么根据上面的结论，如果 \((i,k)\) 和 \((j,l)\) 有边，且 \((j,k)\) 没有边，那么加上 \((j,k)\) 后容斥系数变为相反数，方案数不变，抵消了！
所以我们钦定的边要么包含，要么不交（可以在端点上交）。
然后钦定所有不被包含的边后，将其称为极长边，将相邻的极长边合并成一个块。那么每条边内部（不包含两端点）的边就互相独立了，而跨过这些极长边的区间一定要包含若干个完整的块，这些区间显然是可以随便选的。
根据上面的做法就可以设计状态了。
设 \(f_i\) 表示有 \(i\) 个点，钦定 \((1,i)\) 有边，只计算 \([2,i-1]\) 内部的边的贡献和，\(g_i\) 表示 \(i\) 个点，没有任何限制的贡献和。
转移的时候就再设一个二维状态 \(h_{i,j}\) 表示 \(i\) 个点，有 \(j\) 个块的贡献和，再乘上跨块的方案数即可。
具体细节见代码。
时间复杂度：\(O(n^3)\)。
Code
#include <bits/stdc++.h>// #define int int64_tconst int kMaxN = 305;int n, mod;
int f[kMaxN], g[kMaxN];// f[n] : n 个点，1 和 n 有边，且不能有 [1, n] 这个区间的贡献之和int qpow(int bs, int64_t idx = mod - 2) {int ret = 1;for (; idx; idx >>= 1, bs = (int64_t)bs * bs % mod)if (idx & 1)ret = (int64_t)ret * bs % mod;return ret;
}inline int add(int x, int y) { return (x + y >= mod ? x + y - mod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + mod); }
inline void inc(int &x, int y) { (x += y) >= mod ? x -= mod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += mod : x; }
inline int getop(int x) { return (~x & 1) ? 1 : (mod - 1); }void dickdreamer() {std::cin >> n >> mod;f[1] = 1;static int tmp[kMaxN][kMaxN];memset(tmp, 0, sizeof(tmp));tmp[1][1] = 1;for (int i = 2; i <= n; ++i) {// static int tmp[kMaxN][kMaxN];// memset(tmp, 0, sizeof(tmp));// tmp[1][1] = 1;// for (int j = 2; j <= i; ++j) {// for (int k = 1; k <= j - 1; ++k) {// inc(tmp[j][k + 1], tmp[j - 1][k]);// for (int x = 1; x <= j - k; ++x)// dec(tmp[j][k], 1ll * tmp[j - x][k] * f[x + 1] % mod);// }// }for (int j = std::max(i - 1, 2); j <= i; ++j) {std::fill_n(tmp[j], j + 1, 0);for (int k = 1; k <= j - 1; ++k) {inc(tmp[j][k + 1], tmp[j - 1][k]);for (int x = 1; x <= j - k; ++x)dec(tmp[j][k], 1ll * tmp[j - x][k] * f[x + 1] % mod);}}for (int j = 1; j <= i; ++j) {int val = tmp[i][j];if (j >= 3) val = 1ll * val * qpow(2, (j - 2) * (j - 1) / 2) % mod;inc(f[i], val);// [1, i] 没有 (1, i) 这条边inc(g[i], 1ll * tmp[i][j] * qpow(2, j * (j + 1) / 2) % mod);// [1, i] 有 (1, i) 这条边dec(g[i], 1ll * tmp[i][j] * qpow(2, std::max(j - 2, 0) * (j - 1) / 2 + 1) % mod);}// std::cerr << f[i] << '\n';}std::cout << g[n] << '\n';
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;// std::cin >> T;while (T--) dickdreamer();// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}