// 母函数解决的问题 // n 种物品,每个有一个wi,组合成total价值有多少种组合方案 // 将组合问题转换为 幂级数上的相乘问题(important) (Orz) // #include<iostream> // #include<cstdio> // #include<cstring> // using namespace std; // int n,a[105],b[105],m,s[10010],t[10010]; // int main() // { // while(~scanf("%d",&n),n) // { // m=0; // for(int i=0; i<n; i++) // { // scanf("%d%d",&a[i],&b[i]); // m+=(a[i]*b[i]); // } // if(m%3!=0) // { // printf("sorry "); // continue; // } // memset(s,0,sizeof(s)); // memset(t,0,sizeof(t)); // m/=3; // for(int i=0; i<=b[0]&&i*a[0]<=m; i++) // { // s[i*a[0]]=1; // } // for(int i=1; i<n; i++) // { // for(int j=0; j<=m; j++) // for(int k=0; k<=b[i]&&k*a[i]+j<=m; k++) // { // t[k*a[i]+j]+=s[j]; // t[k*a[i]+j]%=10000; // } // for(int j=0; j<=m; j++) // { // s[j]=t[j]; // t[j]=0; // } // } // if(s[m]!=0) // { // printf("%d ",s[m]); // } // else printf("sorry "); // } // return 0; // }
//母函数训练 2019/9/22 13:36 #include<iostream> #include<cstdio> #include<cstring>//HDU 1398 附上一些最近母函数做的水题(hahaha） using namespace std;//1 4 9 16 25 36 49 ... 289 const int maxn = 300 + 15; const int coin[] = {1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289}; int sup[maxn],tmp[maxn];//sup数组内的为系数 int PF(int n) { memset(sup,0,sizeof(sup)); memset(tmp,0,sizeof(tmp)); for(int i=0;i<=n;++i) sup[i] = 1;//因为有价值为1的coin存在 for(int k=1,j=coin[k];j<=n;++k,j=coin[k])//枚举除第一枚coin外的其他硬币 {//对每一枚硬币的value //cout<<k<<endl; for(int i=0;i<=n;++i) {//对于多项式每一项 for(int l=0;l+i<=n;l+=j) { tmp[i+l] += sup[i]; } } for(int i=0;i<=n;++i) { sup[i] = tmp[i]; tmp[i] = 0; } } return sup[n]; }//母函数 int main() { int n; while(cin>>n&&n) { cout<<PF(n)<<endl; } }