2741. 特别的排列

Link

文章目录

2741. 特别的排列
- 题意
- 思路
- 代码

2741. 特别的排列

题意

给你一个下标从 0 开始的整数数组 nums ，它包含 n 个互不相同的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：

对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。
请你返回特别排列的总数目，由于答案可能很大，请将它对 10^9 + 7 取余后返回。

2 <= nums.length <= 14
1 <= nums[i] <= 10^9

思路

状态压缩+dfs+记忆化搜索

看到nums的长度并不长，考虑将状态压缩

类似全排列的思路（拿一个空数组，从左往右开始填数），一个包含 n 个不同整数的数组有 n! 种排列，如果直接dfs并判断是否是特别的排列，可能会超时。遂考虑将状态压缩为01串，0表示这个数并未选过，1表示这个数已经选过
举例子
1. 例如数组 [2, 3, 6]，如果状态为101，说明2和6被选过
2. 考虑对dfs进行优化
  1. 在从左往右填数的过程中，维护在原数组的坐标，只需要考虑下一个数是否和前一个数构成因数关系即可
  2. 根据第一条的结论，我们就可以从一层一层的状态中过滤很多，保证下一层继承的上一层是正确的
  3. 考虑记忆化搜索，Python可以用@cache优化
3. 状态转移：
  1. 维护两个值
    1. 一个是mask的01串，代表哪个数被选了，初始为0
    2. 一个是prev_index，代表前一个选的坐标是什么，初始为-1，代表是dfs时的第一个数，必选
  2. 类似全排列，查找 mask 中哪个没别选，如果这个数满足要求，那么下一个dp状态就是 dp(mask | (1 << i), i)，即让这个mask的这一位置1，并且我们维护的前一个数的下标更改为i
4. 最后当mask全为1时，则代表全选完了，而且是正确结果

代码


'''
Author: NEFU AB-IN
Date: 2024-06-26 15:20:32
FilePath: \LeetCode\2741\2741.py
LastEditTime: 2024-06-26 20:34:10
'''
# import
from functools import cache
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor
from types import GeneratorType
from typing import TypeVar, List, Dict, Any, Callable


# Data structure
class SA:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __lt__(self, other):
        return self.x < other.x


# Constants
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
E = int(100)

# Set recursion limit
setrecursionlimit(INF)

# Read
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
read_list = lambda: list(map(int, input().split()))


# Func
class std:

    # Recursion
    @staticmethod
    def bootstrap(f, stack=None):
        if stack is None:
            stack = []

        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if isinstance(to, GeneratorType):
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to

        return wrappedfunc

    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    array = staticmethod(lambda x=0, size=N: [x] * size)
    array2d = staticmethod(
        lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)
    filter = staticmethod(lambda func, iterable: list(filter(func, iterable)))


# —————————————————————Division line ——————————————————————


class Solution:

    def specialPerm(self, nums: List[int]) -> int:
        n = len(nums)
        all_mask = (1 << n) - 1
        MOD = int(1e9 + 7)

        @cache
        def dp(mask, prev_index):
            if mask == all_mask:
                return 1

            total_perms = 0
            for i in range(n):
                if mask & (1 << i) == 0:
                    if prev_index == -1 or nums[prev_index] % nums[i] == 0 or nums[i] % nums[prev_index] == 0:
                        total_perms = (total_perms + dp(mask | (1 << i), i)) % MOD

            return total_perms

        return dp(0, -1)