给定一个字符串集合 $S$，若由 $S$ 中 $k$ 个可相同的字符串拼接而成的字符串 $s$ 恰有 $k$ 个循环移位能由若干 $S$ 中的字符串拼成，则称其为好的。一个集合 $S$ 为好的，当且仅当所有能由 $S$ 中若干可相同的字符串拼接而成的字符串都是好的。给定字符串序列求有多少区间中的字符串集合是好的。

如果一个集合是好的，显然一个集合的所有子集都是好的，所以序列中的任意两个极长区间一定互不包含，可以双指针转化成做 $O(n)$ 次检查某个字符串集合 $S$ 是否是好的（注意这里需要去重）。

我们将“若干字符串拼接后得到两个互为循环移位的字符串 $s_1,s_2$”这个过程用一个图来表示：对集合 $S$ 中的每个字符串的每个非空后缀 $t$ 建两个状态分别表示 $s_1=s_2t$，和 $s_2=s_1t$；建空状态表示 $s_1=s_2$。

对字符串做 z-algorithm，可以 $O((\sum_{x\in S}|x|)^2)$ 地连边。途中有环则说明改集合不合法。

更进一步地，如果某个表示 $s_1=s_2t$ 的状态 $t$ 能够到达表示 $s_2=s_1t$ 的状态，根据对称性，它一定能到达它自己。所以对称的两个状态要么在同一个强连通分量里，要么互不能到达。据此我们可以给每个非空后缀只建一个点。

下文用一个二进制数中为 $1$ 的位来表示一个数。

维护集合 $S$，每次插入一个数后查询集合中两个元素 $x\slash y$ 的最大值。$\slash$ 表示集合差。

我们考虑在每次加入 $x$ 后考虑这个集合的答案是否被 $x\slash y$ 或 $y\slash x$ 更新，其中 $y$ 是集合中原有的数。

对从大到小每一位依此贪心，于是问题就变成了，加入数并动态维护 $S$ 中是否存在 $x$ 的子集和超集。

朴素的暴力是加入一个数，遍历其所有子集和超集分别标记。不过注意到，如果 $S$ 中存在 $x$ 的子集，那么对于 $x$ 的所有超集 $y$，$S$ 中均存在 $y$ 的子集。

所以如果 $S$ 中已经存在 $x$ 的超集则返回，否则对 $x$ 分别去掉每一位后的集合递归地标记。子集同理。这样做的总时间复杂度为 $O(n\log n)$。

给定两个大小相等的集合 $A,B$，求满足 $f(i)\not=i$ 的双射 $f$ 的数量。

若 $A=B$ 则为错排问题，所以我们考虑类似地通过递推解决这个问题。

令 $S=A\cap B$，设 $f(n,m)$ 为 $|S|=n,|A|=|B|=n+m$ 时这样的双射 $f$ 的数量。

显然 $f(0,m)=m!$。$n>0$ 时我们令 $t=\inf S$，对所有 $f$ 按照 $f(t)$ 进行分类讨论：

• 若 $f(t)\in S$ 且 $f(t)=f^{-1}(t)$，显然有这种情况下所有合法 $f$ 到 $A,B$ 均去掉 $t,f(t)$ 后所有合法 $f$ 的双射，所以这种情况的方案数为 $(n-1)f(n-2,m)$
• 否则，通过令 $f^{-1}(t)$ 映射到 $f(t)$，可以得到所有合法 $f$ 到 $A,B$ 均去掉 $t$ 后所有合法 $f$ 的双射，所以这种情况的方案数为 $(n+m)f(n-1,m)$。

由此可以得到递推式 $f(n,m)=(n-1)f(n-2,m)+(n+m)f(n-1,m)$。可见合法的状态只有 $O(n)$ 种。

若字符串 $s$ 有周期 $p,q$，且 $p+q\le|s|+\gcd(p,q)$，则 $\gcd(p,q)$ 为 $|s|$ 的周期。

---

若 $p=q$，结论显然。否则设 $p>q$。

考虑归纳地证明。因为 $(p-q)+q\le|s|-q+\gcd(p-q,q)$，如果周期引理对于 $s$ 长为 $|s|-q$ 的后缀成立，那么 $\gcd(p-q,q)$ 是该后缀的一个周期。

又因为 $2q\le p-\gcd(p,q)+q\le|s|$，即该后缀长度不少于 $\gcd(p,q)$，所以 $\gcd(p-q,q)$ 是该后缀的周期，也就为 $s$ 长为 $q$ 的前缀的周期，并且是整周期。

所以 $\gcd(p,q)$ 为 $s$ 的周期。

求若干个首项为 $0$ 公差为 $1$ 的等差数列总和为 $s$ 的情况下长度之和最少为多少。

注意到和不超过 $s$ 的这样的等差数列只有 $\sqrt s$ 种，暴力 DP 即可。

LGV 引理

一个带权 DAG 上，对于某个起点序列 $A_k$ 和终点序列 $B_k$，称一组不相交路径 $S$ 为 $k$ 条路径 $A_i\to B_{\sigma_S(i)}$ 构成的集合，满足路径间两两没有公共点，其中 $\sigma_S$ 是与 $S$ 相关的一个 $k$ 阶排列。

定义一条路径 $p$ 的权值 $\omega(p)$ 为路径上所有边的边权乘积。$e(u,v)$ 表示 $u$ 到 $v$ 的所有路径的边权之和。那么有

$$\displaylines{\sum_{S}(-1)^{\tau(\sigma_S)}\prod_{i=1}^k\omega(S_k)= \begin{vmatrix}e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_k)\\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_k)\\ \vdots&\vdots&\ddots&\vdots\\ e(A_k,B_1)&e(A_k,B_2)&\cdots&e(A_k,B_k)\end{vmatrix} }$$

其中 $\tau(\sigma_S)$ 表示 $\sigma_S$ 的逆序对数。

称左式 $\sum$ 内的部分为 $S$ 的权值。根据行列式定义，右式计算的是所有 $k$ 条路径 $A_i\to B_{\sigma_S(i)}$ 构成的路径组的权值之和，而左式是其中路径两两无公共点的路径组的权值之和。

对于一个相交的路径组 $S$，我们找出图上编号最小的出现在至少两条路径中的点 $u$，找经过它的路径中编号最小的两条边，交换它们 $u$ 以后的部分。因为交换一个排列的两个位置，排列的逆序对数奇偶改变，所以我们构造出了一个贡献完全相反的路径组 $S'$。

而且不难发现对 $S'$ 进行相同的构造可以得到 $S$，所以实际上我们获得了所有路径有相交的路径组的一组匹配，且这个匹配内相对的路径组贡献相反。所以所有路径有相交的路径组的贡献总和是 $0$。

而对于有向网格图，$A_i$ 均在第一行，$B_i$ 均在最后一行这样的只有满足 $\sigma_S(i)=i$ 的路径组 $S$ 不相交的情形，LGV 引理算出来的即 $k$ 条不相交路径 $A_i\to B_i$ 构成的路径组的权值和。

todo

给二分图的每条边染色，求最小的颜色数量，使得任何两个共顶点的边不同色。

证明

我们构造性的证明该问题的答案为所有点度数的最大值。

首先将颜色映射到自然数。然后以任意顺序考察每条边，将其染色。我们需要保证每一步染色之后，已经染色的这些边满足限制。

对于一条边 $(u,v)$，设以 $u$ 为端点的所有边的颜色构成的集合的补集中最小的（即 $\mathrm{mex}$）为 $x$，$v$ 的为 $y$。若 $x=y$，则将边 $(u,v)$ 染成该颜色。

否则构造这样的序列：$p_0,q_1,p_1,q_2,p_2,\cdots$。其中 $p_0=u$，$q_i$ 为 $p_{i-1}$ 连出的颜色为 $y$ 的边的另一端，$p_i$ 为 $q_i$ 连出的颜色为 $x$ 的边的另一端。如果 $p_i$ 不存在连出的颜色为 $y$ 的边，或 $q_i$ 不存在连出的颜色为 $x$ 的边，则该项为序列结尾。

显然，不存在 $p_i\not=p_j,q_{i+1}=q_{j+1}$，不存在 $q_i\not=q_j,p_i=p_j$。所以这样的序列元素一定两两不同，其长度不超过总点数。

并且 $v$ 一定不在该序列中，因为 $v$ 不存在颜色为 $y$ 的边。

然后将图上每条边 $(p_i,q_{j+1})$ 的颜色改为 $x$，将 $(p_i,q_i)$ 的颜色改为 $y$。然后给 $(u,v)$ 染色为 $y$ 即可。

显然原问题答案不会小于所有点的最大度数，而上述构造方案得出的所有边的颜色不会超过所有点的最大度数，证毕。

应用

直接按照上述过程进行构造，时间复杂度为 $O(nm)$。

可以利用它将 k-正则图分解为若干组匹配的无交并。染色后每条边的颜色即它属于哪个匹配。

例题：[SNOI2024] 拉丁方

网格图有一个优美的性质，它的最小割的大小等于较短边的长度，不超过 $\sqrt S$，其中 $S$ 为网格图面积。

所以网格图上的最短路可以分治地做，网格上一块矩形区域，在较长边中点处切开。此时两个点间的最短路分为，只经过其中一部分的和跨过切面的。只经过其中一部分的，分治处理；跨过切面的，我们以切面上每个点为源，在整个区域内求最短路。对于一块面积为 $S$ 的矩形区域，所需时间为

$$\displaylines{T(S)=2T\left(\frac S2\right)+\sqrt S\cdot S\log S }$$

根据主定理有 $T(S)=O(S^\frac32\log S)$。

首先将所有方案中 $\vert\sum B_i\vert$ 和最大转化成 $\max(\sum B_i,-\sum B_i)$。

于是问题转化成了，每个点可以选择以 $B_i,-B_i,-A_i$ 计入贡献，对于之间有边的一对点 $(u,v)$，要么 $u$ 以 $-A_u$ 或 $v$ 以 $-A_v$ 计入贡献（被删掉），要么同时以 $B_u,B_v$ 或同时以 $-B_u,-B_v$ 计入贡献。

这是一个类似最大权独立集的问题。考虑转化为最小割模型，将点 $u$ 拆为 $u_+,u_-$，源 $S$ 向 $u_+$ 连边，$u_-$ 向汇 $T$ 连边。

源 $S$ 向 $u_+$ 的边不被割表示 $u$ 以 $B_u$ 计入贡献，$u_-$ 向 $T$ 的边不被割表示 $u$ 以 $-B_u$ 计入贡献，两条边都被割表示 $u$ 以 $-A_u$ 计入贡献。为了保证两条边不会都不被割，需要连边 $(u_+,u_-,+\infty)$；同理，对于之间有边的一对点 $(u,v)$，需要连边 $(u_+,v_-,+\infty)$ 和 $(u_-,v_+,+\infty)$。

对于某个点 $u$，设 $S$ 到 $u_+$ 的边权为 $x$，$u_-$ 到 $T$ 的边权为 $y$，$u$ 的贡献为 $z$ 减去最小割中连向 $u_+$ 的和从 $u_-$ 出发的容量，联立三种情况得

$$\displaylines{\begin{cases} z-y=B_u\\ z-x=-B_u\\ z-x-y=-A_u \end{cases} }$$

解得

$$\displaylines{\begin{cases} x=A_u+B_u\\ y=A_u-B_u\\ z=A_u \end{cases} }$$

求 $\max$ 式的最小值，首先二分答案，问题转化为单点修改，区间查询是否所有颜色都出现过。

二分后这个问题可以归约到三维数点，带上二分是 $O((n+q)\log^3(n+q))$ 的复杂度。

不过显然这个问题是比三维数点弱的，因为查询的是所有颜色是否都出现过，而非求颜色个数。沿用区间数颜色的记每个位置 $i$ 的上一次为该颜色的位置 $p_i$ 的想法，不难发现区间 $[l,r]$ 中所有颜色均出现，当且仅当对于所有颜色有 $p_i\le l$，其中 $i$ 为该颜色在 $r$ 之后第一次出现的位置（为了让每个颜色都出现，需要在序列末尾把每个颜色都添加一遍），当且仅当对于所有 $i>r$ 都有 $p_i\le l$。

所以用线段树维护后缀 $p_i$ 最小值，在线段树上二分即可做到 $O(q\log n)$。