先考虑如何判断一个询问集是否合法。
考虑询问一次([l,r])，能把([1,l-1]∪[r+1,n])和([l,r])区分开来。
现在定义一个块为一个没有被区分开极大的点集合。
当所有块的大小都是1的时候，这个方案就是合法。
性质：
1.一个块是由若干连续段组成，比如下面这样：
1112233111411
颜色为1的块由三段连续段。
2.块与块之间不会出现交叉的情况：
比如下面这样：
11122211122211
也就说两个块的关系，只有完全包含和互不相交两种。
设(f[i])表示长度为(i)，每个块大小都是1的方案数。
考虑用总的减去不合法的。
不合法的方案数：先枚举一种不合法的块的划分状态，再考虑求变成这样有多少种方案。
对于一个不合法的块的划分状态，我们可以只取其最外层的块的最左点和最右点来统计它。
最外层的块：不被任何其他块包含的块。
比如(112131145657)，保留为：(1?????145?57)
对于(??…?)中间的边，可以随便取。
对于保留下来的块(1、4、5、7)，它们之间要区分，方案数就是(f[最外层块数])
转移：
考虑枚举大小(>1)的最外层块的个数，再枚举要插进大小(>1)的最外层块中间的(?)的个数y，则大小(=1)的最外层块数(z=i-2x-y)
预处理个(g[i][j])表示把(j)个数插进(i)个块的系数积的和，(g[i][j]=sum_{k=1}^jg[i-1][j-k]*2^{k(k+1)/2})
那么(f[i]=2^{i(i+1)/2}-sum_xsum_{y,z=i-2x-y} g[x][y]*f[x+z]*{(x+z)!over x!z!})
其中({(x+z)!over x!z!})是最外层块的排列方案数。
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
int n, mo;
ll ksm(ll x, ll y) {
ll s = 1;
for(; y; y /= 2, x = x * x % mo)
if(y & 1) s = s * x % mo;
return s;
}
const int N = 305;
ll a2[N * N + N];
ll f[N], h[N][N];
ll fac[N], nf[N];
int main() {
freopen("two.in", "r", stdin);
freopen("two.out", "w", stdout);
scanf("%d %d", &n, &mo);
a2[0] = 1; fo(i, 1, (n + 1) * n) a2[i] = a2[i - 1] * 2 % mo;
f[1] = 1;
fac[0] = 1; fo(i, 1, n) fac[i] = fac[i - 1] * i % mo;
fd(i, n, 0) nf[i] = ksm(fac[i], mo - 2);
h[0][0] = 1;
fo(i, 0, n - 1) {
fo(j, 0, n) fo(k, 0, n - j)
h[i + 1][j + k] = (h[i + 1][j + k] + h[i][j] * a2[k * (k + 1) / 2]) % mo;
}
f[1] = 2;
fo(i, 2, n) {
f[i] = a2[i * (i + 1) / 2];
fo(x, 1, i / 2) fo(y, 0, i - 2 * x) {
int z = i - 2 * x - y;
ll v = h[x][y] * f[i - y - x] % mo;
v = v * fac[z + x] % mo * nf[z] % mo * nf[x] % mo;
f[i] = (f[i] - v) % mo;
}
}
pp("%lld
", (f[n] % mo + mo) % mo);
}