51Nod-1597 有限背包计数问题 根号分治

题意

有一个大小为\(n\)的背包，第\(i\)种物品的大小是\(i\),且有\(i\)个

求装满背包的方案数是多少个

\[1 \leq n \leq 1e5 \]

分析

容易发现当\(i > \sqrt{n}\)的时候个数大小相当于没有限制，因此这道题可以往根号分治的角度去思考

• 当\(i \leq \sqrt{n}\)

考虑直接\(DP\)

\[dp[i][j] = \sum dp[i-1][j-k*i] \]

这个东西可以通过维护$ % i$ 的前缀和\(O(1)\)转移，复杂度\(O(n\sqrt{n})\)

• 当\(i > \sqrt{n}\)

个数没有限制。

这里比较巧妙：把原问题转化为每次进行如下操作

1.加入一个最小的物品(大小为\(\sqrt{n} + 1\))

2.所以物品大小+1

容易证明这样的操作和原方案数是一一对应的

这样也可以简单的\(DP\)来实现

最后只需要分别统计一下即可

代码

const int maxn = 1e5 + 5;

int f1[2][maxn],f2[2][maxn];


int main(){
	int n = rd();
	int m = sqrt(n);
	f1[0][0] = 1;
	for(int i = 1;i <= m;i++){
		VI sum(i);
		for(int j = 0;j <= n;j++){
			add(sum[j % i],f1[i & 1 ^ 1][j]);
			if(j - i * (i + 1) >= j % i) add(sum[j % i],MOD - f1[i & 1 ^ 1][j - i  * (i + 1)]);
			f1[i & 1][j] = sum[j % i];
		}
	}
	VI sum(n + 1);
	sum[0] = 1;
	f2[0][0] = 1;
	for(int i = 1;i <= m;i++){
		memset(f2[i & 1] + (i - 1) * (m + 1),0,(m + 1) << 2);
		for(int j = i * (m + 1);j <= n;j++){
			f2[i & 1][j] = (f2[i & 1][j - i] + f2[i & 1 ^ 1][j - (m + 1)]) % MOD;
			add(sum[j],f2[i & 1][j]);
		}
	}
	int ans = 0;
	for(int i = 0;i <= n;i++)
		add(ans,mul(f1[m & 1][i],sum[n - i]));
	printf("%d",ans);
}