在车人的要求下，玉帛拿一下午讲了生成函数 这个大坑不知道要填多久 前置知识：求导（真够让人头大） 这是讲解：懒得写了，全英文但勉强能看 好了看例题： 食物 - BZOJ by HydroOJ - P3028 如果看了上面的资料，那这就十分板了呀 f1=11−x2f2=1+xf3=1+x+x2f4=x1−x2f5=11−x4f6=1+x+x2+x3f7=1+xf8=11−x3⟷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 2 3 4 5 6 while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } 和 1 2 3 4 5 6 while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; }

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

由于机房的牛子们非常的疯狂，我觉得可以记录一下 蠢猪笨牛 的言论…… 2.26~3.3 3.4~3.10 @harmis_yz 3.11~3.17 3.18~3.24 3.25~3.31

莫比乌斯反演 一句话总结：题面极其简洁并且大多能一眼出算法，代码短但是式子又臭又长。 前置知识：数论分块：数论全家桶 - 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的本质不同质因子个数​ 同时莫比乌斯函数有

闲话 我谔谔，第一稿写了一大部分没有保存。 质数 & 约数 质数判定 试除法 没啥好说，会的都会，复杂度 O(n)O(\sqrt{n})O(n​) 1 2 3 4 5 6 7 bool 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 Rabi

前言 有人会问，为什么要用这么多心思来做这么一个博客，为什么不用 luogu，oierspace，csdn，cnblogs……但是 luogu 的文章区前途仍是个未知数，cnblogs 为了生存在个人的博客中插入大量的广告等等，本来就全是广告的 csdn 更变本加厉的刮钱……所以笔者认为，hexo 等方便，小巧，干净的博客才是未来的发展趋势。 前面也有很多个 Hexo 的教程，但本文的方法支持自动化部署和在线的编辑~~ 初步部署 #1.准备工作 * 一个邮箱 * vscode * 呃呃，没有了 #2.Github端操作 Github 加速 由于一些不太友好的原因，GitHub 很难

好吧这是第二个紫模板算法 后缀自动机简介 一个对字符串所有子串进行高度压缩后储存的数据结构，其时空复杂度均为线性。 实际上可以理解为一个压缩了的后缀 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∣}。 等价类 记 maxlenmaxlen

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 回退到

额……被板刷abc的弱智吊打了 只能说又挂分了 T1 ABC226E 水题，首先可以确定边数一定等于点数，那么不可能出现两个环有公共边的情况，因此可以统计环的数量，每个环可以有正反两种情况，就做完了（具体细节不多，可以看代码解决）。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include

2023-12-11 赛后总结

阅读全文