lghjl

摘要： 常见恒等式 \[\binom{n}{m} = \binom{n}{n - m} \]\[\sum_{i}\binom{n}{i} = 2^n \]\[\sum_{i=0}^{n}\binom{i}{m} = \binom{n + 1}{m + 1} \]枚举最后一个结束的位置，设为\(i+1\)，则 阅读全文

摘要： 定义： 积性函数： 若对于正整数\(a,b\)有\(\gcd(a,b)=1\)且\(f(ab)=f(a)f(b)\),则\(f\)函数为积性函数 若对于任意的正整数\(a,b\)，有\(f(ab)=f(a)f(b)\)，则\(f\)函数为完全积性函数 常见积性函数： \[\varphi(p)=\su 阅读全文

摘要： 8.6 P1377 [TJOI2011] 树的序 题解： 其实就是把二叉搜索树建出来然后先序遍历即可，因为发现，先序遍历的过程其实就相当于插入节点 考虑如何建二叉搜索树，又能发现，题目里的建树保证了权值满足二叉搜索树，下标满足堆，那不得不想到笛卡尔树了，但是笛卡尔树是下标满足二叉搜索树，权值满足堆， 阅读全文

该文被密码保护。 阅读全文

摘要： 前置知识：\(SPFA\)，网络流\(Dinic\)算法 有了网络流的基础 可以拓展到最小费用最大流了 与网络流不同 费用流中每一条边除了又一个流量\(f\)的限制，还有一个费用\(c\)（可理解为一单位流量的单价）,我们要做的就是再找出最大流量的前提下，使得花费的费用最小 回顾网络流\(Dinic 阅读全文

摘要： 符号： \(P\)概率 \(F\)事件集合 \(\Omega\)样本空间（一个随机试验的所有可能结果的集合） \(A\)事件，属于样本空间里的一个结果 \(X,Y\)随机变量 \(E\)期望 概率P 定义一个函数\(P(A)\),表示事件\(A\)发生的可能性的大小，称作概率测度 大概理解到这应该就 阅读全文

摘要： 一些约定 字符串下标从\(1\)开始。 字符串\(s\)的长度为\(n\)。 "后缀\(i\)"代指以第\(i\)个字符开头的后缀 后缀数组： 主要有两个数组:\(sa\)和\(rk\)。 其中,\(sa_i\)表示将所有后缀排序后第\(i\)小的后缀的编号； \(rk_i\)表示后缀\(i\)的排 阅读全文

摘要： 一些记号： \(|s|=len(s)\) \(t_0\)：初始状态 \(endpos(t)\)：字符串\(s\)中子串\(t\) 的结束位置的集合，集合大小就是\(t\)在\(s\)中出现的次数 \(link(v)\): 状态\(v\)的后缀链接 \(len(v)\):状态\(v\)对应的最长子串的 阅读全文

摘要： 用途 : 用来解决形似\(a^x\equiv c\mod P(a,c,P为常数且P为质数,a为P的原根,x为要求的数)\) 插播: \(x\)的范围为\(0\le x\le P-1\) 证明: 因为\(a\)是\(P\)的原根,所以$\left { a0,a1,\dots,a^{P-1} \righ 阅读全文

摘要： 当需要取模的程序中有减法时，需要将答案加上模数再模一下 例如: ans = pow(2, n) % mod; ans -= (n + 1); ans = (ans + mod) % mod; P3723 给定两个长度为n的序列，可以平移(例如，a={1,2,3,4}, 平移后a={2,3,4,1}) 阅读全文