官方题解只能做到 $O(mn^3)$？玩的太差了。可以做到 $O(mn^2)$ 时间、$O\left(mn\right)$ 空间。

记 $M=m+1$。把能在不同合法染色中取不同颜色的位置称为关键位置。一个基础结构结论是：关键位置组成一个非空连续区间，其中的数严格递增或严格递减，唯一例外是两个相邻且相等的数。这也是已有题解使用的结构。

下面换成适合实现的刻画。

称前缀 $a_1,\ldots,a_r$ 是“向内的”，如果其中小于 $a_r$ 的数严格递增，大于 $a_r$ 的数严格递减，并且前面没有等于 $a_r$ 的数。设其最后一个数为 $v$，前面小于 $v$ 的最大值为 $L$，大于 $v$ 的最小值为 $U$，不存在时分别取 $0,M$。

加入下一个数 $x$ 时，只有 $L< x< v$ 或 $v< x< U$ 能继续保持向内。前一种情况把旧的 $v$ 放入递减序列，后一种情况把旧的 $v$ 放入递增序列。因此，最长向内前缀可以线性扫描求出。

设它结束于 $r$。一个完整数组完美，当且仅当满足下面对应的结构。

当 $r=n$ 时，不需要其他条件。当 $a_{r+1}=a_r=v$ 时，后面的数必须分成“小于 $v$ 的严格递减序列”和“大于 $v$ 的严格递增序列”。当 $a_{r+1}< v$ 时，必须有 $a_{r+1}\le L$，并且后缀的小数严格递减、大数严格递增，所有大数严格大于 $v$。$a_{r+1}>v$ 的情况完全对称，要求 $a_{r+1}\ge U$。

这里把第一次不再向内的位置称为交叉。除了相邻相等的情况外，$r$ 正是最后一个关键位置，因此上述划分不会重复计数。

最大得分也可以在这里确定。假设关键区间严格递增，则其中至多一个数染绿。将染绿的位置向右移动，其绿色贡献不减，而失去的红色贡献不增，所以最优方案一定是前面的关键位置都染红，只有最后一个关键位置需要比较两种颜色。严格递减时同理。

于是，在中心 $v=a_r$ 之前，小数染红、大数染绿；在它之后，小数染绿、大数染红。若中心之前共有 $x$ 个小数、$y$ 个大数，中心的最优贡献为 $\max(xv,y(M-v))$。相邻两个中心都等于 $v$ 时，它们必须一红一绿，合计贡献为 $xv+y(M-v)$。

还有一个很有用的性质：交叉后的数只会与交叉前的数产生得分贡献，后缀内部的点对贡献全部为零。

用微分递推消掉一次枚举

令 $s=n-t$。先讨论最主要的情况：中心位于尚未确定的部分，中心之后首先出现一个小数。另一方向只需把所有数替换成 $M-a_i$，同时交换红绿，得分保持不变。

固定中心值 $v$。已经给定的前缀必须相对于 $v$ 向内，记其中小数、大数的数量为 $X,Y$，最后一个小数、最后一个大数为 $L,U$，前缀已经产生的得分为 $S_0$。再记 $h=v-L-1$、$H=U-v-1$、$B=m-v$。

在给定前缀与中心之间，放入 $i$ 个小数和 $j$ 个大数。中心之后还有 $q=s-1-i-j\ge1$ 个数。前面两条序列交错的方式数为 $\binom{i+j}{i}$，前面大数的选法为 $\binom Hj$。

设中心之前的最大小数为 $d$。当 $i=0$ 时只能有 $d=L$；当 $i>0$ 时，小数的选法为 $\binom{d-L-1}{i-1}$。后缀若有 $k$ 个小数，则它们从 $[1,d]$ 中选择，其余大数从 $[v+1,m]$ 中选择，而且后缀的第一个位置必须属于小数序列。因此，对固定的 $d$，后缀方案数为 $\sum_{k=1}^q\binom{q-1}{k-1}\binom dk\binom B{q-k}$。

直接反复计算这个和，会多出一次长度枚举。

定义形式多项式 $P_a(z)=\sum_{k\ge0}\binom ak z^k/k!$，再定义 $S_0^{L,v}(z)=P_L(z)$，以及 $i\ge1$ 时的 $S_i^{L,v}(z)=\sum_{d=L+1}^{v-1}\binom{d-L-1}{i-1}P_d(z)$。暂时省略上标。

这样，固定 $i,q$ 后，需要的后缀计数就是 $A_{i,q}=(q-1)![z^{q-1}]P_BS_i'$。完整方案数再乘 $\binom{i+j}{i}\binom Hj$。

关键是，$S_i$ 并不是一组任意的多项式。由帕斯卡恒等式可得 $P_{a+1}'=P_a'+P_a$，对定义中的求和做一次离散分部求和，就得到

$$ S_{i+1}=\binom hiP_v'-S_i'-S_i. $$

但只递推 $S_i$ 还不够，因为我们需要的是 $P_BS_i'$。如果每次再乘 $P_B$，仍然会回到三次复杂度。

为此同时维护 $F=P_BS$ 和 $G=P_B'S$。直接比较系数，可以验证 $P_B$ 满足 $zP_B''+(1+z)P_B'-BP_B=0$。利用这个关系消掉 $P_B''$，就能把 $(P_BS,P_B'S)$ 在线性时间内变成 $(P_BS',P_B'S')$。具体地，若变换后的系数为 $\widehat F_k,\widehat G_k$，则

$$ \widehat F_k=(k+1)F_{k+1}-G_k,\qquad \widehat G_k=(k+2)G_{k+1}+G_k-BF_{k+1}. $$

代码把这个操作写成 differentiate。于是，维护一对乘积后，前面的 $S_i$ 递推也只需逐系数加减。初始化时计算常数个多项式乘积，需要 $O(s^2)$；随后 $O(s)$ 次递推，每次 $O(s)$，仍然是 $O(s^2)$。

中心贡献 $\max((X+i)v,(Y+j)(M-v))$ 在枚举 $i,j$ 时直接乘进去即可。比较在普通整数上进行，比较完才取模。

剩下需要证明的是，其他得分贡献也能用常数个这样的递推求出来。

记 $T(d)=d(d+1)/2$，并令 $\alpha$ 为给定前缀中所有小数的 $T(a)$ 之和，$\beta$ 为给定前缀中所有大数的 $T(M-a)$ 之和。再定义

$$ g_L(d)=\sum_{b=L+1}^{d}\sum_{x=b+1}^{d}x =\frac{d(d+1)(2d-3L-2)+L(L+1)(L+2)}6. $$

这个三次多项式表示：从前面的小数值域中选一个数，再从后面的小数值域中选一个更大的数，其得分之和。

交叉前的贡献。 固定最大小数 $d$ 后，新加入的小数产生的平均得分为 $i(Y+j/2)(M-L)-(d-L)\bigl(Y(i+1)/2+j(2i+1)/6\bigr)$。这是关于 $d$ 的一次式。新加入的大数产生的平均得分为 $jU(X+i/2)-(U-v)j\bigl(X/2+i(2j+1)/(6(j+1))\bigr)$，与 $d$ 无关。

这两个式子可以通过顺序统计量得到。例如，固定最大值为 $d$ 的 $i$ 个小数中，第 $p$ 个数的期望为 $L+p(d-L)/i$；在均匀交错中，它前面的新增大数数量期望为 $jp/(i+1)$。将各个位置的贡献相加即可，最终的式子不需要除以 $i$。

因此，除了 $A_{i,q}$，只需要额外统计带权和中的权值 $d$。

定义算子 $\mathcal E f=zf''+(1+z)f'$。它满足 $\mathcal E P_d=dP_d$，所以只需把 $S_i$ 替换为 $\mathcal ES_i$，便加入了权值 $d$。在已经维护的二元组上，应用 $\mathcal E$ 只需要两次 differentiate 和逐系数加减，仍是线性时间。

交叉后的小数贡献。 固定 $d$ 后，对所有小数值域中的点对求和，给定前缀提供的权值是 $XT(d)-\alpha$，新增前缀提供的权值是 $g_L(d)$。对应的生成多项式为

$$ K_i= \bigl(XT(\mathcal E+1)-\alpha\bigr)S_i^{L-1,v-1} +[i\ge1]\,g_L(\mathcal E+1)S_{i-1}^{L,v-1}. $$

为什么出现 $\mathcal E+1$？因为固定一个后缀小数被选中后，其余 $k-1$ 个小数的选法变成 $\binom{d-1}{k-1}$，对应多项式变成 $P_{d-1}$；此时 $\mathcal E+1$ 才表示原来的 $d$。

为什么第二项的参数改变了？因为指定一个新增前缀小数参与贡献后，剩余前缀的选法变成 $\binom{d-L-2}{i-2}$，恰好对应 $S_{i-1}^{L,v-1}$。当 $i=1$ 时，这一项自动为零，因为 $g_L(L+1)=0$。

这里的权值最高只有三次，所以只需常数次应用 $\mathcal E+1$。这一部分的贡献为 $(q-1)![z^{q-1}]P_BK_i$，再乘前缀交错数及前缀大数选法。若 $X=0$，第一项直接省略，不需要定义 $P_{-1}$。

交叉后的大数贡献。 记 $\Delta_a=P_a-P_{a-1}$，并单独规定 $\Delta_0=0$。固定一个后缀大数被选中后，对应多项式由 $P_B$ 变成 $\Delta_B$。

所有前缀大数与后缀大数之间的值权之和为 $W=\binom Hj(YT(B)-\beta)+\binom{H-1}{j-1}g_{M-U}(B)$，因此这一部分为 $\binom{i+j}{i}W(q-1)![z^{q-1}]\Delta_BS_i'$。额外维护一份参数为 $B-1$ 的乘积递推，与原结果相减即可。

到这里，中心之后首先出现小数的全部计数与得分，都只用了常数个长度为 $O(s)$ 的二元组，每个中心值的总时间为 $O(s^2)$。

最后处理另外几类边界。

中心位于数组最后时，没有后缀，直接枚举 $i+j=s-1$。前面小数不再固定最大值，其平均贡献为 $i(M-L)(Y+j/2)-(v-L)i\bigl(Y/2+j(2i+1)/(6(i+1))\bigr)$；大数仍用前面的公式。

中心后面紧接一个相等的数时，剩余后缀自由交错。若两侧值域大小为 $A,B$，长度为 $q$，则方案数是 $q![z^q]P_AP_B$，指定某个小数或大数被选中的方案数分别是 $q![z^q]\Delta_AP_B$ 和 $q![z^q]P_A\Delta_B$。用组合数直接预处理这三张表，共 $O(s^2)$。两个中心的贡献改成 $(X+i)v+(Y+j)(M-v)$，其余得分仍按前面的小数、大数点对求和计算。

若交叉已经发生在已知前缀中，线性验证后面的固定元素；合法时只剩两个互不相交的值域，直接使用上述后缀计数。若中心恰好是最后一个已知元素，令 $i=j=0$，分别处理向下交叉、向上交叉、相邻相等即可。

若已知前缀尚未交叉，未来中心只能落在扫描维护的 $(L,U)$ 中，且不能等于 $a_t$。中心在 $a_t$ 左侧或右侧时，已知前缀的统计量分别固定，因此也不需要为每个中心重新扫描前缀。

总共有 $O(m)$ 个中心值，每个处理 $O((s+1)^2)$，加上线性扫描和组合数预处理，总时间为 $O(t+m(s+1)^2)$。递推中的长度维可以滚动，只保存组合数、多项式表和常数个二元组，空间为 $O(m(s+1))$。实现预处理到 $s+6$ 阶，并在每次递推后同步缩短安全截断长度。

提交记录：https://qoj.ac/submission/2937814 统一省选的题就是简单。