考虑要求分数的绝对值 $\leq 3$ 是一个有趣的限制，简单的模拟马上可以发现奇数轮取值只有 $\pm 1,\pm 3$ 而偶数轮只有 $\pm 2,0$
一个非常无脑的想法是直接记录每种数的个数，但是状态数显然爆炸，考虑能不能少记录一点
容易发现的规律是和始终为 $0$ 且没种数的总个数为 $2n$ 让我们以此对状态简化
对于偶数轮，那么我们知道偶数轮 $-2$ 和 $2$ 的个数相等，同时因为知道总和，所以我们只需要知道
2/-2的个数 $i$ 就知道了整个状态对于奇数轮，四个未知数，两个方程，所以知二求二，为了后面的方便，记录
3/-3的个数为 $j,k$
那么每轮枚举就是 $n^3$ 假设我们知道转移系数，那么复杂度就是 $\mathcal{O}(kn^3)$ 然而，你发现系数不太好说
主要是很难做到不重不漏，枚举状态 $i,j,k$ ，我们先考虑偶数向奇数转移
那么一个特点是 $\pm 3$ 只能由两个 $\pm 2$ 生成，所以枚举状态后就已经知道
22,-2-2的个数了考虑先计算这部分的系数，也就是 $\binom{i}{2j}\binom{i}{2k}$ 选出的系数乘两两匹配的方案，可以手玩发现是前 $x$ 项奇数乘积
把奇数乘积记做 $bc_i$ 那么系数是 $\binom{i}{2j}\binom{i}{2k}bc_jbc_k$
然后对于剩下的部分，因为
22 --> 31所以我们需要的 $\pm 1$ 的个数是有变化的，所以要重新计算但是你注意到我们这个匹配其实知道一边另一边是可以算出来的，所以我们只需要去做剩下 $2n-2i$ 个 $0$ 和 $i-2j,i-2k$ 个 $-2,2$ 的匹配
怎么计算才能不重不漏？考虑现在的选择是
0-2,00,02,-22(显然，你不能再匹配22,-2-2了)考虑到加入我们先把
-22解决了，我们就每次都需要加一个 $0$ 这样我们就可以认为 $0$ 有序添加到末尾，与其匹配的0/2/-2有序选择一个匹配考虑设 $f_{i,j,k}$ 表示 $i,j,k$ 个 $0,-2,2$ 那么初始化 $f_{0,i,i}=i!$ 即一边固定，另一边随意排列再依次匹配
转移即 $f_{i+2,j,k}\leftarrow f_{i,j,k}(i+1)$ 其它类似
最后总的系数是 $\binom{i}{2j}\binom{i}{2k}bc_jbc_kf_{2n-2i,i-2j,i-2k}$
接下来考虑奇数轮到偶数轮
首先并没有唯一生成了，但是我们还是考虑 $\pm 2$ 因为它们更难生成
考虑能生成 $-2$ 中有
-1-1,-1-3,1-3,3-3那么只要有一个-3就一定有一个-2所以我们还额外需要 $i-j$ 个-2这时需要
-1-1,-1-3考虑去 DP 它，相当于是若干 $-1,-3$ 去凑若干组-1-1或-1-3设 $g_{i,j,k}$ 表示 $-1,-3$ 有 $i,j$ 个，完成了 $k$ 组两个匹配中之一怎么转移？有
-1-1,-1-3和不匹配-1,-3四种选择，类似 $f$ 的算法，我们先处理不匹配-3的方案即 $g_{0,i,0}=1$ 接下来和上面一样每次加入一个无序的
-1然后 不匹配/匹配 -1/匹配 -3 则有 $g_{i+2,j,k+1}\leftarrow g_{i,j,k}(i+1)$ 和其它而对于 $1,3$ 凑 $2$ 是完全一样的，可以用同一个 DP ，考虑剩下的部分，发现可以随便放，只需要正负匹配，所以就是剩下的阶乘
最后总的系数是 $(n+j+k-2i)!g_{n+k-2j,j,i-j}g_{n+j-2k,k,i-k}$
那么复杂度就是 $\mathcal{O}(kn^3)$
