题解：P8340 [AHOI2022] 山河重整

· · 题解

P8340 [AHOI2022] 山河重整

考虑从小到大增量构造出能表示的集合，这肯定是在值域上一段连续的前缀 [1,x]，加入数 w 时，仿照 01 背包可以不加或者加或自创一个，构造的集合变成 [1,x]\cup [w,x+w]，我们声称合法的条件是集合仍然是连续前缀，即满足 x\ge w，否则 w>x，之后加的数只会越来越大，x+1 无法被构造出来。那么可以设计一个朴素的 \mathrm{dp}，f_{i,j} 表示考虑 [1,i] 的数，目前能构造的前缀为 [1,j] 的方案数，分加/不加简单转移即可，时间复杂度是 O(n^2)。

上述直接统计合法方案的 \mathrm{dp} 没有前途，考虑容斥的思想，转而统计不合法的方案数，即考虑值域上第一个断点的位置，即枚举 i，统计 [1,i] 都可以表示出而 (i+1) 无法被表示出的方案数。挖掘这种情况的性质，假设此时选的集合为 B，则不难归纳证明，由于 B 能表示出 [1,i]，B 可以表示 \left[1,\sum B\right]。为了满足极长的能表示出的前缀是 [1,i]，必须满足 \sum B=i。于是定义 f_i 表示满足和恰好为 i 的集合 B 个数。求法还是考虑直接容斥，用 g_i 表示和为 i 的互异分拆数方案数，则转移类似 f_i\leftarrow g_i-\sum\limits_{j} \mathrm{coef}(j,i)\times f_j。

先考虑 g_i 的求法，暴力做 01 背包是 O(n^2) 的，类比 P6189 [NOI Online #1 入门组] 跑步，我们想到分拆出来的数本质不同的只有 O(\sqrt{n}) 种，因为 \sum\limits_{i=1}^{n} i=O(n^2)。形象化就是：

于是我们不必再按照“行”进行 01 背包，而是可以按“列”进行完全背包，并限制每种长度至少使用一次，不难两者的方案一一对应。因此可以从 O(\sqrt{n})\to 1 倒序插入列长度 i，同时钦定每种列长度至少使用一种，其做法是先将每个位置都强制加上 i，然后完全背包转移，即先对于 j\in (i,n] 做 g_j\leftarrow g_{j-i}，[1,i] 部分清空，并跑一遍完全背包。其时间复杂度是 O(n\sqrt{n})，可以接受。

求出了 g 再来考虑容斥，思考系数 \mathrm{coef}(j,i) 的意义，重新审视 f_j 的定义，是可以统计出 [1,j]，和恰好为 j，且 j+1 无法被表示出来。那么 \mathrm{coef}(j,i) 的目的就是满足和的情况下使 i+1 为第一次无法表示，就是要保证 j+1 仍然无法组出的情况下任意组合，和仍然为 i，我们发现这等价于用 \ge j+2 的数组出和为 i-j。考虑用之前求互异分拆数的方法求解这个问题，令 h_i=\sum f_j\times \mathrm{coef}(j,i)，那么有 f_i=g_i-h_i。那么 h_i 只有赋初值与 g_i 有所不同，此处的贡献是 f_j，赋初值考虑插入列的长度为 \ell 时，由于要保证数都 \ge j+2，即行上的长度都至少是 j+2，所以最低限度是放 j+2 个 \ell，并且组出的和要为 i-j，那么要手动加上 j，因此初值赋为 h_{(j+2)\ell+j}\leftarrow f_j。但是看似每次凑出 f_i 的系数都需要一次 O(n\sqrt{n}) 背包，观察到要用 \ge j+2 组出 i-j 那么需要满足 j+2\le i-j，即 2j+2\le i，因此 j\ge \frac{i}{2} 的部分系数都是 0 没有贡献。因此如果我们算出 f_{\le \frac{i}{2}} 的值即可推出 f_i。那么考虑类似分治的做法，每次先算出 \le \frac{n}{2} 的部分，然后推出 \left(\frac{n}{2},n\right] 的答案，分析一下时间复杂度应为 \displaystyle\sum_{k} \frac{n\sqrt{n}}{2^k}=O(n\sqrt{n})，可以通过。

最后是答案的求法，要求的就是没有任何一个数被表示出来的方案数，那么就是其他位置随便选，即 ans=2^n-\displaystyle\sum_{i=0}^{n-1}f_i\times 2^{n-i-1}。

:::info[代码]

#include <bits/stdc++.h>

using namespace std;

typedef long long ll; int mod;
inline int Mod(int x) { return x<0 ? x+mod : (x>=mod ? x-mod : x); }
inline void adm(int &x,int y) { x=Mod(x+y); }
const int N=500010;
int n;
int f[N];
int g[N];
int pw[N];

void solve(int n)
{
    if (n<=1) return;
    solve(n>>1);
    fill(g,g+n+1,0);
    int lim=sqrt(2*n);
    for (int i=lim;i;i--)
    {
        for (int j=n;j>=i;j--) g[j]=g[j-i];
        for (int j=1;j<i;j++) g[j]=0;
        for (int j=0;(j+2)*i+j<=n;j++) adm(g[(j+2)*i+j],f[j]);
        for (int j=i;j<=n;j++) adm(g[j],g[j-i]);
    }
    for (int i=(n>>1)+1;i<=n;i++) adm(f[i],mod-g[i]);
}

int main()
{
    cin >> n >> mod;

    int lim=sqrt(2*n); f[0]=1;
    for (int i=lim;i;i--) 
    {
        for (int j=n;j>i;j--) f[j]=f[j-i];
        for (int j=1;j<=i;j++) f[j]=0;
        for (int j=i;j<=n;j++) adm(f[j],f[j-i]);
    }
    solve(n);

    pw[0]=1;
    for (int i=1;i<=n;i++) pw[i]=(ll)pw[i-1]*2%mod;

    int ans=pw[n];
    for (int i=0;i<n;i++) adm(ans,mod-(ll)f[i]*pw[n-i-1]%mod);
    cout << ans << "\n";

    return 0;
}

:::