洛谷 P8340 山河重整题解

First Post:

2023-05-02

Last Update:

2023-07-04

一道很有启发意义的数数题。

看到这题之后，当然是首先从开始想起。

如果我们从小到大地决策某个数是否被加入，那么现在已经被加入的数字，在值域上能表示的一定是一段前缀，即一个形如的区间，那么可以设计状态表示加入了前个数，当前能表示的区间为的方案数。

在加入数之后，能表示的区间变为，转移合法当且仅当，也就是说，对于的，其可以转移到。

分析上述的过程，可以得到一个很重要的结论，即。这个结论跟上述 dp 的转移式是等价的。

对每个都要求其合法是比较困难的，我们不如计数不合法的方案数。

因为不合法的位置可能有很多，一个计数的套路是考察第一个不合法的位置。

设考虑位置且位置为第一个不合法位置的方案数为。

也就是说，满足均可被拼出，但无法被拼出。

通过上面的结论，我们可以知道中被选中的数的和恰好为。

为了保证是第一个不合法的位置，我们可以用满足上述条件的所有方案，减去第一个不合法位置为的方案数。

形式化地说，，其中是转移的系数，因为根据的意义，不能填数，且中的数和为，那么就是在中选数，使这些数的和为的方案数。

先考虑怎么求，显然，它是的 互异拆分数，也就是将拆分为若干个不同的数的和的方案数。

回顾互异拆分数的经典做法，我们知道，只会被拆为最多个数，我们可以据此设计 DP。

将拆成若干个数的时候，我们会限制来保证计数不重复，但这个限制本身很麻烦，我们考虑差分数组，那我们就只需要保证就可以了，而每个对全局的贡献就是。那么每个就相当于一个大小为的物品，这个 DP 则相当于完全背包（因为没有上界），因为，我们对这些跑完全背包即可求出拆分数。

代码如下：

f[0] = 1;int lim = sqrt(2 * n);
for(int i = lim;i >= 1;i--) // 倒序枚举 i，方便滚动数组
{
	for(int j = n;j > i;j--) f[j] = f[j - i];
	for(int j = i;j >= 1;j--) f[j] = 0;
	for(int j = i;j <= n;j++)
        Plus(f[j],f[j - i]); // 完全背包
}

回到上面的式子，我们考虑怎么处理，假设我们已经知道了，那么我们要解决的是，也就是在中选数，使得它们的和为的方案数。

假设我们已经确定了中选多少个数，设其为，那么我们可以把这其中的所有数全部减去，然后接着做互异拆分数的 DP,事实上，我们只要把贡献到数组中的位置，那么最后提取背包数组中位置的值就可以得到这个的贡献。

因为我们是倒序枚举的（注意这里的是完全背包中的），所以枚举到某个数的时候，我们不妨假设其就是，在后续的枚举中，我们会把其他的物品（也就是其他的一步一步加入进去），DP 完了之后，这个方案自然会被贡献到正确的位置。

上述两段可以结合代码理解。

另一个问题是，我们在求的时候，假设已经被算出来了，那我们怎么实现这个算法呢？

事实上，能贡献到，说明，即。也就是说，如果要求的，我们可以先递归求出的，再用上述做法求出后半部分的即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n,P;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int f[N],t[N];
void Solve(int n)
{
	if(n <= 1) return;
	int lim = sqrt(2 * n);
	Solve(n >> 1);
	for(int i = 0;i <= n;i++) t[i] = 0;         
	for(int i = lim;i >= 1;i--)
	{
		for(int j = n;j >= i;j--) t[j] = t[j - i];
		for(int j = i - 1;j >= 0;j--) t[j] = 0;
		for(int j = 0;j + (j + 2) * i <= n;j++)
			Plus(t[j + (j + 2) * i],f[j]);
		for(int j = i;j <= n;j++) Plus(t[j],t[j - i]);
	}
	for(int i = (n >> 1) + 1;i <= n;i++)
		Plus(f[i],P - t[i]);
}
int Pow2[N];
int main()
{
  	Pow2[0] = 1;
	for(int i = 1;i <= n;i++) Pow2[i] = (Pow2[i - 1] + Pow2[i - 1]) % P;
	f[0] = 1;int lim = sqrt(2 * n);
	for(int i = lim;i >= 1;i--)
	{
		for(int j = n;j > i;j--) f[j] = f[j - i];
		for(int j = i;j >= 1;j--) f[j] = 0;
		for(int j = i;j <= n;j++)
			Plus(f[j],f[j - i]);
	}
	Solve(n);
	int ans = 0;
	for(int i = 0;i < n;i++)
		ans = (ans + 1ll * f[i] * Pow2[n - i - 1] % P) % P;
	ans = (Pow2[n] + P - ans) % P;
	cout << ans << endl;
	return 0;
}

≡

洛谷 P8340 山河重整 题解

洛谷 P8340 山河重整题解