My Blogs
P8340 [AHOI2022] 山河重整
题目限制是 $\forall x,\sum_{a_i\leq x}a_i\geq x$。所以有暴力 DP $f_{i,j}$ 表示考虑了 $\leq i$ 的所有数，和是 $j$。复杂度 $\mathcal O(n^2)$。
考虑优化，首先两维的状态就爆了。进行容斥，$f_i$ 表示 $\sum_{a_j\leq i}a_j=i$，并且 $\leq i$ 的数全部合法的方案数，答案就是 $2^n-\sum_i f_i2^{n-i-1}$，表示钦定 $i+1$ 不合法，对第一次不合法的位置进行容斥。
考虑如何求 $f$，先设 $g_i$ 表示 $i$ 的互异分拆数。考虑把分拆数化成柱形图，一组拆分数 $\sum b_i=n$ 表示为横坐标为 $i$ 的格子上有一个高度为 $b_i$ 的主子。因为是互异的，所以数字个数是 $\mathcal O(\sqrt n)$ 的，也就是柱状图的宽度是 $\mathcal O(\sqrt n)$ 的。枚举最大宽度，因为要求互异，所以比他小的每一种宽度都需要至少有一行，所以从大到小枚举宽度转移 $g$ 就行了。
再考虑 $f$ 的转移：$f_i=g_i-\sum_{j<i}f_jval(j,i-j)$，$val(j,v)$ 表示用 $\geq j+2$ 的数凑出来 $v$ 的方案数。
这个不太好算，我们把所有的 $j$ 放到一起算。这个转移显然有 $i\geq 2j$，所以进行一个牛顿迭代（？）。假设已经知道了 $f_{\leq n}$，考虑如何推出 $f_{\leq 2n}$。
注意到上面的转移天然可以对最小值进行限制。仍然是从大到小枚举宽度，假设枚举到宽度为 $t$ 的，可以选择在 $h$ 中加入一个 $-f_j$ 的贡献：贡献到 $j+(j+2)t$ 的位置上，表示最小值需要大于等于 $j+2$，其余 $h$ 的转移和 $g$ 相同，最后 $f_i=g_i-h_i$ 即可。复杂度 $T(n)=T(n/2)+\mathcal O(n\sqrt n)=\mathcal O(n\sqrt n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int n,MOD;
int g[500010],f[500010],h[500010];
const int B=999;
inline void solve(int n)
{
for(int i=0;i<=n;++i)h[i]=0;
for(int i=B;i>=1;--i)
{
for(int j=0;j+i*(j+1)<=n;++j)
Madd(h[j+i*(j+1)],f[j]);
for(int j=n;j>=i;--j)h[j]=h[j-i];
for(int j=0;j<i;++j)h[j]=0;
for(int j=i;j<=n;++j)Madd(h[j],h[j-i]);
}
for(int i=n/2+1;i<=n;++i)f[i]=Cdel(g[i],h[i]);
}
inline void mian()
{
read(n,MOD);
g[0]=1;
for(int i=B;i>=1;--i)
{
for(int j=n;j>=i;--j)g[j]=g[j-i];
for(int j=0;j<i;++j)g[j]=0;
Madd(g[i],1);
for(int j=i;j<=n;++j)Madd(g[j],g[j-i]);
}
int m=2;
f[0]=f[1]=1;
while(m<n)solve(m),m<<=1;
solve(n);
int ans=power(2,n);
for(int i=0;i<n;++i)Mdel(ans,Cmul(f[i],power(2,n-i-1)));
write(ans,'\n');
}