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

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(nsqrt{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);
}