A Shallow Dive into Private-Key Encryptions

We have the illusion that, as long as the key exchange was done securely, Private-Key, also known as Symmetric Cryptography, is solidly safe; if we ever introduce Public-Key or Asymmetric Cryptography to exchange private keys, then we are unbreakable.…

Maurice Wilkins & DNA

Maurice Wilkins was one of the key scientists involved in the discovery and verification of the structure of DNA. Wilkins began investigating DNA after working on radar screens and the Manhattan Project during World War II. Like many scientists, he was worried the Nazis could develop nuclear weapons, and was…

Oysters Bring Sea to Chicago

This is a translated version. Read the original one by Ent. In 1954, biologist F.A. Brown dug a batch of oysters from the Connecticut Shore. Knowing the oysters’ tide-relating behaviour, the biorhythm researcher brought them to an underground aquarium in Chicago thousands of miles away, hoping for a new…

【笔记】有向图邻接矩阵幂敛指数及其周期的一种可行性算法

引入 一个 $n$ 个点有向图的邻接矩阵 $A$ 是一个 $n$ 阶布尔矩阵,它的幂组成的序列具有周期性。 设 $k,d$ 是满足 $A^k=A^{k+d}$ 的最小正整数,则 $k$ 称为 $A$ 的幂敛指数(index),$d$ 称为 $A$ 的周期(period)。 对于如下邻接矩阵 $A$,其各次幂分别为 $$A^1 = \left[\begin{matrix}0 & 1 & 0 & 0 & 0 \\ 0 & 0…

【笔记】带通配符字符串匹配

题目描述 给你两个带通配符的串 $A,B$。问 $B$ 中可以匹配多少个 $A$,并输出匹配的开头位置。 思路 我们在两个长度相同的字符串 $A, B$ 上定义 $f(A, B)=\sum_{i=0}^{n-1}(A_i – B_i)^2A_iB_i$。令通配符 * 为 0,当 $f(A,B)=0$ 时,$A = B$。 将 $f$ 展开得 $\sum_{i=0}^{n-1} \left( {A_i}…

【Note】Splay / 文艺平衡树

定义 Splay 是一种可以自我调节的二叉搜索树。它在 $\Theta(\log n)$ ​ 的均摊时间内执行基本操作,例如插入,查找和删除。对于许多非随机操作序列,Splay 比其他搜索树表现更好。 核心操作 我们提到 Splay 可以 “自我调节”,这一性质使得它能维持树形结构,保证复杂度。自我调节分为两部分:旋转 (rotate),以及伸展 (splay)。 旋转 伸展 实际运用 作为二叉搜索树,它能完成所有二叉搜索树都能完成的基本操作。当然,它也可以作为区间树完成诸如区间翻转的操作,正是这一性质使得它可以作为 Link Cut Tree 的辅助树。 代码 普通平衡树 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 插入 $x$ 数删除 $x$ 数(若有多个相同的数,因只删除一个)…

【笔记】Dirichlet 相关

Dirichlet Convolution Definition $$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{xy=n}f(x)g(y)$$ Example $\sigma_0=1*1$$\sigma_1=I*1$$I=\varphi*1$$\epsilon(n)=\mu*1$ Property 交换律:$f*g=g*f$结合律:$(f*g)h=f(g*…

【笔记】简单数论函数集合

Intro 咕了一年的集合。NOIp 内容。 (实际上只讲了两个函数) 常见数论函数 $\epsilon(n)=[n=1]$$1(n)=1$$id_k(n)=n^k$$I(n)=id_1(n)=n$$\sigma_k(n)=\sum\limits_{d|n}d^k$$\varphi(n)$$\mu(n)$ 欧拉函数 $\varphi(n)$ Definition $\varphi(n)$ 等于小于等于 $n$ 且与 $n$ 互质的正整数个数,即 $$\varphi(…