【算法小总结】母函数模板

研究以下多项式乘法

【算法小总结】母函数模板

可以看出:

x2项的系数a1a2+a1a3+...+an-1an中所有的项包括n个元素a1a2an中取两个组合的全体;

同理:x3项系数包含了从n个元素a1a2an中取3个元素组合的全体;

以此类推。 

特例:

若令a1=a2= =an=1,在(8-1)式中a1a2+a1a3+...+an-1an项系数中每一个组合有1个贡献,其他各项以此类推。故有:

【算法小总结】母函数模板

母函数定义:

对于序列a0,a1,a2构造一函数:

【算法小总结】母函数模板

n称函数G(x)是序列a0a1a2的母函数

 

实例分析

例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克的方案有25=3+2=4+1;同样,6=1+2+3=4+210=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;
}




 

上一篇:java前后端分离是否会成为趋势


下一篇:好程序员web前端培训分享如何讲清楚Promise?