题意

有5个盘子，每个盘子有有限个或者无限个体积为 的面包，你有一个体积为 的背包，问刚好装满背包的方案数（两个方案不同当且仅当从某一个盘子中拿出的面包体积不同）。

方法一（暴力解法，不可AC）：分组背包

显然这是一个分组背包问题，其中第1个盘子对应着物体体积为1的完全背包问题，第2个盘子对应着物体体积为1的01背包问题,第3个盘子对应着最多只能拿4个，每个物体体积为1的多重背包问题，第4个盘子对应着物体体积为2的完全背包问题，第5个盘子对应着物体体积为5的完全背包问题。
代码：

class Solution {
public:
    long long f[1000000001];
    long long wwork(int n) {
        f[0]=1;
        for(int i=1;i<=5;i++){
            switch(i){
                case 1:{
                    for(int j=1;j<=n;j++){
                        f[j]+=f[j-1];
                    }
                    break;
                }
                case 2:{
                    for(int j=n;j>=1;j--){
                        f[j]+=f[j-1];
                    }
                    break;
                }
                case 3:{
                    for(int j=n;j>=1;j--){
                        for(int k=1;k<=4&&k<=j;k++){
                            f[j]+=f[j-k];
                        }
                    }
                    break;
                }
                case 4:{
                    for(int j=2;j<=n;j++){
                        f[j]+=f[j-2];
                    }
                    break;
                }
                case 5:{
                    for(int j=5;j<=n;j++){
                        f[j]+=f[j-5];
                    }
                    break;
                }
            }
        }
        return f[n];
    }
};

时间复杂度：
空间复杂度： ，采用滚动数组的形式优化掉一维。

方法二（正解）：生成函数

对于一种面包，我们考虑拿了0个，1个，2个，3个，...，n个。
我们可以考虑用一个多项式 来表示。
其中 的 次幂表示拿了体积为n的面包。
那么，对于每种面包，我们都可以考虑用一个多项式来表示，那么，最后如何计算方案？
答案是多项式求卷积，最后计算出 的系数就是凑成体积为 的面包的方案数。
事实上，考虑任意两个多项式求卷积的过程，某一项 会与另一个多项式的每一项相乘，也就是底数不变，指数相加，这也正是面包体积"拼凑"的过程，显然这样可以枚举出所有的方案。
故以下我们可以考虑对每个面包构造多项式来求解。
设以下
对于面包1，我们可以构造多项式：


对于面包2，我们可以构造多项式：

对于面包3，我们可以构造多项式：

对于面包4，我们可以构造多项式：


对于面包5，我们可以构造多项式：


于是有：
根据广义二项式定理可得：

故 的系数为
即最后的答案为
代码：

class Solution {
public:
    long long wwork(int n) {
        return 1ll*(n+1)*(n+2)/2;
    }
};

时间复杂度： ，直接返回表达式的值即可。
空间复杂度： ，没有额外申请内存。