题解给定一个长度为$n(n \leq 10^6)$的字符串$S$，求其中的回文套娃个数。回文套娃定义为两个序列$l_1<l_2<…<l_k$和$r_1>r_2>…>r_k$，其中每个$S[l_i:r_i]$均为回文串。 在回文树中，每个节点$x$代表的字符串有两个前驱，第一个是删除第一个和最后一个字符得到的父亲节点$fa(x)$，第二个是最长前/后缀所代表的节点$f(x)$。 对于每个回文串$s[l:r]$，其包含的回文子串$s[x:y]$都可以通过如下的方式 ...

题解维护一个序列$a$，支持修改某个元素的值和寻找最小的满足$\sum_{i=1}^t a_i >= k$的$t$。（如果把该序列下标看成值域，值看作出现的次数，则第二种操作表示找第$k$大元素） 显然线段树上二分可以做到$O(logn)$的查询修改复杂度。 但是树状数组同样存在一种类似数位$DP$的方式，将修改操作做到一个$log$的复杂度。（时间空间上更优秀） 考虑树状数组的定义方式，第$i$位$Bit[i] = a[i-2^k+1] + a[i-2^k+2] + … + a[i]$（ ...

题解字符串的半前缀即前缀删除一个子串后得到的字符串，可以用$s[1…i]+s[j…k]$表示。 问题即给定一个长度为$n(n \leq 10^6)$的字符串，求其半前缀的个数。 \textbf{对于这种本质不同的字符串计数问题，通常都是将某个串在它第一次或最后一次出现时统计。} 本题中，如果将每个字符串在第一次出现的前缀中（即尽可能缩短用到的前缀长度），那么看起来就不太能做。但是如果将每一个串在最后一次出现的前缀中统计，就会非常简单：对于一个串，假设它可以表示为 $s[1…i]+s[j…k]$ ...

题解$f(n)=af(n-1)+bf(n-2),f(1)=c,f(2)=d$ 求$f(n) \ mod \ p$的最小循环节长度。 当$c$是模$p$的二次剩余时，枚举$n=p-1$的因子。 当$c$是模$p$的二次非剩余时，枚举$n=(p+1)(p-1)$的因子。 找到最小的因子$ans$，使得 $\begin{pmatrix} a & b \ 1 & 0 \end{pmatrix}^{ans}=\begin{pmatrix} 1 & 0 \ 0 & 1 \en ...

题解求满足以下条件的$(x,y)$整数对数：（适用高位到低位$DP$） $x∈[0,A],y∈[0,B]$ $x xor y≤W$ 求满足以下条件的$(x,y)$整数对数：（适用低位到高位$DP$） $x∈[0,A],y∈[0,B]$ $x xor y ≤ W$ $x - y ≤ K$ 大多数情况下，从高位到低位进行$DP$都更为便捷。但第二道例题中有加法（也可以看作减法），也就是有进位（也可以看作有借位），此时从低位到高位显然更便捷。 对于第二道例题：设$f[bit][xA] ...

因为0的个数和1的个数要保持一致，所以沿途要记录0的个数与1的个数的差，每个差值对应都要一个状态，而这个值可能是无限的，所以无法用有穷状态机表示。（D中01和10最多差1，所以是正则的）

题解定义序列$a_{1…n}$的权值为$\sum a_i$ 求满足$l_i \leq a_i \leq r_i$且$a_i$单调不降的所有序列$a_{1…n}$的权值和。 考虑最高位，那么一定存在一个$k$，使得$a[1…k]$最高位是$0$，$a[k+1…n]$最高位是$1$，那么可以分成两个子区间去做。 设$f[i][L][R][LIML][LIMR]$表示：在$i+1…60$位已经定下来的情况下（此时$a[L…R]$的$i+1..60$位的值一样），区间$[L…R]$只考虑$1…i$位的答 ...

题解$Boruvka$算法流程： 先对于每个点，选择在所有与之相连的边中，权值最小的边，并将这条边加入到最小生成树中。显然这样连出来的边会形成一个森林，并且连边后连通块个数至少减半。然后我们将每个连通块再看成一个点，重复以上算法即可。时间复杂度$O(mlogn)$。 例题： 给定一个$n$个节点的完全图，每个节点有个编号$a_i$,节点$i$和节点$j$之间边的权值为$a_i⨁a_j$,求该图的最小生成树的权值和。 从高位往低位贪心。把所有点按当前位为$0$还是$1$分为两类。显然在执行$Bor ...

题解$f(1)=1,f(0)=0$ $f(n)=f(n-1)+f(n-2)$ $f(n)=((\frac {1+{\sqrt 5}} 2 )^n-(\frac {1-{\sqrt 5}} 2 )^n)/ {\sqrt 5}$ 斐波那契数列任意两项和都不相等 斐波那契数列的第$n+2$项代表了集合$，， {1，2，…n }$中所有不包含相邻正整数的子集的个数 $f(n+m)=f(n-1)f(m)+f(n)f(m+1)$ $gcd(f(n),f(m))=f(gcd(n,m))$ $\frac {a_ ...