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
 
## 前置 先定义 $\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 ......