ACM201403版_09)母函数.ppt

ACM程序设计;第九讲;研究以下多项式乘法：; 若令a1=a2= …=an=1，在（8-1）式中a1a2+a1a3+...+an-1an项系数中每一个组合有1个贡献，其他各项以此类推。故有：;母函数定义：; For example:;实 例 分 析;例1：若有1克、2克、3克、4克的砝码各一 枚，能称出哪几种重量？各有几种可能方案？?;几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：;例2：求用1分、2分、3分的邮票贴出不同数值的方案数—— ;概念：整数拆分 ;练习（写出以下问题的母函数）：;如何编写程序实现母函数的应用呢？;以整数拆分为例：;// Author by lwg #include iostreamusing namespace std;const int lmax=10000; int c1[lmax+1],c2[lmax+1];int main(){ int n,i,j,k; while (cinn) {for (i=0;i=n;i++) {c1[i]=0; c2[i]=0; } for (i=0;i=n;i++) c1[i]=1; for (i=2;i=n;i++) { for (j=0;j=n;j++) for (k=0;k+j=n;k+=i) { c2[j+k]+=c1[j]; } for (j=0;j=n;j++) { c1[j]=c2[j]; c2[j]=0; } } coutc1[n]endl; } return 0; };主打例题：HDOJ_1398 Square Coins ;算法分析：;//HDOJ_1398 Square Coins #include iostream using namespace std; const int lmax=300; int c1[lmax+1],c2[lmax+1]; int main(void) { int n,i,j,k; while (cinn n!=0) { for (i=0;i=n;i++) { c1[i]=1; c2[i]=0; } for (i=2;i=17;i++) { for (j=0;j=n;j++) for (k=0;k+j=n;k+=i*i) { c2[j+k]+=c1[j]; } for (j=0;j=n;j++) { c1[j]=c2[j]; c2[j]=0; } } coutc1[n]endl; } return 0; };//HDOJ_1398 Square Coins //变化一点，灵活多多 … int main(void) { int n,i,j,k; int elem[17]={1,4,9,16,25,36,…,169,196,225,256,289} while (cinn n!=0) { for (i=0;i=n;i++) { c1[i]=1; c2[i]=0; } for (i=2; i=17; i++) { for (j=0;j=n;j++) for (k=0;k+j=n; k+=elem[i-1] ) { c2[j+k]+=c1[j]; } for (j=0;j=n;j++) { c1[j]=c2[j]; c2[j]=0; } } coutc1[n]endl; } return 0; } ;思考（1）：;思考（2）：;思考（3）：;思考（4）???;Any questions?;Welcome to HDOJ