卡特兰数（Catalan数）学习笔记一、引入问题1由\(n\)个\(+1\)和\(n\)个\(-1\)组成的\(2n\)项序列\(a_1,a_2,\cdots,a_{2n}\)，求有多少种方案满足其部分和\(a_1+a_2+\cdots+a_k\ge0\(k=1,2,\cdots,2n)\)。分析设满足条件的方案数（即答案）为\(C_n\)，不满足条件的方案数为\(U_n\)。由\(n\)个\(+1\)和\(n\)个\(-1\)组成的序列总数为\(\dfrac{(2n)!}{n!n!}=\dbinom{2n}{n}\)那么\(C_n+U_n=\dbinom{2n}{n}\)我们只要求出\(U_
「学习笔记」字符串基础：Hash，KMP与Trie点击查看目录目录「学习笔记」字符串基础：Hash，KMP与TrieHash算法代码KMP算法前置知识：\(\text{Border}\)思路代码\(\text{KMP}\)匹配思路代码Trie数据结构01-Trie代码练习题HashBovineGenomics思路代码[TJOI2018]碱基序列思路代码[CQOI2014]通配符匹配[NOI2017]蚯蚓排队思路代码KMPSeektheName,SeektheFame思路代码[NOI2014]动物园思路代码[USACO15FEB]CensoringS思路代码[POI2006]OKR-Period
洛谷P2973[USACO10HOL]DrivingOutthePiggiesG题目描述TheCowshaveconstructedarandomizedstinkbombforthepurposeofdrivingawaythePiggies.ThePiggycivilizationconsistsofN(2ThestinkbombisdeployedinPiggycity1.Eachhour(includingthefirstone),ithasaP/Q(11,000,000;PBecauseoftherandomnatureofthestinkbomb,theCowsarewonderi
[笔记]浅谈分块0前言分块真的是一个很好的思想和数据结构。它是一种优雅的暴力。——LYM1分块入门一般来说，分块解决的是在序列上的操作问题。在某种情况下，它可以运用一些简单的操作来解决一些线段树\树状数组\树套树较为恶心的题目。用一道例题来引入吧。数列分块入门4就是要设计一个支持区间加、区间求和查询的题目。考虑（线段树）分块。先来想想最暴力的做法，查询、修改都是\(O(n)\)。整体是\(O(nm)\)。显然会炸。不妨先把序列分成\(\sqrtn\)块（实际上会多一点或少一点，但这不影响），每个块的长度为\(\sqrt{n}\)。\[\underbrace{a_1,a_2,\cdots,a_{
「题解报告」P3167[CQOI2014]通配符匹配思路*和?显然无法直接匹配，但是可以发现「通配符个数不超过\(10\)」，那么我们可以考虑分段匹配。我们首先把原字符串分成多个以一个通配符开头的字符串，如将happy*birthday?xingchen分成：happy*birthday?xingchen然后设原串有\(m\)个通配符，\(op_i\)表示分出来的第\(i\)个串前的通配符（\(0\)没有，\(1\)是?，\(2\)是*），\(len_i\)表示分出来的第\(i\)个串的长度，\(f_{i,j}\)表示分出来的第\(i\)个串的结尾能否匹配上当前查询的字符串的位置\(j\)。则
论文链接：http://proceedings.mlr.press/v80/mhamdi18a/mhamdi18a.pdfSGD存在问题数据并行的SGD梯度聚合是所有梯度的线性组合，即：\(F(G_1,...,G_n)=\sum_{i=1}^n\lambda_iG_i\)因此一个恶意的节点可以让全局模型朝着自己想的方向偏移（\(G_n\)为恶意节点的梯度）：\(G_n=\dfrac{1}{\lambda_n}(U-\sum_{i=1}^{N-1}\lambda_iG_i)\)如图所示：由此，我们需要新的梯度聚合规则（GAR）\((\alpha,f)\)-ByzatineResilientGAR
前言概率论学科定义概率与信息论在人工智能领域的应用3.1，为什么要使用概率论3.2，随机变量3.3，概率分布3.3.1，离散型变量和概率质量函数3.3.2，连续型变量和概率密度分布函数3.4，边缘概率3.5，条件概率3.5.1，条件概率的链式法则3.6，独立性和条件独立性3.7，条件概率、联合概率和边缘概率总结3.8，期望、方差和协方差3.8.1，期望期望数学定义期望应用3.8.2，方差方差数学定义总体方差数学定义3.8.3，期望与方差的运算性质3.8.4，协方差协方差数学定义3.9，常用概率分布3.9.1，伯努利分布3.9.2，Multinoulli分布3.9.3，高斯分布3.9.4，指数分
[笔记]浅谈分块0前言分块真的是一个很好的思想和数据结构。它是一种优雅的暴力。——LYM1分块入门一般来说，分块解决的是在序列上的操作问题。在某种情况下，它可以运用一些简单的操作来解决一些线段树\树状数组\树套树较为恶心的题目。用一道例题来引入吧。数列分块入门4就是要设计一个支持区间加、区间求和查询的题目。考虑（线段树）分块。先来想想最暴力的做法，查询、修改都是\(O(n)\)。整体是\(O(nm)\)。显然会炸。不妨先把序列分成\(\sqrtn\)块（实际上会多一点或少一点，但这不影响），每个块的长度为\(\sqrt{n}\)。\[\underbrace{a_1,a_2,\cdots,a_{
「题解报告」P3167[CQOI2014]通配符匹配思路*和?显然无法直接匹配，但是可以发现「通配符个数不超过\(10\)」，那么我们可以考虑分段匹配。我们首先把原字符串分成多个以一个通配符开头的字符串，如将happy*birthday?xingchen分成：happy*birthday?xingchen然后设原串有\(m\)个通配符，\(op_i\)表示分出来的第\(i\)个串前的通配符（\(0\)没有，\(1\)是?，\(2\)是*），\(len_i\)表示分出来的第\(i\)个串的长度，\(f_{i,j}\)表示分出来的第\(i\)个串的结尾能否匹配上当前查询的字符串的位置\(j\)。则
论文链接：http://proceedings.mlr.press/v80/mhamdi18a/mhamdi18a.pdfSGD存在问题数据并行的SGD梯度聚合是所有梯度的线性组合，即：\(F(G_1,...,G_n)=\sum_{i=1}^n\lambda_iG_i\)因此一个恶意的节点可以让全局模型朝着自己想的方向偏移（\(G_n\)为恶意节点的梯度）：\(G_n=\dfrac{1}{\lambda_n}(U-\sum_{i=1}^{N-1}\lambda_iG_i)\)如图所示：由此，我们需要新的梯度聚合规则（GAR）\((\alpha,f)\)-ByzatineResilientGAR
