抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 常见数位dp如果一个在数字上的计数问题只与数位和数的大小有关的时候 我们可以尝试用数位dp来解决。最经典的就像不要62那道题。 数位dp状态我们常常设dp[val][len][limit][lead...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 例题1http://codeforces.com/contest/617/problem/E 给长度为n的序列,给数字k,给q次询问,每次询问给出[L,R],求这个区间内有多少个连续区间的异或和等于...

理论篇

决策单调性

对于一类一维$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 DFS计算最大团 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484...

简介

快速幂是能快速计算一个幂的方案,他可以作用于所有满足结合律、封闭性的二元运算,即半群

定义

不妨假设这个二元运算为$\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)$次二元计算即可的到最终答案。

前言

本文力争用理性分析的手段,来推测此算法发明者的思维过程, 尝试感受其在设计此算法的时所展现出的思维方式, 力求用数学证明的手段,尽可能多的为读者证明相关结论,建议有其他自动机学习的基础,最好已经学会AC自动机和回文自动机,后缀自动机很难,他 和其他自动机不一样,它的状态更加复杂,一个算法的创作过程很 复杂,学起来当然会感到很难。强烈建议看陈立杰的ppt,看一遍肯定看不懂,仔细看,一遍看不懂看多遍,第一次可能只能看懂几面,第二次可 能就能看懂到十几面了,慢慢的就全懂了。

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 给你一棵n个节点的树,要你求出包含每个点的连通点集的数量。答案对1e9+7取模。 两次dfs,第一次处理每个节点的子孙方向的联通点集数量,$$dp[i]=\prod _{all.....

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 12345678910111213141516171819202122232425262728293031323334353637383940struct Manacher {//鉴于...

AC自动机

所谓AC自动机,其实是kmp算法与字典树的结合,不懂这两个,是无法学会的。

自动机

自动机,是一个五元组,包括了状态的非空有穷集合,符号的有限集合,状态转移函 数, 开始状态,终止状态集合,而在字典树上,增加了两个新的东西,一个标记了终止状态集合,另一个辅助了状态转移函数。 我们利用字典树上 的节点来表示状态,而边则用来表示状态转移函数的一部分。

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 回文自动机,就像AC自动机一样,他采取字典树来储存状态集合,也像AC自动机是KMP 算法与字典树结合一样,回文自动机就是manacher算法和字典树结合的新算法。 在回文自动机里面,状态指的是,...