lemma
CF1909G Pumping Lemma 题解
题目链接 点击打开链接 题目解法 很 \(nb\) 的字符串题 首先,\(x+y\) 是 \(s,t\) 的公共前缀,\(y+z\) 是 \(s,t\) 的后缀 所以如果 \(s,t\) 的最长公共后缀与 \(lcp\) 不交,那么无解,如果有解,则只留下 \(s,t\) 的最长公共后缀,因为前缀的 ......
Codeforces 1909G - Pumping Lemma
这个题思考角度很多,做法也很多。这里介绍一种 @asmend 和我讲的做法。 设 \(d=m-n\),那么我们枚举 \(|x|=i,|y|=j\),设 \(s,t\) 的 LCP 长为 \(l_1\),LCS 长为 \(l_2\),那么可以得到这组 \((i,j)\) 合法的充要条件是: \(i\l ......
确定性上下无关文法(DCFL)的 Pumping Lemma
![](https://img2023.cnblogs.com/blog/1592654/202307/1592654-20230711222955489-973173401.jpg) ![](https://img2023.cnblogs.com/blog/1592654/202307/15926 ......
Lovász Local Lemma (LLL)
## 前置 先定义 $\text{independent}$。称两个事件 $A$ 和 $B$ 为 $\text{independent}$ 的,$\text{iff}\;\Pr[A]=\Pr[A|B]$,即 $A$ 的发生概率与 $B$ 无关。 称 $A$ 与 $A_1,A_2,..,A_m$ 所有 ......
Matrix determinant lemma
## 内容 对于两个列向量 $u,v$ 和可逆方阵 $A$ 有 $\det (A+uv^T)=\det(A)(1+v^TA^{-1}u)$ 。 ## 引理 内容 $$ \det(I+uv^T)=(1+v^Tu) $$ 证明: 暴力计算可以发现有如下等式: $$ \begin{pmatrix} I & ......
2) Chernoff bound, Hoeffding's Lemma, Hoeffding's inequality
防盗 https://www.cnblogs.com/setdong/p/17370017.html 1. Chernoff bound (切尔诺夫限) Given a random variable (r.v.) $X$ and $\epsilon>0$, for any $t>0$ the fo ......
证明霍夫丁引理 Hoeffding Lemma
马尔可夫不等式(Markov's inequality) $X\ge0$ 为非负随机变量,$t>0$ 为常数,则有 $$ \begin{align*} \mathbb P(X\ge t)\le{\mathbb EX\over t} \end{align*} $$ 证: 指示器函数 $I\lbrace ......