官方题解只能做到 $O(n^6)$ ~ $O(n^8)$？玩的太差了。这题可以先得到一个 $O(n^4)$ 时间、$O(n^3)$ 空间的算法，再将权值预处理和主动态规划同时加速，得到 $O(n^{\omega(1,2,1)+\varepsilon})$ 的理论时间上界，$\varepsilon>0$ 任意，空间仍为 $O(n^3)$。这里 $\omega(1,2,1)$ 是计算一个 $n\times n$ 矩阵与一个 $n\times n^2$ 矩阵之积的指数；采用已发表的 $\omega(1,2,1)\le 3.250035$ 上界，例如可以得到 $O(n^{3.251})$ 时间算法。下面先推导计数方法，再说明如何严格处理动态规划的依赖，实现这个低于四次的复杂度。([arXiv][1])
把强连通集合转化为带权计数
题目允许重复经过位置，也允许一步不走。因此，一个非空集合 $S$ 能成为某次闭合游走恰好访问的点集，当且仅当它的诱导子图强连通：必要性显然；充分性则可以固定起点，依次走到每个点并返回。题目要求的就是强连通非空点集数量，而不是简单环数量。原题的范围为 $n\le 50$，所有计算对 $998244353$ 取模。([QOJ][2])
首先注意一个陷阱：集合中最左点和最右点互相可达，不意味着整个集合强连通。
例如三个点的移动区间分别为 $[1,3],[2,2],[1,3]$。点 $1,3$ 互相可达，但集合 ${1,2,3}$ 不合法，因为点 $2$ 无法离开自己。直接维护两个端点之间的可达性会多算。
不过，多算的集合有一个很好的结构。
考虑一个最左点和最右点互相可达的集合 $T$，令 $C$ 为这两个端点所在的强连通分量。由于每个点的出边指向一个包含自身的区间，$C$ 能到达 $T$ 中的所有点。具体地，取一条从最左点到最右点的路径；对于任意夹在中间的点 $x$，这条路径必然经过 $x$，或者存在一步从 $x$ 左侧跳到右侧。这一步的移动区间覆盖 $x$，于是 $x$ 可达。
设 $l< r$ 是 $C$ 中相邻的两个点。对于夹在它们之间、属于 $T\setminus C$ 的点 $i$，必须有 $a_i>l$ 且 $b_i< r$。否则 $i$ 能直接走到 $l$ 或 $r$，便能返回 $C$，与 $i\notin C$ 矛盾。
反过来，给定任意强连通集合 $C$，在每对相邻点 $l< r$ 之间，任意加入一些满足 $a_i>l,\ b_i< r$ 的点，两个端点仍然互相可达，而加入的点不可能返回 $C$：它们的出边始终被限制在同一个开区间 $(l,r)$ 内。
因此，所有端点互相可达的集合，都可以唯一分解成一个强连通的“核心” $C$，以及每个相邻核心点之间独立选择的额外点。记这些额外点的候选集合为 $U(l,r)={i\mid l< i< r,\ a_i>l,\ b_i< r}$。
接下来给每一对 $l< r$ 构造权值 $w_{l,r}$。对于递增排列的非空集合 $T={t_1< \cdots< t_k}$，定义其权值为 $W(T)=\prod_{h=1}^{k-1}w_{t_h,t_{h+1}}$，单点集合的权值为 $1$。
我们要求，每个间隙中所有添加方式的权值和恰好为 $1$，也就是
$$ \sum_{\substack{X\subseteq U(l,r)\\ \{l\}\cup X\cup\{r\}=\{x_0< x_1 < \cdots< x_{k+1}\}}} \ \prod_{h=0}^{k}w_{x_h,x_{h+1}}=1. $$
这个要求唯一确定了所有 $w_{l,r}$。因为 $X=\varnothing$ 对应的项就是 $w_{l,r}$，而其余项只会使用跨度严格小于 $r-l$ 的权值，所以按跨度递增计算即可。
普通实现中，对固定的 $l,r$，在 ${l,r}\cup U(l,r)$ 上做一次递增路径动态规划：暂时令 $w_{l,r}=0$，设 $q_l=1$，按照下标递增计算 $q_v=\sum_{u< v}q_uw_{u,v}$，最后赋值 $w_{l,r}=1-q_r$。这里的路径属于辅助有向无环图，每个较小下标都向每个较大下标连一条权为 $w$ 的边，不要求它是原图中允许的一步移动。每对端点耗时 $O(n^2)$，总计 $O(n^4)$。
这些权值的作用是：固定一个强连通核心 $C$，把所有以它为核心的扩展集合 $T$ 的权值加起来。不同间隙相互独立，而每个间隙的权值和都为 $1$，所以这些集合的总权值恰好也是 $1$。
于是，原问题等价于：
枚举所有最左点与最右点互相可达的非空集合 $T$，求它们的权值 $W(T)$ 之和。
权值可以为负，或者在模意义下表现为很大的数；它们不是概率，也不要求每个合法集合自身的权值为 $1$。我们保证的是，具有同一个强连通核心的所有扩展集合，总权值为 $1$。
用三个参数维护端点互相可达
现在按下标递增选择集合中的点。
对于相邻的已选点 $x< y$，考虑它们之间的切口。从最左点能到达最右点，当且仅当每个切口都有从左侧指向右侧的边；反方向同理，需要每个切口都有从右侧指向左侧的边。
这些条件的充分性依赖于区间出边结构。例如，从右往左扫描，如果右侧已选点中某个点的 $a$ 不大于下一个待加入的点，那么该点便可达；如此不断向左扩展即可。
设动态规划状态为 $f_{i,B,m}$，表示当前最后一个已选点为 $i$，并且最左点已经能够到达所有已选点的集合权值和。其中 $B$ 是所有已选点的 $b$ 的最大值；$m$ 是尚未被右向左的边跨过的切口中，最小的左端点。如果所有切口都已满足，则约定 $m=i$。
先看向右的可达性。假设下一个选择的点为 $j>i$，那么必须有 $j\le B$。这个条件成立时，原来必有一个已选点能直接走到 $j$；反之，若 $j>B$，所有已选点都无法跨过这个新切口，整个集合的最左点就不可能到达最右点。加入 $j$ 后，更新为 $B'=\max(B,b_j)$。
再看向左的可达性。新点 $j$ 能跨过左端点为 $x$ 的切口，当且仅当 $a_j\le x$。
如果 $a_j\le m$，那么所有未满足切口都被跨过，而且新产生的切口的左端点 $i$ 也不小于 $m$，所以全部条件满足，令 $m'=j$。否则，最小的未满足切口仍然是 $m$，令 $m'=m$。
这里也包含此前没有未满足切口的情况：此时 $m=i$，判断 $a_j\le m$，恰好就是判断新切口是否被跨过。
因此，对每个 $i< j\le B$，按照上述规则计算 $B',m'$，执行转移 $f_{j,B',m'}\mathrel{+}=f_{i,B,m}w_{i,j}$。每个单点集合提供初值 $f_{i,b_i,i}\mathrel{+}=1$，答案为 $\sum_i\sum_{B\ge i}f_{i,B,i}$。
只需要维护最小未满足切口，是因为后续某个点一旦能跨过它，就能同时跨过所有更靠右的未满足切口；而在此之前，无论其他切口是否满足，都不会改变这个最小值。
这个动态规划有 $O(n^3)$ 个状态，每个状态枚举下一个点，耗时 $O(n^4)$。加上前面的权值预处理，已经得到一个完整的 $O(n^4)$ 时间、$O(n^3)$ 空间算法。
但两部分的四次复杂度都可以继续降低。
同时加速权值预处理与主动态规划
先看主动态规划。把 $f_{i,B,m}$ 中的 $(B,m)$ 展平成一个长度为 $n^2$ 的向量，并定义“尚未处理新点限制”的贡献 $P_j[B,m]=\sum_{i< j}w_{i,j}f_{i,B,m}$。
得到 $P_j$ 之后，只需扫描所有 $(B,m)$，丢弃 $B< j$ 的项，再执行 $B'=\max(B,b_j)$ 以及前述 $m'$ 更新，就能得到 $f_j$。这一步只依赖新点 $j$，不再依赖上一个点 $i$。所有点的局部处理合计只需 $O(n^3)$。
剩下的任务是批量计算这些 $P_j$。按最后一个点的下标做分治：先求出左半部分的全部 $f_i$，再将左半部分对右半部分的贡献用一次矩阵乘法加入，最后递归右半部分。
SolveDP(V):
若 V 只有一个点 j：
将 P[j] 按 B'、m' 的规则转入 f[j]
f[j][b[j]][j] += 1
返回
将 V 平分为 L、R
SolveDP(L)
P[R] += transpose(w[L,R]) × f[L]
SolveDP(R)这里 $f[L]$ 的每一行对应一个左侧下标，每一列对应一个状态 $(B,m)$。每一对 $i< j$ 恰好在分治树上将它们分开的那一层被处理一次，所以没有漏算或重复计算。
不过，仅仅加速这一步是不够的，权值预处理仍然是 $O(n^4)$。下面把预处理也改成可以批量矩阵乘法的形式。
对任意 $\ell,i,j$，令 $E_\ell(i,j)=[a_i>\ell\text{ 且 }b_i< j]$。定义 $H_\ell(i,j)$ 为所有从 $i$ 开始、到 $j$ 结束的递增序列的权值和，要求除最后一个点 $j$ 外，序列上的每个点 $x$ 都满足 $a_x>\ell$ 且 $b_x< j$。
按序列的第二个点分类，令 $C_\ell(i,j)=\sum_{i< k< j}w_{i,k}H_\ell(k,j)$，便有
$$ w_{i,j}=1-C_i(i,j),\qquad H_\ell(i,j)=E_\ell(i,j)\bigl(1+C_\ell(i,j)-C_i(i,j)\bigr). $$
第一式就是先前的权值归一化条件：$C_i(i,j)$ 枚举间隙中至少选择一个额外点的情况。第二式则对应直接走到 $j$，或者先走到某个中间点 $k$。
这些转移只依赖跨度更小的状态。可以先初始化所有 $i< j$ 的 $w_{i,j}=1$、$H_\ell(i,j)=E_\ell(i,j)$，然后逐批加入各个分割点 $k$ 的贡献。
具体地，设 $I< K< J$ 是三个按位置先后排列的下标块，需要批量处理所有 $i\in I,k\in K,j\in J$。计算矩阵乘积 $D_{i,(\ell,j)}=\sum_{k\in K}w_{i,k}H_\ell(k,j)$，然后进行以下更新：
Update(I,K,J):
D = w[I,K] × H[K, 所有 (ell,j)，其中 j 属于 J]
对每个 i 属于 I、j 属于 J：
z = D[i,(i,j)]
w[i,j] -= z
对每个 ell：
H[ell][i,j] += E[ell][i,j] × (D[i,(ell,j)] - z)第二个矩阵只是把所有 $H_\ell[K,J]$ 横向拼接。这个更新正好给 $w$ 加入 $-C_i$ 的贡献，同时给 $H_\ell$ 加入 $E_\ell(C_\ell-C_i)$ 的贡献。
关键在于正确安排这些批量更新：参与乘法的两个较短区间必须已经算完。下面给出一种完整的分治顺序。为简化描述，可以将下标数补到二次幂，补出的点设为孤立点，且不参与最终计数。
设 Complete(A,B) 负责补完跨越两个等长下标块 $A< B$ 的状态。在调用它时，两个块各自内部的状态已经完成，位于这两个块以外的分割点贡献也已经加入。
SolveW(V):
若 V 只有一个点：返回
将 V 平分为 L、R
SolveW(L)
SolveW(R)
Complete(L,R)
Complete(A,B):
若 A、B 都只有一个点：返回
将 A 平分为 A1、A2
将 B 平分为 B1、B2
Complete(A2,B1)
Update(A1,A2,B1)
Complete(A1,B1)
Update(A2,B1,B2)
Complete(A2,B2)
Update(A1,A2,B2)
Update(A1,B1,B2)
Complete(A1,B2)可以把跨块状态看成一个矩形：先完成左下块 $A_2\times B_1$，再完成左上块和右下块，最后完成右上块。
例如，计算 $A_1\times B_2$ 时，位于中间的分割点分成 $A_2$ 和 $B_1$ 两类，分别由最后两次 Update 加入；它们需要的状态此时都已完成。继续递归后，每个三元组 $i< k< j$ 都恰好被处理一次。这个顺序只依赖“左右子区间先于大区间”的关系，并不需要假设转移满足额外的结合律。
最后分析复杂度。假设一个 $s\times s$ 矩阵与一个 $s\times s^2$ 矩阵相乘可以在 $O(s^\gamma)$ 时间完成，其中 $\gamma>3$。
对权值预处理，一个块长为 $s$ 的 Update 要计算 $s\times s$ 与 $s\times ns$ 的矩阵乘积。将后一矩阵的列分成 $O(n/s)$ 组，每组 $s^2$ 列，耗时为 $O(ns^{\gamma-1})$。同一尺度上共有 $O(n^2/s^2)$ 次这样的更新，因此该尺度的总时间为 $O(n^3s^{\gamma-3})$。由于 $\gamma>3$，对所有二次幂尺度求和由最大尺度主导，得到 $O(n^\gamma)$。
对主动态规划，一个左右块长为 $s$ 的分治节点，要计算 $s\times s$ 与 $s\times n^2$ 的矩阵乘积。按每组 $s^2$ 列拆开，耗时为 $O(n^2s^{\gamma-2})$。同一尺度有 $O(n/s)$ 个节点，总时间同样为 $O(n^3s^{\gamma-3})$，所有尺度合计也是 $O(n^\gamma)$。
所以，两部分合起来的时间为 $O(n^{\omega(1,2,1)+\varepsilon})$；主要数组 $H,f,P$ 都只有 $O(n^3)$ 个元素，矩阵乘法按块处理并复用临时空间即可。