研究以下多项式乘法:
可以看出:
x2项的系数a1a2+a1a3+...+an-1an中所有的项包括n个元素a1,a2, …an中取两个组合的全体;
同理:x3项系数包含了从n个元素a1,a2, …an中取3个元素组合的全体;
以此类推。
特例:
若令a1=a2= …=an=1,在(8-1)式中a1a2+a1a3+...+an-1an项系数中每一个组合有1个贡献,其他各项以此类推。故有:
母函数定义:
对于序列a0,a1,a2,…构造一函数:
实例分析
例1:若有1克、2克、3克、4克的砝码各一枚,能称出哪几种重量?各有几种可能方案?
如何解决这个问题呢?考虑构造母函数。
如果用x的指数表示称出的重量,则:
1个1克的砝码可以用函数1+x表示,
1个2克的砝码可以用函数1+x2表示,
1个3克的砝码可以用函数1+x3表示,
1个4克的砝码可以用函数1+x4表示,
几种砝码的组合可以称重的情况,可以用以上几个函数的乘积表示:
(1+x)(1+x^2)(1+x^3)(1+x^4)
=(1+x+x^2+x^3)(1+x^3+x^4+x^7)
=1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^10
从上面的函数知道:可称出从1克到10克,系数便是方案数。
例如右端有2x5项,即称出5克的方案有2:5=3+2=4+1;同样,6=1+2+3=4+2;10=1+2+3+4。
故称出6克的方案有2,称出10克的方案有1
//母函数模板
//形如(1+x^1+x^2+x^3+....+x^n)*(1+x^2+x^4+x^6+....+x^n)*......(1+x^m+x^2m+x^3m+....+x^n)
#include<iostream> using namespace std; const int lmax=10000; int c1[lmax+1],c2[lmax+1]; int main() { int n,i,j,k; while(cin>>n) { for(i=0;i<=n;i++) { c1[i]=1;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)//第i个大括号中的所有元素 {c2[j+k]+=c1[j];} for(j=0;j<=n;j++)//得到一个新的第一个大括号 { c1[j]=c2[j];c2[j]=0; } } cout<<c1[n]<<endl; } return 0; }