P8340 [AHOI2022] 山河重整 做题记录

给定 $n,p$，求有多少个 $\{1,2,3,\dots,n\}$ 的子集 $S$，满足 $\forall 1\le x\le n,\exist T\subseteq S,x=\sum\limits_{y\in T} y$，对给定正整数 $p$ 取模。

也就是求有多少个子集 $S$ 满足其 01 背包可以表示出 $[1,n]$ 中的所有数。

$1\le n\le 5\times 10^5,2\le p\le 1.01\times 10^9$，时限 $3$ s。

首先有一个显然的充要条件：将 $S$ 中元素排序后，$S_i\le 1+\sum\limits_{j<i} S_j$。

那么直接得到了 $O(n^2)$ 做法：设 $f_{i,j}$ 表示考虑了 $[1,i]$，当前 $\min\left(\sum\limits_{x\in S} x,n\right)=j$ 的方案数，转移是简单的。

问题是这个做法没有优化前途。

考虑容斥，钦定 $i$ 作为最小的不能被表示的数，那么 $T=\{x|x\in S,x<i\}$ 要满足 $\sum\limits_{x\in T} x=i-1$ 且 $T$ 能表示出 $[1,i-1]$ 中的所有数。

那么只要求出 $f_i$ 表示有多少个 $T\subseteq \{1,2,3,\dots n\}$ 满足 $\sum\limits_{x\in T} x=i$ 且其可以表示 $[1,i]$ 中的所有数。

考虑容斥计算 $f_i$，先算出 $\sum\limits_{x\in T} x=i$ 的 $T$ 的个数。再枚举一个 $0\le j<i$，钦定无法表示 $j+1$，那么 $f_j$ 对 $f_i$ 的贡献为 $-f_j\times g_{j+2,i}$，其中 $g_{j+2,i}$ 表示有多少个 $T'\subseteq \{j+2,j+3,\dots,i\}$ 满足 $\sum\limits_{x\in T'}x=i-j$。

继续，容易发现当 $j> \lfloor\frac{i-2}{2}\rfloor=\frac{i}{2}-1$ 则 $j+j+2>i$，那么此时 $g_{j+2,i}=0$。故可以倍增计算 $f_i$。

现在问题变成如何求 $f_i$ 的初值以及 $g_{j+2,i}$。

先来考虑 $f_i$ 的初值，即求有多少个 $T\subseteq\{1,2,3,\dots,i\}$ 满足 $\sum\limits_{x\in T} x=i$。这是一个经典问题，即互异拆分数：

考虑暴力 dp，设 $f_{i,j}$ 表示考虑完 $[1,i]$，现在总和为 $j$。这样做是 $O(n^2)$ 的。

考虑 Ferrers 图，即总共有 $i$ 个点，每行点数递减，一行表示 $T$ 中的一个数：

.......
.....
...
.

这个暴力 dp 相当于逐行加点，而注意到由于要求互异，即每行的点数不同，所以行数是 $O(\sqrt i)$ 的。那么可以考虑逐列加点：

• 设 $f_{i,j}$ 表示当前列有 $i$ 个点，总共加入了 $j$ 个点；

那么这样 dp 就变成了 $O(n\sqrt n)$ 的。

那么跑一遍该 dp 即可得到 $f_i$ 的初值，而不难发现并不用显式求出 $g_{j+2,i}$，仅需将前一半的计算完成的 $f$ 作为初值跑该 dp 即可。具体实现看代码。

那么时间复杂度为 $T(n)=O(n\sqrt n)+T(\frac{n}{2})=O(n\sqrt n)$，代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int BS=1005,S=500005;

int n,p;
int f[S],g[S];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

void slove(int n)
{
	if(n==1) return;
	int m=n/2;
	slove(m);
	for(int i=0;i<=n;i++) g[i]=0;
	for(int i=BS-3;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;
		for(int j=0;j<=m&&j+(j+2)*i<=n;j++)
			add(g[j+(j+2)*i],p-f[j]);
		for(int j=i;j<=n;j++) add(g[j],g[j-i]);
	}
	for(int i=m+1;i<=n;i++) add(f[i],g[i]);
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>p;
	for(int i=BS-3;i>=1;i--)
	{
		for(int j=n;j>=i;j--) f[j]=f[j-i];
		for(int j=0;j<i;j++) f[j]=0;
		add(f[i],1);
		for(int j=i;j<=n;j++) add(f[j],f[j-i]);
	}
	f[0]=1;
	slove(n);
	int ans=1;
	for(int i=1;i<=n;i++) ans=1ll*ans*2%p;
	for(int i=n,pw2=1;i>=1;i--,pw2=1ll*pw2*2%p)
		add(ans,p-1ll*pw2*f[i-1]%p);
	cout<<ans<<'\n';
	return 0;
}
/*
相当于背包覆盖所有点
相当于 a[i]<=(\sum a[1,i])+1
考虑容斥，数不合法的序列
最多有 log 个位置违法
* n sqrt n
* 考虑互异分拆数的 n sqrt n 做法，记录 f[i][sm] 表示这一列还有 i 个点，和为 sm
	f[i][sm]->f[i][sm+i] or f[i-1][sm+i]
容斥，考虑枚举爆掉的点前一个位置的和
so hard
*/