[51nod1597]有限背包计数问题
2024-08-25 09:45:07
你有一个大小为n的背包,你有n种物品,第i种物品的大小为i,且有i个,求装满这个背包的方案数有多少
两种方案不同当且仅当存在至少一个数i满足第i种物品使用的数量不同
Input
第一行一个正整数n
1<=n<=10^5
Output
一个非负整数表示答案,你需要将答案对23333333取模
首先我们可以发现,令S=sqrt(n),那么对于大小大于S的物品,其实是用不完的,我们可以把他们的数量视为无限个对于大小小于S的物品,我们可以令f[i][j]表示考虑了前i个物品,总大小为j的方案数,那么有:f[i][j]=sum{f[i-1][j-k*i]},0<=k<=i我们在DP的时候,假设当前要计算f[i][j],可以设tmp[v]为当前满足t mod i=v的f[i-1][t]的和然后就可以通过维护tmp数组,轻松计算出f[i][j]了这一步的时间复杂度是O(nsqrt(n))接下来考虑大小大于S的物品我们考虑一个给物品“动态添加大小”的DP:令g[i][j]表示,当前有i个物品,大小总和为j我们可以做的转移是:(1):将所有物品的大小加一 :g[i][j]->g[i][j+i](2):新建一个大小为S+1的物品g[i][j]->g[i+1][j+S+1]可以发现,物品总数最多为n/S个,所有g的第一维的规模是n/S的,所以这一个DP也是O(n*sqrt(n))的于是总复杂度就是O(n*sqrt(n))这道题还有更加优美的算法,可以用多项式黑科技进行推导,可以得到复杂度O(nlogn)的做法,由于出题人能力有限所以这里就不阐述了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define ll long long
#define ui unsigned int
#define ull unsigned long long
const int maxn=,modd=;
int f[][maxn],g[][maxn],sm[maxn],tmp[maxn];
int i,j,k,n,m,n1; int ra;char rx;
inline int read(){
rx=getchar(),ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
} #define MOD(x) x-=x>=modd?modd:0
#define UPD(x) x+=x<0?modd:0
int main(){
n=read(),n1=sqrt(n);register int i,j,k; bool now=,pre=;f[][]=;int mod;
for(i=;i<=n1;i++,std::swap(now,pre)){
memset(tmp,,i<<),mod=-;
for(j=,k=-i*i;j<=n;j++,k++){
if(++mod>=i)mod=;
tmp[mod]+=f[pre][j],MOD(tmp[mod]),
f[now][j]=tmp[mod];
if(k>=)tmp[mod]-=f[pre][k],UPD(tmp[mod]);
}
}//printf("n1:%d\n",n1);
//for(i=1;i<=n;i++)printf(" %d",f[pre][i]);puts("");
int n2=n/n1;
bool now1=,pre1=;g[][]=;
for(i=;i<=n2;i++,std::swap(now1,pre1)){
memset(g[now1],,(n1+)<<);
for(j=n1+,k=;j<=n;j++,k++)g[now1][j]=g[pre1][k];
for(j=i;j<=n;j++)g[now1][j]+=g[now1][j-i],MOD(g[now1][j]);
for(j=;j<=n;j++)sm[j]+=g[now1][j],MOD(sm[j]);
}
int ans=f[pre][n]+sm[n];MOD(ans);
for(i=;i<n;i++)ans=(ans+1ll*f[pre][i]*sm[n-i])%modd;
printf("%d\n",ans);
}
最新文章
- 阿里聚安全受邀参加SFDC安全大会,分享互联网业务面临问题和安全创新实践
- linux下安装redis的详细过程
- TCP建立连接、断开连接以及正常报文的报头和报位的大小
- Yii2分页
- LeetCode Longest Palindrome
- 转--优化临时表使用,SQL语句性能提升100倍
- 使用Notepad++快速有效删除复制代码中的行号
- bzoj 3879 虚树
- iOS开发——打包静态库与Framework
- C++ 常见的 Undefined symbols for architecture *
- Android开源项目——设置图文居中的按钮 IconButton
- django创建命令及配置
- .net使用websocket
- ASP.NET MVC案例教程(五)
- Learning-Python【18】:Python常用模块(1)—— time、datetime、randrom
- R语言常用基础知识(入门)
- iterm2 恢复默认设置
- 在yii中使用memcache
- Ansible 连接主机显示报错的处理方案
- 【转】基于R语言构建的电影评分预测模型