2741.特别的排列

链接：2741.特别的排列
难度：Medium
标签：位运算、数组、动态规划、状态压缩
简介：请你返回特别排列的总数目，由于答案可能很大，请将它对 109 + 7 取余 后返回。

题解 1 - python

• 编辑时间：2024-06-26
• 执行用时：3193ms
• 内存消耗：128.91MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def specialPerm(self, nums: List[int]) -> int:
        n = len(nums)
        @cache
        def dfs(last: int, mask: int) -> int:
            if mask == (1 << n) - 1: return 1
            return sum(
                dfs(nums[i], mask | (1 << i))
                for i in range(n)
                if mask & (1 << i) == 0 and (last % nums[i] == 0 or nums[i] % last == 0)
            )
        return sum(dfs(nums[i], 1 << i) for i in range(n)) % (10 ** 9 + 7)