有限背包计数问题

51nod1597 有限背包计数问题

time:2.333 s memory:131072 KB

Description
你有一个大小为n的背包，你有n种物品，第i种物品的大小为i，且有i个，求装满这个背包的方案数有多少
两种方案不同当且仅当存在至少一个数i满足第i种物品使用的数量不同

Input
第一行一个正整数n

Output
一个非负整数表示答案，你需要将答案对23333333取模

Sample Input

3

Sample Output

2

Hint
1<=n<=10^5

---

解题思路

被题目吓到了啊~~

把题目分成两个部分：
①编号为 1→n√ 的物品 ，多重背包的方案数统计问题，参照多重背包问题，把单点队列部分改改就好了 O(n√∗n√)=O(n)
②编号为 n√+1→n 的物品，因为这些物品任一放完的话都会超过背包容量，所以这些就相当于无限背包的方案数统计问题，但是考虑到直接背包的时间复杂度加上①是 O(n2) 的，所以我们就要用另一种动态规划的设法：
设 f[i][j] 表示加上了i个物品，容量为j的方案数，对于当前状态，我们可以考虑:
1. 把加上的物品都加1,容量就会加j，也就是f[i][j+i]+=f[i]
2. 再加一个编号为 n√+1 的物品f[i+1][j+sqrt(n)+1]+=f[i]
这样执行 n√ 次，也就是加上了 n√ 个物品，就可以不重复不遗漏地求出所有状态了 O(n32)

新套路啊

Code：

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cctype>
#define mo 23333333
using namespace std;

typedef long long ll;

int n,sq;
void swap(int &a,int &b){a^=b;b^=a;a^=b;}
ll f[3][100001],que[100001],h,t,sum,num[100001],las=2,now=1;

int main(){
scanf("%d",&n);sq=floor(sqrt(n));
    f[1][0]=1;f[0][0]=1;
for(int i=1;i<=sq;i++){
        swap(las,now);
for(int j=0;j<=n;j++){
            f[now][j]=0;
if(j>=sq+1)f[now][j]+=f[las][j-sq-1];
if(j>=i)f[now][j]+=f[now][j-i];
if(f[now][j]>=mo)f[now][j]-=mo;
            f[0][j]+=f[now][j];if(f[0][j]>=mo)f[0][j]-=mo;
        }
    }
for(int i=1;i<=sq;i++){
for(int l=0;l<i;l++){
            h=1;t=0;sum=0;
for(int k=l;k<=n;k+=i){
                que[++t]=k;num[t]=f[0][k];sum+=f[0][k];while(h<=t && que[h]+i*i<k)sum-=num[h++];
                sum%=mo;sum+=mo;if(sum>=mo)sum-=mo;f[0][k]=sum;
            }
        }
    }
printf("%lld",f[0][n]);
return 0;
}