51nod1597 有限背包计数问题

基准时间限制：2.333 秒 空间限制：131072 KB 分值: 160 难度：6级算法题
你有一个大小为n的背包，你有n种物品，第i种物品的大小为i，且有i个，求装满这个背包的方案数有多少
两种方案不同当且仅当存在至少一个数i满足第i种物品使用的数量不同
Input
第一行一个正整数n 1<=n<=10^5
Output
一个非负整数表示答案，你需要将答案对23333333取模
Input示例
3
Output示例
2

题外话：我喜欢这道题的时间限制和模数。这道题我感觉非常好（也可能是因为我太弱了）。时间效率光荣垫底了（所以建议大家不要看我的代码，请只看分析吧）。
作为蒟蒻我只可以想到没有限制时的$O(n^2)$完全背包：$f[i][j]$表示用前i个物品填满容量为j的背包时的方案数，$f[i][j]=f[i-1][j]+f[i][j-i]$，现在有了限制而且$n$又这么大该怎么办呢？

我们不妨分成两部分考虑：设$m=sqrt{n}$，那么前$m$件物品的确有限制，但$m$之后的物品实际上是没有数量限制的（刚好用完或根本用不完）。
首先是前$m$件物品的那部分，我们可以用一个类完全背包处理，完全背包第二部分是$f[i][j-i]$正是因为利用了$f[i][j]$顺序处理从而十分方便地统计了$f[i-1][...]$的部分和，现在有了数量限制，我们就不得不回归原始了：把原来的完全背包时的转移方程展开，全部用$f[i-1][...]$转移过来就好了，得到$f[i][j]=sum_{k=0}^if[i−1][j−k∗i]$，为了简化时间，我们用$displaystyle tmp[x]=sum_{y mod i≡x}{f[i-1][y]}$来加速转移，那么$f[i][j]=tmp[j mod i]$，不断维护$tmp$数组即可做到$O(n*sqrt{n})$完成$f$数组的计算了。

再来看第二部分的计算，什么？你想用完全背包？算一下时间复杂度吧。这里我们就要用到一种比较神奇的思想了——序列思想（澄清一下：出题人解题报告里称其为“给物品动态添加大小的$DP$”，序列纯属个人理解）。想象一下现在有一个长度为$i$，相加和为$j$的序列，我们用$g[i][j]$表示生成这个序列的方案数，再回顾一下我们的目标：处理出来只用$>m$的物品凑出来某一个容量时的方案数。那么决策就来了，决策一：把当前序列中的所有数$+1$（即$g[i][j+i]+=g[i][j]$）；决策二：向当前序列中添加一个数$m+1$（即$g[i+1][j+m+1]+=g[i][j]$）。不好理解的话可以想象一张图，由于决策一和决策二的执行次数和时间不尽相同，我们一定能统计出正确的方案数（当然也可以用背包的模型来解释和理解其正确性）。由于每个物品占用容量至少为$m$，所以我们可以得到这个序列的最长长度为$frac{n}{m}=sqrt{n}$，所以这一步的时间复杂度也为$O(n*sqrt{n})$。

撒花庆祝，剩下的我们只需要统计一下总方案数就好了，乘法原理：$displaystyle ans=sum_{j+k=n}{f[m][j]*g[...][k]}$

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
const int M=320;
const ll mod=23333333LL;
int n,m,f[2][N],g[M][N],tmp[N];
int now,pre=1;ll f1[N],g1[N],ans;
int main()
{
    scanf("%d",&n);f[0][0]=g[0][0]=1;
    m=(int)ceil(sqrt((double)n));
    for (int i=1;i<=m;++i)
    {
        for (int j=0;j<i;++j)tmp[j]=0;
        int nowmod=-1;swap(now,pre);
        for (int j=0;j<=n;++j)
        {
            ++nowmod;if(nowmod>=i)nowmod=0;
            (tmp[nowmod]+=f[pre][j])%=mod;
            f[now][j]=tmp[nowmod];
            if(j>=i*i)
            tmp[nowmod]=(tmp[nowmod]-f[pre][j-i*i]+mod)%mod;
        }
    }
    for (int i=0;i<=m;++i)
    {
        for (int j=0;j<=n;++j)
        {
            if(i&&j+i<=n)(g[i][j+i]+=g[i][j])%=mod;
            if(j+m+1<=n)(g[i+1][j+m+1]+=g[i][j])%=mod;
        }
    }
    ++g1[0];
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
        (g1[i]+=g[j][i])%=mod;
    for (int i=0;i<=n;++i)f1[i]=f[now][i];
    for (int i=0;i<=n;++i)
    (ans+=(f1[i]*g1[n-i]%mod))%=mod;
    printf("%I64dn",ans);
    return 0;
}

其它比我厉害多了的做法：ORZ r_64的母函数解法
ORZ tangjz的五边形数解法（咦，好像也是母函数吧，只不过是从系数以及函数的角度考虑的）：
关于五边形数定理：参考文章1、参考文章2、参考文章3
对于这道题我们先求出没有限制时的分割数，然后再化一下式子（公式恐惧症又犯了），如果只有$P(x)$则代表没有限制时的方案数，现在有了限制，无非就是在前面添加了一个多项式，$x^n$前的系数仍是当前有限制下的方案数，所以我们考虑前面的多项式对后面多项式前的系数有何影响（多少贡献）即可。由于前面的多项式已经不是$(1-x^i)$的形式，所以无法使用五边形数定理，所以我的程序实际上相当于是暴力跑出了所有的系数。（能否只求出$x^n$前的系数从而减少时间呢？请发表一下评论指导一下蒟蒻吧。）
$(1+x)*(1+x^2+x^4)*cdots*(1+x^i+x^{2i}+cdots+x^{ii})*cdots$
$displaystyle =frac{1-x^{1*2}}{1-x}*frac{1-x^{2*3}}{1-x^2}*cdots*frac{1-x^{i*(i+1)}}{1-x^i}*cdots$
$displaystyle =prod_{i=1}^{+infty}{1-x^{i*(i+1)}}*P(x)$
$displaystyle =(prod_{i=1}^{+infty}{1-x^{i*(i+1)}})*(1+x^1+2x^2+3x^3+5x^4+7x^5+11x^6+15x^7+22x^8+cdots)$

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=100100;
const int mod=23333333;
int T,n,K,ans[N];
#define f(x) (((x)*(3*(x)-1))>>1)
#define g(x) (((x)*(3*(x)+1))>>1)
#define h(x) ((x)*((x)+1))
int main()
{
    scanf("%d",&n);ans[0]=1;
    for (int i=1;i<=n;++i)
    {
        for (int j=1;f(j)<=i;++j)
            if(j&1) ans[i]=(ans[i]+ans[i-f(j)])%mod;
            else ans[i]=(ans[i]-ans[i-f(j)]+mod)%mod;
        for (int j=1;g(j)<=i;++j)
            if(j&1) ans[i]=(ans[i]+ans[i-g(j)])%mod;
            else ans[i]=(ans[i]-ans[i-g(j)]+mod)%mod;
    }
    for (int i=1;h(i)<=n;++i)
        for (int j=n;j>=h(i);--j)
        ans[j]=(ans[j]-ans[j-h(i)]+mod)%mod;
    printf("%dn",ans[n]);
    return 0;
}

总结：
1、仔细且耐心分析题目中限制性条件的诸多性质，例如其影响、贡献、被限制的条件、与没有限制的不同（比如考虑放松限制然后计数原理等）。
2、考虑分块、分治等方法处理问题（比如把定义域、值域分为不同的两部分，分别处理，还有经典的meet in the middle），往往能简化时间、空间复杂度。
3、序列思想很值得推广，体现了一种动态修改的思想，修改的时间不同，得到的结果也不同，对于能简化为一个序列、多项式等模型貌似都可以使用。

最后

以上就是超帅小懒猪为你收集整理的51nod1597 有限背包计数问题的全部内容，希望文章能够帮你解决51nod1597 有限背包计数问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。