我不行了，非常有意思的题目，必须同步发到 cnblogs 上。
老大，我们 AHOI 也有如此神题吗。
这不就来了。
题意简述
给定 \(n,p\)，求出全集 \(S=\{1,2,3,...,n\}\) 有多少个非空子集 \(T\) 满足 \(T\) 的子集和覆盖 \([1,n]\)。
\(n \leq 5 \times 10^5,p \leq 1.01 \times 10^9\)。
判定条件
问题比较复杂，显然如何判定一个集合 \(T\) 是否合法是关键，先考虑它。
考虑从小到大加入数，设当前可以组成的最长前缀是 \([1,k]\)。那么当加入数 \(x\) 时：
- 若 \(x>k+1\)，意味着 \(x\) 配合之前的数无法组成 \(k+1\)。又因为 \(x\) 是当前没有被加入的数中最小的，因此 \(k+1\) 一定组成不了，不合法。
- 若 \(x \leq k+1\)，可以接上，\(k \to k+x\)。
这个过程还是太抽象了，然而可以简洁的表述它：
对于任意 \(k\)，\(\sum_{x \in T,x \leq k} \geq k\)。
容易说明两者是等价的。
计数
如果直接从前往后决策每个数选不选这也太笨蛋了，还是 \(O(n^2)\) 的，即记录当前选到哪，和为多少。
这个 dp 看起来没有什么优化空间了，因为状态数都是 \(O(n^2)\) 的。
我们考虑容斥，计算不合法的方案数量。为了不算重，考虑把每一种不合法方案放在第一个不合法的 \(k\)（见判定条件）处统计。
现在考虑枚举第一个不合法的 \(k\)，这相当于是限定了 \(k'<k\) 的 \(k'\) 全部合法，然而在 \(k\) 不合法。考虑从 \(k-1 \to k\)，维护 \(\leq k\) 的和 \(S\)。已知 \(S_{k-1} \geq k-1\)，那么若 \(S_{k-1} \geq k\) 那么 \(k\) 就合法了，因此 \(S_{k-1}=k-1\)。又如果 \(k\) 被选了，那么 \(S_{k-1}\) 一定 \(\geq k\)，所以 \(k\) 一定不选。
所以只要我们求出 \(f_i\) 表示从前 \(i\) 个数中选出一些使得和为 \(i\)，并且任意 \(k \leq i\) 的 \(k\) 都满足判定条件的方案数。答案就是 \(2^n-\sum{2^{n-i-1}f_i}\)。
如何计算 \(f\) 呢，考虑求出 \(g_i\) 表示从前 \(i\) 个数中选出一些使得和为 \(i\) 的方案数（区别在于 \(f\) 有关于 \(k\) 的限制）。如何用 \(g\) 辅助 \(f\) 计算？有： \(f_i=g_i-\sum{f_j \times w(j,i)}\)。
其中 \(w(j,i)\) 表示从 \([j+2,i]\) 中选出一些数使得和为 \(i-j\) 的方案数。
为什么是这样呢？解释一下意思，即用所用组成 \(i\) 的方案数 \(g_i\)，减掉不合法的。考虑在不合法的第一个位置 \(j+1\) 计算，类似的它相当于是告诉我们 \(k \leq j\) 的合法，然而在 \(j+1\) 不合法，根据前面的分析我们又知道 \(j+1\) 一定不选，所以就是在 \([j+2,i]\) 中选出一些组成 \(i-j\) 使得 \(j \to j+(i-j)=i\)。
现在考虑 \(g\) 怎么求，这个是简单的。考虑 Ferrers 图像，即把数化成柱状图以后旋转 45 度。
可以发现 \(K_1,K_2\) 形成双射，对 \(K_2\) 计数，注意到值域 \(O(\sqrt{n})\) 的，所以复杂度正确。并且由于值互不相同，所以 \(K_2\) 中数组成的集合 \(V\) 还得是值域上 \(1\) 开头的连续一段（首先 \(V\) 显然包含 \(1\)，然后证明连续：如果有值域上相邻的两个数 \(x<y\) 满足 \(y-x \geq 2\)，那么意味着 \(x \to y\) 的相邻移动过程中有超过 \(2\) 个数被筛掉了，而它们值一定相等，故矛盾）。
对这个东西直接做完全背包即可，一些很有说法的细节是：
-
需要从大到小枚举所有值
-
每次要强制选 \(1\) 个（保证至少选了 \(1\) 个）。
然后考虑怎么求 \(f\)，容易发现现在的问题是 \(w(i,j)\) 不好计算。先考虑一个暴力的计算方法：
假设现在要计算 \(f_i\)。
从 \(i\) 往前扫，设当前扫的数是 \(j\)，把 \(j\) 加入背包中。
处理 \(f_{j-2}\) 的贡献。
上面其实我们不用直接新拉个背包出来做，可以直接每次类似背包转一样把 \(f_{i-x}\) 的贡献转移到 \(f_i\)，\(x\) 是新加进来的数。
这个背包转移和 \(g\) 是本质相同的，所以我们也可以考虑那样转移。
则个显然是 \(O(n^2)\) 的，我们要优化它。
直接上一些科技是不好做的，因为有这么一个扫描的过程，过程的每一步都很关键，没法直接去掉。
观察 \(f_j \times w(j,i)\) 这个乘法的形式，如果我们把 \(f_j\) 作为刚刚移动过程中维护 \(w(j,i)\) 的背包的初始系数，那么就直接查 \(w(j,i)\) 就可以得到这个乘积。
比如这个例子（不与题目相关，只是用于理解）：
求 \(g_i \times f_x\)？在 dp 前令 \(g_0=f_x\) 即可。
然而现在我们不是用 \(1\) 到 \(i\) 凑出 \(i\) 了，而是用 \([j+2,i]\) 凑出 \(i-j\)。我们先考虑用 \([1,i-j]\) 凑出 \(i-j\)（不限制值域）怎么做，其实就是在 \(j\) 插入 \(f\) 值，然后背包的时候就可以自然的卷到 \(i\)，并且 \(f\) 乘的系数自然就是 \([1,i-j]\) 凑出 \(i-j\) 的方案数。
现在是用 \([j+2,i]\) 凑出 \(i-j\)（其实这里的上界等于 \(i\) 相当于没有限制上界，这个理解是关键的）。这个也是类似的，我们可以先直接让所有数减掉 \(j+1\)，然后用 \(\geq 1\) 的数凑，这个我们会啊！这个就是上面说的吧，所以这样就解决了！
具体的说，也就是把 \(f_j\) 的值在 \(f_{j+c(j+1)}\) 处插入，然后往后卷。这个 \(c\) 是 \([j+1,i]\) 中选的数的个数。
如果我们用朴素的转移方法（每次考虑加入新的数值，而非用 ferrers 图像转换法）我们没法保证在往后卷的时候一定就选了 \(c\) 个。然而如果我们用 ferrers 以后的状态来思考，其实我们只需要对 \(c\) 从大往小枚举，每次加入所有 \(j\) 对应的 \(j+c(j+1)\) 处插入，然后对 \(c\) 做完全背包往后卷，这样就可以使得这些 \(j+c(j+1)\) 插入后被卷到的第一次是 \(c\) 的转移。因为是从大到小枚举的，此时第一次被转移的 \(c\) 的意义就是数量，这样就对完了。
现在看起来我们做完了？实际上并没有！当要计算 \(i\) 的时候，如果要用上面的方法计算，必须要 \(f_{1},f_{2},...,f_{i-1}\) 都算好并且还得做一次背包，这样又退化成暴力复杂度了 TAT。
观察到 \(j+c(j+1) \geq 2j\)。所以可以考虑先算出前一半，然后贡献到后一半。
具体的我们可以考虑先算出 \(f_{1},f_{2},...,f_{\lfloor \frac{n}{2} \rfloor}\)，此时如何计算 \(f_{\lfloor \frac{n}{2} \rfloor+1},f_{\lfloor \frac{n}{2} \rfloor+2},...,f_n\)？直接按照上面的做法在对应位置插一下然后再背包即可！做一次是 \(O(n\sqrt{n})\)
于是用递归实现这个不断规约的过程即可。
令 \(n\) 的复杂度为 \(T(n)\)。有 \(T(n)=T(n/2)+O(n\sqrt{n})\)，得到 \(T(n)=O(n\sqrt{n})\)。
不是很卡常，但是得写的优美一点。
const int N = 5e5 + 5;
int pw2[N], sq[N], cur;
int f[N], u, g[N];
int p;
void add(int &x, int y) { x = (x + y >= p? x + y - p: x + y); }
void solve(int n) {if (n == 1) return;solve(n / 2);rep(i, 0, n) g[i] = 0;per(i, sq[n], 1) {rep(j, 0, n / 2)if (j + (j + 1) * i <= n) add(g[j + (j + 1) * i], f[j]);per(j, n, i) g[j] = g[j - i];per(j, i - 1, 0) g[j] = 0;rep(j, i, n) add(g[j], g[j - i]);}rep(i, n / 2 + 1, n) add(f[i], p - g[i]);
}
int n;
void solve() {cin >> n >> p;pw2[0] = 1;rep(i, 1, n) {pw2[i] = 2ll * pw2[i - 1] % p;sq[i] = sq[i - 1];while (1ll * sq[i] * (sq[i] + 1) / 2 <= i)++sq[i];}f[0] = 1;per(i, sq[n], 1) {per(j, n, i + 1) f[j] = f[j - i];rep(j, 1, i) f[j] = 0;rep(j, i, n) add(f[j], f[j - i]);}solve(n);int ans = pw2[n];rep(i, 0, n - 1)add(ans, p - 1ll * f[i] * pw2[n - i - 1] % p);cout << ans << '\n';
}