精华内容
下载资源
问答
  • 生成函数

    万次阅读 多人点赞 2017-09-11 17:40:15
    生成函数生成函数是组合计数中的一个重要工具,总结一下吧~定义在数学中,某个序列an{a_n}的母函数(又称生成函数)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母...

    生成函数

    生成函数是组合计数中的一个重要工具,总结一下吧~

    定义

    在数学中,某个序列an的母函数(又称生成函数)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。
    母函数可分为很多种,包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题,因此选用何种母函数视乎序列本身的特性和问题的类型。

    类型

    普通母函数

    普通母函数就是最常见的母函数,一般来说,序列(an)的母函数是:n=0anxn
    akbkck是已知的序列,它们的普通型生成函数分别为A(x)B(x)C(x)
    (本段摘抄至离散数学教材。。)
    1) 若bk=αak,α为常数,则B(x)=αA(x)称为A(x)的常数倍。
    2) 若ck=ak+bk,则C(x)=A(x)+B(x)称为A(x)B(x)的和。
    3) 若ck=ki=0aibki,则C(x)=A(x)B(x)称为A(x)B(x)的积。
    (3)的形式就是两个多项式的相乘,使用FFT我们就可以O(nlogn)得出c序列。

    应用

    普通母函数常用于多重集组合问题。
    考虑如下的经典问题:对于非负整数x1,x2,x3,...xk,x1+x2+x3+..+xk=n有多少组非负整数解。
    我们可以为每个变量构造一个生成函数,这里每个的权值都是1,所以每个变量得到的生成函数均为1+x+x2+...+xn+...+(不选为1,选i个为xi,这里变量的取值没有限制,所以生成函数有无穷多项),变量的组合相加对应于生成函数的乘积,这样我们将这些多项式相乘得到f(x)=(1+x+x2+...+xn+..)k,将f(x)展开,则其中xn这一项的系数即为此方程解的个数。

    这里给出一个常见的化简公式:
    1+x+x2+...+xn+...=11x
    上式之所以成立,是因为我们假设1<x<1,而不关注具体x的取值,这是没有意义的。
    由上式可以很容易得出接下来的式子:
    i=0xki=11xk
    11ax=1+ax+a2x2+a3x3+....+anxn+...+...
    还有一个这样的式子:11+xx2=1(1+5+12x)(1+152x),这里化成多项式后xn这一项的系数为ni=0(5+12)i(152)ni.

    继续上面的问题,这样我们得到了f(x)=(1x)k,使用广义二项式定理展开得到

    f(x)=(1x)k=n=0(n+k1k1)xn

    这里可以看出xn项的系数为(n+k1k1),这与我们用插板法得到的结论是相同的。

    上述例子给出了使用普通母函数来解决组合问题的一个常见思路,为每个数构造一个生成函数,组合得到n的方案数即为xn这一项的系数。
    如果没办法像上面的例子一样通过公式化简怎么办?那么我们可以考虑使用背包dp来计数。

    整数划分问题

    说到普通母函数,不得不提另外一个经典的问题:整数划分问题。
    问题如下:使用正整数相加组合成n的方案有多少种。
    比如4有以下几种:1+1+1+1, 2+2,4,1+3,1+1+2。

    初看这个问题不是很简单嘛:dp[i][j]表示使用不大于j的正整数来组成i的方案数,那么dp[i][j]=dp[ij][j]+dp[i][j1],如果j>i,那么dp[i][j]=dp[i][i]
    如果需要求1到n(n<=1e5)内每个数呢?
    dp复杂度太高,无法承受。这里就要用到五边形数定理了~。

    五边形数:组成刚好n个五边形的点的数量称为五边形数,第n个五边形数为3n2n2,那么五边形数序列为1,5,12,22,35,51…..
    广义五边形数组成的序列是当上式中n取0,1,-1,2,-2,…x,-x…时得到的数值,即0,1,2,5,7,12,15….

    我们定义将n拆分为一些正整数的和的方案数为p(n)。
    有如下结论:
    这里写图片描述
    这里写图片描述
    欧拉函数φ(x)的展开为

    φ(x)=n=1(1xn)=k=(1)kxk(3k1)2=1+k=1(1)kxk(3k±1)2

    这里我们不必要去知道这个怎么证明得来的,只需要知道分割函数的生成函数以及五边形数定理即可~。
    有了五边形数定理,我们就可以O(nn)求出1到n内每个数的分割数了。
    如下,具体参见hdu 4651

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    const int N = 1e5 + 5, mod = 1e9 + 7;
    int f1[270], f2[270];
    LL ans[N];
    
    void upd(LL& x) {
        x %= mod;
        if (x < 0) x += mod;
    }
    void init() {
        for (int i = 1; ; i++) {
            f1[i] = (3 * i * i - i) >> 1;
            if (f1[i] > 100000) break;
            f2[i] = (3 * i * i + i) >> 1;
            if (f2[i] > 100000) break;
        }
        ans[0] = 1;
        for (int i = 1; i <= 100000; i++) {
            for (int j = 1; ; j++) {
                if (f1[j] <= i) ans[i] += j & 1 ? ans[i-f1[j]] : -ans[i-f1[j]];
                else break;
                if (f2[j] <= i) ans[i] += j & 1 ? ans[i-f2[j]] : -ans[i-f2[j]];
                else break;
            }
            upd(ans[i]);
        }
    }
    int main() {
        init();
        int t;
        scanf("%d", &t);
        while (t--) {
            int n;
            scanf("%d", &n);
            printf("%lld\n", ans[n]);
        }
        return 0;
    }

    指数型母函数

    序列(an)的指数型母函数是:n=0anxnn!
    序列an的指数型生成函数与bn的指数型生成函数相乘,得到的新序列的系数ck=ki=0(ki)aibki,只要使用FFT,我们同样可以得出两个指数型生成函数多项式的乘积。

    应用

    指数型母函数适用于解决多重集排列问题。

    这里给出指数型生成函数常见的化简公式:
    i=0xii!=ex
    1x1!+x22!...+(1)nxnn+..=ex
    所以只取偶数项的指数型生成函数为ex+ex2,只取奇数项的指数型生成函数为 exex2
    ①数列 rn的指数型生成函数为 erx=i=0(rx)ii!
    ②数列{0,1,0,-1,0,1,0,-1….}的指数型生成函数为sin(x)。
    ③数列{1,0,-1,0,1,0,-1,0….}的指数型生成函数为cos(x)。
    A=a1a2a3.an是n元集,从中可重复地选取r个元作排列,那么作成的排列数 erE(t)=ni=1xtt!展开式中xrr!的系数,式中t是ai这个元可以选取的次数。

    有了上述定理,我们就可以解决一些复杂的多重集排列问题了~
    考虑如下的一个简单问题:
    把n个彼此相异的球放到4个不同的盒子A1,A2,A3,A4中,求使得A_1A1中含有奇数个球,A_2A2含有偶数个球的不同的放球方法数g_ngn
    解:任意一种方案对应于A_1,A_2,A_3,A_4A1,A2,A3,A4的一个多重集排列.
    A1的生成函数为

    x1!+x33!+...+x2k+1(2k+1)!+...=exex2
    ;
    A2的生成函数为
    1+x22!+x44!+...+x2k(2k)!+..=ex+ex2;

    A3A4均为
    1+x1!+x22!+...+xnn!+...=ex

    所以
    E(t)=exex2ex+ex2e2x=e4t14=n=14n1tnn!

    所以gn=4n1

    除上述两种外,还存在其他类型的生成函数,但是在此就不多介绍了。
    (没出现过题目而且我不会-_-)

    下面来看一些题目吧~

    习题

    先来看个水题压压惊。。。
    hdu 2082 找单词
    传送门
    题意:给出26个字母的个数,字母c的价值为c-‘A’+1,求求能够组成的总价值小于50的单词个数(单词只与选的字母有关,与排列顺序无关)。
    分析:非常水的普通母函数,这里每个字母个数有限制,我们暴力dp算系数就可以。

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 30;
    int dp[2][55], num[N];
    
    int solve() {
        memset(dp[0], 0, sizeof(dp[0]));
        dp[0][0] = 1;
        for (int i = 1, p = 1; i <= 26; i++, p = !p) {
            memset(dp[p], 0, sizeof(dp[p]));
            for (int j = 0; j <= num[i] && j * i <= 50; j++)
                for (int k = 0; k + j * i <= 50; k++) dp[p][k + j * i] += dp[!p][k];
        }
        int ans = 0;
        for (int i = 1; i <= 50; i++) ans += dp[0][i];
        return ans;
    }
    int main() {
        int t;
        scanf("%d", &t);
        while (t--) {
            for (int i = 1; i <= 26; i++) scanf("%d", num + i);
            printf("%d\n", solve());
        }
        return 0;
    }

    poj 3734 Blocks
    传送门
    题意:N块砖排成一行,每块砖可以被涂成红、蓝、绿、黄四种颜色,求最后涂为红、绿的砖的数目均为偶数的方案数。
    分析:很水的指数型生成函数。可以知道E(t)=e2t(ex+ex2)2,化简得到第n项的系数即为4n+2n+14
    当然这题还可以矩阵快速幂。

    #include <cstdio>
    using namespace std;
    
    const int mod = 10007, inv = 2502;
    
    int qpow(int x, int n) {
        n %= mod - 1;
        int res = 1;
        while (n) {
            if (n & 1) res = res * x % mod;
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }
    int main() {
        int t;
        scanf("%d", &t);
        while (t--) {
            int n;
            scanf("%d", &n);
            printf("%d\n", (qpow(4, n) + qpow(2, n + 1)) % mod * inv % mod);
        }
        return 0;
    }

    poj 1322
    传送门
    题意:包裹里有无限个分布均匀且刚好c种颜色的巧克力,现在要依次拿n个出来放到桌子上,每次如果桌子上面有两种相同颜色的巧克力就会把这两个巧克力给吃掉,求最后桌子上面还有m个巧克力的概率。
    分析:概率dp是可行的,令dp[i][j]表示拿i个巧克力出来后桌子上面还剩j个巧克力的概率。这样复杂度就是O(NC)的,无法承受,但是注意到题目只要求输出三位小数,通过打表找规律可以发现在n大于一定数值的时候,后面的值都是与奇偶有关了,做1000次迭代就已经远超过精度要求了。

    本题当然可以直接生成函数搞:
    还剩m个巧克力,也就是说有m种颜色选了奇数次,有c-m种颜色选了偶数次。
    取n个巧克力出来刚好就对应于c种颜色的一个多重集排列。总共可能有cn个排列,现在我们只需要算出有多少种可能的排列满足上述要求即可。
    生成函数相乘得到E(t)=(ex+ex2)cm(exex2)m.如果分子当中xnn!这一项的系数为a,那么答案即为(cm)a2ccn
    这里分子为

    i=0cm(cmi)exiex(cmi)j=0m(mj)(1)mjexjex(mj)
    .
    这是两个多项式的积,数据范围很小,我们直接暴力算就可以。左右两个多项式相乘后会得到(1)mj(cmi)(mj)ex(2i+2jc)的形式,我们只需要暴力枚举i,j,然后算其对答案的贡献:(1)mj(cmi)(mj)(2i+2jcc)n
    不过本人不是很明白,为什么一定要用快速幂计算(2i+2jcc)n。用对数搞就是各种wa,1e-3的精度开long double也还是wa。。。

    #include <cstdio>
    #include <cmath>
    using namespace std;
    
    const int N = 105;
    double C[N][N], d[N<<1];
    void init() {
        for (int i = 0; i <= 100; i++) C[i][0] = C[i][i] = 1;
        for (int i = 2; i <= 100; i++) {
            for (int j = 1; j < i; j++) C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
    double qpow(double x, int n) {
        double res = 1;
        while (n) {
            if (n & 1) res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
    int main() {
        init();
        int c, n, m;
        while (scanf("%d", &c), c) {
            scanf("%d %d", &n, &m);
            if (m > c || m > n || ((n - m) & 1)) { puts("0.000"); continue; }
            double ans = 0;
            for (int i = 0; i <= m; i++) {
                int s = c - m;
                for (int j = 0; j <= s; j++) {
                    int k = 2 * (i + j) - c;
                    if ((m - i) & 1) ans -= qpow(1.0 * k / c, n) * C[m][i] * C[s][j];
                    else ans += qpow(1.0 * k / c, n) * C[m][i] * C[s][j];
                }
            }
            printf("%.3f\n", ans / qpow(2.0, c) * C[c][m]);
        }
        return 0;
    }

    codeforces 451E Devu and Flowers
    传送门
    题意:有n(n<=20)种花,每种花的数量fi(<=1e12)已知,现在要取si(si<=1e14)朵,求方案数。
    分析:数据范围明显没办法dp,但是注意到n很小。带有限制的计数问题我们都可以考虑容斥原理。
    所以我们只需要这样算即可:没有任何限制的方案数-一种限制不满足的方案数+两种限制不满足的方案数-….
    没有任何限制的方案数在最开始已经讨论过了,就是n个变量和为s的非负整数解的个数。有一些限制不满足的话,那么就说明某种花用的数量大于fi了,这样的话我们只需要令s=fi+1,将解的下界重新变为0就可以转化了相同的问题了。复杂度O(2n)

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    const int mod = 1e9 + 7, N = 25;
    LL f[N], sum, s, inv[N];
    int n;
    
    void init() {
        inv[1] = 1;
        for (int i = 2; i <= 20; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
    int C(LL n, int m) {
        if (n < m) return 0;
        if (!m || n == m) return 1;
        if (m > n - m) m = n - m;
        int res = 1;
        for (int i = 1; i <= m; i++) res = (LL)res * ((n - i + 1) % mod) % mod * inv[i] % mod;
        return res;
    }
    int dfs(int i, LL s, bool fl) {
        if (s < 0) return 0;
        if (i == n) {
            int res = C(s + n - 1, n - 1);
            return fl ? res : -res;
        }
        int ans = dfs(i + 1, s, fl);
        ans = (ans + dfs(i + 1, s - f[i] - 1, !fl)) % mod;
        return ans < 0 ? ans + mod : ans;
    }
    int main() {
        scanf("%d %I64d", &n, &s);
        init();
        for (int i = 0; i < n; i++) scanf("%I64d", f + i), sum += f[i];
        printf("%d\n", sum < s ? 0 : dfs(0, s, 1));
        return 0;
    }

    hdu 4658 Integer Partition
    传送门
    题意:求n的整数划分方案,其中没有任意一个整数出现超过k-1次。
    分析:结论题。。如果是n的整数划分方案,那么可以直接用五边形数定理O(nn)预处理。
    不过这里同样是有结论的,定义定义将n拆分为一些正整数的和且任意一种正整数的个数不能大于等于m的方案数为pp(n)。
    pp(n) = p(n) – p(n-m) – p(n-2m) + p(n-5m)+p(n-7m)-….这里也是广义五边数序列。

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    const int N = 1e5 + 5, mod = 1e9 + 7;
    int f1[270], f2[270];
    LL ans[N];
    
    void upd(LL& x) {
        x %= mod;
        if (x < 0) x += mod;
    }
    void init() {
        for (int i = 1; ; i++) {
            f1[i] = (3 * i * i - i) >> 1;
            if (f1[i] > 100000) break;
            f2[i] = (3 * i * i + i) >> 1;
            if (f2[i] > 100000) break;
        }
        ans[0] = 1;
        for (int i = 1; i <= 100000; i++) {
            for (int j = 1; ; j++) {
                if (f1[j] <= i) ans[i] += j & 1 ? ans[i-f1[j]] : -ans[i-f1[j]];
                else break;
                if (f2[j] <= i) ans[i] += j & 1 ? ans[i-f2[j]] : -ans[i-f2[j]];
                else break;
            }
            upd(ans[i]);
        }
    }
    void solve(int n, int k) {
        LL res = ans[n];
        for (int i = 1; ; i++) {
            if (f1[i] * k <= n) res += i & 1 ? -ans[n-f1[i]*k] : ans[n-f1[i]*k];
            else break;
            if (f2[i] * k <= n) res += i & 1 ? -ans[n-f2[i]*k] : ans[n-f2[i]*k];
            else break;
        }
        upd(res);
        printf("%lld\n", res);
    }
    int main() {
        init();
        int t;
        scanf("%d", &t);
        while (t--) {
            int n, k;
            scanf("%d %d", &n, &k);
            solve(n, k);
        }
        return 0;
    }

    hdu 6042 Journey with Knapsack
    传送门
    题意:一个体积为2n的背包,有n(n<=5e4)种食物,第i种食物的体积是i,数量是ai(0<=a1<a2<...<an<=2n),还有m种装备,第i种装备的体积是bi(1<=bi<=2n),求装一些食物和一件装备使得背包装满的方案数。
    分析:很明显的组合问题,我们首先考虑装食物的方案数。
    首先为每一种食物构造生成函数然后相乘得到f(z)=ni=1(1+xi+x2i+...+xaii)=ni=11xi(ai+1)1xi
    我们尝试把上述式子分解然后合并:

    f(z)=i=1n1xi(ai+1)1xi=i=12n11xij=1n1xj(aj+1)k=n+12n1xk

    之所以需要将式子分解是因为我们从最初的f(z)无法直接算系数,如果暴力dp算系数复杂度太高无法承受。
    因为我们只需要计算1到2n的系数,所以多项式合并时是在mod x2n+1意义下进行的。
    看第一个积式2ni=111xi,这个就是1到2n内每个数的整数划分方案p(n)的生成函数!
    那么我们就可以将式子变为:
    f(z)=i=02np(i)xij=1n1xj(aj+1)k=n+12n1xk

    那么我们将第一个多项式与第二积式的每一项的那个多项式合并。
    p(i)xi1xj(aj+1)合并得到p(i)xip(i)xi+j(aj+1)
    这样我们只需要从大到小更新xi(j(aj+1)<=i<=2n)的系数即可,可以知道(aj+1)j>=j2,只有O(n)项会更新第一个和式的系数,总复杂度O(nn)
    然后我们考虑与最后一项2nk=n+11xk的合并。
    mod x2n+1意义下,2nk=n+11xk=12nk=n+1xk
    那么现在我们合并得到
    f(z)=i=02np(i)xi(1j=n+12nxj)=i=1np(i)xi+i=n+12n(p(i)j=0in1p(j))xj.
    所以我们O(n)地以前缀和的方式更新系数即可。
    这样我们枚举装的装备,得到ans=mi=1p′′(2nbi)

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    const int N = 1e5 + 5, mod = 1e9 + 7;
    LL p[N];
    int dp[N];
    
    void add(int& x, int y) {
        x += y;
        if (x >= mod) x -= mod;
        else if (x < 0) x += mod;
    }
    void init() {
        int f1[270], f2[270];
        for (int i = 1; ; i++) {
            f1[i] = (3 * i * i - i) >> 1;
            if (f1[i] > 100000) break;
            f2[i] = (3 * i * i + i) >> 1;
            if (f2[i] > 100000) break;
        }
        p[0] = 1;
        for (int i = 1; i <= 100000; i++) {
            for (int j = 1; ; j++) {
                if (f1[j] <= i) p[i] += j & 1 ? p[i-f1[j]] : -p[i-f1[j]];
                else break;
                if (f2[j] <= i) p[i] += j & 1 ? p[i-f2[j]] : -p[i-f2[j]];
                else break;
            }
            if ((p[i] %= mod) < 0) p[i] += mod;
        }
    }
    int main() {
        init();
        int n, m, ca = 0;
        while (~scanf("%d %d", &n, &m)) {
            int s = n << 1;
            for (int i = 0; i <= s; i++) dp[i] = p[i];
            for (int i = 1, v; i <= n; i++) {
                scanf("%d", &v);
                LL k = (LL)(v + 1) * i;
                for (LL j = s; j >= k; j--) add(dp[j], -dp[j-k]);
            }
            int sum = dp[0];
            for (int i = 1; i <= n; i++) add(dp[i+n], -sum), add(sum, dp[i]);
            int ans = 0, v;
            while (m--) scanf("%d", &v), add(ans, dp[s-v]);
            printf("Case #%d: %d\n", ++ca, ans);
        }
        return 0;
    }

    bzoj 3771 Triple
    传送门
    题意:给n个互不相同的数ai,现在可以任选一个、两个或者三个数,需要输出这些数所有可能的和sum,以及每个sum下组成sum的方案数。
    分析:选一个数直接加上即可;
    选两个数,那么这就是一个明显的FFT了,对权值为0或者1的序列做自卷积即可,需要减去一个数选两次的情况,然后除2即可。
    选三个数,就是同样地序列做两次卷积。减掉一个数选超过一次的情况,然后除以6即可。
    构造三个01序列,分别为a[i]b[i2],c[i3],简单地容斥一下,那么选两个数的情况就是(a[i]a[i]b[i])/2,选三个数的情况就是(a[i]a[i]a[i]3a[i]b[i]+2c[i])/6
    我们只需要在DFT意义下直接算,然后将结果IDFT回来就行了。

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    const double PI = acos(-1.0);
    struct Complex {//复数结构体
        double x, y; //实部和虚部 x+yi
        Complex(double _x = 0.0, double _y = 0.0) : x(_x), y(_y) {}
        Complex operator -(const Complex &b)const { return Complex(x - b.x, y - b.y); }
        Complex operator +(const Complex &b)const { return Complex(x + b.x, y + b.y); }
        Complex operator *(const Complex &b)const { return Complex(x * b.x - y * b.y, x * b.y + y * b.x); }
    };
    //进行FFT和IFFT前的反转变换,位置i和 (i二进制反转后位置)互换,len必须取2的幂
    void change(Complex y[], int len) {
        int i, j, k;
        for (i = 1, j = len / 2; i < len - 1; i++) {
            if (i < j) swap(y[i], y[j]);//交换互为小标反转的元素,i<j保证交换一次
            //i做正常的+1,j左反转类型的+1,始终保持i和j是反转的
            k = len / 2;
            while (j >= k) j -= k, k /= 2;
            if (j < k) j += k;
        }
    }
    //做FFT,len必须为2^k形式,on==1时是DFT,on==-1时是IDFT
    void fft(Complex y[], int len, int on) {
        change(y, len);
        for (int h = 2; h <= len; h <<= 1) {
            Complex wn(cos(-on * 2 * PI / h), sin(-on * 2 * PI / h));
            for (int j = 0; j < len; j += h) {
                Complex w(1, 0);
                for (int k = j; k < j + h / 2; k++) {
                    Complex u = y[k];
                    Complex t = w * y[k + h / 2];
                    y[k] = u + t;
                    y[k + h / 2] = u - t;
                    w = w * wn;
                }
            }
        }
        if (on == -1) for (int i = 0; i < len; i++) y[i].x /= len;
    }
    
    const int N = 150003;
    Complex a[N], b[N], c[N], d[N];
    
    int main() {
        int n, m = 0, va;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &va);
            a[va] = b[va << 1] = c[va*3] = Complex(1, 0);
        }
        m = va * 3;
        int l = 1;
        while (l <= m) l <<= 1;
        fft(a, l, 1); fft(b, l, 1); fft(c, l, 1);
        for (int i = 0; i <= l; i++) {
            d[i] = d[i] + a[i];
            d[i] = d[i] + (a[i] * a[i] - b[i]) * Complex(0.5, 0);
            d[i] = d[i] + (a[i] * a[i] * a[i] - Complex(3, 0) * a[i] * b[i] + Complex(2, 0) * c[i]) * Complex(1.0 / 6, 0);
        }
        fft(d, l, -1);
        for (int i = 0; i <= l; i++) {
            int ans = (int)(d[i].x + 0.5);
            if (ans) printf("%d %d\n", i, ans);
        }
        return 0;
    }

    bzoj 3028 食物
    传送门
    题意:明明出去旅游,他带的食物和它们的限制如下:
    承德汉堡:偶数个
    可乐:0个或1个
    鸡腿:0个,1个或2个
    蜜桃多:奇数个
    鸡块:4的倍数个
    包子:0个,1个,2个或3个
    土豆片炒肉:不超过一个。
    面包:3的倍数个
    求带N个食物的方案数。
    分析:明显的生成函数,我们考虑为每一种食物建立生成函数然后相乘。

    f(n)=(1+x2+x4+..+x2k+..)(1+x)(1+x+x2)
    (1+x+x3+..+x2k+1+..)(1+x4+x8+...+x4k+...+)
    (1+x+x2+x3)(1+x)(1+x3+x6+..+x3k+..)
    =11x2(1+x)1x31xx1x211x41x41x(1x)11x3
    =x(1x)4

    这里我们可以知道1(1x)4关于第n项的系数是(n+33),乘上x之后那么答案就是(n+23)

    import java.math.BigDecimal;
    import java.math.BigInteger;
    import java.util.Scanner;
    
    public class Main {
        static Scanner in = new Scanner(System.in);
        public static void main(String[] args) {
            BigInteger s = in.nextBigInteger(), t = s.add(BigInteger.ONE);
            BigInteger L = s.multiply(t).multiply(t.add(BigInteger.ONE));
            L = L.divide(BigInteger.valueOf(6));
            System.out.println(L.mod(BigInteger.valueOf(10007)));
        }
    }

    bzoj 4772 显而易见的数论
    传送门
    题意:给定整数n(n<=2000),和一个长为k(k<=1e5)的序列ai(ai<=1e7),求n的每一种划分方案的价值之和,假设n的一种划分方案的所有整数组成的序列为p,长为m,那么n的这一种划分方案的价值为mi=1mj=i+1g(aF(p[i],p[j])%k)。这里g(n)=ni=1(i1,n)[(i,n)==1]
    输入时会给定一个整数type,当type=1,F(x,y)=1,当type=2时,F(x,y)=gcd(x,y),当type=3时,F(x,y)=xy+yx+x xor y

    分析:看完题目有一种绕地球几圈的感觉。。。不过这个题还是值得一做的。。
    这里枚举每一个划分方案显然是不现实的,我们可以计算每一对pi,pj的贡献。这样我们就可以知道每一个ai出现的次数了,那么最终ans=k1i=0cnt[i]g(a[i])。cnt[i]表示ai出现的次数。
    那么问题就转化为每两个小于n的整数x,y在所有划分方案中出现的次数了。
    如果x!=y,且x和y在一个划分方案数出现了a次和b次,那么x和y贡献的次数就是a*b次,我们可以换个角度,也就是说a和b出现的次数中每一对数(c,d)1<=c<=a,1<=d<=b)在这个划分方案都要被统计一次,两者刚好是等价的,这样我们直接枚举每一对数x,y和其出现的次数c,d,假设F(x,y)%k==s,那么cnt[s]+=xc<=nxc+yd<=np(nxcyd)p(n)表示n的划分方案的个数。
    如果x==y呢?那么我们是不能这么计算的,因为两者并不等价,如果一个划分方案中x出现了d次,那么(x,x)贡献的次数就是d(d1)2。我们计算出刚好只有dx的划分方案的个数,这个个数很容易计算->p(nxd)p(nx(d+1))
    所以问题变得清晰了,预处理p(n),gcd(x,y)、x^y以及g函数,然后计算cnt[i]即可。
    现在我们来考虑g函数的性质。
    gcd是积性函数,那么g函数也是积性函数。
    g(x)=g(a)g(b),其中(a,b)==1
    对于函数g(x),对于多素因子的合数,我们不好在线性筛时计算,所以我们可以考虑将x转化为两个互质的数的函数之积,也就是如果x=ti=1peii,那么g(x)=g(pe11)g(ti=2peii)
    对于pe这样形式的数,g(pe)就变得很容易计算了。

    g(pe)=i=1pe(i1,pe)[(i,pe)==1]=i=1pe(i1,pe)i=1pe(i1,pe)[(i,pe)>1]

    这里(pi1,pe)==1,通过反证法很容易证明得出。所以后面那一项只有pe1个数与pe不互质。
    那么我们有g(pe)=ei=0piφ(pei)pe1=(e+1)(pepe1)
    在线性筛的时候记录每一个数的最小的质因数的幂pe11,假设为q[i]。然后对于质数p,g(p)=2*p-2。
    令T = s * p,那么
    g(T)=g(i)p+ipi,g(i/q[i])g(q[i]p),g(i)g(p)if s%p==0q[s]==sif s%p==0q[s]<sif s%p!=0

    另外,g(n)=d(n)φ(n);我们可以通过线性筛d(n)φ(n)得出g(n)
    到了这里问题已经解决了~
    ps:这里s%p==0&&q[s]==s这一种情况容易忽略。。。本题还是出的挺好的。

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    const int N = 1e7, M = 2001, mod = 1e9 + 7, K = 1e5 + 1;
    int gcd[M][M], pri[N+1], a[K], cnt[K], q[N+1], g[N+1], p[M][M], type, k, n;
    bool vis[N+2];
    LL sum[M];
    
    void init() {
        for (int i = 1; i <= n; i++) {
            p[i][0] = 1;
            for (int j = 1; j <= n; j++) p[i][j] = (LL)p[i][j-1] * i % k;
        }
        for (int i = 0; i <= n; i++) gcd[i][0] = gcd[0][i] = gcd[i][i] = i, gcd[i][1] = gcd[1][i] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j < i; j++) {
                if (!gcd[i][j]) gcd[i][j] = gcd[j][i-j];
                gcd[j][i] = gcd[i][j];
            }
        }
        int f1[40], f2[40];
        for (int i = 1; i <= 37; i++) {
            f1[i] = (3 * i * i - i) >> 1;
            f2[i] = (3 * i * i + i) >> 1;
        }
        sum[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; ; j++) {
                if (f1[j] <= i) sum[i] += j & 1 ? sum[i-f1[j]] : -sum[i-f1[j]];
                else break;
                if (f2[j] <= i) sum[i] += j & 1 ? sum[i-f2[j]] : -sum[i-f2[j]];
                else break;
            }
            if ((sum[i] %= mod) < 0) sum[i] += mod;
        }
        g[1] = 1; int k = 0;
        for (int i = 2; i <= N; i++) {
            if (!vis[i]) pri[k++] = i, g[i] = 2 * i - 2, q[i] = i;
            for (int j = 0; j < k; j++) {
                int pr = pri[j], s = i * pr;
                if (s > N) break;
                vis[s] = 1;
                if (i % pr == 0) {
                    q[s] = q[i] * pr;
                    if (q[i] != i) g[s] = (LL)g[i /q[i]] * g[q[i] * pr] % mod;
                    else g[s] = ((LL)g[i] * pr + i * pr - i) % mod;
                    break;
                }
                q[s] = pr; g[s] = (LL)g[i] * g[pr] % mod;
            }
        }
    }
    int f(int i, int j) {
        if (type == 1) return k == 1 ? 0 : 1;
        if (type == 2) return gcd[i][j] % k;
        return (p[i][j] + p[j][i] + (i ^ j)) % k;
    }
    void add(int& x, int y) {
        x += y;
        if (x >= mod) x -= mod;
        else if (x < 0) x += mod;
    }
    int main() {
        scanf("%d %d %d", &type, &n, &k);
        init();
        for (int i = 0; i < k; i++) scanf("%d", a + i);
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; i + j <= n; j++) {
                int t = f(i, j);
                for (int _i = 1; _i * i + j <= n; _i++)
                    for (int _j = 1; _i * i + _j * j <= n; _j++) add(cnt[t], sum[n - _i * i - _j * j]);
            }
        for (int i = 1; i <= n; i++) {
            int t = f(i, i);
            for (int _i = 1; _i * i <= n; _i++) {
                int s = sum[n - _i * i];
                if ((_i + 1) * i <= n) add(s, -sum[n - (_i + 1) * i]);
                add(cnt[t], (LL)_i * (_i - 1) / 2 * s % mod);
            }
        }
        int ans = 0;
        for (int i = 0; i < k; i++) add(ans, (LL)g[a[i]] * cnt[i] % mod);
        printf("%d\n", ans);
        return 0;
    }
    

    hdu 6067 Big Integer
    传送门
    题意:Q 喜欢k(k<=10)进制下的大整数,这个整数不能包含0,且每个数字c出现的次数不能超过n(n<=14000)次。他有一个(k1)(n+1)的矩阵ggi,j为0代表这个他喜欢的大整数中i这个数字不能刚好出现j次。每天他的口味会变化,也就是矩阵中的某一个位置会翻转。总共有m(m<=200)天,求mi=0cnt[i] mod 786433cnt[i]表示第i天后Q喜欢的整数的个数。
    分析:首先我们可以计算出初始时Q喜欢的整数个数,这个可以通过生成函数求出,每个数i的生成函数为f(i)=nj=0gijxjj!
    那么我们只需要求k1t=1f(i)的系数即可。k比较小,这里我们可以直接NTT。
    初始的答案我们可以直接先算出来;考虑变化,对于一个翻转u、v。它只会影响到第f(u)这个多项式DFT的过程。Xk=N1n=0an(gp1N)nk。这里p是模数,N是序列长度,g是原根。一次操作只会加上或者删除1v!这一项,那么对于f(u) DFT的过程会使得X0,X1,...XN1加上或者减去1v!,1v!(gp1N)v,1v!(gp1N)2v...1v!(gp1N)(N1)v。这是一个等比数列。
    V[i]=ti=1Xi(0<=i<N),这样一次修改操作我们可以直接O(N)的完成,在V[i]中除去这一项(乘上逆元)、修改Xv,然后在给V[i]乘上去即可。为了方便计算,我们考虑记录每一项中0的个数。
    总时间复杂度O(nk2log(nk)+mnk)。做完这题,可以回顾一下FFT的原理了~

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    const int MAX = 1 << 17, mod = 786433, g = 10;
    int fac[MAX], inv[mod], invf[mod];
    
    int qpow(int x, int n) {
        int res = 1;
        while (n) {
            if (n & 1) res = (LL)res * x % mod;
            x = (LL)x * x % mod; n >>= 1;
        }
        return res;
    }
    void init() {
        fac[0] = fac[1] = inv[1] = invf[0] = invf[1] = 1;
        for (int i = 1; i < MAX; i++) fac[i] = (LL)i * fac[i - 1] % mod;
        for (int i = 2; i < mod; i++) {
            inv[i] = mod - (LL)(mod / i) * inv[mod % i] % mod;
            invf[i] = (LL)inv[i] * invf[i-1] % mod;
        }
    }
    void ntt(int* y, int len, int on) {
        for (int i = 1, j = len >> 1; i < len - 1; i++) {
            if (i < j) swap(y[i], y[j]);
            int k = len >> 1;
            while (j >= k) j -= k, k >>= 1;
            if (j < k) j += k;
        }
        for (int h = 2; h <= len; h <<= 1) {
            int wn = qpow(g, (mod - 1) / h);
            if (on == -1) wn = qpow(wn, mod - 2);
            for (int j = 0; j < len; j += h) {
                LL w = 1;
                for (int k = j; k < j + h / 2; k++) {
                    int u = y[k], t = (LL)w * y[k + h / 2] % mod;
                    y[k] = u + t >= mod ? u + t - mod : u + t;
                    y[k + h / 2] = u - t < 0 ? u - t + mod : u - t;
                    w = w * wn % mod;
                }
            }
        }
        if (on == -1) {
            LL t = qpow(len, mod - 2);
            for (int i = 0; i < len; i++) y[i] = y[i] * t % mod;
        }
    }
    const int N = 131075;
    int f[N], X[11][N], cnt[N], ans[N];
    char s[14002];
    bool mp[11][14002];
    
    void add(int& x, int y) {
        x += y;
        if (x >= mod) x -= mod;
        else if (x < 0) x += mod;
    }
    int main() {
        init();
        int t;
        scanf("%d", &t);
        while (t--) {
            int k, n, m, L;
            scanf("%d %d %d", &k, &n, &m);
            k--; L = 1;
            int mu = k * n;
            while (L <= mu) L <<= 1;
            fill(f, f + L, 1);
            for (int i = 1; i <= k; i++) {
                scanf("%s", s);
                for (int j = 0; j <= n; j++) if (s[j] == '1') X[i][j] = invf[j], mp[i][j] = 1;
                ntt(X[i], L, 1);
                for (int j = 0; j < L; j++) X[i][j] ? f[j] = (LL)f[j] * X[i][j] % mod : cnt[j]++;
            }
            for (int i = 0; i < L; i++) ans[i] = cnt[i] ? 0 : f[i];
            int q = qpow(g, (mod - 1) / L), u, v;
            while (m--) {
                scanf("%d %d", &u, &v);
                int tm = invf[v], s = qpow(q, v), i = 0;
                if (mp[u][v]) tm = mod - tm;
                mp[u][v] = !mp[u][v];
                for (int* x = X[u]; i < L; i++, tm = (LL)tm * s % mod) {
                    x[i] ? f[i] = (LL)f[i] * inv[x[i]] % mod : cnt[i]--;
                    add(x[i], tm);
                    x[i] ? f[i] = (LL)f[i] * x[i] % mod : cnt[i]++;
                    if (!cnt[i]) add(ans[i], f[i]);
                }
            }
            ntt(ans, L, -1);
            int res = 0;
            for (int i = 1; i <= mu; i++) add(res, (LL)ans[i] * fac[i] % mod);
            printf("%d\n", res);
            if (t) {
                for (int i = 1; i <= k; i++) memset(X[i], 0, L << 2), memset(mp[i], 0, (n + 1) << 2);
                memset(cnt, 0, L << 2);
            }
        }
        return 0;
    }

    CodeForces - 438E The Child and Binary Tree
    传送门
    题意:给定长为n(n<=1e5)c序列,以及m(m<=1e5),构造二叉树,每个点的权值必须是c序列中的数,而一颗二叉树的总权值为树中所有节点的权值之和,输出m个数,第i个数代表总权值为i的二叉树的个数。
    分析:做了就长姿势了。。
    首先,我们可以很容易地得出递推式,令fi表示总权值为i的二叉树的个数,那么fi=w{c1,c2,...cn}iwj=0fjfiwj
    很容易看出来后面的和式是个卷积。这里我们通过生成函数来化简求解。
    F(x)f的生成函数,g(x)=xi=0fifxi,那么fi=w{c1,c2,...cn}giw,实际上这里还是个卷积的形式。
    我们知道,如果f(x)=ni=0aixi,g(x)=ni=0bixi,那么两个生成函数的乘积f(x)g(x)中每一项xn的系数是ni=0aibni
    那么如果c序列的生成函数为C(x),这里就有F(x)=C(x)F2(x)+1。后面的+1f0
    所以我们可以得到F(x)=21+14C(x)

    那么现在到了问题的关键了,如何求F(x),我们只需要做一次多项式开根和一次多项式求逆,就可以得出f的生成函数,进而得到f序列了。
    这里就可以学会多项式求逆和多项式开根,2333。。
    还可以看看picks大牛的博客。

    这算是第一次做自己感觉高级的内容了。。哈哈,感觉挺有意思的。。

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    const int mod = 998244353, g = 3, N = 262144, inv = 499122177;
    int w[30];
    
    int qpow(int x, int n) {
        int res = 1;
        while (n) {
            if (n & 1) res = (LL)res * x % mod;
            x = (LL)x * x % mod; n >>= 1;
        }
        return res;
    }
    void ntt(int y[], int len, int on) {
        for (int i = 1, j = len >> 1; i < len - 1; i++) {
            if (i < j) swap(y[i], y[j]);
            int k = len >> 1;
            while (j >= k) j -= k, k >>= 1;
            if (j < k) j += k;
        }
        for (int h = 2, _i = 1; h <= len; h <<= 1, _i++) {
            int wn = w[_i];
            if (on == -1) wn = qpow(wn, mod - 2);
            for (int j = 0; j < len; j += h) {
                LL w = 1LL;
                for (int k = j; k < j + h / 2; k++) {
                    int u = y[k], t = w * y[k + h / 2] % mod;
                    y[k] = u + t >= mod ? u + t - mod : u + t;
                    y[k + h / 2] = u - t < 0 ? mod + u - t : u - t;
                    w = w * wn % mod;
                }
            }
        }
        if (on == -1) {
            int t = qpow(len, mod - 2);
            for (int i = 0; i < len; i++) y[i] = (LL)y[i] * t % mod;
        }
    }
    int t[N];
    void pol_inv(int* a, int* b, int n) {
        if (n == 1) { b[0] = qpow(a[0], mod - 2); return ; }
        pol_inv(a, b, n >> 1);
        memcpy(t, a, n << 2);
        memset(t + n, 0, n << 2);
        int len = 1;
        while (len <= n) len <<= 1;
        ntt(b, len, 1); ntt(t, len, 1);
        for (int i = 0; i < len; i++) t[i] = (LL)b[i] * (mod + 2 - (LL)b[i] * t[i] % mod) % mod;
        ntt(t, len, -1);
        for (int i = 0; i < n; i++) b[i] = t[i];
        memcpy(b, t, n << 2);
        memset(b + n, 0, n << 2);
    }
    int tb[N], c[N], sqlc[N], invc[N];
    void pol_sqr(int* a, int* b, int n) {
        if (n == 1) { b[0] = 1; return ; }
        pol_sqr(a, b, n >> 1);
        memset(tb, 0, n << 2);
        pol_inv(b, tb, n);
        memcpy(t, a, n << 2);
        memset(t + n, 0, n << 2);
        int len = 1;
        while (len <= n) len <<= 1;
        ntt(t, len, 1); ntt(b, len, 1); ntt(tb, len, 1);
        for (int i = 0; i < len; i++) t[i] = (LL)inv * ((LL)tb[i] * t[i] % mod + b[i]) % mod;
        ntt(t, len, -1);
        memcpy(b, t, n << 2);
        memset(b + n, 0, n << 2);
    }
    int main() {
        for (int i = 1; i <= 20; i++) w[i] = qpow(g, (mod - 1) >> i);
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 1, v; i <= n; i++) scanf("%d", &v), c[v]++;
        c[0] = 1;
        for (int i = 1; i <= m; i++) if (c[i]) c[i] = mod - 4;
        int len = 1;
        while (len <= m) len <<= 1;
        pol_sqr(c, sqlc, len);
        if (++sqlc[0] >= mod) sqlc[0] -= mod;
        pol_inv(sqlc, invc, len);
        for (int i = 1; i <= m; i++) printf("%d\n", invc[i] * 2 % mod);
        return 0;
    }
    展开全文
  • 生成函数入门及应用 生成函数

    千次阅读 2018-07-15 14:35:13
    普通型生成函数做组合问题,而指数型生成函数做排列问题。 练习题:求选n个水果的方案数。苹果和香蕉有无限个,但苹果必须成对拿,而香蕉必须五个一组地拿;橘子只有4个,梨只有一个。 设 f ( n ) f(n) f ( n ) ...

    说实话这东西至少得学一天……

    普通型生成函数 OGF

    数列f(x)=axf(x)=a_x的普通型生成函数为g(x)=i=0aixig(x)=\sum_{i=0}^\infty a_ix^i
    一般来说,f(x)f(x)是有特殊性质的。它会得到一些特殊的生成函数。在收敛意义下(假设函数会收敛)x[1,1]x\in[-1,1]时,由等比数列计算公式i=0n1a0qi=a0(1qn)1q\sum_{i=0}^{n-1}a_0q^i=\frac{a_0(1-q^n)}{1-q}, 生成函数有以下计算公式:
    i=0xi=11x\sum_{i=0}^\infty x^i=\frac{1}{1-x},即f(x)=1f(x)=1的生成函数为g(x)=11xg(x)=\frac{1}{1-x}
    i=0nCnixi=(1+x)n\sum_{i=0}^n C_n^ix^i=(1+x)^n,即f(x)=Cnxf(x)=C_n^x的生成函数。这其实是二项式定理。
    i=0Cn+i1ixi=1(1x)n\sum_{i=0}^\infty C_{n+i-1}^ix^i=\frac{1}{(1-x)^n},即f(x)=Cn+x1xf(x)=C_{n+x-1}^x的生成函数。(广义二项式定理)
    i=0(i+1)xi=1(1x)2\sum_{i=0}^\infty (i+1)x^i=\frac{1}{(1-x)^2},即f(x)=x+1f(x)=x+1的生成函数。这是上式的特殊情况。
    在第一个式子中,将xx代为其它式子,有:
    i=0xki=11xk\sum_{i=0}^\infty x^{ki}=\frac{1}{1-x^k},即f(x)=[kx]f(x)=[k|x]的生成函数。
    i=mxi=xm1x\sum_{i=m}^\infty x^i=\frac{x^m}{1-x},即f(x)=[xm]f(x)=[x\ge m]的生成函数。
    i=0aixi=11ax\sum_{i=0}^\infty a^ix^i=\frac{1}{1-ax},即f(x)=axf(x)=a^x的生成函数。
    还有一些显然的式子,如:
    i=0nxi=1xn+11x\sum_{i=0}^n x^i=\frac{1-x^{n+1}}{1-x},即f(x)=1(xn)f(x)=1(x\le n)的生成函数。
    将以上形式进行组合,还可以得到多种生成函数。得到生成函数后,从右反推到左得到原函数。
    生成函数的意义在于将复杂的组合问题转化为简单的计算问题。普通型生成函数做组合问题,而指数型生成函数做排列问题。

    练习题:求选n个水果的方案数。苹果和香蕉有无限个,但苹果必须成对拿,而香蕉必须五个一组地拿;橘子只有4个,梨只有一个。

    f(n)f(n)表示选nn个水果的方案数。将每种水果的生成函数乘起来,有
    g(x)=i=0x2ii=0x5ii=04xii=01xig(x)=\sum_{i=0}^\infty x^{2i}\sum_{i=0}^\infty x^{5i}\sum_{i=0}^4 x^i\sum_{i=0}^1 x^i
    =11x211x51x51x(1+x)=\frac{1}{1-x^2}\frac{1}{1-x^5}\frac{1-x^5}{1-x}(1+x)
    =1(1x)2=\frac{1}{(1-x)^2}
    由开篇第四个式子,得f(x)=x+1f(x)=x+1

    求斐波那契数列通项

    斐波那契数列的生成函数为g(x)=x+x2+2x3+3x4+5x5+8x6+...g(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+...
    由数列性质容易推知x2g(x)+xg(x)+x=g(x)x^2g(x)+xg(x)+x=g(x)
    整理得g(x)=x1xx2g(x)=\frac{x}{1-x-x^2}
    我们需要将生成函数还原。设g(x)=a1cx+b1dxg(x)=\frac{a}{1-cx}+\frac{b}{1-dx}
    化简解得参数,于是得到递推式。具体请读者计算。

    开篇第四个式子的解释

    upd on 2019.4.18
    广义二项式定理描述为1(1x)n=i=0(ni)xi\frac{1}{(1-x)^n}=\sum_{i=0}^\infty\binom{-n}{i}x^i
    其中(ni)=(n)!i!(ni)!=(1)n11(n1)!i!(1)n+i11(n+i1)!=(n+i1)!i!(1)i(n1)!=(1)i(n+i1i)\binom{-n}{i}=\frac{(-n)!}{i!(-n-i)!}=\frac{(-1)^{n-1}\frac{1}{(n-1)!}\infty}{i!(-1)^{n+i-1}\frac{1}{(n+i-1)!}\infty}=\frac{(n+i-1)!}{i!(-1)^i(n-1)!}=(-1)^i\binom{n+i-1}{i}
    然后再吃掉一个负号就行了。

    总之原来写的式子肯定是对的……这个是什么我就不知道了

    指数型生成函数 EGF

    函数f(x)=axf(x)=a_x的指数型生成函数为h(x)=i=0aixii!h(x)=\sum_{i=0}^\infty \frac{a_ix^i}{i!}
    由泰勒展开,新的公式是i=0xii!=ex\sum_{i=0}^\infty \frac{x^i}{i!}=e^x。同样可以通过代换xx得到很多公式变形。以下为典型变形:
    i=0x2i(2i)!=ex+ex2\sum_{i=0}^\infty \frac{x^{2i}}{(2i)!}=\frac{e^x+e^{-x}}{2}
    i=0x2i+1(2i+1)!=exex2\sum_{i=0}^\infty \frac{x^{2i+1}}{(2i+1)!}=\frac{e^x-e^{-x}}{2}
    数列{0,1,0,-1,0,1,0,-1….}的指数型生成函数为sin(x),数列{1,0,-1,0,1,0,-1,0….}的指数型生成函数为cos(x)。

    练习题:求选n个水果的方案数。苹果、香蕉、橙子、梨都有无限个,但苹果要选奇数个,香蕉要选偶数个。每个水果都不同

    因为是排列问题,所以用指数型生成函数。
    h(x)=exex2ex+ex2(ex)2h(x)=\frac{e^x-e^{-x}}{2}\frac{e^x+e^{-x}}{2}(e^x)^2
    =e4x14=\frac{e^{4x}-1}{4}
    =i=14ixii!4=\frac{\sum_{i=1}^\infty4^i\frac{x^i}{i!}}{4}
    =i=14i1xii!=\sum_{i=1}^\infty4^{i-1}\frac{x^i}{i!}
    于是f(x)=4x1f(x)=4^{x-1}

    生成函数的运算

    upd on 2019.1.28
    无论是OGF还是EGF,生成函数都可以如下计算:

    • F+GF+G意义为可能是两种情况中的一种。
    • FGFG意义为同时选择两种情况。
    • eFe^F意义为自我组合(合并)。

    练习题

    大朋友与多叉树

    叶子结点权值为11,非叶子结点权值为儿子的权值的和,且其儿子个数D\in D。求这样的根节点权值为SS的无标号且儿子形状有序的树的个数。

    FF表示根节点权值为xx的树的方案数OGF。考虑一个方案是什么,即可能是儿子数D\in D的OGF,还有可能是一个权值为11的叶子,其方案数为11dd个儿子是必须同时选择dd棵子树的,dd可能DD中的任何一个元素。由上,转移公式为F=1@1+dDFdF=1@1+\sum_{d\in D}F^d,其中1@11@1表示1x11x^1

    于是用拉格朗日反演解出FF的第SS项即可。

    城市规划

    (2018.12.5)
    nn个点的有标号的简单连通无向图的个数。n130000n\le 130000

    在本题中,“有标号简单连通无向图计数”的组合是“有标号简单无向图”,因此我们只需解决有标号简单无向图计数,然后用多项式取对数即可。
    而有标号简单无向图计数非常简单,答案就是2(n2)2^{n\choose 2}。其指数型生成函数为G(x)=i=02(i2)xii!G(x)=\sum_{i=0}^\infty2^{i\choose 2}\frac{x^i}{i!}

    展开全文
  • 生成函数题目汇总

    2020-02-27 22:48:38
    这是一篇关于生成函数题目的汇总 简单,即博主能做出来的 中等 困难 CF1010F

    这是一篇关于生成函数题目的汇总

    简单,即博主能做出来的

    中等

    困难

    CF1010F

    展开全文
  • 生成函数(母函数)

    千次阅读 多人点赞 2012-03-23 10:24:56
    生成函数,英文是Generating Function。恕本人不才,本文只介绍生成函数的其中一种用法。 生成函数是说,构造这么一个多项式函数g(x),使得x的n次方系数为f(n)。 对于母函数,我看到最多的是这样两句话: 1.“把...

    生成函数,英文是Generating Function。恕本人不才,本文只介绍生成函数的其中一种用法。

    生成函数是说,构造这么一个多项式函数g(x),使得x的n次方系数为f(n)。

    对于母函数,我看到最多的是这样两句话:

    1.“把组合问题的加法法则和幂级数的乘幂对应起来。”

    2.“把离散数列和幂级数一 一对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造。 “

    其实这两句话我也不算太懂。先放这里,说不定以后可能会慢慢理解吧。


    还是先举个大牛博客中的例子吧:

    有1克、2克、3克、4克砝码各一枚,问你能称出哪几种重量?每种重量各有几种方案?

    下面是用母函数解决这个问题的思路:

    首先,我们用X表示砝码,X的指数表示砝码的重量。那么,如果用函数表示每个砝码可以称的重量,

    1个1克的砝码可以用函数X^0 + X^1表示,

    1个2克的砝码可以用函数X^0 + X^2表示,

    依次类推。

    如果我们把上面2个多项式相乘,可以得到X^0 + X^1 + X^2 + X^3。继续把它与X^0 + X^3相乘,得到X^0 + X^1 + X^2 + 2*X^3 + X^4 + X^5 + X^6。

    聪明的你,是不是发现了什么?

    如果没有,接着把它与X^0+X^4相乘,最后得到X^0 + X^1 + X^2 + 2*X^3 + 2*X^4 + 2*X^5 + 2*X^6 + 2*X^7 + X^8 + X^9 + X^10。

    由于X的指数表示的是重量,所以,在相乘时,根据幂的运算法则(同底幂相乘,指数相加),得到的结果正是所有的方案。而且,每个X前面的系数代表它有几种方案。

    真是神奇啊。。。。

    需要注意的是,如果有2个1克的砝码,应该用X^0 + X^1 + X^2表示,而不是X^0 + 2*X^1。


    母函数还可以解决其他问题,比如,整数划分。

    整数划分是个很经典的问题,划分规则就不再细述,直接说思路。与上面的问题相比,每种砝码的个数不再是1个,而是无限个。于是,

    1克的砝码可以用X^0 + X^1 + X^2 + X^3 ……表示,

    2克的砝码可以用X^0 + X^2 + X^4 + X^6……表示,

    3克的砝码可以用X^0 + X^3 + X^6 + X^9……表示,

    依次类推。

    相乘后求出X^n的系数,就是结果。


    总而言之,解决此类问题,只要模拟好2个多项式相乘就好了。

    大概思路是开2个数组,c1[ ]保存当前得到的多项式各项系数,c2[ ]保存每次计算时的临时结果,当每次计算完毕后,把它赋给c1,然后c2清零。

    计算的时候,开3层for循环。最外层,记录它正在与第几个多项式相乘。第二层,表示c1中的每一项,第三层表示后面被乘多项式中的每一项。

    今天南阳出太阳了,祥兆啊,加油。


    附三道题目及代码:

    http://blog.csdn.net/dgq8211/article/details/7386274

    http://blog.csdn.net/dgq8211/article/details/7386443

    http://blog.csdn.net/dgq8211/article/details/7387013


    展开全文