题目：http://acm.hdu.edu.cn/showproblem.php?pid=1028
就是可以用任意个1、2、3、...，所以式子写出来就是这样：(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...(1+x^n+x^(2*n)+...)... 因为求 x^n 系数，所以再往后的式子就没有贡献了，求到第 n 个式子即可。
一个x^2就像一条边一样，可以让第 k 项的系数转移给第 k+2 项。按这个思路写代码就行了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=125; int n,a[N],b[N]; int main() { while(scanf("%d",&n)==1) { 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;j+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/Narh/p/10025518.html