Question

2741. Special Permutations

中文文档

Description

You are given a 0-indexed integer array nums containing n distinct 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

class Solution:
  def specialPerm(self, nums: List[int]) -> int:
    mod = 10**9 + 7
    n = len(nums)
    m = 1 << n
    f = [[0] * n for _ in range(m)]
    for i in range(1, m):
      for j, x in enumerate(nums):
        if i >> j & 1:
          ii = i ^ (1 << j)
          if ii == 0:
            f[i][j] = 1
            continue
          for k, y in enumerate(nums):
            if x % y == 0 or y % x == 0:
              f[i][j] = (f[i][j] + f[ii][k]) % mod
    return sum(f[-1]) % mod

class Solution {
  public int specialPerm(int[] nums) {
    final int mod = (int) 1e9 + 7;
    int n = nums.length;
    int m = 1 << n;
    int[][] f = new int[m][n];
    for (int i = 1; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          int ii = i ^ (1 << j);
          if (ii == 0) {
            f[i][j] = 1;
            continue;
          }
          for (int k = 0; k < n; ++k) {
            if (nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0) {
              f[i][j] = (f[i][j] + f[ii][k]) % mod;
            }
          }
        }
      }
    }
    int ans = 0;
    for (int x : f[m - 1]) {
      ans = (ans + x) % mod;
    }
    return ans;
  }
}

class Solution {
public:
  int specialPerm(vector<int>& nums) {
    const int mod = 1e9 + 7;
    int n = nums.size();
    int m = 1 << n;
    int f[m][n];
    memset(f, 0, sizeof(f));
    for (int i = 1; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          int ii = i ^ (1 << j);
          if (ii == 0) {
            f[i][j] = 1;
            continue;
          }
          for (int k = 0; k < n; ++k) {
            if (nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0) {
              f[i][j] = (f[i][j] + f[ii][k]) % mod;
            }
          }
        }
      }
    }
    int ans = 0;
    for (int x : f[m - 1]) {
      ans = (ans + x) % mod;
    }
    return ans;
  }
};

func specialPerm(nums []int) (ans int) {
  const mod int = 1e9 + 7
  n := len(nums)
  m := 1 << n
  f := make([][]int, m)
  for i := range f {
    f[i] = make([]int, n)
  }
  for i := 1; i < m; i++ {
    for j, x := range nums {
      if i>>j&1 == 1 {
        ii := i ^ (1 << j)
        if ii == 0 {
          f[i][j] = 1
          continue
        }
        for k, y := range nums {
          if x%y == 0 || y%x == 0 {
            f[i][j] = (f[i][j] + f[ii][k]) % mod
          }
        }
      }
    }
  }
  for _, x := range f[m-1] {
    ans = (ans + x) % mod
  }
  return
}