母函数

冷不防 2022-01-15 10:11 221阅读 0赞

[为什么80%的码农都做不了架构师？>>> ][80_]  ![hot3.png][]

学了好长时间母函数了，一直没时间进行总结（忙于一些琐事），今天正好放一天假，趁空闲，对母函数做个总结，以便以后更加方便学习。

进入主题：

我对母函数的理解是，母函数，顾名思义，就是母亲，那就说明，在这个函数里面还有儿子，即子函数。说白了，就是子函数可以看作是母函数的一个子集。

而如何把这些子函数用一个母函数来表示呢？即所谓的通项公式，我个人觉的这是问题的症结之处，解决了这一症结，那么，后面的问题就容易多了。

下面我来谈谈怎么来求解母函数：

看过许多有关母函数的资料，介绍母函数的思想基本一样，我这里就通俗理解为：母函数就是一个多项式前面的系数的一个整体的集合，而子函数就是这个多项式每一项前面的系数。

那么，在碰到问题时，我们如何区分它是不是要用母函数来求解？如果用到母函数，那么需要什么样的母函数来求解？母函数是用来解决哪种类型的问题？

我想这是包括我在内的很多初次接触母函数的朋友所关心的问题。

下面我来逐一做出解答：

1.  **什么样的题型适合用母函数**

****

母函数有普通型的，也有指数型的。而我们通常在做题当中碰到的大多是普通型的，指数型的较少，主要用来求解多重排列的题型（我至今未涉及到有关指数型的母函数，希望读者提议，若以后碰到，我会加以补充），接下来，我重点说一下普通型母函数。

普通型的可以用在求解组合以及整数拆分的题型中。

例如，对于有n种物品，如果第i个物品有ki个，我们可以列式n个项相乘 (x^0+x^1+...x^k1)\*(x^0+x^1+...x^k2)\*...\*(x^0+x^1+...x^kn)，每一项表示对于第i件物品，可以有(x^0+x^1+...x^ki)中取法，【注意系数都为1，因为同种物品去i件，它的取法是1】多项相乘：因为取m件物品这件事实要分为对n种物品各取分别取1次【0~ki个】，  是组合计数的乘法原理， x^m 的系数是组合成m件物品的所有方案数.（可以参考hduacm课件）

整数拆分

![15103653_hB8t.gif][] ![15103653_uieb.gif][] 1028

`1 #include " iostream " 2   using namespace std; 3   #define N 130 4   int a[N + 1 ],b[N + 1 ]; 5   int main() 6 { 7 int n,i,j,k; 8 while (cin >> n && n != 0 ) 9 { 10 for (i = 0 ;i <= n;i ++ ) 11 {a[i] = 1 ;b[i] = 0 ;} 12 for (i = 2 ;i <= n;i ++ ) 13 { 14 for (j = 0 ;j <= n;j ++ ) 15 for (k = 0 ;k + j <= n;k += i) 16 { 17 b[k + j] += a[j]; 18 } 19 for (j = 0 ;j <= n;j ++ ) 20 { 21 a[j] = b[j];b[j] = 0 ; 22 } 23 } 24 cout << a[n] << endl; 25 } 26 return 0 ; 27 28 }`

![15103653_hB8t.gif][] ![15103653_uieb.gif][] hdu2028

`1 #include " iostream " 2   using namespace std; 3   #define N 50 4 #define M 26 5 int a[M + 1 ],b[M + 1 ],c1[N + 1 ],c2[N + 1 ]; 6 int main() 7 { 8 int n,i,j,k,sum; 9 10 cin >> n; 11 while (n -- ) 12 13 { 14 sum = 0 ; 15 16 17 for (i = 0 ;i < 26 ;i ++ ) 18 { 19 cin >> a[i]; 20 b[i] = i + 1 ; 21 } 22 memset(c1, 0 , sizeof (c1)); 23 memset(c2, 0 , sizeof (c2)); 24 c1[ 0 ] = 1 ; 25 26 for (i = 0 ;i < 26 ;i ++ ) 27 { 28 for (j = 0 ;j <= 50 ;j ++ ) 29 if (c1[j]) 30 for (k = 0 ;k + j <= 50 && k <= a[i] * b[i];k += b[i]) 31 32 { 33 c2[k + j] += c1[j]; 34 } 35 for (j = 0 ;j <= 50 ;j ++ ) 36 37 {c1[j] = c2[j];c2[j] = 0 ;} 38 } 39 for (i = 1 ;i <= 50 ;i ++ ) 40 sum += c1[i]; 41 cout << sum << endl; 42 43 } 44 return 0 ; 45 }`

**2，需要什么样的母函数来求解**

可以说不同的问题，有不同的解法，对于一道可以用母函数来求解的题而言，可能还有比母函数更简洁的方法，因人而异。不一定遇到组合类型的题型就要用组合函数，在这里我只是要通过一些例子来说明如果我们需要用母函数来求解，那么，该如何选定合适的母函数呢？

母函数的框架基本一样，

如hdu2082,

for(i=0;i<26;i++)  
        \{  
            for(j=0;j<=50;j++)  
            if(c1\[j\])  
                 for(k=0;k+j<=50&&k<=a\[i\]\*b\[i\];k+=b\[i\])//**关键**  
                    c2\[k+j\]+=c1\[j\];  
                for(j=0;j<=50;j++)  
              \{

c1\[j\]=c2\[j\];

c2\[j\]=0;

\}  
        \}

如hdu1028,

for(i=2;i<=n;i++)  
   \{  
             for(j=0;j<=n;j++)  
                for(k=0;k+j<=n;k+=i)//**关键**  
                   \{  
                     b\[k+j\]+=a\[j\];  
                   \}  
                for(j=0;j<=n;j++)  
               \{  
                   a\[j\]=b\[j\];b\[j\]=0;  
                \}  
     \}

注：根据题意，仔细分析，建立关系。

转载于:https://my.oschina.net/garyun/blog/602810

[80_]: https://my.oschina.net/u/2663968/blog/3051541
[hot3.png]: /images/20220115/2dedf68ae557439ba9ac7252d4fcae23.png
[15103653_hB8t.gif]: http://static.oschina.net/uploads/img/201601/15103653_hB8t.gif
[15103653_uieb.gif]: /images/20220115/bd71d0a5ece64ac1ba7688e7970b5f0b.png