环

我们不妨考虑按$0-n$顺序的前缀和，记作数组$D$。于是$D[i]$就表示环上按顺时针方向从$0$号车站到$i$号车站的距离总和。为了后面方便的推导，我们再假设环的总长度（也就是答案）为X，于是便可得到如下的不等式约束（箭头后方是差分约束的标准形式）：

由于相邻车站之间的距离是正整数，所以有：

$$D[i]+1\le D[i+1] \rightarrow D[i]-D[i+1]\le -1$$

不难发现$D[0]=0,D[n]=X$，所以我们又可以得到以下式子：

$$D[0]+X=D[n] \rightarrow D[0]-D[n]<=-X,D[n]-D[0]<=X$$

对于题目给的第一种条件，我们根据按照顺时针方向是否跨越过0号车站，分类讨论一下，也不难建立不等式关系：

$$1.S < T,D[T]-D[S]\ge L \rightarrow D[S]-D[T]\le -L$$

$$2.S>T,X+D[T]-D[S]\ge L \rightarrow D[S]-D[T]\le X-L$$

同理对于第二种条件，也可以获得以下不等式关系：

$$1.S < T,D[T]-D[S]\le L \rightarrow D[T]-D[S]\le L$$

$$2.S>T,X+D[T]-D[S]\le L \rightarrow D[T]-D[S]\le -X+L$$

这是一个经典的差分约束模型。所有不等式约束可以转化为图论中最短路的模型，如果出现负环则说明该不等式组无解。

在这道题中，我们由于设了一个未知数$X$，所以似乎无法直接求解。但是我们不难发现给定一个答案$X$，我们可以在转化的图上跑$bellman-ford$或者$spfa$来判断是否存在负环，从而判断该答案是否可行。但显然答案的范围可能很大，枚举验证的方法效率不高，我们不妨采用以下两种思路来解决问题。

不难发现最终的答案其实是在一个区间范围之内。于是我们如果设计出一个算法来判断一个不合法的X是低于下界还是高于上界，便可以进行二分求解出最终答案的区间。

对于一个不可行的答案，我们必然是可以在转化的图中找到一个负环的。于是我们不妨在求最短路的时候对于每一个值都记录下$X$的系数，那当我们找到一个负环的时候，我们也可以得到该负环数值中的X的系数。如果$X$的系数是正的话，那么显然我们只有将$X$调大，才能使该负环变成非负环，所以该X的值是低于答案的下界。同理，如果$X$的系数为负，可以得到该$X$高于答案的上界。值得注意的是，如果存在一个负环$X$的系数为$0$便会无解。

至此，我们可以使用二分算法，对上界和下界分别进行二分便可获得答案区间。时间复杂度为$O(nmlogn)$。

塔

我们注意到，一个方块的具体颜色对转移并没有太大影响，只要处理相邻颜色相同的就可以了（也可以理解为相对颜色）。

我们定义状态$dp_{i,k,a}$为高度为$i$，已经有$k$对相邻方块颜色相同，顶面相对颜色序列为$a$的方案数。

对于这里的序列$a$，我们以如下方法构造。先为顶层的方块编号，编号为$1$的方块的相对颜色定义为$1$。

然后以编号从小到大顺序枚举，如果当前方块的颜色在之前没有出现过，便将其编号为之前所有编号的最大值$+1$如果当前方块的具体颜色在以前出现过，就用以前出现的编号。

枚举最上面一层以及第二层的相对颜色，计算并更新相邻方块颜色相同的个数，直接叠加即可。

由于$H$过大，上文的算法显然会超时，因此我们要挖掘一些性质。

我们发现，转移方程是线性的，且$i$不会影响转移方程的形式。因此我们使用矩阵乘法+快速幂优化。

设$m=a的种类数\times(K+1)+1$。

我们可以构造$1\times m$矩阵$a$为每种状态初始的方案数，再定义$m\times m$矩阵$b$为动态规划中任意两种状态转移的常数，并用最后一个位置记录每一种高度的方案的和。

答案显然为$a\times b^h$的最后一项。

数

我们可以将题目中的要求转化为求$[1, T]$中满足$F(x) \equiv 0 \pmod{m}$的$x$个数。不难发现，$F(x) \mod{m}$仅与$x \mod{m}$和$k$的最大值有关，且假如$F(x) \equiv 0 \mod{m}$，那么就有$F(x + m) \equiv 0 \mod{m}$。因此，我们可以对所有的$x$按模$m$的余数进行分类，并计算出每一类$x$中满足条件的下界是多少，就能得到答案了。设这个下界为$A_m[]$。

此外，对于一组满足$(x, y) = 1$的$x$和$y$，不难利用$A_x[]$及$A_y[]$在$O(xy)$时间内构造出正确的$A_{xy}[]$。因此，现在的问题是，给定某个质数幂$p^c$，求出$A_{p^c}[]$的值。

考虑最直接的做法。对于每个$[0, p^c)$中的$i$，我们枚举$k$，计算出$i-k^2$中$p$的数量并累加，直到不少于$c$；$A_{p^c}[i]$就等于此时的$k^2 + 1$。由于$k$是$O(\sqrt{x})$的，总复杂度$O(m \sqrt{hi})$。

这样做的复杂度太高了，需要优化。注意到$c$的范围非常小，因此假如我们只枚举$i-k^2$中包含至少一个$p$的$i$和$k$，复杂度就会降低许多。因此，我们先枚举$k$，并维护一个$cnt[i]$表示到目前为止所有$i-k^2$中$p$的总个数；然后再枚举满足$i \equiv k^2 \mod{p}$的所有$i$，这样的$i$就只有$p^{c-1}$个了，单次求解的复杂度降至$O(p^{c-1} \sqrt{hi})$。

我们发现，每个$k$所影响的$i$以$p$为周期循环，$k$与$k+p$所影响的$i$是相同的；而每次每个受影响的$i$的$cnt[i]$至少会加一，因此有用的$k$只有$p*c$个。与算法二结合后，复杂度降至$O(p^{c-1} * p * c) = O(p^c * c)$，由于$c=O(\log m)$，总复杂度$O(m \log m)$，可以通过本题。