关于算法名称

强调一下，虽然说它又叫回文自动机，但是它不是自动机！！！

1.它有多个初始状态。
2.它不能够“接受一个字符串”。

kmp算法

1
2
3
4
5

int p=nxt[0]=-1;
for(int i=1;i<=n;i++) {
    while(~p&&str[p+1]!=str[i]) p=nxt[p];
    nxt[i]=++p;
}

kmp 算法的正确性基于：

下文中的字符串大小比较都是字典序的比较。

Lyndon word

对于一个字符串$s$，$s$小于$s$的所有后缀，那么$s$就是一个Lyndon word。

前言

如果现在你有一个序列，你知道他们满足$m$阶的

递推关系，而你需要通过这个序列中的数解出这个序列的递推式。这就是BM算法解决的问题。

定义

对于一个数列$h_0,h_1\cdots h_n,\cdots $，称这个数列满足k阶线性递推关系是指存在量$a_1,a_2,\cdots a_k (a_k \not= 0 )$和量$b_n$（$a_1,a_2,\cdots a_k,b_n$都可能以来于$n$），使得$h_n = a_1h_{n-1} + a_2h_{n-2} \cdots a_k h_{n-k} + b_n(n\ge k)$成立。

如果$b_n$是常数$0$，我们称这个线性递推关系式齐次的。

一个引理

设$I$是一个下标集合。对于每一个$j\in I$，设$\alpha_j$和$\beta_j$是实数，并且令$x_j$是一个实数变量。设$\gamma$是一个实数。

如果对于变量$x_j$的任意设置，我们都有$\sum_{j\in I} \alpha_j x_j = \gamma + \sum_{j\in I} \beta_jx_j$。那么可以推出对于任意的$j\in I$有$\alpha_j = \beta_j$并且$\gamma =0$。

结合律

矩阵乘法满足结合律，即$(AB)C=A(BC)$。

证明：设最后得到的结果为$D,AB=E,BC=F$。

P4457 [BJOI2018]治疗之雨

$n\le 1500$，不能直接$n^3$高斯消元。然而这道题需要高斯消元的那个矩阵很特殊，近似上三角矩阵，大概长这样（$1$表示值不为$0$）：

如果我们从第一行开始消，那么消完第一行后，矩阵就变成这样的了：

一些定义

线性函数、线性约束、线性规划问题

已知一组实数$a_1,a_2\cdots a_n$和一组变量$x_1,x_2,\cdots x_n$，在这些变量上的一个线性函数定义为$f(x) = \sum a_ix_i$。

问题：有 $n$ 个变量 $x_1,x_2,\cdots x_n$，以及一系列限制 $x_{v_i} - x_{u_i}\le w_i$（$w_i$ 可以为任意实数）。求出一组合法解或判定无解。

回顾最短路的概念：

对于一张包含 $n$ 个点的有向图，设 $dis_i$ 表示从 $1$ 到 $i$ 的最短路长度，令 $dis_1 = 0$。则对于每条边 $(u_i,v_i,w_i)$，显然会有 $dis_{v_i} \le dis_{u_i} + w_i$，也就是 $dis_{v_i} - dis_{u_i} \le w_i$。