网站开发案列,国家建设部举报网站,wordpress一键关注,浦东新区手机网站设计正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1597 题目大意 nnn种物品#xff0c;第iii个大小为iii且有iii个。
求恰好填满大小为nnn的背包的方案数 解题思路
我们可以将背包分为两份#xff0c;对于大小小于等于n\sqrt nn的物品#xff0c;这…正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1597 题目大意
nnn种物品第iii个大小为iii且有iii个。
求恰好填满大小为nnn的背包的方案数 解题思路
我们可以将背包分为两份对于大小小于等于n\sqrt nn的物品这样的物品数量不超过nnn\sqrt nnn个所以我们可以用多重背包来做这里要优化我们将fi,jf_{i,j}fi,j中根据j%ij\%ij%i的不同来进行分组这样只有组内可以相互转移且是在一个区间内转移可以O(nn)O(n\sqrt n)O(nn)的计算出答案然后反向枚举压缩掉iii这一维就有方程u枚举余数 fup∗i∑p−i≤k≤p−1fuk∗if_{up*i}\sum_{p-i\leq k\leq p-1}f_{uk*i}fup∗ip−i≤k≤p−1∑fuk∗i
然后对于大于n\sqrt nn的物品我们可以将其视为有无限个物品所以我们可以将问题变为求将一个数字分解成若干个可以相同但是要大于n\sqrt nn的数字的和的方案数。
考虑一个集合每次可以加入一个数字物品n1\sqrt n1n1或者全体数字都111物品都变大一个。
然后设gi,jg_{i,j}gi,j表示目前集合内数字和选择的物品和为iii然后集合内数字物品个数为jjj就有方程gi,jgi−n−1,jgi,j−1g_{i,j}g_{i-\sqrt n-1,j}g_{i,j-1}gi,jgi−n−1,jgi,j−1
然后转移即可 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N1e510,XJQ23333333;
int n,T,f[N],g[2][N],s[N],ans;
int main()
{scanf(%d,n);Tsqrt(n)1;f[0]1;for(int i1;iT;i){for(int u0;ui;u){int sum0,t(n-u)/i;for(int pt;pmax(t-i,-1);p--)(sumf[ui*p])%XJQ; for(int pt;p0;p--){if(p-i0)sum(sumf[ui*(p-i)])%XJQ;sum(sum-f[ui*p]XJQ)%XJQ;f[up*i](f[up*i]sum)%XJQ;}}}g[0][0]s[0]1;for(int i1;iT;i){memset(g[i1],0,sizeof(g[i1]));for(int jT;jn;j)g[i1][j](g[~i1][j-T]g[i1][j-i])%XJQ,(s[j]g[i1][j])%XJQ;}for(int i0;in;i)(ans1ll*f[i]*s[n-i]%XJQ)%XJQ;printf(%d,ans);
}
