官方题解只能做到 $O(n^3)$？玩的太差了。这道题可以做到矩阵乘法级别的时间复杂度，不必停留在 $O(n^3)$ 区间 DP：若 $n\times n$ 矩阵乘法能够在 $O(n^\omega)$ 时间内完成，其中 $\omega>2$，下面的算法就是 $O(n^\omega + n^2 \log n)$。
题目给出非降序序列 $a$，要求统计有多少个不同序列能够通过“选择一个当前区间，允许整体翻转，再切成两段”的过程变成 $a$。题目中 $n\le 500$，答案模 $998244353$。([QOJ][1])
称能够通过上述过程排成非降序的序列为合法序列。
考虑第一次分割。合法序列有一个递归刻画：单个元素合法；对于两个非空合法序列 $u,v$，若 $u$ 中的所有元素都不大于 $v$ 中的所有元素，则 $uv$ 与 $vu$ 都合法，而且所有长度大于一的合法序列都能这样得到。
这里用到了一个简单事实：合法序列翻转后仍然合法。只需把第一次操作中的“翻转或不翻转”取反，就能到达原来第一次分割前的状态。
另一个后面需要用到的性质是：合法序列的任意非空子序列仍然合法。在上述递归分解树上删除不需要的叶子，并压掉只有一个非空孩子的节点即可。这保证了我们选取的分割不必是某一棵原始分解树上的分割。
对于一个序列的某个分割位置，如果左侧所有元素都不大于右侧所有元素，称它为正向切口；如果左侧所有元素都不小于右侧所有元素，称它为反向切口。长度大于一的合法序列至少有一种切口。
以下使用边界下标 $0\le i< j\le n$，用 $(i,j]$ 表示多重集合 $a_{i+1},\ldots,a_j$。定义 $F_{i,j}$ 为这个多重集合能组成的合法序列数，$G_{i,j}$ 为其中没有正向切口的合法序列数。
先计算至少存在一个正向切口的序列数，记作 $P_{i,j}$。
对每个这样的序列，选取它的第一个正向切口。若左侧长度为 $k-i$，那么左侧的多重集合一定是 $(i,k]$，右侧一定是 $(k,j]$。左侧不能再有正向切口，否则整个序列会有更早的正向切口；右侧只需合法。因此
$P_{i,j}=\sum_{i< k< j}G_{i,k}F_{k,j}$。
反过来，任取这样一个左侧和右侧拼接，得到的第一个正向切口一定就是 $k$。所以这个式子没有重计数，重复元素也不会破坏它：正向切口之前有多少个元素，就唯一确定了取走排序后最小的多少个元素。
翻转是一个双射，因此至少存在一个反向切口的序列数也等于 $P_{i,j}$。问题在于：同时具有两种切口的序列被算了两次。
对于不全相等的序列，有如下关键结论：
同时具有正向切口和反向切口，当且仅当首尾元素相等，且这个共同的值是整个序列的最小值或最大值。
证明并不复杂。设正向切口位于 $p$，反向切口位于 $q$。若 $p=q$，两边所有元素只能全部相等，与假设矛盾。
若 $p< q$，把序列写成三个非空部分 $ABC$。正向切口给出 $A\le B$、$A\le C$，反向切口给出 $A\ge C$、$B\ge C$。于是 $A,C$ 中的所有元素必须等于同一个值，且它是全局最小值。因此首尾都是最小值。$q< p$ 时同理，首尾都是最大值。
反过来，首尾同为最小值时，第一个元素之后是正向切口，最后一个元素之前是反向切口；首尾同为最大值时则相反。
现在可以精确计算交集。首尾都是最小值，要求最小值至少出现两次；删除这两个端点之后，中间可以是剩余多重集合组成的任意合法序列。删除保持合法性，而给合法序列两端补上最小值，也保持合法性。最大值的情况相同。
所以对于不全相等的区间，交集大小为
$I_{i,j}=[a_{i+1}=a_{i+2}]F_{i+2,j}+[a_{j-1}=a_j]F_{i,j-2}$。
最小值和最大值不同，因此这里的两类互不相交。于是 $F_{i,j}=2P_{i,j}-I_{i,j}$，而 $G_{i,j}=F_{i,j}-P_{i,j}=P_{i,j}-I_{i,j}$。
全相等的区间直接处理：$F_{i,j}=1$；长度为一时 $G_{i,j}=1$，长度大于一时 $G_{i,j}=0$。
至此得到了一个正确的 $O(n^3)$ 区间 DP，但还可以继续加速。
二、把整个递推改写成分块矩阵运算
把 $F,G$ 看作 $(n+1)\times(n+1)$ 严格上三角矩阵。对角线为零，不把空序列记成一个方案。这样上一节的求和就是普通矩阵乘法 $P=GF$。
再定义两个固定的严格上三角矩阵。$H_{i,j}=1$ 当且仅当 $(i,j]$ 非空且全相等，否则为零；$E$ 只有第二条上对角线可能非零，具体为 $E_{i,i+2}=[a_{i+1}=a_{i+2}]$。
那么两项交集修正分别就是 $EF$ 和 $FE$。把全相等区间的边界情况也合并进去，可以得到适用于所有位置的统一递推：
$$ \begin{aligned} F&=H-2E+2GF-EF-FE,\\ G&=H-2E+GF-EF-FE. \end{aligned} $$
不全相等的区间显然与上一节一致。对于全相等的区间，可以直接验证：长度为一时只有 $H$ 贡献；长度为二时初值 $H-2E=-1$，而 $GF=1$，最终得到 $F=1,G=0$；长度至少为三时，$GF=EF=FE=1$，同样得到 $F=1,G=0$。
因此，可以先将两个矩阵都初始化为 $H-2E$，再按照依赖顺序累加乘积贡献。初始化时出现 $-1$ 没有问题：这些位置尚未完成递推，并不是最终的计数值。
这里不能直接做一次完整矩阵乘法，因为乘法的输入也是我们正在计算的结果。需要利用严格上三角依赖，按块求解。
设 $I,K,J$ 是三个从左到右互不相交的等长下标区间。一次 update(I,K,J) 负责累加所有满足 $i\in I,k\in K,j\in J$ 的转移。
先计算 $T=G[I,K]F[K,J]$，向 $F[I,J]$ 加上 $2T$，向 $G[I,J]$ 加上 $T$；再从两者中减去 $E[I,K]F[K,J]+F[I,K]E[K,J]$。
一次更新只需要一次一般矩阵乘法。由于 $E$ 只有第二条上对角线非零，另外两项直接复制、减去相应元素即可，耗时不超过 $O(|I|^2)$。
现在考虑怎样完成一个交叉矩形 $I\times J$，其中 $I$ 在 $J$ 左侧，两个区间等长。调用时，$I,J$ 各自内部的上三角块已经算完；位于二者之间、但不属于 $I\cup J$ 的中间点，其贡献也已经由外层加入。
将它们分别二分成 $I_1,I_2$ 和 $J_1,J_2$。正确的顺序是先左下，再左上和右下，最后右上：
solve(I2, J1)
update(I1, I2, J1)
update(I2, J1, J2)
solve(I1, J1)
solve(I2, J2)
update(I1, I2, J2)
update(I1, J1, J2)
solve(I1, J2)例如，完成左下块 $I_2\times J_1$ 之后，就可以将中间点在 $I_2$ 中的贡献加入左上块，将中间点在 $J_1$ 中的贡献加入右下块。等这两块完成，再把它们分别对右上块的贡献加入。
这个顺序保证每次矩阵乘法的两个输入块都已经完成。每个三元组 $i< k< j$ 恰好由一次 update 负责：在递归中，只有当中间点 $k$ 首次落到端点块之外时才加入该贡献，之后不会再次计算。因此，这里使用的是普通加法计数，不依赖任何布尔运算或“重复加入也没关系”的性质。
对于一个对角块，先递归完成左右两个对角子块，再按上述方式完成它们之间的交叉矩形即可。最后的答案是 $F_{0,n}$。
设矩阵乘法复杂度为 $M(s)=O(s^\omega)$。完成交叉矩形的复杂度满足 $R(s)=4R(s/2)+4M(s/2)+O(s^2)$，所以 $R(s)=O(s^\omega)$；完成对角块的复杂度满足 $D(s)=2D(s/2)+R(s/2)$，所以仍是 $D(s)=O(s^\omega)$。将 $n+1$ 补到二的幂只改变常数。
