给你一个下标从 0 开始的整数数组 nums 它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件我们称它是一个特别的排列：对于 0 = i n - 1 的下标 i 要么 numsi numsi+1 == 0 要么 numsi+1 numsi == 0 。请你返回特别排列的总数目

由于题目要求的是排列，因此我们可以考虑使用回溯算法来枚举排列。具体地，我们从左到右依次填补每一个位置的数，每次填补时考虑所有未被填过的数，如果该数能够满足特别排列的条件，则填补该数。如果填完了所有位置，则说明这是一个合法的特别排列。

为了加速判断特别排列的条件，我们可以事先计算出一个布尔数组 $g_{i,j}$，表示是否存在 $i$ 到 $j$ 的特别排列。具体地，状态转移方程为：

$$ g_{i,j} = \begin{cases} \text{true}, &\text{if } i = j \ \text{false}, &\text{if } i > j \ g_{i,j-1} \land \big(\text{nums}[j] \bmod \text{nums}[j-1] = 0\big), &\text{if } i < j \ g_{i+1,j} \land \big(\text{nums}[i] \bmod \text{nums}[i+1] = 0\big), &\text{otherwise} \end{cases} $$

最终的答案即为所有合法的特别排列的个数。时间复杂度为 $O(n^22^n)$，其中 $n$ 是数组的长度