【题解】[AHOI2022] 山河重整

题目链接：[AHOI2022] 山河重整

题意：

计数有多少个元素在 $[1,n]$ 的集合，其 $01$ 背包能表示 $[1,n]$ 中的所有数。

$1\le n\le 5\times 10^5$，时间限制 $\text{3s}$。

首先考虑从小到大加入数字，那么加入数字中途的每一个时刻，所能表示的都应是值域的一个前缀（因为加的数字越来越大）。

若目前能组合出 $[1,p]$，加入的新数是 $x$，那么能表示出的集合就变成了 $[1,p]\cup[x,p+x]$。若 $p+1<x$，由于加入的数字越来越大，所以以后再也组合不出 $p+1$ 了。因此，$x$ 需满足 $x\le p+1$，能拼出的新集合变成了 $[1,p+x]$。

于是容易得到一个 $\mathcal{O}(n^2)$ 的算法：设 $\text{dp}(i,p)$ 表示考虑前 $i$ 个数，已经能拼出 $[1,p]$ 的方案数。每次只需要决策是否将 $i$ 加入集合，将 $\text{dp}(i-1,p)$ 转移到 $\text{dp}(i,p+i)$ 即可。

我们需要一个更好的方式来描述上述过程。

直接计数所有满足条件的序列看起来不那么容易，尝试钦定不满足条件的位置，然后进行容斥。确切来说，即找到一组不合法方案的，最小的 $i$，满足 $[1,i]$ 均可拼出但 $i+1$ 无法拼出，对这样的位置进行容斥。

若值域 $[1,i]$ 中每个数均可拼出，且值域在 $[1,i]$ 中所有元素的和 $> i$，那么 $i+1$ 一定可以拼出。又需要能拼出 $i$，所以可知：若 $i$ 是这样一个位置，那么值域在 $[1,i]$ 中的所有元素的和恰好为 $i$。

我们设 $f_i$ 表示，只考虑值域在 $[1,i]$ 中的元素，能拼出 $[1,i]$ 中每个数字，且总和恰好为 $i$ 的方案数。其计算可以通过 “所有方案” 减去 “$[1,i]$ 中存在元素无法拼出的方案”。前者是 $i$ 的互异拆分数，而后者可以通过之前的 $f$ 求得。

更具体些，枚举第一个无法拼出的数字，在计算 $f_i$ 的时候，一个可以贡献的 $f_j$ 大概形如：$[1,j]$ 均可拼出，跳过 $j+1$（无法拼出），$[j+2,i]$ 中的元素加上 $[1,j]$ 中的元素总和恰好为 $i$（由 $f_j$ 定义可知，$[1,j]$ 中的元素之和恰好为 $j$，因此 $[j+2,i]$ 中的元素和应恰好为 $i-j$）。

考虑求解互异拆分数的具体做法。拆分出的数字个数是 $\mathcal{O}(\sqrt{n})$ 级别，于是我们将 “计数 $\mathcal{O}(\sqrt{n})$ 个不同数字和为 $n$ 的方案数” 转变为 “对 $i\in[1,\sqrt{n}]$，考虑有多少个数 $\ge i$”。

例如，上图可以看作 $12$ 的一组互异拆分 $\{1,2,4,5\}$（每行看作一个数字），也可以看作 $\ge 1$ 的有 $4$ 个，$\ge 2$ 的有 $3$ 个，$\ge 4$ 的有 $2$，$\ge 5$ 的有 $1$ 个（考虑每列）。

由于 $\ge i+1$ 的数字个数一定不多于 $\ge i$ 的数字个数，所以可以从 $\sqrt{n}$ 到 $1$ 倒序枚举 $i$，类似完全背包加入一个体积为 $i$ 的元素（表示有 $i$ 个元素 $\ge$ 某一个值）。

而 $f_j$ 向 $f_i$ 的贡献中，也存在 $[j+2,i]$ 中数字的背包状物。暴力做法可以从 $i$ 倒序枚举，在背包中逐步加入元素，在适当的时刻加入 $f_j$ 对 $f_i$ 的贡献。

考虑用上述方法类似地优化。$f_j$ 贡献的时候，其他所有元素应 $\ge j+2$。所以，我们可以在确定 $[j+2,i]$ 的集合中有多少个数的时候（设其为 $c$，即上图第一列有多少点），将 $f_j$ 贡献到背包的 $j+(j+2)\times c$ 处作为初值（可以结合代码理解）。

最后只剩下一个问题。在计算 $f_i$ 的时候，需要 $f_j$ 已经计算好了。但是上述做法中，我们需要先做一次完整的背包，才可以得到 $f_i$ 的系数。

注意到，若 $f_j$ 能贡献到 $f_i$，则 $i\ge j+(j+2)$（$i$ 要在 $j$ 的两倍以上）。因此，只需要先计算 $\dfrac{n}{2}$ 以下部分的 $f_i$，便可以得到所有 $f_i$ 的答案（类似一个倍增的过程）。

其复杂度为 $T(n)=\mathcal{O}(n\sqrt{n})+T\Big(\dfrac{n}{2}\Big)=\mathcal{O}(n\sqrt{n})$。

//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;

//#define FILE
//#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
#define y1 _y1

const int MAXN = 5e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, mod, lim, Ans;
int dp[MAXN], t[MAXN], p2[MAXN];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

void modadd(int &x, int y) { x += y; if(x >= mod) x -= mod; }

void run(int n) {
    if(n <= 1) return;
    run(n >> 1);
    for(int i = 0; i <= n; ++i) t[i] = 0;
    lim = sqrt(2 * n);
    for(int i = lim; i >= 1; --i) {
        for(int j = n; j >= i; --j) t[j] = t[j - i];
        for(int j = i - 1; j >= 0; --j) t[j] = 0;
        for(int j = 0; j + (j + 2) * i <= n; ++j)
            modadd(t[j + (j + 2) * i], dp[j]);
        for(int j = i; j <= n; ++j) modadd(t[j], t[j - i]);
    }
    for(int i = (n >> 1) + 1; i <= n; ++i)
        modadd(dp[i], mod - t[i]);
}

signed main () {
#ifdef FILE
    freopen("P8340.in", "r", stdin);
    freopen("P8340.out", "w", stdout);
#endif
    read(n), read(mod); p2[0] = 1;
    for(int i = 1; i < MAXN; ++i)
        p2[i] = (p2[i - 1] + p2[i - 1]) % mod;
    lim = sqrt(2 * n); dp[0] = 1;
    for(int i = lim; i >= 1; --i) {
        for(int j = n; j > i; --j) dp[j] = dp[j - i];
        for(int j = i; j >= 1; --j) dp[j] = 0;
        for(int j = i; j <= n; ++j) modadd(dp[j], dp[j - i]);
    }
    run(n);
    for(int i = 0; i < n; ++i)
        Ans = (Ans + 1ll * dp[i] * p2[n - i - 1]) % mod;
    Ans = (p2[n] - Ans + mod) % mod;
    printf("%d\n", Ans);
    return 0;
}