Preface
翻到自己两年前出的题，记得好像被一位 gm 评价为「参考山河重整可以轻易做到 \(\mathcal O(n\sqrt{n})\)」。现在我也是 (not-i)gm 了，但是回过头来看看还是只会 \(\mathcal O(n^3)\)，然而当年指导我的 gm 已经高三退役了，令人感叹。
金黄的树林里分出两条路，可是我走上了 oi 退役这一条、、
还是看看远处的山河重整吧（结果我还是花了一个晚上看，太菜。
Solution
\(n^2\) dp 我好像 pj 2= 的时候就会了，那不讲了。
dp 不太好优化。第一步容斥：计数 \(f_i\) 表示值域 \([1, i]\) 恰能凑出 \(\bm{[1\dots i]}\) 内所有数 的方案数。这个是充要条件就不证了吧。
恰能凑出也不好做，那么我们 第二步容斥，就计数 \(g_i\) 表示 \(i\) 的互异拆分数，然后减去，枚举 \(j\)，要不能表示出第一个数为 \(j + 1\) 的方案（\(= f_j\)），乘上用 \([j + 2, i]\) 表示 \(i - j\) 的方案数。这得到了 \(f_i\)。
先来转移 \(g\)，容易发现如果我们转置这个加入数的过程（杨表），那么就相当于对每个 \(s\) 做 \(1\dots s\) 的完全背包凑出 \(i\)，但是额外要求 \(1\dots s\) 均出现一次否则杨表会炸，因此 \(s\) 是 \(\mathcal O(\sqrt{n})\) 级别的，\(\mathcal O(n\sqrt{n})\) 直接求。听说这个很经典。
注意到这里每个数都出现一次确实是后面的依赖于前面的，因此仔细斟酌，我们要 \(s\) 从大到小 做完全背包，这样才能保证加入 \(s\) 之后我们可以钦定加入 \(1 \dots (s - 1)\)。
但是第二步看起来没啥头绪，唉唉唉。首先考虑 \(j + 2 \leq i - j\)，也就是说我们其实只需要用到下标不超过 \(i/2\) 的 \(j\)，这是一个伏笔，但现在它并不重要。
最核心的一步，也是我一年前没看懂的部分，其实是，考虑 在计算 \(\bm g\) 的过程中同步容斥 \(\bm f\) 的值。那么考虑那个 \([j + 2, i]\)，我们会把它 转置为 最大的元素（对应了最小的数，上文的 \(s\)）至少被加入 \(j + 2\) 次。凑出 \(= i\) 的方案数，也就是 从现在到最后这一过程的所有贡献 最终计算出来的 \(g_i\) 了（但是请注意如果你真的同步做的话贡献会很麻烦，所以请先把 \(f\) 的拆分数求出来之后把 \(g\) 置 \(0\) 重新算；也就是说本文的 \(g\) 前后有两种不同的含义）。
具象一点，在枚举转置后最大值 \(= s\) 的时候，我们钦定在 \(j\) 处，初始值为 \(f_j\) 的元素会和 \(g\) 以相同的速度（\(s \dots 1\)）转移，然后我们先钦定它转移 \(j + 2\) 步也就是 \(pos' = j + (j + 2)s\)。然后它完全背包一路做完跑到终点（因为我们还要钦定加入 \((s - 1) \dots 1\)）之后，我们给 \(f_i\) 减掉对应位置上的贡献 \(g_i\) 即可。然后到这里就很容易实现了。
回收伏笔：我们计算 \(f_{1\dots i}\) 只需要 \(f_{1\dots (i/2)}\)，倍增计算即可。时间复杂度 \(\mathcal O(n\sqrt{n})\)。我实现的有点劣，因为我确实是倍增的 /xk，实际上最好的做法是每次递归到 \(n/2\)。
Code
#include <bits/stdc++.h>
#define MAXN 500001
int f[MAXN << 1], g[MAXN << 1];
int N, p;
inline void add(int& x, int y) { (x += y) >= p && (x -= p); }
inline void del(int& x, int y) { (x -= y) < 0 && (x += p); }
inline int gMax(int N) { int s = 1, sum = 1; while (sum + (s + 1) <= N) sum += ++s; return s; }
int main() {
std::cin >> N >> p;
f[0] = 1;
for (int s = gMax(N); s; --s) {
for (int i = N; i; --i) f[i] = (i >= s ? f[i - s] : 0); // note that we can't move f[0]
for (int i = s + 1; i <= N; ++i) add(f[i], f[i - s]); // note that f[s] is updated
}
for (int lim = 2, lst = 1; lst < N; lim <<= 1, lst <<= 1) {
lim = std::min(lim, N);
for (int i = 0; i <= lim; ++i) g[i] = 0;
for (int s = gMax(lim); s; --s) {
for (int i = N; ~i; --i) g[i] = (i >= s ? g[i - s] : 0);
for (int j = 0, J = 2 * s; j <= lst && J <= lim; ++j, J += s + 1) add(g[J], f[j]);
for (int i = s; i <= lim; ++i) add(g[i], g[i - s]);
}
for (int i = lst + 1; i <= lim; ++i) del(f[i], g[i]);
}
int ans = 1; for (int i = 1; i <= N; ++i) add(ans, ans);
for (int i = N - 1, t = 1; ~i; --i) del(ans, 1ll * t * f[i] % p), add(t, t);
return std::cout << ans, 0;
}