生成_生成器 - CSDN
  • Generative adversarial network 据有关媒体统计:CVPR2018的论文里,有三分之一的论文与GAN有关!...生成对抗网络GAN,是当今的一大热门研究方向。在2014年,被Goodfellow大神提出来,当时的G...

    Generative adversarial network

    据有关媒体统计:CVPR2018的论文里,有三分之一的论文与GAN有关
    由此可见,GAN在视觉领域的未来多年内,将是一片沃土(CVer们是时候入门GAN了)。而发现这片矿源的就是GAN之父,Goodfellow大神。
    文末有基于keras的GAN代码,有助于理解GAN的原理


    生成对抗网络GAN,是当今的一大热门研究方向。在2014年,被Goodfellow大神提出来,当时的G神还只是蒙特利尔大学的博士生而已。
    GAN之父的主页:
    http://www.iangoodfellow.com/

    GAN的论文首次出现在NIPS2014上,论文地址如下:
    https://arxiv.org/pdf/1406.2661.pdf


    入坑GAN,首先需要理由,GAN能做什么,为什么要学GAN。
    GAN的初衷就是生成不存在于真实世界的数据,类似于使得 AI具有创造力或者想象力。应用场景如下:

    1. AI作家,AI画家等需要创造力的AI体;
    2. 将模糊图变清晰(去雨,去雾,去抖动,去马赛克等),这需要AI具有所谓的“想象力”,能脑补情节;
    3. 进行数据增强,根据已有数据生成更多新数据供以feed,可以减缓模型过拟合现象。
      以上的场景都可以找到相应的paper。而且GAN的用处也远不止此,期待我们继续挖掘,是发论文的好方向哦

    GAN的原理介绍

    这里介绍的是原生的GAN算法,虽然有一些不足,但提供了一种生成对抗性的新思路。放心,我这篇博文不会堆一大堆公式,只会提供一种理解思路。

    理解GAN的两大护法GD

    G是generator,生成器: 负责凭空捏造数据出来

    D是discriminator,判别器: 负责判断数据是不是真数据

    这样可以简单的看作是两个网络的博弈过程。在最原始的GAN论文里面,G和D都是两个多层感知机网络。首先,注意一点,GAN操作的数据不一定非得是图像数据,不过为了更方便解释,我在这里用图像数据为例解释以下GAN:
    图片名称

    稍微解释以下上图,z是随机噪声(就是随机生成的一些数,也就是GAN生成图像的源头)。D通过真图和假图的数据(相当于天然label),进行一个二分类神经网络训练(想各位必再熟悉不过了)。G根据一串随机数就可以捏造一个“假图像”出来,用这些假图去欺骗D,D负责辨别这是真图还是假图,会给出一个score。比如,G生成了一张图,在D这里得分很高,那证明G是很成功的;如果D能有效区分真假图,则G的效果还不太好,需要调整参数。GAN就是这么一个博弈的过程。


    那么,GAN是怎么训练呢
    根据GAN的训练算法,我画一张图:
    图片名称

    GAN的训练在同一轮梯度反传的过程中可以细分为2步,先训练D在训练G;注意不是等所有的D训练好以后,才开始训练G,因为D的训练也需要上一轮梯度反传中G的输出值作为输入。

    当训练D的时候
    ,上一轮G产生的图片,和真实图片,直接拼接在一起,作为x。然后根据,按顺序摆放0和1,假图对应0,真图对应1。然后就可以通过,x输入生成一个score(从0到1之间的数),通过score和y组成的损失函数,就可以进行梯度反传了。(我在图片上举的例子是batch = 1,len(y)=2*batch,训练时通常可以取较大的batch)

    当训练G的时候, 需要把G和D当作一个整体,我在这里取名叫做’D_on_G’。这个整体(下面简称DG系统)的输出仍然是score。输入一组随机向量,就可以在G生成一张图,通过D对生成的这张图进行打分,这就是DG系统的前向过程。score=1就是DG系统需要优化的目标,score和y=1之间的差异可以组成损失函数,然后可以反向传播梯度。注意,这里的D的参数是不可训练的。这样就能保证G的训练是符合D的打分标准的。这就好比:如果你参加考试,你别指望能改变老师的评分标准


    需要注意的是,整个GAN的整个过程都是无监督的(后面会有监督性GAN比如cGAN),怎么理解这里的无监督呢?
    这里,给的真图是没有经过人工标注的,你只知道这是真实的图片,比如全是人脸,而系统里的D并不知道来的图片是什么玩意儿,它只需要分辨真假。G也不知道自己生成的是什么玩意儿,反正就是学真图片的样子骗D。

    正由于GAN的无监督,在生成过程中,G就会按照自己的意思天马行空生成一些“诡异”的图片,可怕的是D还能给一个很高的分数。比如,生成人脸极度扭曲的图片。这就是无监督目的性不强所导致的,所以在同年的NIPS大会上,有一篇论文conditional GAN就加入了监督性进去,将可控性增强,表现效果也好很多。


    from __future__ import print_function, division
    
    from keras.datasets import mnist
    from keras.layers import Input, Dense, Reshape, Flatten, Dropout
    from keras.layers import BatchNormalization, Activation, ZeroPadding2D
    from keras.layers.advanced_activations import LeakyReLU
    from keras.layers.convolutional import UpSampling2D, Conv2D
    from keras.models import Sequential, Model
    from keras.optimizers import Adam
    
    import matplotlib.pyplot as plt
    
    import sys
    
    import numpy as np
    
    class GAN():
        def __init__(self):
            self.img_rows = 28
            self.img_cols = 28
            self.channels = 1
            self.img_shape = (self.img_rows, self.img_cols, self.channels)
            self.latent_dim = 100
    
            optimizer = Adam(0.0002, 0.5)
    
            # Build and compile the discriminator
            self.discriminator = self.build_discriminator()
            self.discriminator.compile(loss='binary_crossentropy',
                optimizer=optimizer,
                metrics=['accuracy'])
    
            # Build the generator
            self.generator = self.build_generator()
    
            # The generator takes noise as input and generates imgs
            z = Input(shape=(self.latent_dim,))
            img = self.generator(z)
    
            # For the combined model we will only train the generator
            self.discriminator.trainable = False
    
            # The discriminator takes generated images as input and determines validity
            validity = self.discriminator(img)
    
            # The combined model  (stacked generator and discriminator)
            # Trains the generator to fool the discriminator
            self.combined = Model(z, validity)
            self.combined.compile(loss='binary_crossentropy', optimizer=optimizer)
    
    
        def build_generator(self):
    
            model = Sequential()
    
            model.add(Dense(256, input_dim=self.latent_dim))
            model.add(LeakyReLU(alpha=0.2))
            model.add(BatchNormalization(momentum=0.8))
            model.add(Dense(512))
            model.add(LeakyReLU(alpha=0.2))
            model.add(BatchNormalization(momentum=0.8))
            model.add(Dense(1024))
            model.add(LeakyReLU(alpha=0.2))
            model.add(BatchNormalization(momentum=0.8))
            model.add(Dense(np.prod(self.img_shape), activation='tanh'))
            model.add(Reshape(self.img_shape))
    
            model.summary()
    
            noise = Input(shape=(self.latent_dim,))
            img = model(noise)
    
            return Model(noise, img)
    
        def build_discriminator(self):
    
            model = Sequential()
    
            model.add(Flatten(input_shape=self.img_shape))
            model.add(Dense(512))
            model.add(LeakyReLU(alpha=0.2))
            model.add(Dense(256))
            model.add(LeakyReLU(alpha=0.2))
            model.add(Dense(1, activation='sigmoid'))
            model.summary()
    
            img = Input(shape=self.img_shape)
            validity = model(img)
    
            return Model(img, validity)
    
        def train(self, epochs, batch_size=128, sample_interval=50):
    
            # Load the dataset
            (X_train, _), (_, _) = mnist.load_data()
    
            # Rescale -1 to 1
            X_train = X_train / 127.5 - 1.
            X_train = np.expand_dims(X_train, axis=3)
    
            # Adversarial ground truths
            valid = np.ones((batch_size, 1))
            fake = np.zeros((batch_size, 1))
    
            for epoch in range(epochs):
    
                # ---------------------
                #  Train Discriminator
                # ---------------------
    
                # Select a random batch of images
                idx = np.random.randint(0, X_train.shape[0], batch_size)
                imgs = X_train[idx]
    
                noise = np.random.normal(0, 1, (batch_size, self.latent_dim))
    
                # Generate a batch of new images
                gen_imgs = self.generator.predict(noise)
    
                # Train the discriminator
                d_loss_real = self.discriminator.train_on_batch(imgs, valid)
                d_loss_fake = self.discriminator.train_on_batch(gen_imgs, fake)
                d_loss = 0.5 * np.add(d_loss_real, d_loss_fake)
    
                # ---------------------
                #  Train Generator
                # ---------------------
    
                noise = np.random.normal(0, 1, (batch_size, self.latent_dim))
    
                # Train the generator (to have the discriminator label samples as valid)
                g_loss = self.combined.train_on_batch(noise, valid)
    
                # Plot the progress
                print ("%d [D loss: %f, acc.: %.2f%%] [G loss: %f]" % (epoch, d_loss[0], 100*d_loss[1], g_loss))
    
                # If at save interval => save generated image samples
                if epoch % sample_interval == 0:
                    self.sample_images(epoch)
    
        def sample_images(self, epoch):
            r, c = 5, 5
            noise = np.random.normal(0, 1, (r * c, self.latent_dim))
            gen_imgs = self.generator.predict(noise)
    
            # Rescale images 0 - 1
            gen_imgs = 0.5 * gen_imgs + 0.5
    
            fig, axs = plt.subplots(r, c)
            cnt = 0
            for i in range(r):
                for j in range(c):
                    axs[i,j].imshow(gen_imgs[cnt, :,:,0], cmap='gray')
                    axs[i,j].axis('off')
                    cnt += 1
            fig.savefig("images/%d.png" % epoch)
            plt.close()
    
    
    if __name__ == '__main__':
        gan = GAN()
        gan.train(epochs=30000, batch_size=32, sample_interval=200)
    
    展开全文
  • 生成函数

    2017-10-12 23:09:12
    生成函数生成函数是组合计数中的一个重要工具,总结一下吧~定义在数学中,某个序列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-06-11 11:09:03
    http://www.logowu.com/点击打开链接http://www.55.la/ http://www.ico.la/ ico图标http://www.makepic.com/ 图片制造 打造个性签名 拒绝垃圾邮件 生成个性印章http://seal.wen.la/ 个性印章...

    http://www.zhenhaotv.com/

    http://www.logowu.com/点击打开链接

    http://www.55.la/

     http://www.ico.la/ ico图标

    http://www.makepic.com/   图片制造 打造个性签名 拒绝垃圾邮件 生成个性印章

    http://seal.wen.la/ 个性印章

    http://www.pic123.org/ 生成LOGO 和Email 图片

    http://www.gaitu.com 改图

    http://www.czxiu.com   彩字秀 在线彩字闪字 QQ表情 搞笑图片(第三版)

    http://www.ziq.com    字Q_超好玩的QQ闪字_QQ字_QQ彩字_QQ表情_QQ图片

    http://www.igogo8.com   爱狗狗吧 / 彩字闪字生成,印章名片制作,网店空间装修

    http://diy.iseeclan.com   iSee部落提供免费的一站式照片处理软件,内置免费网络相册轻松发布图片

    http://www.eoool.com   最全的邮件/QQ/MSN/BLOG图片生成器支持BLOG,SNS,IM图标生成,支持blog的相关图标生成

    http://glitter.hotfreelayouts.com   这个也不错 QQ空间英文彩字在线生成

    http://cn.hipicture.com   QQ空间相册视频在线制作

    http://www.logomaker.cn/Logo在线制作::动态logo在线制作::中文Logo在线制作

    http://www.youmade.com/font/   字体字库在线图片生成 免费字体下载前查询转换

    http://phorum.com.tw/Generator.aspx支持域名图标的生成。

    http://www.abi-station.com/tchinese自己生成漫画小图像的站 

    自动生成闪字(只可以英文):http://www.hotglitter.com/
    自动生成粉丝证及彩字:http://www.igogo8.com/
    印章:http://www.makepic.com/print.php
    香烟盒: http://tools.fodey.com/generators/cigarette_packet/generator.cig
    结业证:http://www.makepic.com/kiss/cert.php

    一个日本武士劈出你想要的字:http://tools.fodey.com/generators/animated/ninjatext.asp
    可生成头像:http://www.eoool.com/Sevice.aspx?TypeID=2
    可生成邮址:http://www.makepic.com/email.php
    身份证号及IP地址查询等:http://www.k505.com/sfzj.htm
    iGOGO8爱狗狗吧 - 粉丝身份证·个性网络身份 http://id.igogo8.com


    生成头像——这个很棒
    http://www.eoool.com/ImageDIY/DIYChooseImg.aspx?ImgSize=96x96x1


    制作印章:http://www.makepic.com/print.php

    邮址图片生成:http://www.makepic.com/email.php

    条形码生成:http://www.makepic.com/barcode.php


    邮件:http://www.eoool.com/Sevice.aspx?TypeID=1

    Kiss学堂 颁发结业证:http://www.makepic.com/kiss/cert.php

    聊天图标:http://www.eoool.com/Sevice.aspx?TypeID=2

    博客图标:http://www.eoool.com/Sevice.aspx?TypeID=3

    网络书签:http://www.eoool.com/Sevice.aspx?TypeID=5

    朋友圈:http://www.eoool.com/Sevice.aspx?TypeID=4

    按扭:http://www.eoool.com/Sevice.aspx?TypeID=11

    生成拼凑图:http://blog.outer-court.com/letters/
    英文和数字 :http://post.baidu.com/f?kz=12400307


    展开全文
  • 转载:...utm_medium=social&utm_oi=623434717970698240&from=timeline&isappinstalled=0&wechatShare=1 论文一、《Generative Advers...

    转载:https://zhuanlan.zhihu.com/p/36880287?utm_source=wechat_timeline&utm_medium=social&utm_oi=623434717970698240&from=timeline&isappinstalled=0&wechatShare=1

    论文一、《Generative Adversarial Nets》NIPS 2014

    1、模型简述

    这篇论文是最早提出 GAN 的文章,作者 Ian J. Goodfellow 提出了一种新的对抗过程来评价生成模型的效果。GAN 主要分为两部分:生成模型和判别模型。生成模型的作用是模拟真实数据的分布,判别模型的作用是判断一个样本是真实的样本还是生成的样本,GAN 的目标是训练一个生成模型完美的拟合真实数据分布使得判别模型无法区分。

    生成模型和判别模型之间的交互可以类比为这样一个场景:生成模型是一个生产假币的伪造者,他的任务就是要生成假币然后使用假币而不被发现,判别模型则是一个警察,他的任务则是识别出那些假币,两者之间的较量使得伪造者不断提升制造假币的能力,警察不断提升识别假币的能力,最终警察无法区分伪造者生产的假币和真实的货币。

    2、数学表示

    真实数据分布: x\sim p_{data}(x)

    生成模型: G(z;\theta_g) ,其中 z 是噪声输入,满足分布 z\sim p_z(z)\theta_g 是参数,最终生成的样本满足分布 p_g ,生成模型的目标是要尽量使得 p_g 拟合 p_{data}

    判别模型: D(x;\theta_{d}) ,其中 x 是输入的样本,\theta_d 是参数,最终输出 x 来自 p_{data} 而不是 p_g 的概率。

    最后的训练目标为:

    \min \limits_{G} \max \limits_{D} V(D,G)=\mathbb{E}_{x\sim p_{data}(x)}[\log D(x)] + \mathbb{E}_{z\sim p_z(z)}[\log (1-D(G(z))]

    解释一下:

    对于生成模型 G ,它希望 D 判别 真实数据x 的概率低,判别生成数据 G(z) 的概率高,所以 V(D,G) 的值小;

    对于判别模型 D ,它希望判别真实数据 x 的概率高,判别生成数据 G(z) 的概率低,所以V(D,G) 的值大。

    3、算法

    这是训练 GAN 的算法,在训练时,并不是生成模型和判别模型交替训练,而是训练 k 次判别模型同时训练1次生成模型。在训练早期,判别模型 D 能够轻松否定 G(z)D(G(z))值很小,\log (1-D(G(z))) 接近饱和,因此对于 G 而言,我们不试图优化\min \limits_G \log(1-D(G(z))) ,而是 \max \limits_G \log(D(G(z)))

    训练的最后将达到一个全局最优条件: p_g=p_{data}=0.5 ,同时若固定 GD_G^*(x) 收敛为 \frac {p_{data}(x)}{p_{data}(x)+p_g(x)}

    证明:
    若固定 G ,则训练目标为 \max \limits_{D} V(G,D)
    \begin{align} V(D,G) &= \mathbb{E}_{x\sim p_{data}(x)}[\log D(x)] + \mathbb{E}_{z\sim p_z(z)}[\log (1-D(G(z))] \\ &= \int_{x} p_{data}(x)\log(D(x))dx + \int_{z} p_z(z) \log(1-D(G(z)))dz \\ &= \int_{x} p_{data}(x)\log(D(x))dx + p_g(x) \log(1-D(G(x)))dx \end{align} \\
    对于区间 (a,b) \in \mathbb{R}^2 \backslash \{0,0\} 来说,函数 x\rightarrow a\log(x) + b\log(1-x) 的最优解在 \frac {a}{a+b} 处取得,即 D^*_{G}(x)= \frac {p_{data}(x)}{p_{data}(x)+p_g(x)}
    \begin{align} C(G) &= \max \limits_{D}V(G,D) \\ &= \mathbb{E}_{x\sim p_{data}} \log[D_G^*(x)] + \mathbb{E}_{z\sim p_z}\log[1-D_G^*(G(z))] \\ &= \mathbb{E}_{x\sim p_{data}} \log[D_G^*(x)] + \mathbb{E}_{x\sim p_g}\log[1-D_G^*(x)] \\ &= \mathbb{E}_{x\sim p_{data}} \log \frac {p_{data}(x)}{p_{data}(x)+p_g(x)} + \mathbb{E}_{x\sim p_g} \log \frac {p_g(x)}{p_{data}(x)+p_g(x)} \end{align} \\
    那么最终训练目标是最小化 C(G) ,即 \min \limits_{G}C(G) ,下证当且仅当 p_g=p_{data} ,此时最小值 C(G)=-\log4
    KL-散度:衡量两个概率分布之间的差异情况。 D(P||Q)=\sum_{x \in X}{\log \frac {P(x)}{Q(x)}}
    那么
    \begin{align} \mathbb{E}_{x\sim p_{data}} \log \frac {p_{data}(x)}{p_{data}(x)+p_g(x)} &= \int_{x} p_{data}(x) \log \frac {p_{data}(x)}{p_{data}(x)+p_g(x)} \\ &= \int_{x} p_{data}(x) \log [\frac {p_{data}(x)}{\frac {p_{data}(x)+p_g(x)}{2}} * \frac {1}{2}] \\ &= KL(p_{data}||\frac {p_{data}+p_g}{2}) + \int_{x}p_{data}(x) \log \frac {1}{2} \\ &= KL(p_{data}||\frac {p_{data}+p_g}{2}) + \log \frac {1}{2} \end{align} \\
    同理, \begin{align} \mathbb{E}_{x\sim p_g} \log \frac {p_g(x)}{p_{data}(x)+p_g(x)} = KL(p_g||\frac {p_{data}+p_g}{2}) + \log \frac {1}{2} \end{align}

    JS-散度:衡量两个概率分布之间的相似度。 JS(P||Q)=\frac {1}{2}KL(P||\frac {P+Q}{2})+\frac {1}{2}KL(Q||\frac {P+Q}{2})

    因此
    \begin{align} C(G) &=-\log4 + KL(p_{data}||\frac {p_{data}+p_g}{2})+KL(p_g||\frac {p_{data}+p_g}{2}) \\ &= -\log4+2 \cdot JS(p_{data}||p_g) \end{align} \\
    JS-散度总是大于等于0,当且仅当 P=Q 时, JS(P||Q)=0 。所以
    C(G)-(-\log4)=2 \cdot JS(p_{data}||p_g) \geq 0C(G) 最小值是 -\log4 ,当且仅当 p_{data}=p_g

     

    论文二、《GANs for Sequences of Discrete Elements with the Gumbel-softmax Distribution》 2016

    1、写作动机

    虽然 GAN 在计算机视觉领域取得巨大的成功,但对于离散型数据的序列却捉襟见肘。原因在于,从离散对象的分布中采样这一过程是不可导的,因此参数难以更新。作者认为,这一问题可以通过 Gumbel-softmax 分布来避免,Gumbel-softmax 分布是对基于 softmax 函数的多项式分布的一个连续逼近。

    Gumbel分布是一种极值型分布。举例说明,假设每次测量心率值为一个随机变量(服从某种指数型分布,如正态分布),每天测量10次并取最大的心率作为当天的心率测量值。显然,每天记录的心率值也是一个随机变量,并且它的概率分布即为 Gumbel 分布。

    2、Gumbel-softmax 分布

    对于一个 d 维向量 h 和一个 d 维 one-hot 向量 y ,softmax 函数可以参数化表示y 上的多项分布。 p 是一个 d 维向量,表示 y 上的多项分布,其中 p_i=p(y_i=1),i=1,...,d ,所以

    p=\text{softmax}(h) \tag{1} \\

    [\text{softmax}(h)]_i=\frac {\exp(h_i)}{\sum_{j=1}^{d}{\exp(h_j)}},i=1,...,d \tag{2} \\

    式(1)按照向量 p 中的概率对 y 进行多项分布的采样等价于:

    y=\text{one_hot}(\mathop{\arg\max} \limits_{i}(h_i+g_i)) \tag{3} \\

    这里的 g_i 相互独立且符合 Gumbel 分布,可以证明, \mathop{\arg\max}(h_i+g_i) 的分布等于由 softmax 函数计算的概率分布。

    但是,式(3)对向量 h 的梯度等于0,因为 \text{one_hot}(\mathop{\arg\max}(\cdot)) 操作是不可导的。作者提出了一种基于 softmax 转换的可微函数来逼近式(3):

    y=\text{softmax}(\frac {1}{\tau (h+g)}) \tag{4} \\

    这里的 \tau 是一个控制 softmax 函数 soft 程度的参数,当 \tau\rightarrow0 ,式(4)和式(3)生成的样本接近一样,当 \tau\rightarrow \infty ,式(4)生成的样本满足均匀分布,当 \tau 大于0且有限时,式(4)生成的样本比较平滑而且对 h 可导。因此,这里的式(4)所代表的的概率分布就称为 Gumbel-softmax 分布,GAN 在离散型数据上的训练可通过式(4)进行, \tau 最开始的值较大,慢慢接近于0 。

    3、模型算法


    原始的生成模型是对隐藏状态 h_i 做 softmax 操作取最大值对应的单词,但因为从 softmax 分布采样输出这一过程是不可导的,所以训练中对隐藏状态 h_i 使用 Gumbel-softmax 分布进行采样输出,最终,生成模型和判别模型的参数都可以通过基于梯度的算法进行更新。

     

    论文三、《Generating Text via Adversarial Training》NIPS 2016 Workshop

    1、写作动机

    本篇论文同样是为了解决 GAN 模型中离散输出的问题。作者以 LSTM 作为 GAN 的生成器,以 CNN 作为 GAN 的判别器,并使用光滑近似(smooth approximation)的思想逼近生成器 LSTM 的输出,从而解决离散导致的梯度不可导问题。与原始 GAN 模型的目标函数不同,作者的优化函数采用的是 feature matching 的方法,并使用了多种训练手段来改善 GAN 模型的收敛性。

    2、TextGAN 模型定义

    语料集: S=\{s_1, \cdots ,s_n \}s_i 表示第 i个句子,n 表示句子个数。

    句子: s=\{w^t\}_{t=1}^mw^t 表示句子的第 t 个单词。每一个单词 w^t 都映射为一个 k 维词向量 x_t=W_e[w^t] ,其中 W_e \in \mathbb{R}^{k\times V} 是在训练过程中逐渐学习的词嵌入矩阵, V 是词典的大小,符号 [v] 表示单词 v 在词典中对应的索引值。

    CNN discriminator:

    一个长度为 T (长度不足则补齐)的句子可以表示成一个矩阵 X \in \mathbb{R}^{k\times T} ,它的每一列由句子中单词的词向量组成,例如第 t 列是单词 x_t 的词向量。

    抽取句子的一个特征需要对句子进行一次卷积操作和池化操作。

    卷积核 filter: W_c\in \mathbb{R}^{k\times h} ,对句子中 h 大小窗口内的连续单词做卷积: c=f(X * W_c +b),其中 f(\cdot) 是一个非线性激活函数, * 是卷积操作,最终得到一个 feature map c ,然后对 feature map 做最大池化操作, \hat{c}=\max\{c\} 作为这次操作的最终特征。

    最大池化的目的是为了获取最重要的特征(对应重要的单词位置),过滤掉信息量少的单词。

    在实验中,作者使用了多个卷积核 filter 以及多种窗口大小 h 。每一个卷积核都可以看做是一个语言特征的提取器,它能够识别提取 h-gram 的特征。假设我们有 m 种窗口大小, d 个卷积核,最终我们可以得到一个 md 维的特征。在这个 m*d 维的特征之上,应用一个 softmax 层映射为输出 D(X)\in [0,1] ,表示句子 X 来自真实数据的概率。

    LSTM generator:

    生成器将一个输入噪声 z 映射为一个句子 \tilde{s} 。生成概率为:

    p(\tilde{s}|z)=p(w^1|z)\prod_{t=2}^{T}p(w^t|w^{<t},z) \\

    p(w^1|z)=\arg\max(Vh_1) \\

    h_1=\tanh(Cz) \\

    之后的所有单词则按顺序使用 LSTM 计算得出,直至遇到结束标志符。

    p(w^t|w^{<t},z)=\arg\max(Vh_t) \\

    h_t=\text{LSTM}(y_{t-1},h_{t-1},z) \\

    y_{t-1}=W_e[w^{t-1}] \tag{*}\\

    需要注意的是,噪声 z 作为额外的 LSTM 输入指导句子的生成。模型框架如下:

    3、训练方法

    本篇论文的目标函数和原始 GAN 有所不同,文中采用了 feature matching 的方法 。迭代优化过程包含以下两个步骤:

    \begin{align} \text{minimizing:}&\ L_D=-\mathbb{E}_{s\sim S}\log D(s)-\mathbb{E}_{z\sim p_z(z)}\log [1-D(G(z))] \\ \text{minimizing:}&\ L_G=\text{tr}(\Sigma^{-1}_s\Sigma_r+\Sigma^{-1}_r\Sigma_s)+(\mu_s-\mu_r)^{\mathrm{T}}(\Sigma^{-1}_s+\Sigma^{-1}_r)(\mu_s-\mu_r) \\ \end{align}

    其中 \Sigma_s\Sigma_r 分别表示生成句子特征向量 f_s 和真实句子特征向量 f_r 的协方差矩阵, \mu_s\mu_r 则分别表示 f_sf_r 的平均值。 \Sigma_s , \Sigma_r , \mu_s\mu_r 都是通过经验设置。通过设置 \Sigma_s=\Sigma_r=\text{I} ,生成器 G 的优化则变成了 feature matching 方法。第二个损失 L_G 是两个多元正态分布 N(\mu_r,\Sigma_r)N(\mu_s,\Sigma_s) JS-散度。论文中详细说明了这种方法好。

    因为生成器 G 包含离散变量,直接应用梯度估计的方法无法使用。基于 score function 的强化学习算法,例如 Monte Carlo 估计,可以得到离散变量梯度的无偏估计值。但是,这种方法的梯度估计值的方差会很大,因此,这里作者采用的是用 soft-argmax 函数来逼近 (*) 式:

    y_{t-1}=W_e\text{softmax}(Vh_{t-1}\odot L) \\

    这里的 L 生成器的损失,当 L\rightarrow \infty ,逼近越接近 (*) 式。

    梯度下降的优化策略往往会因为在鞍点附近徘徊而难以收敛至纳什均衡。一个好的初始化往往能加快收敛速度。本篇论文的初始化非常有意思,对于生成器,作者预训练了一个标准自编码 LSTM 模型来初始化生成器的 LSTM 参数;对于判别器,作者使用了一种 confusion 训练策略,利用原始的句子和该句子中随机交换两个词的位置后得到的新句子进行判别训练。(在初始化的过程中,运用逐点分类损失函数对判别器进行优化)。之所以进行交换操作而不进行增加/删除操作,是因为作者希望 CNN 学习到句子结构上的特征,而不是某些单词的特征,将两个单词互换位置,输入的数据信息实际上是基本相同的,大多数卷积计算最终会得出完全相同的值。这种方法能够避免生成器通过产生重复的“realistic”单词来试图获取更高分数以欺骗判别器。

    在实验中,作者交替地对生成器和判别器进行训练,每训练5次生成器就训练1次判别器,因为 LSTM 的参数比 CNN 更多,更难训练,这与原始的 GAN 训练过程相反。

     

    论文四、《Adversarial Feature Matching for Text Generation》ICML 2017

    1、写作动机

    这篇论文是论文三的续作,着重叙述对抗训练的过程。训练时的目标函数不是原始 GAN 的目标函数,而是通过 kernelized discrepancy metric 对真实句子和生成句子的隐藏特征表示进行 match 操作。这种方法可以缓解对抗训练中的模式崩溃(mode collapse)问题。

    什么是模式崩溃(mode collapse)?
    真实世界中的数据分布可能会有多个样本集中的“波峰”。例如,假设有一个数据集,其中包含澳大利亚中部爱丽丝泉(通常非常热)和南极南极(通常非常寒冷)的夏日温度读数的混合数据。数据的分布是双峰的 - 两个地区的平均温度存在峰值,两者之间存在差距。如上图。
    现在我们想训练一个产生合理温度值的 GAN。直观地说,我们希望生成器学会以几乎相等的概率产生热和冷的温度。然而,通常遇到的问题是模式崩溃,导致生成器仅从单一模式输出样本(例如,仅低温)。为什么会这样?可以考虑以下情形:
    1、生成器学习到它可以通过产生接近南极温度的值来欺骗判别器认为它正在输出实际温度。
    2、判别器通过了解所有澳大利亚温度都是真实的(不是由生成器产生的)而对生成器进行反驳,并且猜测南极温度是真实的还是虚假的,因为它们无法区分。
    3、该生成器切换模式使得产生的值接近澳大利亚的温度来欺骗判别器,放弃南极模式。
    4、判别器现在假设澳大利亚所有的温度都是假的,而南极的温度是真实的。
    5、返回到第1步。
    这种猫捉老鼠的游戏总是重复让人厌烦,生成器也从未被直接激励来覆盖这两种模式。在这种情况下,生成器在生成的样本中将表现出非常差的多样性,这限制了 GAN 的使用。

    论文同样使用 LSTM 作为生成器,CNN 作为判别器。作者还考虑了再生核希尔伯特空间(Reproducing Kernel Hilbert Space, RKHS)下基于核的矩匹配模式(kernel-based moment-matching scheme),它能够使得真实句子和生成句子的经验分布在隐藏向量空间上有匹配的矩。这种方法能够很好地缓解原始 GAN 训练中的模式崩溃问题。

    2、模型解读

    原始的 GAN 模型优化目标是:

    L_{GAN}=\mathbb{E}_{x\sim p_x}\log D(x) + \mathbb{E}_{z\sim p_z}\log [1-D(G(z))] \tag{1}\\

    在论文一中我们知道,当判别器 D 达到最优解时,这个优化目标就等于最小化 p_xp_z 的JS-散度问题。但是,在大多数情况下,式(1)在鞍点附近没有很好地解决办法,所以交替更新生成器 G 和判别器 D 是常用的选择。

    给定一个语料集 S ,与其直接优化式(1),作者采取了一种类似 feature matching 的方法。作者的目标函数是:

    \begin{align} L_{D}&=L_{GAN}-\lambda_rL_{recon}+\lambda_mL_{MMD^2} \tag{2} \\ L_G&=L_{MMD^2} \tag{3} \\ L_{GAN}&=\mathbb{E}_{s\sim S}\log D(s)+\mathbb{E}_{z\sim p_z}\log [1-\log[1-D(G(z))]] \tag{4} \\ L_{recon}&=||\hat{z}-z||^2 \tag{5} \\ \end{align}

    L_DL_G 分别是对 D(\cdot)G(\cdot) 的最大化和最小化函数。 L_{GAN} 是原始 GAN 的目标函数(1)。 L_{recon} 表示初始隐藏向量 z 和重构隐藏向量 \hat{z} 之间的欧氏距离, z 来自先验分布 p_z 。作者定义生成的句子为 \hat{s}\hat{s}\triangleq G(z)z\sim p_z(\cdot)L_{MMD^2} 表示真实句子和生成句子的特征矩阵 f\hat{f} 经验分布的 MMD 值。具体如下图所示:

    MMD:maximum mean discrepancy。最大平均差异。最先提出的时候用于双样本的检测(two-sample test)问题,用于判断两个分布p和q是否相同。它的基本假设是:如果对于所有以分布生成的样本空间为输入的函数f,如果两个分布生成的足够多的样本在f上的对应的像的均值都相等,那么那么可以认为这两个分布是同一个分布。现在一般用于度量两个分布之间的相似性。

    优化函数解读:

    对于生成器 G 来说,考虑式(3),它的目标是使得生成的句子 \hat{s} 能够尽量模仿真实句子 s ,这就需要计算特征矩阵 \hat{f}f 的经验分布之间的 MMD 值。

    对于判别器 D 来说,考虑式(2),它的目标是希望生成的特征矩阵 f\hat{f} 能够具有 discriminative,representative 以及 challenging 三种特性。这分别体现在式(2)的三部分中:i) L_{GAN} 保证了真实句子和生成句子的特征矩阵 f\hat{f} 具有 discriminative 特性;ii) L_{recon} 保证了生成句子的特征矩阵 \hat{f} 最大程度保留原始信息,即 representative 特性,也就是重构表示 \hat{z} 和初始输入 z 的欧氏距离较小;iii) L_{MMD^2} 保证判别器 D 选择最 challenging 的特征与生成器 G 进行特征匹配 (feature matching) 。

     

    论文五、《SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient》

    AAAI 2017

    1、写作动机

    GAN 在生成连续离散序列时会遇到两个问题:一是因为生成器的输出是离散的,梯度更新从判别器传到生成器比较困难;二是判别器只有当序列被完全生成后才能进行判断,但此刻指导用处已不太大,而如果生成器生成序列的同时判别器来判断,如何平衡当前序列的分数和未来序列的分数又是一个难题。在这篇论文中,作者提出了一个序列生成模型——SeqGAN ,来解决上述这两个问题。作者将生成器看作是强化学习中的 stochastic policy,这样 SeqGAN 就可以直接通过 gradient policy update 避免生成器中的可导问题。同时,判别器对整个序列的评分作为强化学习的奖励信号可以通过 Monte Carlo 搜索传递到序列生成的中间时刻。

    具体来说,作者将生成器生成序列的过程看做是一个强化学习中的序列决策过程。生成模型被看作一个 agent,目前为止已生成的序列表示当前 state,下一个要生成的单词则是采取的 action,判别模型对序列的评价分数则是返回的 reward。

    2、问题定义

    给定一个真实世界的序列数据集。

    1)训练以 \theta 为参数的生成模型 G_{\theta} ,生成序列 Y_{1:T}=(y_1,\cdots ,y_t,\cdots ,y_T),y_t \in VV 是词典。我们将这个问题建立在强化学习基础上。在时间步 t,状态 s 是当前已生成序列 (y_1,\cdots ,y_{t-1}) ,动作 a 是下一个选择的单词 y_t ,策略 policy是生成器 G_{\theta}(y_t|Y_{1:t-1}) ,当下一步动作选择之后,状态转换是确定的,即 \delta^a_{s,s'}=1 当下一个状态 s'=Y_{1:t} ,当前状态 s=Y_{1:t-1} ,动作 a=y_t ;如果下一步是其他状态 s'' ,则 \delta^a_{s,s^{''}}=0

    2)训练以 \phi 为参数的判别模型,指导生成器 G 的生成。 D_{\phi}(Y_{1:T}) 表示序列 Y_{1:T} 来自真实数据中的概率。

    如上图,左边是判别器的训练,通过输入来自真实数据的正样例和来自生成器生成的负样例从而训练,判别器由 CNN 组成;右边是生成器的训练,通过将判别器判别的概率回传给生成器从而训练,这里使用了 Monte Carlo search 和 policy gradient 方法。

    3、Policy Gradient

    生成模型(policy) G_\theta(y_t|Y_{1:t-1}) 的目标是最大化期望奖励:

    J(\theta)=\mathbb{E}[R_T|s_0,\theta]=\sum_{y_1 \in V}^{}{G_\theta(y_1|s_0)\cdot Q^{G_\theta}_{D_\phi}(s_0,y_1)} \tag{1} \\

    其中 R_T 是完全生成序列的奖励,来自判别器 D_\phiQ^{G_\theta}_{D_\phi}(s,a) 是整个序列的 action-value function,表示从状态 s 开始,依据策略 G_\theta 采取动作 a 直到结束所得到的期望累计奖励。所以,最重要就是如何计算 action-value function。

    在这篇论文中,作者将判别器 D_\phi(Y^n_{1:T}) 判断序列 Y^n_{1:T} 为真的概率作为奖励,即:

    Q^{G_\theta}_{D_\phi}(a=y_T,s=Y_{1:T-1})=D_\phi(Y_{1:T}) \tag{2} \\

    但是,前面已经说明,判别器只能当序列被完全生成之后才能返回一个奖励。因为我们在每一个时间步上,真正关心的是长期的收益,所以我们不仅应该考虑已生成序列的效果,也要考虑接下来生成的结果,这就好比在下棋时,我们会适当放弃一些眼前优势从而追求长远的胜利。因此,为了估计中间时间步上的 action-value,我们使用 Monte Carlo 搜索 和 roll-out policy G_\beta 来对剩下的 T-t 个未知单词进行采样。我们将这个 N 次 Monte Carlo 搜索过程表示为:

    \{Y^1_{1:T},\cdots,Y^N_{1:T}\}=\text{MC}^{G_\beta}(Y_{1:t};N) \tag{3}\\

    roll-out 算法是对于当前状态,从每一个可能的动作开始,之后根据给定的策略进行路径采样,根据多次采样的奖励总和来对当前状态的行动值进行估计。当当前估计基本收敛时,会根据行动值最大的原则选择动作进入下一个状态再重复上述过程。在蒙特卡洛控制中,采样的目的是估计一个完整的,最优价值函数,但是roll-out中的采样目的只是为了计算当前状态的行动值以便进入下一个状态,而且这些估计的行动值并不会被保留。在roll-out中采用的策略往往比较简单被称作 roll-out 策略 (roll-out policy)

     

    蒙特卡洛树搜索是上面提到的 roll-out 算法的拓展版,在于它会记录搜索过程中的行动值变化以便更好的采样,完整的步骤有以下四步:
    1、选择:从根节点出发,根据树策略(tree policy)选择一个叶节点
    2、拓展:有一定概率发生,从选择的叶节点中执行一个未执行过的行动来增加一个子节点
    3、模拟:从当前叶节点开始,根据 roll-out 策略执行动作直到终止时间
    4、回溯:利用本次模拟中得到的奖励和逐层更新所使用到的树内节点
    如下图所示。

    进行 N 次Monte Carlo 搜索之后,我们将得到一个 batch 为 N 的输出样例。因此,

    Q^{G_\theta}_{D_\phi}(s=Y_{1:t-1},a=y_t)=\left\{ \begin{array}{rcl} \frac {1}{N}\sum \nolimits_{n=1}^{N}{D_\phi (Y^n_{1:T}),Y^n_{1:T}\in \text{MC}^{G_\beta}(Y_{1:t};N)} & \text{for} & t<T\\ D_\phi(Y_{1:t}) & \text{for} & t=T \tag{4} \end{array} \right .

    使用判别器 D_\phi 作为奖励函数的好处在于奖励值可以动态地更新从而循环地改进生成模型的效果。论文中指出,每当我们生成许多与真实数据相像的序列,我们就要重新训练一次判别器:

    \min \limits_\phi -\mathbb{E}_{Y\sim p_{data}}(\log D_\phi (Y))-\mathbb{E}_{Y\sim G_\theta}[\log(1-D_\phi(Y))] \tag{5} \\

    每当重新训练得到新的判别器之后就可以更新生成器。文中采用的是 policy gradient 的方法,式(1)关于生成器中参数 \theta 的梯度为:

    \nabla J(\theta)=\sum \nolimits_{t=1}^{T}{\mathbb{E}_{Y_{1:t-1}\sim G_\theta}}[\sum_{y_t \in V}^{}{\nabla_\theta G_\theta (y_t|Y_{1:t-1})\cdot Q^{G_\theta}_{D_\phi}(Y_{1:t-1},y_t)}] \tag{6}\\

    之后,更新参数 \theta

    \theta\leftarrow \theta+\alpha_h \nabla_\theta J(\theta) \\

    具体推导过程可以参考论文附录。下图是整个算法:

     

    论文六、《MaskGAN: Better Text Generation via Filling in the ____》ICLR 2018

    1、写作动机

    作者认为,以往的神经文本生成模型,例如 seq2seq,是机器翻译,摘要提取的基本模型,它们通常利用 maximun likelihood 和 teacher forcing 进行训练,生成文本的质量也都通过 validation perplexity 来定义。这些训练方法对于 perplexity 的优化来说可能很合适,但却不能保证生成文本的质量足够好,因为生成文本时,历史生成单词可能在训练时没有出现过,导致误差逐渐累积,也就是常说的 exposure bias 问题。虽然之前已经有 Professor Forcing 和 Scheduled Sampling 来解决这些问题,但它们都没有针对输出明确定义一个损失函数来提高结果质量,这篇论文对此做了改变。另外,离散输出也是导致梯度不能反向传播训练的原因,作者在这篇论文中利用强化学习中的 actor-critic 算法来训练生成器,利用最大似然和随机梯度下降来训练判别器。最后,GAN 模型中的模式崩溃和训练不稳定问题在文本生成任务下也更严重。训练不稳定会随着句子的长度增加而加重。为了避免这两个问题的影响,作者选择了基于上下文环境对缺失单词进行填充的场景。

    2、模型定义

    (x_t,y_t) 表示输入输出 token 对, <m> 表示 token 遮住符号, \hat{x}_t 表示遮住的原始 token, \tilde{x}_t 表示生成的 token。

    计算被遮住的 token 需要我们的 MaskGAN 模型基于历史和将来的信息。生成器由 seq2seq 模型组成。对一个输入序列 x=(x_1,\cdots ,x_T) ,随机或者确定地生成一个二进制向量 m=(m_1,\cdots ,m_T)m_t \in \{0,1\} 。如果 m_t=0 ,则输入序列中的 x_t<m> 替换,否则不变。seq2seq 模型中的 encoder 将这个遮住部分 token 的序列编码为一个表示,记 m(x) 。在 decoder 中的时间步 t,当我们在生成被遮住的 token 时,不仅依赖于 m(x) ,也依赖到目前为止被补充的完整序列 (\hat{x}_1,\cdots ,\hat{x}_{t-1}) ,所以

    P(\hat{x}_1,\cdots , \hat{x}_T|m(x))=\prod_{t=1}^{T}P(\hat{x}_t|\hat{x}_1,\cdots ,\hat{x}_{t-1},m(x)) \\

    G(x_t) \equiv P(\hat{x}_t|\hat{x}_1,\cdots ,\hat{x}_{t-1},m(x)) \\

    判别器的模型同样也是 seq2seq 模型,它的encoder 输入是已经被生成器补充后的序列,同时还要给定被部分遮住的序列 m(x) ,decoder 在每个时间步的输出不再是一个词典上的 token 概率分布,而是一个0到1之间的概率(标量)。所以

    D_\phi (\tilde{x}_t|\tilde{x}_{0:T},m(x))=P(\tilde{x}_t=x^{real}_t|\tilde{x}_{0:T},m(x)) \\

    最后的奖励函数为:

    r_t \equiv\log D_\phi (\tilde{x}_t|\tilde{x}_{0:T},m(x)) \\

    最后一个部分则是 critic 网络,critic 网络的作用是对做出的动作估计 value function,这里表示填充后的序列总的折扣收益: R_t=\sum_{s=t}^{T}{\gamma^sr_s}\gamma 表示每一个位置上的折扣率。

    3、训练目标

    这篇论文同样是利用 policy gradient 方法对生成器的参数 \theta 进行训练。生成器优化目标则是最大化累积总奖励 R=\sum \nolimits_{t=1}^{T}{R_t} 。所以,我们通过对 \mathbb{E}_{G(\theta)}[R] 进行梯度上升操作来优化生成器的参数 \theta

    论文七、《Long Text Generation via Adversarial Training with Leaked Information》

    AAAI 2018

    1、写作动机

    作者认为,虽然之前已经有许多研究将 policy gradient 方法运用到 GAN 的文本生成任务中,也取得了一些成功,但这些方法最后返回的奖励只有当生成器完全生成序列之后才能得到,序列生成过程中缺乏一些关于序列结构的中间信息的反馈,而且,这个奖励标量没有太多关于序列语义结构方面的信息量,无法起到特别大的指导作用,这些限制了序列生成的长度(一般不大于20)。在这篇论文中,作者提出了一个 LeakGAN 模型来解决长文本生成的问题。判别器会在中间时间步泄露一些提取的特征给生成器,生成器则利用这个额外信息指导序列的生成。

    2、模型定义

    如上图,在生成器中,作者使用的是 hierarchical reinforcement learning 结构,包括 Manager 模块和 Worker 模块。Manager 模块是一个 LSTM 网络,充当中介的一个角色。在每个时间步上,它都会从判别器中接收一个特征表示(例如,CNN 中的 feature map),然后将它作为一个指导信号传递为 Worker 模块。因为判别器的中间信息在原始的 GAN 中是不应该被生成器知道的,所以作者把这个特征表示称为泄露的信息。接收到这个指导信号的 embedding 之后,Worker 模块同样也利用 LSTM 网络编码当前输入 x_t ,然后将 LSTM 的输出和收到的指导信号 embedding 连接在一起共同计算下一步的动作,即选择下一个单词。

    泄露的特征表示:

    传统的 RL 下,模型的 reward functi\ \phi=(\phi_f,\phi_l) on 一般是个黑匣子,而在这个对抗文本生成模型中,作者使用判别器 D_\phi 作为可学习的 reward function, D_\phi 可以分解为一个特征提取器 F(\cdot;\phi_f) 和一个权重为 \phi_l 的 sigmoid 分类层。数学化表示为,给定一个输入 s ,有

    D_\phi(s)=\text{sigmoid}(\phi_l^{\text{T}}F(s;\phi_f))=\text{sigmoid}(\phi_l^{\text{T}}f) \tag{1}\\

    这里的 \phi=(\phi_f,\phi_l)f=F(s;\phi_f) 是输入 s 的特征向量,也就是泄露给生成器的中间信息。从式(1)可以看出,判别器对每一时刻的状态 s 的奖励值依赖于提取出的特征 f 。也正因为这样,从判别器 D_\phi 中获得一个高奖励值的优化目标可以等价为在特征空间 F(S;\phi_f)=\{F(s;\phi)\}_{s\in S} 中找到一个高奖励值的的区域。相比于之前奖励值为标量的模型,特征向量 f 可以提供更多的指导信息给生成器。

    生成器层次结构:

    Manager:LSTM 的初始化状态为 h^M_0 ,在每个时间步 t 上,以泄露的特征向量 f_t 为输入,输出目标向量 g_t ,如下式:

    \hat{g}_t,h^M_t=M(f_t,h^M_{t-1};\theta_m) \\

    g_t=\hat{g}_t/||\hat{g}_t|| \\

    为了结合 Manager 产生的目标向量 g_t ,作者对最新的 c 个目标向量进行求和并进行权重为 W_\psi 的线性变换,得到一个 k 维的目标嵌入 w_t

    w_t=\psi(\sum_{i=1}^{c}{g_{t-i}})=W_\psi(\sum_{i=1}^{c}{g_{t-i}}) \\

    Worker:以当前单词 x_t 为输入,输出一个矩阵 O_t ,它将通过矩阵乘法和目标嵌入 w_t 连接在一起,决定下一步动作的概率分布:

    O_t,h^W_t=W(x_t,h^W_{t-1};\theta_w) \\

    G_\theta(\cdot|s_t)=\text{softmax}(O_t\cdot w_t/\alpha) \\

    3、训练生成器

    在 LeakGAN 模型中,作者对生成器中的 Manager 模块和 Worker 模块分别训练。Manager 模块的训练目标是要在判别器的特征空间中找到有利的指导方向,Worker 模块的训练目标是遵循这个方向以得到奖励。

    Manager 模块的梯度为:

    \nabla^{adv}_{\theta_m}g_t=-Q_{F}(s_t,g_t)\nabla_{\theta_m}d_{cos}(f_{t+c}-f_t,g_t(\theta_m)) \\

    其中 Q_F(s_t,g_t)=Q(F(s_t),g_t)=Q(f_t,g_t)=\mathbb{E}[r_t] ,是当前策略下的预期奖励,可以通过 Monte Carlo 搜索近似估计。 d_{cos} 表示 c 步之后特征向量的改变 f_{t+c}-f_t 和目标向量 g_t(\theta_m) 之间的余弦相似度。损失函数要求目标向量匹配特征空间的转换,同时获得更高奖励。同时,Worker 模块要最大化这个奖励,这可以通过对状态 s_{t-1} 和动作 x_t 进行采样来近似。

    \nabla_{\theta_m}\mathbb{E}_{s_{t-1}\sim G}[\sum_{x_t}^{}{r^I_tW(x_t|s_{t-1};\theta_w)}]=\mathbb{E}_{s_{t-1}\sim G,x_t\sim W(x_t|s_{t-1})}[r^I_t\nabla_{\theta_m}\log W(x_t|s_{t-1};\theta_w)] \\

    当鼓励 Worker 模块遵循 Manager 指示的方向时,Worker 的内在奖励定义为:

    r^I_t=\frac {1}{c}\sum_{i=1}^{c}{d_{cos}(f_t-f_{t-i},g_{t-i})} \\

    扫码关注一起随时随地学习!!!就在洋葱攻城狮,更多精彩,等你来!!

     

     

    展开全文
  • 生成函数(母函数) 什么是生成函数:wiki上的介绍 在数学中,某个序列(an)n∈N\large {\displaystyle (a_{n})_{n\in \mathbb {N} }}(an​)n∈N​ 的母函数(又称生成函数,英语:Generating function)是一种形式幂...

    生成函数(母函数)

    什么是生成函数:wiki上的介绍

    在数学中,某个序列(an)nN\large {\displaystyle (a_{n})_{n\in \mathbb {N} }}母函数(又称生成函数,英语:Generating function)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法

    母函数可分为很多种,包括普通母函数指数母函数L级数贝尔级数狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题,因此选用何种母函数视乎序列本身的特性和问题的类型。

    母函数,又称生成函数,是ACM竞赛中经常使用的一种解题算法,常用来解决组合方面的题目。

    生成函数的定义:g(x)=a0+a1x+a2x2+a3x3+...\large g(x)=a_0+a_1x+a_2x^2+a_3x^3+...g(x)\large g(x)是序列a0,a1,a2,...a_0,a_1,a_2,...的生成函数。

    小题


    一、

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

    我们用母函数来解决这个问题

    1个1克砝码可以看成1+x^1,1表示不取,x^1表示取一个,以下同理
    1个2克砝码可以看成1+x^2
    1个3克砝码可以看成1+x^3
    1个4克砝码可以看成1+x^4
    

    那么生成函数就是

    g(x)=(1+x1)(1+x2)(1+x3)(1+x4)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10\large g(x)=(1+x^1)(1+x^2)(1+x^3)(1+x^4)\\=1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10}

    这个函数中可以看出重量为3克的方案有两种,重量为7的方案有两种,重量为10的有1种。

    不难发现指数表示重量,系数表示方案数。


    二、

    求用1分、2分、3分的邮票贴出不同数值的方案数:
    大家把这种情况和第一种比较有何区别?第一种每种是一个,而这里每种是无限的。
    

    那么生成函数就是g(x)=(1+x+x2+x3+...)(1+x2+x4+x6+...)(1+x3+x6+x9+...)\large g(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+x^9+...)

    以展开后的x^4为例,其系数为4,即4拆分成1、2、3之和的拆分方案数为4;

    即 :4=1+1+1+1=1+1+2=1+3=2+2


    三、

    设有n个标志为1,2,…,n的网袋,第i个(i=1,2,…n)网袋里放有ni个球。不同网袋里的球是不同的,而同一网袋里的球则是没有差别的,认为是相同的。询问从中取r个球的方案数。
    

    设生成函数g(x)=(1+x1+x2+...+xn1)(1+x1+x2+...+xn2)...\large g(x)=(1+x^1+x^2+...+x^{n1})(1+x^1+x^2+...+x^{n2})...

    最后指数为r的那一项的系数就是方案数。


    总结一下,生成函数大多用来解决有限或无限物体的组合方案。

    给出通用模板,其实就是暴力拆这个函数罢了。

    #include<cstdio>
    using namespace std;
    int N,g[2][125];
    int main(){
    	while(~scanf("%d",&N)){
    		for(int i=0;i<=N;++i) g[1][i]=1,g[0][i]=0;
    		for(int i=2;i<=N;++i){
    			for(int j=0;j<=N;++j)
    			for(int k=0;k<=N-j;k+=i) g[i&1][j+k]+=g[1-(i&1)][j];
    			for(int j=0;j<=N;++j) g[1-(i&1)][j]=0;
    		}
    		printf("%d\n",g[N&1][N]);
    	}
    	return 0;
    }
    

    以上是一些基础,接下来给一道难题(反正我一点也不会,逃):BZOJ4001

    不会也没有关系,我们慢慢来。


    特殊情况

    a={1,1,1,1,...}a=\{1,1,1,1,...\}f(x)=1+x+x2+x3+...=11x\large f(x)=1+x+x^2+x^3+...=\frac{1}{1-x}

    这又是为什么呢?

    我们发现f(x)\large f(x)是一个等比数列

    又因为x(1,1)x∈(-1,1)

    所以当nn \to \infty时,1xn1x\frac{1-x^n}{1-x}中,xn0x^n \to 0,所以f(x)=1+x+x2+x3+...=11x\large f(x)=1+x+x^2+x^3+...=\frac{1}{1-x}