专栏文章

题解：P8340 [AHOI2022] 山河重整

WWrongAnswer_90Alive
P8340题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip3cysr
此快照首次捕获于
2025/12/03 05:29
3 个月前
此快照最后确认于
2025/12/03 05:29
3 个月前
查看原文

My Blogs

P8340 [AHOI2022] 山河重整

题目限制是，对于一种选法 aa，要求 ∀x,∑ai≤xai≥x\forall x,\sum_{a_i\leq x}a_i\geq x。所以有暴力 DP fi,jf_{i,j} 表示考虑了 ≤i\leq i 的所有数，和是 jj。复杂度 O(n2)\mathcal O(n^2)。
考虑优化，首先两维的状态就爆了。进行容斥，fif_i 表示 ∑aj≤iaj=i\sum_{a_j\leq i}a_j=i，并且 ≤i\leq i 的数全部合法的方案数，答案就是 2n−∑ifi2n−i−12^n-\sum_i f_i2^{n-i-1}，表示钦定 i+1i+1 不合法，对第一次不合法的位置进行容斥。
考虑如何求 ff，先设 gig_i 表示 ii 的互异分拆数。考虑把分拆数化成柱形图，一组拆分数 ∑bi=n\sum b_i=n 表示为横坐标为 ii 的格子上有一个高度为 bib_i 的主子。因为是互异的，所以数字个数是 O(n)\mathcal O(\sqrt n) 的，也就是柱状图的宽度是 O(n)\mathcal O(\sqrt n) 的。枚举最大宽度，因为要求互异，所以比他小的每一种宽度都需要至少有一行，所以从大到小枚举宽度转移 gg 就行了。
再考虑 ff 的转移：fi=gi−∑j<ifjval(j,i−j)f_i=g_i-\sum_{j<i}f_jval(j,i-j)，val(j,v)val(j,v) 表示用 ≥j+2\geq j+2 的数凑出来 vv 的方案数。
这个不太好算，我们把所有的 jj 放到一起算。这个转移显然有 i≥2ji\geq 2j，所以进行一个牛顿迭代（？）。假设已经知道了 f≤nf_{\leq n}，考虑如何推出 f≤2nf_{\leq 2n}。
注意到上面的转移天然可以对最小值进行限制。仍然是从大到小枚举宽度，假设枚举到宽度为 tt 的，可以选择在 hh 中加入一个 −fj-f_j 的贡献：贡献到 j+(j+2)tj+(j+2)t 的位置上，表示最小值需要大于等于 j+2j+2，其余 hh 的转移和 gg 相同，最后 fi=gi−hif_i=g_i-h_i 即可。复杂度 T(n)=T(n/2)+O(nn)=O(nn)T(n)=T(n/2)+\mathcal O(n\sqrt n)=\mathcal O(n\sqrt n)。
CPP
    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');
	}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...