字符串，太深刻了/kk定义下标从1开始。\(+\)是字符串拼接。\(|s|\)表示\(s\)的长度。\(s_i\)表示\(s\)的第\(i\)个字符。\(s^k\)表示\(k\)个\(s\)拼接的结果。字符串间的大小关系用字典序比较。Lyndon串字符串\(s\)是Lyndon串当且仅当\(s\)小于其

伯恩斯坦引理：若\({\rmcard}X\le{\rmcard}Y\)且\({\rmcard}Y\le{\rmcard}X\)，则\({\rmcard}X={\rmcard}Y.\)证明：由条件得存在单射\(f\colonX\longrightarrowY\)和\(g\colonY\longrightarrowX.\)，取\(g\)的一个左逆\(h\colonX\longrightarrow

真的是简记2-SAT$2-SAT$用于求解一个变量只有两种情况的适应性问题（就是有没有解以及输出一种方案）；其实可以类比二分图最大匹配（但其实两者的差别还是很大的）；算法流程对于每一个变量，我们都有两种情况，$true$和$false$；而题目中给我们的，是形如{$A=true/false$或

引理一：最小覆盖矩形的所有边上都有点，而且所有边都有凸包上的点，并且这条边上如果有多个点，那么这条边也是凸包的边引理二：矩形的某一条边与凸包的某一条边共线证明：反证。如果最小覆盖矩形没有边与凸包的边共线，那么根据引理一，矩形的每条边上有且仅有一个凸包上的点，如下图四个红色

或曰，有学长两天授吾以十专题，吾顿感日月之紧迫，以专题竟不能以吾之所有，遂成此文，以记之语文确实没学好本文可能涵盖多个知识点，故每个的讲解比较简略，仅供参考一.2-SAT$2-SAT$用于求解一个变量只有两种情况的适应性问题（就是有没有解以及输出一种方案）；其实可以类比二分图最大

定义：\(e(x,y)\)表示\(\sum_{P(x\rightarrowy)}\omega(P)\)。\(\omega(P)\)表示\(P\)这条路径中所有边权之积。路径组\((S,p)\)表示\(a_{i}\tob_{p_{i}}\)的一种路径组，即\(S_{1},S_{2},\dots,S_{n}\)。\((S,p)^{*}\)表示满足不存在\(S_{i}\)与\(S_{

这是我们的某一天的联考题目：\(n\le500\)。显然使用平面图完美匹配计数可以获得\(O(n^6)\)，但是有一种神秘的对路径的双射。当时我们都认为这是超级人类智慧，但是今天看书发现是书上的某个例的题的方法（有不同）。。考虑对正六边形的菱形密铺方案数（上图）。可以等价的问题是完美匹

群的基本概念给定一个集合\(\text{G}=\{a,b,c,\cdots\}\)以及一个运算符*，满足以下性质：封闭性：\(\foralla,b\in\text{G},\existsc\in\text{G},a*b=c\)结合律：\(\foralla,b,c\in\text{G},(a*b)*c=a*(b*c)\)单位元：\(\existse\in\text{G},\foralla\in\text{

参考了https://spaces.ac.cn/archives/8679/comment-page-1，有一些增删。JL引理首先下面需要应用马尔可夫不等式的另一个形式：\[\newcommand\E{\mathbbE}P(x\gea)=P(e^{\lambdax}\gee^{\lambdaa})(\lambda>0)\le\min_{\lambda>0}e^{\lambdaa}\E[e^{\lambdax}]\]单

在一张有向无环图DAG中，有边权，给定起点点集A，终点点集B，且A,B中的点数一致。定义P表示DAG中的一条路径。定义w(P)表示路径P上的边权乘积。定义e(a,b)表示a到b的所有路径的边权乘积之和，即\(e(a,b)=\sum_{P_i\in(a\tob)}w(P_i)\)定义一组A到B的不相交路

LyndonWords一个串为Lyndon串当且仅当其为其所有后缀中字典序最小的.Lyndon分解：将一个串\(w\)分解为若干个字典序单调不增的Lyndon串\(w_1,w_2,\cdots,w_k\)的拼接，每个\(w_i\)为\(w\)的Lyndon因子.可以证明一个串的Lyndon分解是存在且唯一的.引理1：若\(

\(\text{LGV}\)引理学习笔记\(\text{LGV}\)引理一般用于求解有向无环图中多条不相交路径的方案数，引理内容如下。引理定义\(w(P)\)指的是路径\(P\)上所有边权的乘积（在路径计数问题中认为所有边权均为\(1\)即可），\(e(A,B)\)指的是\(A\toB\)的所有路径的\(w\)和。对

（轨道公式）$$|G|=|G_x|\cdot|O_x|$$对于\(G\)在\(\Omega\)上的群作用，\(\forallx\in\Omega\)，定义\(O_x:=\{g(x)\midg\inG\}\)，称为\(x\)的\(G\)-轨道。定义\(G_x:=\{g\inG\midg(x)=x\}\)，称为\(x\)的稳定子群，它的确是\(G\)的子群。而轨道有如下性质

LGV引理行列式引出来的有趣的东西，是与图论的交界处。LGV引理大致内容为：对于一张有向无环图，每条边上都有一个权值\(w(e)\)，记\(weight(P)\)表示路径\(P\)上所有边的权值乘积，对于一个起点组成的集合\(A\)和终点组成的集合\(B\)，满足\(|A|=|B|\)，记\(e(i,j)\)表示所有\(

LGV引理行列式引出来的有趣的东西，是与图论的交界处。LGV引理大致内容为：对于一张有向无环图，每条边上都有一个权值\(w(e)\)，记\(weight(P)\)表示路径\(P\)上所有边的权值乘积，对于一个起点组成的集合\(A\)和终点组成的集合\(B\)，满足\(|A|=|B|\)，记\(e(i,j)\)表示所有\(

《自动机理论、语言和计算导论》学习第10天，p261-p314总结，总计48页。一、技术总结1.generating&reachable2.ChomskyNormalForm(CNF)乔姆斯基范式。3.pumpinglemma泵作用引理。引理：引理是数学中为了取得某个更好的结论而作为步骤的已证明命题，其意义并不在于自身已完

二、说明如何利用引理16.12的性质2在O(|A|)时间内确定一个给定任务集合A是独立的。文心一言：引理16.12的性质2可能是指某个特定引理中关于任务集合独立性的一个性质。由于具体的引理内容没有给出，我将基于任务集合独立性的通用概念来提供一个一般性的解释。任

CS3800在线W.Schnyder2024年春季3/6/2024课业7（3月15日星期五到期）说明：此课业应在到期日之前11:59pm之前以一年级的PDF（不零件）提交。您可以在文字处理器中键入解决方案，然后将其打印到PDF，或者手工编写并提交扫描副本。写下并提交答案，就像他们是专业报告一样。如果提交不整洁（

\(20240303\)随机好题CF40E引理1：若答案不为\(0\)，则\(n,m\)同奇偶。证明：每行、列都是\(1\)，那么考虑把每个数乘起来。有\((-1)^n=(-1)^m\)。所以\(n\equivm(\bmod2)\)引理2：在引理1的条件下，若已确定所有列满足条件，一行之外的所有行也满足条件，那么该行也满足。

LGV引理内容（不会证明）\(\omega(P)\)表示P这条路径上所有边的边权之积。（路径计数时，可以将边权都设为1）（事实上，边权可以为生成函数）e(u,v)表示u到v的每一条路径P的$\omega(P)$之和，即$e(u,v)=\sum\limits_{P:u\rightarrowv}\omega(P)$。起点集合\(A\)，是有向无

一道练习贪心证明的好题。绝大多数题解只是点出了以下结论：要么最快的带最慢的；要么最慢的带次慢的。并没有给出证明。我就补上这个证明。为了证明这个贪心结论，我们先证明几个引理。引理一：每次将火把带回来的，一定是对岸最快的。引理一证明：如果回来的不是对岸最快的，让对岸最

ReferenceOI-wiki介绍LGV引理(Lindström–Gessel–Viennotlemma)用来解决有向无环图上不相交路径计数，注意仅适用于有向无环图。给定\(n\)个起点构成的集合\(S\)和\(n\)个终点构成的集合\(T\)，定义\(\omega(P)\)表示路径\(P\)上所有边权的乘积（计数时设边权为\(1\)

#[数论学习笔记01]完系/同余最短路/费马小定理/扩欧/中国剩余定理###每日蒟蒻小故事(1/1)蒟蒻带了一本崭新的笔记本到S组.他发现这一节课居然在学习数论."听不懂,求讲解!"蒟蒻说.大佬邪魅一笑,并未理会.蒟蒻只能一边听着老师的讲解,一边努力地记着笔记."什么是完全剩余系

为了防止明天就把好不容易听完的东西都还给rabbit_lb了，还是记一点吧。1.群论基础1.1群(group)的定义给定集合\(G\)和\(G\)上的二元运算\(\cdot\)，满足下列条件称之为群：封闭性：若\(a,b\inG\)，则\(a\cdotb\inG\)。结合律：对于任意\(a,b,c\inG\)，有\((a\cdotb)\cd

这个东西一般用来求DAG中从初始点集合\(S\)到终止点集合\(T\)的有符号不相交路径方案数（不相交指的是点不会同时出现在两个路径中），\(n=|S|=|T|\)。设\(P(w)\)表示路径\(w\)上的边权的乘积，\(e(s,t)\)表示\(\sum_{w:s\tot}P(w)\)。\[A=\begin{bmatrix}&e(A_1,B_1)&e