T1. 排水系统

拓扑排序 + 高精。

T2. 字符串匹配

题意：给你一个长度为字符串 $S$ ，求对 $S$ 的划分个数，使得 $S=(AB)^iC$ ，其中 $(s)^i$ 表示将 $s$ 复制 $i$ 遍拼接， $A,B,C$ 均为非空字符串。

多组数据。 $T\le5$ ， $|S|\le2^{20}$ 。

枚举倍数调和级数是 $O(n\ln n+26n)$ 或者 $O(n\ln n\log 26)$ 的。

扩展 KMP 可以做到 $O(n)$ 。

T3. 移球游戏

题意：有 $n+1$ 根柱子，前 $n$ 根柱子上每根有 $m$ 个球。所有 $n\times m$ 个球共 $n$ 种颜色，每种颜色 $m$ 个。

你可以对当前局面进行以下操作若干次：

将某柱子顶端的球移到另一个柱子的顶端。

最后使得将相同颜色的球最后全部放置在相同柱子上。操作过程中需要满足：

原来的柱子上至少有 $1$ 个球。且

新的柱子上至多有 $m-1$ 个球。

请你给出一种操作次数 $\le820000$ 的方案。保证方案存在。

$2\le n\le50$ ， $2\le m\le400$ 。

我们定义『切分』操作为：对于两根柱子 $X,Y$ ，我们可以用一根满柱 $H$ 和一根空柱 $E$ ，将它们的较小的一半元素放在 $X$ ，较大的一半元素放在 $Y$ 。这一步操作次数 $\le5m$ 。

考虑归并排序，按照 $\max{X}$ 的大小归并，这样会有 $\le L$ 次切分和 $\le2L$ 次整体移动，总操作次数 $7n\left\lceil\log_2n\right\rceil m=840000$ ，优化一下切分操作就能过了。

注意特判 $n=2$ ，因为此时切分操作选不出来 $H$ 。

代码还在咕咕咕。

T4. 微信步数

题意： $k$ 维空间内的每一个点可以用 $(a_1,a_2,\cdots,a_k)$ 表示，规定地图中第 $i$ 维的坐标是整数，且满足 $1\le a_i\le w_i$ 。

在 $P=\prod_{i=1}^kw_i$ 天的时间中，小 C 每天会选择一个不同的坐标出发，并循环地走 $n$ 步直到出界。第 $i$ 步用两个整数 $c_i,d_i$ 表示，代表小 C 会将当前坐标的第 $c_i$ 维加上 $d_i$ （ $d_i\in\{1,-1\}$ ）。

求 $P$ 天移动的总步数，答案对 $10^9+7$ 取模。若出现某天小 C 无法结束移动，输出 -1。

两类数据范围：

$n\le5\times10^5$ ， $k\le10$ ， $w\le10^6$ 。

$n\le5\times10^5$ ， $k\le3$ ， $w\le10^9$ 。