对于一类一维$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$的值关于该偏序关系单调,则称该函数具有区间包含单调性。
快速幂是能快速计算一个幂的方案,他可以作用于所有满足结合律、封闭性的二元运算,即半群
不妨假设这个二元运算为$\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)$次二元计算即可的到最终答案。