[HDU1028] Ignatius and the Princess III

给定 (N)，问有多少种方案将其划分成若干个可重复整数的组合。(Nleq 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;
}