You are given a 0-indexed integer array nums containing ndistinct positive integers. A permutation of nums is called special if:
For all indexes 0 <= i < n - 1, either nums[i] % nums[i+1] == 0 or nums[i+1] % nums[i] == 0.
Return the total number of special permutations. As the answer could be large, return it modulo 109 + 7.
Example 1:
Input: nums = [2,3,6]
Output: 2
Explanation: [3,6,2] and [2,6,3] are the two special permutations of nums.
Example 2:
Input: nums = [1,4,3]
Output: 2
Explanation: [3,1,4] and [4,1,3] are the two special permutations of nums.
Constraints:
2 <= nums.length <= 14
1 <= nums[i] <= 109
Solutions
Solution 1: State Compression Dynamic Programming
We notice that the maximum length of the array in the problem does not exceed $14$. Therefore, we can use an integer to represent the current state, where the $i$-th bit is $1$ if the $i$-th number in the array has been selected, and $0$ if it has not been selected.
We define $f[i][j]$ as the number of schemes where the current selected integer state is $i$, and the index of the last selected integer is $j$. Initially, $f[0][0]=0$, and the answer is $\sum_{j=0}{n-1}f[2n-1][j]$.
Considering $f[i][j]$, if only one number is currently selected, then $f[i][j]=1$. Otherwise, we can enumerate the index $k$ of the last selected number. If the numbers corresponding to $k$ and $j$ meet the requirements of the problem, then $f[i][j]$ can be transferred from $f[i \oplus 2^j][k]$. That is:
$$
f[i][j]=
\begin{cases}
1, & i=2^j\
\sum_{k=0}^{n-1}f[i \oplus 2^j][k], & i \neq 2^j \textit{ and nums}[j] \textit{ and nums}[k] \textit{ meet the requirements of the problem}\
\end{cases}
$$
The final answer is $\sum_{j=0}{n-1}f[2n-1][j]$. Note that the answer may be very large, so we need to take the modulus of $10^9+7$.
The time complexity is $O(n^2 \times 2^n)$, and the space complexity is $O(n \times 2^n)$. Here, $n$ is the length of the array.