数学、生成函数

对数量为 $n$，重量为 $w$ 的砝码构造生成函数

$$f(w,n)=1+x^{w}+x^{2w}+x^{3w}+ \cdots + x^{nw}$$

构造完成后将所有重量的砝码对应的生成函数相乘得到 $F(x)$，令 $F(x)$ 的 $i$ 次项系数为 $k_i$，这些砝码有 $k_i$ 种凑出重量 $i$ 的方案，答案为 $\sum\limits_{i=1}^{\infty} [k_i \neq 0]$。

#include<bits/stdc++.h>
using namespace std;
constexpr int S[]={0,1,2,3,5,10,20};
template<typename T>
struct Poly{
    int len;T f[2005];
    Poly(){len=0,memset(f,0,sizeof(f));}
    Poly operator*(const Poly<T> &x)const{
        Poly<T> ret;
        ret.f[0]=f[0]*x.f[0];
        for(int i=1;i<=len;i++) ret.f[i]+=f[i]*x.f[0];
        for(int i=1;i<=x.len;i++) ret.f[i]+=f[0]*x.f[i];
        for(int i=1;i<=len;i++)
            for(int j=1;j<=x.len;j++)
                ret.f[i+j]+=f[i]*x.f[j];
        ret.len=len+x.len;
        while(ret.len&&!ret.f[ret.len]) ret.len--;
        ret.len=max(ret.len,1);
        return ret;
    }
};
Poly<int> pol;
int ans,opt;
int main(){
    pol.len=0,pol.f[0]=1;
    for(int i=1;i<=6;i++){
        scanf("%d",&opt);
        Poly<int> fio;
        fio.len=S[i]*opt;
        for(int j=0;j<=opt;j++) fio.f[j*S[i]]=1;
        pol=pol*fio;
    }
    for(int i=1;i<=pol.len;i++) if(pol.f[i]) ans++;
    printf("Total=%d\n",ans);
    return 0;
}