又是一年 520 了，可现在的我却没有心上人…… 悲哀

在车人的要求下，玉帛拿一下午讲了生成函数 这个大坑不知道要填多久 前置知识：求导（真够让人头大） 这是讲解：懒得写了，全英文但勉强能看 好了看例题： 食物 - BZOJ by HydroOJ - P3028 如果看了上面的资料，那这就十分板了呀 f1=11−x2f2=1+xf3=1+x+x2f4=x1−x2f5=11−x4f6=1+x+x2+x3f7=1+xf8=11−x3<a1,a2,a3…an>⟷11−x2(1+x)(1+x+x2)x1−x211−x4(1+x+x2+x3)(1+x)11−x3=1(1+x)(1−x)(1+x)(1+x+x2)x(1+x)(1−x)x(1+x2)(1+x)(1−x)(1+x2)(1+x)(1+x)1(1−x)(1+x+x2)=x(1−x)4=x(1−x)−4=x∑k≥0(−4k)(−x)kai=(−4i−1)(−1)i−1=(i+2i−1)=(i+23)=i(i−1)(i−2)6\begin{aligned} &f1=\frac{1}{1-x^2}\\ &f2=1+x\\ &f3=1+x+x^2\\ &f4 ...

呃呃，没想到还会有这种若只东西 写一下： 123456789while (l <= r){ int mid = l + r >> 1; if (check(mid)) r = mid - 1, res = mid; else l = mid + 1; //或 //if (check(mid)) r = mid - 1; //else l = mid + 1}

我的的算法模板库，收录了常用的算法模板~~ 由于是开的新坑，正在缓慢更新qwq 更新速度可能跟做的专题有关吧~~~ 仓库地址： 12https://github.com/lfyszy/lfyszy-s-oi-code # githubhttps://gitee.com/lfyszy/lfyszy-s-oi-code # gitee镜像

由于机房的牛子们非常的疯狂，我觉得可以记录一下 蠢猪笨牛 的言论……

莫比乌斯反演 一句话总结：题面极其简洁并且大多能一眼出算法，代码短但是式子又臭又长。 前置知识：数论分块：数论全家桶 - lfyszy（别问为啥没有狄利克雷卷积) 莫比乌斯函数 μ\muμ 为莫比乌斯函数，定义为： μ(n)={1n=10n 含有平方因子(−1)kk 为 n 的本质不同质因子个数\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases} μ(n)=⎩⎨⎧​10(−1)k​n=1n 含有平方因子k 为 n 的本质不同质因子个数​ 同时莫比乌斯函数有以下性质： ∑d∣nμ(d)={1n=10n≠1\sum_{d\mid n}\mu(d)= \begin{cases} 1&n=1\\ 0&n\neq 1\\ \end{cases} d∣n∑​μ(d)={10​n=1n=1​ 证明： 设 n=∏i=1kpici,n′=∏i=1kpi\displaystyle n=\prod_{i=1}^k{p_ ...

闲话 我谔谔，第一稿写了一大部分没有保存。 质数 & 约数 质数判定 试除法 没啥好说，会的都会，复杂度 O(n)O(\sqrt{n})O(n​) 1234567bool isprime(int x){ if(x == 1) return false; for(int i = 2; i <= n / i; i ++) if(x % i == 0) return false return true;} Fermat 素性检验 通过反着使用费马小定理，多次换底增加正确性。 但是可以被卡迈尔数完美卡掉。 Miller Rabin 素性检验 【朝夕的ACM笔记】数论-Miller Rabin素数判定 - 知乎 (zhihu.com) 在 Fermat 素性检验基础上，引入二次探测定理（对于质数 ppp，x2≡1(modp)x^2\equiv1\pmod px2≡1(modp) 的解仅可能为 x≡1(modp)x\equiv 1\pmod px≡1(modp) 或 x≡p−1(modp)x\equiv p-1\pmod px≡p− ...

前言 有人会问，为什么要用这么多心思来做这么一个博客，为什么不用 luogu，oierspace，csdn，cnblogs……但是 luogu 的文章区前途仍是个未知数，cnblogs 为了生存在个人的博客中插入大量的广告等等，本来就全是广告的 csdn 更变本加厉的刮钱……所以笔者认为，hexo 等方便，小巧，干净的博客才是未来的发展趋势。 前面也有很多个 Hexo 的教程，但本文的方法支持自动化部署和在线的编辑~~ 初步部署 #1.准备工作 一个邮箱 vscode 呃呃，没有了 #2.Github端操作 Github 加速 由于一些不太友好的原因，GitHub 很难访问，在不用 magic 的情况下，我们选择 watt toolkit. 这里是官网→点我。 正常下载安装，勾选 国外验证码平台 与 Github，点击一键加速。 <ps：实测验证码需要 magic，自己找去> 注册 Github 打开 github.com，Edge的翻译都修好了，自己注册去。 创建仓库&Codespaces 新建一个仓库，图上勾出来的要选择，最后点击箭头指的按钮创建： 然后会 ...

好吧这是第二个紫模板算法 后缀自动机简介 一个对字符串所有子串进行高度压缩后储存的数据结构，其时空复杂度均为线性。 实际上可以理解为一个压缩了的后缀 Tire，因为共用了大量节点，所以 SAM 整体来看是一个 DAG。 概念 endpos 对于字符串 sss 的任意子串 ttt（含空串），我们记它在 sss 中结束位置的下标（从 111 开始）的集合为 endpos(t)endpos(t)endpos(t)。 特别的，空串的 endpos={1,2,…,∣s∣}endpos=\{1,2,\dots,|s|\}endpos={1,2,…,∣s∣}。 等价类 记 maxlenmaxlenmaxlen 为同一等价类中最长字符串的长度，minlenminlenminlen 为最短。 对于 endposendposendpos 相同的一些子串，我们称他们为一个等价类，则有以下性质： 同一等价类中的任意两个子串一定呈后缀关系。 同一等价类中，子串长度一定互不相同，且长度一定占据 [minlen,maxlen][minlen,maxlen][minlen,maxlen] 这个区间 两个等价类的 e ...

0x00 引入 给定主串与模式串 ，问主串中是否存在模式串。 实际上这是一个最为简单的字符串匹配问题，对于暴力匹配来讲，每一次匹配失败时将模式串后移一位从头开始匹配是 O(n2)O(n^2)O(n2) 的复杂度，显然不够优。 而观察会发现，上述的解法会有很多次不必要的匹配过程，而 KMP 则可以减少匹配次数，Z 函数则是用另外的方法对更多信息进行处理，经过适当转换也可解决上述问题。 0x01 KMP 对与上图的情况，我们假设 1、2、3、4 部分是一样的，那么我们在 jjj 处发现 tj≠sit_j \ne s_itj​=si​ 时，由于 1，2 部分相等，可以让 jjj 回退到 j′j'j′ 位置，这样就可以节省匹配次数。 假如我们已经知道了在每个点应回退到那个位置，即 nxt[] 数组，不难写出以下代码： 12345678910void kmp(string s, string t){ int n = s.size(), m = t.size(); for(int i = 0, j = 0; i < n; i ++) { ...