#根号分治，背包#51nod 1597 有限背包计数问题 LOJ 6089 小Y的背包计数问题

题目

有一个大小为(n)的背包，有(n)种物品，

第(i)种物品的大小为(i)，且有(i)个，

求装满这个背包的方案数

(nleq 10^5)

---

分析

直接多重背包会有问题，考虑根号分治，
对于大小(leq sqrt n)的物品，
其实可以用前缀和优化多重背包，因为大小为(i)
对于大小(> sqrt n)的物品，设(g[i][j])表示选了(i)种物品容量为(j)的方案数，
考虑整体物品加1或者给背包新加入大小为(sqrt n+1)的物品，即
(g[i][j]=g[i][j-i]+g[i-1][j-sqrt n-1])
合并两个背包即可

---

代码

#include <cstdio>
#include <cctype>
#include <cmath>
#define rr register
using namespace std;
const int N=100011,mod=23333333;
int f[2][N],g[2][N],s[N],n,bl,ans;
inline signed mo(int x,int y){return x+y>=mod?x+y-mod:x+y;}
signed main(){
	scanf("%d",&n),bl=sqrt(n),f[0][0]=1;
	for (rr int i=1;i<=bl;++i){
		for (rr int j=0;j<i;++j) s[j]=0;
		for (rr int j=0;j<=n;++j){
			f[i&1][j]=mo(f[(i&1)^1][j],s[j%i]);
			s[j%i]=mo(s[j%i],f[(i&1)^1][j]);
			if (j>=i*i) s[j%i]=mo(s[j%i],mod-f[(i&1)^1][j-i*i]);
		}
	}
	g[0][0]=1,ans=f[bl&1][n];
	for (rr int i=1;i<=bl;++i){
		for (rr int j=0;j<i;++j) g[i&1][j]=0;
		for (rr int j=i;j<=n;++j){
			g[i&1][j]=g[i&1][j-i];
			if (j>bl) g[i&1][j]=mo(g[i&1][j],g[(i&1)^1][j-bl-1]);
		}
		for (rr int j=i;j<=n;++j) ans=mo(ans,1ll*f[bl&1][n-j]*g[i&1][j]%mod);
	}
	return !printf("%d",ans);
}