【總結】母函數在ACM上的應用

More details see :

http://blog.csdn.net/xiaofei_it/article/details/17042651

http://blog.sina.com.cn/s/blog_79b832820100x8pa.html

https://www.jianshu.com/p/c752969ddde1

一、普通母函數

普通母函數一般是解決類似下面這樣的問題：

給10張1元，8張2元，7張5元，要得到35元，有多少種組合？

然後還可以添加各種條件，不細說了，很模闆的一個東西

HDU1085 ↓

#include<bits/stdc++.h>
using namespace std;

const int v[] = {1,2,5};
int num[3],res[9999],tmp[9999];

int main(){
    while(cin >> num[0] >> num[1] >> num[2]){
        if(!num[0] && !num[1] && !num[2]) break;
        res[0] = 1;
        int last = 0;
        for(int i = 0;i < 3;++i){
            memset(tmp,0,sizeof tmp);
            for(int j = 0;j <= num[i];++j)
                for(int k = 0;k <= last;++k)
                    tmp[k+j*v[i]] += res[k];
            memcpy(res,tmp,sizeof tmp);
            last += num[i] * v[i];
        }
        for(int i = 0;i <= last + 1;++i) if(!res[i]){
            printf("%d\n",i);
            break;
        }
    }

    return 0;
}      

 若要改進時間效率，可以修改memset和memcpy以及for循環的終止條件。

二、指數型母函數

指數型母函數一般是解決類似下面這樣的問題：

給幾種物品，有的物品隻能取偶數個，有的可以取任意個，取出的總數必須是m，問最後取出的物品的排列方案數有多少。

對應的母函數如下

然後可以進行各種變形，最後答案就是m!除以x^m的系數。

HDU2065 ↓

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
int MOD = 100;
int myPow(ull x,ull n){
    ull res = 1;
    x %= MOD;
    while(n){
        if(n & 1) res = (res * x) % MOD;
        x = (x * x) % MOD;
        n >>= 1;
    }
    return res;
}

int T;
ull n;

int main(){
    while(cin >> T){
        if(!T) break;
        for(int cas = 1;cas <= T;++cas){
            cin >> n;
            int ans = myPow(4,n-1) + myPow(2,n-1);
            printf("Case %d: %d\n",cas,ans%100);
        }
        putchar('\n');
    }

    return 0;
}      

轉載于:https://www.cnblogs.com/doub7e/p/8547241.html