[HDU1028] Ignatius and the Princess III - 生成函数

给定 \(N\)，问有多少种方案将其划分成若干个可重复整数的组合。\(N\leq 120\)。

Solution

考虑 OGF，\(f(x)=(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...\)

乘到 \(n\) 就可以了，所求为 \([x^n]f(x)\)，暴力多项式乘法即可，复杂度 \(O(n^3)\)

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 255;

int f[N],g[N],h[N],n;

void mul() {
    memset(h,0,sizeof h);
    for(int i=0;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            h[i+j]+=f[i]*g[j];
        }
    }
    for(int i=0;i<=n;i++) f[i]=h[i];
}

signed main() {
    n=120;
    f[0]=1;
    for(int i=1;i<=n;i++) {
        memset(g,0,sizeof g);
        for(int j=0;j<=n;j+=i) g[j]=1;
        mul();
    }
    while(cin>>n) cout<<f[n]<<endl;
}

[HDU1028] Ignatius and the Princess III - 生成函数

原文：https://www.cnblogs.com/mollnn/p/12603029.html