[LOJ6089] 小Y的背包计数问题

问题描述

小 Y 有一个大小为 n 的背包,并且小 Y 有 n 种物品。

对于第 i 种物品,共有 i 个可以使用,并且对于每一个 i 物品,体积均为 i 。

求小 Y 把该背包装满的方案数为多少,答案对于 23333333 取模。

定义两种不同的方案为:当且仅当至少存在一种物品的使用数量不同。

输入格式

第一行一个整数 n 。

输出格式

输出一行,表示方案数。

样例输入

3

样例输出

2

数据范围

n<=100000

解析

观察一下题目,最特殊的地方在于第 i 个物品只有 i 个。而背包的容量只有 n ,所以,对于体积大于(sqrt{n}) 的物品,是不可能全部放完的。也就是说,(sqrt{n})以后的物品相当与没有限制存在。所以,初步的思路是小于(sqrt{n}) 的物品用多重背包,大于的用完全背包。

但是即使这样也无法通过。我们需要优化两种DP。

先来考虑多重背包。设(f[i][j])表示前(i)个物品消耗了(j)的体积,那么多重背包的转移方程是这样的:

[f[i][j]=sum_{k=0}^{j}f[i-1][j-k imes i] ]

可以发现,(f[i][j])只会从(f[i-1][j],f[i-1][j-i],...,f[i-1][j-k imes i])转移过来。所以,我们可以用类似前缀和的方式优化转移,将前半部分的复杂度优化到(O(nsqrt{n}))

再来考虑完全背包。我们可以转化一下模型。假设我们现在有很多长度为(sqrt{n})的木棍,每次可以在最前面加入一根,或者把所有已经加入的木棍的长度全部加一。设(g[i][j]) 表示选了(i)根木棍,总长度为(j)的方案数,那么,我们有如下DP方程:

[g[i][j]=g[i-1][j-sqrt{n}]+g[i][j-i] ]

其实,(g[i][j])对应的就是原问题中选了前(i)个物品,总体积为(j)的方案数。有了这些,我们就可以统计答案了。设(sum[i]=sum_{j=sqrt{n}+1}^{n} g[j][i]) ,那么答案就是

[Ans=sum_{i=0}^{n}f[sqrt{n}][i] imes sum[n-i] ]

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#define N 100002
#define M 350
using namespace std;
const int mod=23333333;
int n,m,f[M][N],g[M][N],sumf[N],sumg[N],i,j,k,l;
int read()
{
	char c=getchar();
	int w=0;
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0'){
		w=w*10+c-'0';
		c=getchar();
	}
	return w;
}
signed main()
{
	n=read();
	m=sqrt(n);
	f[0][0]=1;
	for(i=1;i<=m;i++){
		for(j=0;j<i;j++){
			int cnt=0;
			for(k=j;k<=n;k+=i){
				cnt++;
				sumf[cnt]=(sumf[cnt-1]+f[i-1][k])%mod;
			}
			for(k=j,l=1;k<=n;k+=i,l++) f[i][k]=((f[i][k]+sumf[l])%mod-sumf[max(0,l-1-i)]+mod)%mod;
		}
	}
	g[0][0]=sumg[0]=1;
	for(i=1;i<=m;i++){
		for(j=0;j<=n;j++){
		    if(j>=i) g[i][j]=(g[i][j]+g[i][j-i])%mod;
			if(j>=m+1) g[i][j]=(g[i][j]+g[i-1][j-(m+1)])%mod;
			sumg[j]=(sumg[j]+g[i][j])%mod;
		}
	}
	long long ans=0;
	for(i=0;i<=n;i++) ans=(ans+1LL*f[m][i]*sumg[n-i]%mod)%mod;
	printf("%lld
",ans);
	return 0;
}
原文地址:https://www.cnblogs.com/LSlzf/p/12203059.html