hdu 1028 Ignatius and the Princess III【生成函数】

老是想着化简，实际上O(n^3)就行了……
写成生成函数是\( \prod_{i=1}^{n}(1+x^i+2^{2i}+...+x^{ \left \lfloor \frac{n}{i} \right \rfloor }) \)，暴力乘即可

#include<iostream>
#include<cstdio>
using namespace std;
const int N=125;
int n,a[N],b[N];
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=0;i<=n;i++)
            a[i]=1,b[i]=0;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
                for(int k=0;k<=n;k+=i)
                    b[j+k]+=a[j];
            for(int j=0;j<=n;j++)
                a[j]=b[j],b[j]=0;
        }
        printf("%d\n",a[n]);
    }
    return 0;
}

hdu 1028 Ignatius and the Princess III【生成函数】

原文：https://www.cnblogs.com/lokiii/p/10017685.html