111
【算法小總結】母函數模板
研究以下多項式乘法：
可以看出：
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;
}
最後更新：2017-04-03 05:39:49