detect

一句话总结杜教筛： 综合起来，杜教筛算法可以概况为：用狄利克雷卷积构造递推式，编程时用整除分块和线性筛优化，算法复杂度达到了O(n23)O(n^{\frac{2}{3}})O(n32​)。 只要给你的函数的卷积和函数可以方便的表示出来且好计算，那么杜教筛就有用武之地。 现在开始推倒杜教筛的过程 要求函数：f(x)f(x)f(x)的前缀和 s(x)s(x)s(x) 我们设两个函数为h(x)g(x)h(x) g(x)h(x)g(x)有h(x)=f(x)∗g(x)h(x)=f(x)*g(x)h(x)=f(x)∗g(x) ∑i=1nh(x)=∑i=1n∑j∣if(ij)g(j)\sum_{i=1}^nh(x)=\sum_{i=1}^n\sum_{j|i}f(\frac{i}{j})g(j) i=1∑n​h(x)=i=1∑n​j∣i∑​f(ji​)g(j) ∑i=1nh(x)=∑j=1n∑j∣inf(ij)g(j)\sum_{i=1}^nh(x)=\sum_{j=1}^n\sum_{j|i}^nf(\frac{i}{j})g(j) i=1∑n​h(x)=j=1∑n​j∣i∑n​f(ji​)g ...

Ac自动机 它由三个部分组成： 建立字典树 找出字典树上每个点的fail 跑匹配串来搞事情 建立字典树 就是表面意思，我们把所有待匹配串来建一个字典树 寻找fail指针 这个和kmp类似，如果一段前缀和另外一段后缀重合，那么这段区间就不需要再来一个个匹配。 我们考虑用bfs来求fail指针（最大重合部分的指针）： 对于一个点u，现在目标求所有u的子节点的fail（注意顺带搞一下空节点，对后来的模式串匹配过程有帮助） 若存在u的连边v。 那么v的fail即为u的fail的v’儿子 若不存在u的连边v。 既然不存在这个点，那我们手动添加虚点，保证原来的字典树上所有点都有所有的儿子，这样将情况转回到1去。 匹配 我们沿着字典树跑一边匹配串 每跑一个点，都沿着fail把所有可以fail的跳一遍，这些点都是可到的。 然后接着一直跑到底。（注意如果跑出字典树的边界也无妨，因为虚点的连边又将其引回字典树上） 板题1 AC自动机（简单版） 此题只要求出不出现，于是查询时不断打标记，保证同一个点不走两遍即可 code 12345678910111213141516 ...

无源汇有上下界可行流 我们先强行给每条边把底线塞满，但是这必然导致出入流不等，现在我们要寻找一种流法将这差值补满。 新建源点和汇点，原图上连r−lr-lr−l的流量，每个点多出或少的流量从源点接入或接出到汇点。再从源点到汇点跑网络流最大流，如果能做到出流等于入流，那么说明可以构造出一种流法补全原来出入流不对等的方案。 有源汇有上下界可行流 区别仅是出点和入点这两个点不用满足出入流平衡，那么从汇点连无线流量到源点（不是上面定义的超级源汇点），即可。 有源汇有上下界最大流 首先跑一遍有源汇有上下界可行流，然后关注残余网络，s->t图中剩下的流量是我们可以人为安排的，所以再从原来的源点到汇点来一次的最大流即是答案。 由于S没有入边，而T没有出边，因此增广路不会经过S,T也就不会导致约束条件失效（即始终满足流量平衡）。 （最后答案由两部分构成，之前的可行流flow1，和之后的增广流flow2的和。注意到第一次求可行流时，已经有了一条s->t的流量为flow1的边，所以直接再自从s->t跑一次最大流就是flow1+flow2） 1234567891011121314151617 ...

前置知识：FMT 或卷积 FMT FMT(x)=∑i∣xxiFMT(x)=\sum_{i|x}x_i FMT(x)=i∣x∑​xi​ 123void FMT(int *A){ for(int i=0;i<=n;i++) for(int j=0;j<=up;j++) if(j&(1<<i)) (A[j]+=A[j^(1<<i)])%=mod;} IFMT FMT的逆运算。 123void IFMT(int *A){ for(int i=0;i<=n;i++) for(int j=0;j<=up;j++) if(j&(1<<i)) (A[j]-=A[j^(1<<i)])%=mod;} 或卷积 C=A∣orB −>Ci=∑j∣k==iAjBkC=A|_{or}B \ ->C_i=\sum_{j|k==i}A_jB_k C=A∣or​B −>Ci​=j∣k==i∑​Aj​Bk​ 有 FMT(C)=FMT(A)∗FMT(B)FMT(C)=FMT(A) ...

生成函数 前置知识 数学功底（包括但不限于基本的积分求导） NTT与多项式全家桶 引入 思考 有2个红球，3个黑球，5个白球（同色球完全相同），从中任 取6个球。 有多少种不同的取法？ 如果还要将取出的球排成一排，有多少种不同的排法？ 问题一的答案是多项式 F(x)=(1+x+x2)(1+x+x2+x3)(1+x+x2+x3+x4+x5)F(x)=(1+x+x^2)(1+x+x^2+x^3)(1+x+x^2+x^3+x^4+x^5)F(x)=(1+x+x2)(1+x+x2+x3)(1+x+x2+x3+x4+x5) 的[x6]F(x)[x^6]F(x)[x6]F(x) 从卷积形式思考很容易。 但是如何思考问题2？ 我们从答案考虑如果选了a,b,ca,b,ca,b,c个，那么答案为(a+b+c)!a!b!c!\frac{(a+b+c)!}{a!b!c!}a!b!c!(a+b+c)!​，那么我们对多项式分配一下得到： G(x)=(1+x+x22!)(1+x+x22!+x33!)(1+x+x22!+x33!+x44!)G(x)=(1+x+\frac{x^2}{2!})(1+ ...

Accelerating Techniques for self-Attention detect0530@gamil.com 计算量和耗时 当输入序列很长时，在key和query计算dot-product时候计算量非常的大。（瓶颈） 当input的sequence数量很大时，transformer模型中self-attention组件是最耗时的，也就是运算量的瓶颈，那么如果我们加快self-attention的运算速度，就可以加快整个模型的训练速度。 加快 Self-Attention运算的方法 Skip some calculation with human knowledge 也许不需要把attention matrix所有值都算出来。 Local Attention 举个例子，如果只有sequence相邻的部分才有作用： 相当于每次做attention只看一个小范围的区域。但是这样做的话，和CNN就没什么区别了，也就是说虽然这样可以提速，但是效果不一定会很出色。 Stride Attention 同时也可以隔固定x位置看一下。 Global Attention ...

Transformer detect0530@gmail.com Sequence to Sequence (seq2seq) 输出的长度是可变的，让机器自己判断该输出多少内容。 这种类型的模型能做非常多的事情。能在自然语言、音频、图像等领域广泛的应用。具体的例子暂且不展开。 Transformer也是一种Seq2Seq模型，但是它的结构和传统的RNN模型不同。它是基于Attention机制的，而不是RNN。 网络结构 Encoder 原始的transformer里面encoder更复杂 右边就是一个block里面的内容，实际上在encoder中种这样的block会做n次。 Decoder 一开始会用BOS作为输入，然后会产生一个输出，然后把这个输出作为下一次的输入，然后再产生一个输出，然后再把这个输出作为下一次的输入，一直这样做下去，直到产生EOS为止。 解释一下图中的Masked，实际上Masked就是在self-attention的时候，不让它看到后面的内容。因为在预测的时候，decoder产生的东西是一个一个产生的，后面的内容是不知道的，所以在训练 ...

Batch Normalization 为什么会难训练 一种可能是，不同参数的斜率差别很大，导致learning rate设小设大都不好。 比如：当x1x_1x1​和x2x_2x2​数值范围差异很大时，就会导致w1w_1w1​,w2w_2w2​出现上述情况。 Feature Normalization 对数据集的每一个维度（特征）进行Normalization。保证不同维度的原始数据不会差异数量级。 同时我们也希望对中间输出的结果进行normalization，因为输出的结果也会被当做input去处理训练新的参数。 实际上，一旦我们最数据进行了Normalization，那么这些数据接不能独立计算了，他们被耦合成了一个整体。但是如果把所有数据一下拿去训练，显存会爆。 于是我们采用batch的形式，比如一次训练64组数据，对这64组数据形象normalization处理区更新参数。 使用batch normalization适用于batch size比较大的时候，因为要算均值和标准差。 在实际中，我们还会加上一个参数γ\gammaγ和β\betaβ，来控制normalizat ...

Word Embedding detect0530@gmail.com 对word的编码是困难的，用one-hot维数太高，分类的话类别也太多，一个单词会出现的很多类中， 于是，我们希望把word project到一个空间中，类似语义的词汇在space里是接近的。且每一个特定的维度有一定的意义。 但是，我们只知道输入，不知道输出。所以我们需要一个神经网络来学习这个project的过程。 可以用auto-encoder吗？ 弄一个encoder和decoder然后输入等于输出去训练。最后把encode拿出来就可以了？ 是不行的。 比如你用one-of-N encoding来说，每一个单词都是独立的，把这样的vector做auto-encoder，没法train出一些有用的特征分布来编码。（根源在与基础的编码方式是独立无关的，同时如果用n-gram来表述一个单词，也许可以抓到一些前缀后缀字母组的含义，但是效果肯定不好，不会这么干） 我们更希望从训练文本里，结合上下文找出相似关系的word。 一些基于上述思想的方法 Count based Predict based 我们要 ...

对单词的编码 one hot （拉胯） Beyond for 1-of-N encoding 于是我们可以暴力使用feedforward network来做这件事情。用输出的分类概率来表示每个词语的slot。 但是有个问题，一个单词在不同的语境有不同的slot。 于是，我们希望模型是有记忆的，也就是可以根据上下文产生不同的output。（对同一input） 于是，这种有记忆的model被称作Recurrent Neural Network(RNN)。 当然也可以是双向的。 这样一来，产出时模型关注的范围就比较广了（单向->双向了） 。 常见的形式 输入的参数还包括三个gate，分别是input gate, forget gate, output gate。 只要forget gate的值不为0，就会不更新memory cell的值，可以记得更久。 具体的一种实现： (蓝红数字即weight和bios都是training得到的) 举例，当输入向量为[4,1,0][4,1,0][4,1,0] 将LSTM运用刚在RNN里面。 RNN遇到的一些问题 有时候 ...