题解 P8340【[AHOI2022] 山河重整】

· · 题解

我们首先找一个必要条件吧。

然后发现，对于每个 i，全体不大于其的元素之和不小于其 是必要条件。

这个条件是充分的吗？

盲猜是的

考虑归纳。对于选出的集合大小和表示界同时归纳，每次尝试把界增加一，然后删去最大数，到达一个大小更小、界更小的态，即可归纳。

有了这个性质，我们就可以简单设计一个 n^2 的 DP。但是这个 DP 并不能简单扩展至正解。

考虑容斥，用合法态数减去不合法态数。

考虑不合法态的特征：存在 i 满足 1\sim i 中所有数之和等于 i，且 i+1 未被选中。

考虑令 f_i 为 1\sim i 中所有数之和等于 i 的方案，然后容斥找到这是首个不合法的位置的方案数，即可避免重复计算。

暴力 DP 仍然是平方的。但是注意到这玩意长得很像 整数拆分，并且这题的整数拆分还有特殊性质，也即 选择的数中不存在相同元素。这就直接推出 至多选取根号个数。

整数拆分的一种优化至平方的经典套路是考虑令 f_{i,j} 表示 j 个数组合成 i 的方案数，然后每次执行操作全体加一或者插入一个 1。

我们发现将这种东西直接写成 DP，在本题的性质下，状态数就是线性根号级别的，只需特别保证一下两两不同的性质即可。

1*
3***
4****
7*******
8********

关于上图，常规 DP 是从上往下的；上述优化是从左往右的。为了保证特殊性质，假如最终共选择了 i 个数，满足特殊性质就等价于 1\sim i 都被计入了至少一次。我们可以从左往右 DP，每次插入一个最终选择 i 个数的状态即可。

则我们现在已经会了一个线性根号的 DP，现在就要考虑如何容斥了。

考虑一个暴力的容斥，即 f_j\to f_i，其中 f_j 前要带一个系数。

什么系数呢？是区间 [j+2,i] 中选取若干个数和为 i-j 的方案数。

这玩意跟我们上面的 DP 是长得没啥区别的，只需确定最终选择了 i 个数，然后把所有数减去 j+2、总和减去 (j+2)i 即可。

然后紧接着我们发现，这个系数在 j\geq\dfrac i2 时为零，因为备选的每个数都大于 i-j，因而不可能合法。

这引出一个很好的想法： 考虑 CDQ 分治。这牵涉到左区间内部贡献、左区间对右区间的贡献、右区间内部贡献。

然后我们惊讶地发现，依据上述观察，右区间内部 没有贡献。这意味着我们分治 不需要进入右区间，则每层分治长度都是折半的。假如反过来想，这就是个类倍增的流程。

现在我们考虑计算左区间对右区间的贡献。可以用一个辅助 DP g 来表示：枚举左区间中每个 f_j 在 [j+2,i] 中选择了多少个数，为 g 初始化；然后 g 转移是简单的。

也可以参照代码（有注释）。

#include<bits/stdc++.h>
using namespace std;
const int BBB=1000;
int mod,f[500100],g[500100],res,bin[500100];
void ADD(int&x,int y){if((x+=y)>=mod)x-=mod;}
void solve(int n){
    if(n==1)return;
    solve(n>>1);
    for(int j=0;j<=n;j++)g[j]=0;
    for(int i=BBB;i;i--){
        for(int j=n;j>=i;j--)g[j]=g[j-i];//g[i] is the value that f[i] must substract in order to be correct.
        for(int j=0;j+(j+2)*i<=n;j++)ADD(g[j+(j+2)*i],f[j]);
        //take the transferrings where after state f[j] there are exact i numbers chosen(each of them is no less than j+2,and i(j+2) is pre-calculated) into consideration
        for(int j=i;j<=n;j++)ADD(g[j],g[j-i]);
    }
    for(int j=(n>>1)+1;j<=n;j++)ADD(f[j],mod-g[j]);
}
int n;
int main(){
    scanf("%d%d",&n,&mod);
    for(int i=BBB;i;i--){//a state that we have i chosen numbers in parallel
        for(int j=n;j>=i;j--)f[j]=f[j-i];f[i]=1;//force there to be at least one i exist.
        for(int j=i;j<=n;j++)ADD(f[j],f[j-i]);//do complete knapsack.
    }
    f[0]=1;//set f[0]=1 in order to do exclusion&inclusion.
    solve(n);
    bin[0]=1;for(int i=1;i<=n;i++)bin[i]=(bin[i-1]<<1)%mod;
    for(int i=0;i<n;i++)res=(1ll*f[i]*bin[n-i-1]+res)%mod;
    printf("%d\n",(bin[n]+mod-res)%mod);
    return 0;
}