母函数【模板】

普通母函数

1.根据题目要求得到母函数(生成函数)

2.把第一个括号的表达式的系数赋值到c1中。

3.从第二个括号开始计算每一项乘积。

4.迭代得到最终母函数结果。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

int c1[1100],c2[1100];
int A[1100];

int main()
{
    int T,N,K;
    cin >> T;
    while(T--)
    {
        cin >> N >> K;
        memset(A,0,sizeof(A));
        for(int i = 1; i <= K; ++i)
        {
            int a,b;
            cin >> a >> b;
            A[a] = b;
        }
        for(int i = 0; i <= N; ++i)
            c1[i] = c2[i] = 0;
        c1[0] = 1;
        for(int i = 1; i <= K; ++i) //第i项表达式(1+x^2+...)
        {
            for(int j = 0; j <= N; ++j)
            //前面i个表达式累乘的表达式(前一表达式)里第j个变量
            {
            /*如(1+x)(1+x^2)(1+x^3),j先指示的是1和x的系数,i=2执行完之后变为(1+x+x^2+x^3)(1+x^3),这时候j应该指示的是合并后的第一个括号的四个变量的系数。*/
                for(int k = 0; j+i*k <= N && k <= A[i]; ++k)
                    c2[j+i*k] += c1[j];//c2[]保存结果
            }// k表示的是将要计算的表达式的每项。(因为第i个表达式的增量是i,所以k每次增i)。
            for(int j = 0; j <= N; ++j)
            {
                c1[j] = c2[j];//迭代
                c2[j] = 0;
            }
        }
        cout << c1[N] << endl;
    }
    return 0;
}

指数型母函数

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

double f[] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
double num[11],c1[11],c2[11];
int main()
{
    int N,M;
    while(cin >> N >> M)
    {
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        for(int i = 0; i < N; ++i)
            cin >> num[i];
        for(int i = 0; i <= num[0]; ++i)
            c1[i] = 1.0/f[i];
        for(int i = 1; i < N; ++i)
        {
            for(int j = 0; j <= M; ++j)
                for(int k = 0; k <= num[i] && (k+j)<=M; ++k)
                    c2[k+j] += (c1[j]/f[k]);
            for(int j = 0; j <= M; ++j)
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        double s = 1.0*c1[M]*f[M];
        printf("%.0lf\n",s);
    }

    return 0;
}
时间: 05-07

母函数【模板】的相关文章

组合数学 - 母函数 + 模板总结

// Memory Time // 1347K 0MS // by : Snarl_jsb // 2014-09-19-18.23 #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<vector> #include<queue> #include<stack>

hdu 2082 找单词(母函数)

找单词 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4971    Accepted Submission(s): 3537 Problem Description 假设有x1个字母A, x2个字母B,..... x26个字母Z,同时假设字母A的价值为1,字母B的价值为2,..... 字母Z的价值为26.那么,对于给定的字母,可以找

HDU1028 Ignatius and the Princess III【母函数】【完全背包】

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1028 题目大意: 给定正整数N,定义N = a[1] + a[2] + a[3] + - + a[m],a[i] > 0,1 <= m <= N. 对于给定的正整数N,问:能够找出多少种这样的等式? 思路: 对于N = 4, 4 = 4: 4 = 3 + 1: 4 = 2 + 2: 4 = 2 + 1 + 1: 4 = 1 + 1 + 1 + 1. 共有5种.N=4时,结果就是5.其实就是

【母函数】hdu1028 Ignatius and the Princess III

大意是给你1个整数n,问你能拆成多少种正整数组合.比如4有5种: 4 = 4;  4 = 3 + 1;  4 = 2 + 2;  4 = 2 + 1 + 1;  4 = 1 + 1 + 1 + 1; 然后就是母函数模板题--小于n的正整数每种都有无限多个可以取用. (1+x+x^2+...)(1+x^2+x^4+...)...(1+x^n+...) 答案就是x^n的系数. #include<cstdio> #include<cstring> using namespace std;

母函数入门+模板(转)

在数学中,某个序列的母函数(Generating function,又称生成函数)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息.使用母函数解决问题的方法称为母函数方法. 母函数可分为很多种,包括普通母函数.指数母函数.L级数.贝尔级数和狄利克雷级数.对每个序列都可以写出以上每个类型的一个母函数.构造母函数的目的一般是为了解决某个特定的问题,因此选用何种母函数视乎序列本身的特性和问题的类型. 这里先给出两句话,不懂的可以等看完这篇文章再回过头来看: 1.“把组合问题的加法法则和幂级数

HDU1398 Square Coins【母函数】

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1398 题目大意: Silverland居住的人们使用方币,这种硬币的价值都是平方数.硬币的价值分别为1分.4分.9分, -,最大为289(17^2)分.要得到10分钱,共有四种硬币组合 10个1分硬币.1个4分硬币和6个1分硬币.2个4分硬币和2个1分硬币,1个9分硬币和1个1分硬币. 现在给你一个数,问:得到这个值,共有多少种不同的硬币组合方式. 思路: 典型的母函数问题. 可列出母函数 g(x

母函数详解

母函数(Generating function)详解 在数学中,某个序列的母函数是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息.使用母函数解决问题的方法称为母函数方法. 母函数可分为很多种,包括普通母函数.指数母函数.L级数.贝尔级数和狄利克雷级数.对每个序列都可以写出以上每个类型的一个母函数.构造母函数的目的一般是为了解决某个特定的问题,因此选用何种母函数视乎序列本身的特性和问题的类型. 这里先给出两句话,不懂的可以等看完这篇文章再回过头来看: "把组合问题的加法法则和幂级数的t的

母函数细致讲解

母函数又称生成函数.定义是给出序列:a0,a1,a2,.......ak,......,那么函数G(x)=a0+a1*x+a2*x2+......ak*xk称为序列a0,a1,a2,.......ak,......的母函数(即生成函数). 例如:序列1,2,3.......n的生成函数为:G(x)=x+2x2+3x3+........nxn.点此链接:百度百科 特别的当序列为:1,1,1,1,.......1,这个生成函数为:G(x)=x+x2+x3+.......+xn=(1-xn)/(1-x

HDU 2189 悼念512汶川大地震遇难同胞——来生一起走(母函数或完全背包)

悼念512汶川大地震遇难同胞--来生一起走 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3773    Accepted Submission(s): 1913 Problem Description 妈妈你别哭泪光照亮不了我们的路让我们自己慢慢的走 妈妈我会记住你和爸爸的模样记住我们的约定来生一起走 上面这首诗节选自一位诗人纪念遇难