后缀自动机二·重复旋律5题目链接：HihoCoder - 1445 题意：求一个串所有不同子串的个数 思路：文本串S的后缀自动机是一部恰好只能识别S全部子串的机器，所以统计所有不同子串的个数，只需要将每个状态内子串的个数相加即可，而每个状态内子串的个数为sam[i].longest-sam[i].shortest+1 12345678910111213141...

过山车题目链接：hdu - 2063 题意：求二分图的最大匹配 思路：二分图最大匹配模板题，利用匈牙利算法解决，其核心是通过不停地找增广路来增加匹配中的匹配边和匹配点，找不到增广路时，达到最大匹配 123456789101112131415161718192021222324252627282930313233343536373839404142434445...

New Distinct Substrings题目链接：spoj - SUBST1 题意：给你一个串，求他的子串个数 思路：每个子串都是某个后缀的前缀，所以计算每个后缀的贡献即可，按照后缀suffix(sa[1])，suffix(sa[2])…的顺序计算，当加入suffix(sa[k])时，本应产生n-sa[k]+1个前缀，但是有height[k]个前缀在前...

前置技能平衡树是二叉搜索树的一种，二叉搜索树的定义如下： 空树是二叉搜索树 若二叉搜索树的左子树不为空，则其左子树上所有点的权值均小于其根节点的值 若二叉搜索树的右子树不为空，则其右子树上所有点的权值均大于其根节点的值 二叉搜索树的左右子树均为二叉搜索树 对于有$n$个节点的二叉搜索树，每次基本操作的最优复杂度为$O(logn)$，由于二叉搜索树可能退化...

题目链接：XOR 题意：给定n个整数，求满足子集异或和为0的子集大小之和 思路：先求出n个整数的线性基r，线性基的大小为cr，讨论每个元素对答案的贡献 线性基r外的元素共有n-cr个，对于每个元素，都能够与其他n-cr-1个线性基外的元素组合，组合后一定能在r内找到唯一的对应元素，所以每个元素对答案的贡献为$2^{n-cr-1}$种，有n-cr个元素，所以...

题目链接：小Z的袜子 题意：$n$只袜子，$m$个询问，每次回答有多大概率在$[L,R]$区间内抽到两只颜色相同的袜子 思路：普通莫队，如果两个询问左端点在一个块内，则按询问右端点排序，否则按照所在块的序号排序，维护一个数组$num$，表示在区间$[L,R]$中，颜色为$c$的袜子有$num[c]$只，令变量$res=\sum_{c}num[c]*...

题目链接：余数之和 题意：给定正整数$n$和$k$，计算$k%1+k%2+\dots+k%n$的值 思路：因为$k%i=k-\left \lfloor \frac{k}{i} \right \rfloor * i$，所以问题就转换为计算$n*k-\sum _{i=1}^{n}\left \lfloor \frac{k}{i} \right...

题目链接：牛牛的Link Power II 题意：给你一个只含$0$和$1$的串，定义串的$Link$值为串中两个的$1$之间的距离的和，$(u,v)$和$(v,u)$被看认为是同一对，有$m$次操作，每次操作可以把串中某个$1$变为$0$，或者把某个$0$变为$1$，求一开始和每次操作后串的$Link$值。 思路：线段树，维护区间内$1$的数量$cnt、$...

题目链接：Same GCDs 题意：给你两个数$a$，$m(1 \leq a < m \leq 10^{10})$，求有多少个$x$满足：$0 \leq x < m$且$gcd(a,m)=gcd(a+x,m)$ 思路：设$gcd(a,m)=d$，那么问题转换为求多少个$k \in [a,a+m)$满足$gcd(k,m)...

题目链接：矩阵 题意：给定一个$m$行$n$列的$01$矩阵$($只包含数字$0$或$1$的矩阵$)$，再执行$q$次询问，每次询问给出一个$a$行$b$列的$01$矩阵，求该矩阵是否在原矩阵中出现过 思路：二维哈希，从矩阵的右下角为低位到矩阵的左上角为高位，先求出每一行的一维哈希值$h[i][j]$，在$a$行$b$列的$01$矩阵向下移动的过程中，先向下...