母函数+例题（hdu 2079+hdu 2082）

待我称王封你为后i 2023-06-10 09:28 103阅读 0赞

# 母函数+例题（hdu 2079+hdu 2082） #

虽然ACM的确有点力不从心，但是还是贵在坚持，继续啃啃算法。。。。。

昨天一个下午学了学母函数，**离散数学+幂级数**，只能说nb…  
看了半天的原理，结果其实还是没看太明白，于是开始去看板子和板子题了

这是昨天看的两篇大佬的博客：  
[母函数（对于初学者的最容易理解的）][Link 1]

[母函数详解和史上最通用最高效的母函数模板][Link 2]

第二篇的板子是真的很好，看了板子于是就开始去敲板子题了（今天下午才开始做）

**例一：**

[hdu 2079：选课时间][hdu 2079]

题目大意很简单：需要修n个学分，然后每组数据会给出k组学分为v\[i\]，对应的课程数量为n\[i\]的数据  
要求最终会有多少种组合形式

也就是做这道题开始了解母函数的，结合第二篇博客的板子，自己结合自己的编码习惯敲了两份自己的板子：

**模板一：**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int a[50];     //最后结果
    int b[50];     //中间结果
    int n[50];     //每个物品的数量
    int v[50];     //每个物品对应的价值或权重
    int main(){
        
        int t;     //样例个数
        int N,K;    //N表示需要获得的学分，k表示右多少组
        scanf("%d",&t);
        while(t--){
        
            scanf("%d%d",&N,&K);
            for(int i=0;i<K;i++){
        
                scanf("%d%d",&v[i],&n[i]);
            }
            
            //初始化a
            memset(a,0,sizeof(a));
            a[0]=1;
            for(int i=0;i<K;i++){
                 //循环每个因子
                memset(b,0,sizeof(b));
                for(int j=0;j<=n[i]&&j*v[i]<=N;j++){
             //循环每个因子的每一项
                    for(int k=0;k+j*v[i]<=N;k++){
              //循环a的每一项
                        b[k+j*v[i]]+=a[k];            //把结果加到对应位
                    }
                }
                memcpy(a,b,sizeof(b));       //b赋值给a
            }
            printf("%d\n",a[N]);
        }
        return 0;
    }

![在这里插入图片描述][20191026231859325.png]

**模板二：**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int n[50];            //每个物品的数量
    int v[50];            //每个物品的价值或权重
    int a[50];            //计算结果
    int b[50];            //中间结果
    int last,last2;
    int main(){
        
        int t;           //样例个数
        int N,K;         //N表示需要获得的总学分，K表示多少组记录
        scanf("%d",&t);
        while(t--){
        
            scanf("%d%d",&N,&K);
            for(int i=0;i<K;i++){
        
                scanf("%d%d",&v[i],&n[i]);
            }
    
            //初始化a，因为有last，所以这里无需初始化其他位
            a[0]=1;
            last=0;
            for(int i=0;i<K;i++){
        
                last2=min(last+n[i]*v[i],N);            //计算下一次的last
                memset(b,0,sizeof(int)*(last2+1));      //只清空b[0...last2]
                for(int j=0;j<=n[i]&&j*v[i]<=last2;j++){
                   //这里是last2
                    for(int k=0;k<=last&&k+j*v[i]<=last2;k++){
              //一个是last，一个是last2
                        b[k+j*v[i]]+=a[k];
                    }
                }
                memcpy(a,b,sizeof(int)*(last2+1));       //b赋值给a，只赋值0...last2
                last=last2;                     //更新last
            }
            printf("%d\n",a[N]);
        }
        return 0;
    }

![在这里插入图片描述][20191026231752920.png]

这道题，可能看不出模板二比模板一要优化，但是hdu 2082就能很明显看出来

**例二：**

[hdu 2082：找单词][hdu 2082]

题目大意：也很简单，就是每个字母都对应的价值，然后每个字母的数量会给出，然后求由这些字母组成的单词会有多少种（前提：**字母的顺序不同视为同一个单词**）

开始还想复杂了，以为应该是四重循环，其实也就是稍微在上一题的基础上做个简单判断即可

以下代码没有写太多注释

**代码一：**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<cmath>
    #define ll long long
    #define pi acos(-1.0)
    using namespace std;
    int a[55];
    int b[55];
    int n[55];
    int v[55];
    int main(){
        
        int t;
        scanf("%d",&t);
        while(t--){
        
            for(int i=0;i<26;i++){
        
                scanf("%d",&n[i]);
                v[i]=i+1;
            }
            ll sum=0;
            memset(a,0,sizeof(a));
            a[0]=1;
            for(int i=0;i<26;i++){
        
                memset(b,0,sizeof(b));
                for(int j=0;j<=n[i]&&j*v[i]<=50;j++){
        
                    for(int k=0;k+j*v[i]<=50;k++){
        
                        b[k+j*v[i]]+=a[k];
                    }
                }
                memcpy(a,b,sizeof(b));
            }
            /**如果价值不大于50，则记录到结果*/
            for(int i=1;i<=50;i++){
        
                if(a[i])
                    sum+=a[i];
            }
            printf("%lld\n",sum);
        }
        return 0;
    }

![在这里插入图片描述][20191026232622838.png]

**代码二：**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define ll long long
    using namespace std;
    int a[55];
    int b[55];
    int n[55];
    int v[55];
    int last,last2;
    int main(){
        
        int t;
        scanf("%d",&t);
        while(t--){
        
            for(int i=0;i<26;i++){
        
                scanf("%d",&n[i]);
                v[i]=i+1;
            }
            a[0]=1;
            last=0;
            for(int i=0;i<26;i++){
        
                last2=min(last+n[i]*v[i],50);
                memset(b,0,sizeof(int)*(last2+1));
                for(int j=0;j<=n[i]&&j*v[i]<=last2;j++){
        
                    for(int k=0;k<=last&&k+j*v[i]<=last2;k++){
        
                        b[k+j*v[i]]+=a[k];
                    }
                }
                memcpy(a,b,sizeof(int)*(last2+1));
                last=last2;
            }
            ll sum=0;
            /**如果价值不大于50，则记录到结果*/
            for(int i=1;i<=50;i++){
        
                if(a[i])
                    sum+=a[i];
            }
            printf("%lld\n",sum);
        }
        return 0;
    }

![在这里插入图片描述][20191026232752557.png]

麻了，刚刚加了一行注释，然后时间居然又相同了。。。

这种类型的题，以后一定要首先想到母函数，母函数还是挺好用的

[Link 1]: https://blog.csdn.net/yu121380/article/details/79914529
[Link 2]: https://blog.csdn.net/xiaofei_it/article/details/17042651
[hdu 2079]: http://acm.hdu.edu.cn/showproblem.php?pid=2079
[20191026231859325.png]: /images/20230531/ebf4cd8f5aef46fe848755113f20a69d.png
[20191026231752920.png]: /images/20230531/321e7a577d07414589a9923ffea0bd37.png
[hdu 2082]: http://acm.hdu.edu.cn/showproblem.php?pid=2082
[20191026232622838.png]: /images/20230531/6a7eebab85cc4ccf9c53b4efe00f75ad.png
[20191026232752557.png]: /images/20230531/bbdf2ed4030d465c8efae31437613a76.png