nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
理论篇决策单调性对于一类一维$dp$,若有转移$dp[i]=min/max(dp[j]+w(i,j)) 0<j<i$，并假定$pri[i]$为到$dp[i]$的最优转移$j$，如果$pri[i]$关于$i$单调，那么我们称该$dp$具有决策单调性。
对于一类二维$dp$,如果有转移$dp[i][j]=min/max(dp[i][k]+dp[k+1][j]+w(i,j)) i<=k<j $并假定$pro[i][j]$为到$dp[i][j]$的最优转移$k$,如果$pri[i][j]$关于$i$单调，且关于$j$单调，那么我们称该$dp$具有决策单调性。
四边形不等式对于二元数论函数，$w(i,j)$，若满足$a\le b\le c\le d$恒有 $w(a,d)+w(b,c) \ge w(a,c)+w(b,d)$则该二元函数满足四边形不等式
他的充要条件是: 若$a\lt b$ 恒有$w(a,b)+w(a+1,b+1) \ge w(a,b+1)+w(a+1,b)$
可以理解为，交叉小于包含
区间包含单调性对于二元数论函数，$i<j$的$w(i,j)$ 我们将参数看做区间，定义区间的包含为偏序关系， 若$w$的值关于该偏序关系单调，则称该函数具有区间包含单调性。
阅读全文
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
简介快速幂是能快速计算一个幂的方案，他可以作用于所有满足结合律、封闭性的二元运算，即半群
定义不妨假设这个二元运算为$\circ$,两个元素进行运算为$x\circ y$,当$xy$同为$x$时，不妨设$x^2=x\circ x$, 同样的$x^1=x$, 当然$x^0=e$, 还有$x^k=x^{k-1}\circ x$
快速幂核心思想在半群中，只要$k=u+v$一定有$x^k=x^u\circ x^v$.
所以我们可以把k看作一个二进制数，把$x^k$分解为$x^{2^{p_1}}\circ x^{2^{p_2}}\circ x^{2^{p_3}}\circ \circ \circ x^{2^{p_n}}$
这里最多分解为$\log_2(k)$个元素，而且每个元素可以由前k个元素获取，所以只需要进行$log_2(k)$次二元计算即可的到最终答案。
阅读全文
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
前言本文力争用理性分析的手段，来推测此算法发明者的思维过程， 尝试感受其在设计此算法的时所展现出的思维方式， 力求用数学证明的手段，尽可能多的为读者证明相关结论，建议有其他自动机学习的基础，最好已经学会AC自动机和回文自动机，后缀自动机很难，他 和其他自动机不一样，它的状态更加复杂，一个算法的创作过程很 复杂，学起来当然会感到很难。强烈建议看陈立杰的ppt，看一遍肯定看不懂，仔细看，一遍看不懂看多遍，第一次可能只能看懂几面，第二次可 能就能看懂到十几面了，慢慢的就全懂了。
阅读全文
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
AC自动机所谓AC自动机，其实是kmp算法与字典树的结合,不懂这两个，是无法学会的。
自动机自动机，是一个五元组，包括了状态的非空有穷集合，符号的有限集合，状态转移函 数， 开始状态，终止状态集合，而在字典树上，增加了两个新的东西，一个标记了终止状态集合，另一个辅助了状态转移函数。 我们利用字典树上 的节点来表示状态，而边则用来表示状态转移函数的一部分。
阅读全文