星光light

This blog assumes the reader is familiar with the basic concept of rolling hashes. There are some math-heavy parts, but one can get most of the ideas without understanding every detail. The main focus of this blog is on how to choose the rolling-hash parameters to avoid getting hacked and on how to hack codes with poorly chosen parameters. Designing hard-to-hack rolling hashes Recap on rolling hashes and collisions Recall that a rolling hash has two parameters (p, a) where p is the modulo and 0  ...

简介 Vim 是一款功能强大的文本编辑器，其功能和操作方式与传统的编辑器有 很大不同。 但如果熟练之后，速度将大大提高，甚至更快（因为 DEV 没有自动补全）。 部署 Linux NOI 的官方镜像 NOI LINUX 2.0 自带 Vim，如果需要在 Ubuntu 上自己安装，使用： 1$ sudo apt install vim Windows 如果不想装虚拟机，可以用 Windows 下的 gVim，操作和 Vim 一样，但是更加适合初学者。 官网：https://www.vim.org/download.php 使用 打开 Linux 的终端，输入： 1$ vim filename Vim 就会打开 filename 文件。若不存在，则会自动创建。 模式 Vim 有四种模式： 命令模式（Command Mode） 底线命令模式 插入模式（Insert Mode） 可视模式（Visual Mode） 当我们首次进入 Vim，观察到左下方应该是一片空白，此时就是命令模式。 命令模式（Command Mode） 这是 Vim 的默认模式，在其他三种模式下，按 Esc 键就能回到命 ...

欧几里得 algorithm:math 设棋子总共向左移动了 a 次，最终的落地为： s − ax + y(n − a) = s + ny − a(x + y) 容易发现落点对 x + y 的取模结果不变，而 [t − x.t + y) 区间内对 x + y 取模结果两两不同，二分答案即可。 容斥原理 algorithm:dp 一道思维难度大，码量奇小的题目。 由于答案是对 2 取模，容易发现

T1 一切大师 algorithm:math 考虑将原式转换： $$ \begin{aligned} ans &=\sum_{a=1}^{L}\sum_{b=1}^{L}[lcm(a,b)]*|ax-by|\\ &= \sum_{d=1}^{L}\sum_{a=1}^{\left \lfloor \frac{l}{d}\right \rfloor}\sum_{b=1}^{\left \lfloor \frac{l}{ad}\right \rfloor}[\gcd(a,b)=1]*d*|ax-by|\\ \end{aligned} $$ 直接爆算，发现 TLE。 预处理 $\sqrt{L}$ 以内的 gcd ，再卡一下常，即可过掉。 T2 你考它干嘛 暂缺 T3 digital 喜闻乐见的模拟题 algorithm:divide-and-conquer 一个区间众数为 1，当且仅当 1 的个数大于等于 $\left \lfloor \frac{n+1}{2}\right \rfloor$。 考虑分治，设 solve(l, r, x) 表示区间 [l, r] 内有 x ...

T1 United Cows of Farmer John algorithm: segtree 一道非常神奇的数据结构题。 考虑枚举每个区间的右端点，设当前点为 i，值为 vi，上一个 vi 的位置为 prei。 显然，左端点只能在 (prei, i − 1] 这个范围内。 当我们加入点 i，那么 (prei, i − 1] 中左端点的方案数均可以加 1，线段树维护即可。 但有一个问题，左端点不一定是连续的，所以我们再维护一个 0/1 的系数，表示这个点能否作为左端点。 T2 Permutation algorithm: dp 考虑答案的图应该长什么样子： 首先有一个三角形，每次选择一个点，分类讨论： 在三角形内，图还是一个三角形。 在三角形外，它会与原三角形的两个顶点构成一个新的三角形。 就两种情况，我们可以用动态规划来解决。 设 dpp, i, j, k 为当前已经计算了 i 个点，答案为 i, j, k 三个顶点构成的三角形。 内部转移，相当于把 l 取出后，在 i, j, k 中随便选一个点，预处理三角形内部的点的数目即可。 格外注意，预处理时请用标准的计算几何方法，不 ...

强烈建议尝试 Luogu U461211 字符串 Hash（数据加强） 前言 某天看到同学打 字符串hash，发现还在用 腐朽 的 单模数hash。 为了帮助他改进码风，我决定 卡炸hash。 一、大模数哈希 1.前言 我们知道，要想卡掉 hash，本质上就是让两个字符串有相同的 hash 值，我们称为哈希碰撞。 假设 hash 中每个值生成概率相同，则碰撞概率取决于两个因素： - 取值空间大小 - hash 的计算次数 这个问题在数学中有一个经典的问题，叫 生日问题。 简单来说，就是在一个有 d 人的班中，有人生日相同的概率为多少。 实际上，这个问题的答案并没有想象中的小，下面是部分概率： | 人数 | 概率 | | :—: | :——: | | 23 | 50% | | 50 | 97% | | 70 | 99.9% | 2.计算冲突概率 我们设 hash 的取值空间为 d，计算次数为 n。 则 hash 不冲突的概率为： $$ \overline{p}(n,d) = 1 \cdot \left (1 - \frac{1}{d} \right) \cdot \left ( 1- ...