首页 > 其他分享 >状态压缩-6893. 特别的排列

状态压缩-6893. 特别的排列

时间:2023-06-18 21:34:37浏览次数:38  
标签:特别 排列 nums 压缩 示例 rest 6893

6893. 特别的排列

Description

Difficulty: 中等

Related Topics:

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

  • 对于 0 <= i < n - 1 的下标 i ,要么 nums[i] % nums[i+1] == 0 ,要么 nums[i+1] % nums[i] == 0 。

请你返回特别排列的总数目,由于答案可能很大,请将它对10+ 7 取余 后返回。

示例 1:

输入:nums = [2,3,6]
输出:2
解释:[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。

示例 2:

输入:nums = [1,4,3]
输出:2
解释:[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。

提示:

  • 2 <= nums.length <= 14
  • 1 <= nums[i] <= 109

Solution

排列问题时间复杂度为O(n!),一般阶乘能支持最大10! ~= 106,这里已经到了14,显然需要降低到2n,因此需要用状态压缩。
只需要考虑将剩余的数字用二进制保存下来即可,然后dfs。
Language: Python3

class Solution:
    def specialPerm(self, nums: List[int]) -> int:
        MOD = 10 ** 9 + 7
        n = len(nums)
        
        @cache
        def dfs(i, rest):
            if rest == 0: return 1
            
            res = 0
            for j, num in enumerate(nums):
                if rest & (1 << j) and (nums[j] % nums[i] == 0 or nums[i] % nums[j] == 0):
                    res = (res + dfs(j, rest ^ (1 << j))) % MOD
            
            return res
        
        rest = (1 << n) - 1
        
        res = 0
        for i in range(n):
            res = (res + dfs(i, rest ^ (1 << i))) % MOD
        
        return res

标签:特别,排列,nums,压缩,示例,rest,6893
From: https://www.cnblogs.com/hyserendipity/p/17489785.html

相关文章

  • PHP批量压缩图片,基于TP5,fastadmin
    <?php/***CreatedbyPhpStorm.*User:zhuo<[email protected]>*O(∩_∩)O*Date:2022-7-709:34:38*/namespaceapp\command;usethink\Image;usethink\image\Exception;usethink\console\{Command,Input,Output};//压缩图片classCom......
  • 基础排列组合学习笔记
    排列组合是数学中一项非常重要、基础的内容,可以解决许多与计数有关的问题。让我们先从最基本的数数学起。前置知识加法原理假设你现在有\(a_0\)个物品,所有物品互不相同。你要从中拿一个物品出来,拿出的物品可能有几种?显然是\(a_0\)种,因为每一个物品互不相同,每一个物品都可......
  • 使用Thumbnails进行图片压缩,报“No suitable ImageReader found for source data”异
    先转一次byte数组再处理byte[]bigContent=file.getBytes();Thumbnails.of(newByteArrayInputStream(bigContent)).scale(1f).outputQuality(0.3f).toFile(fileThu);这里fileThu直接使用文件路径比较好......
  • 双打姓名排列判断
    问题:区分有效与无效排列第4行张3的搭档为“空白”,无效;第11行和第13行,林8同时与林14和林12搭档,无效 选取J2:K14单元格区域》开始》条件格式》新建规则》使用公式确定要设置格式的单元格 =XLOOKUP($K3,$J:$J,$K:$K,0)=$J3......
  • 【Azure 环境】使用az login登录遇见OSError: [WinError -2146893813] : '' 错误
    azlogin|Decryptionfailed:[WinError-2146893813]Keynotvaidforuseinspecifiedstate|msal_extensions.persistence:DPAPIerrorlikelycausedbyfilecontentnotpreviouslyencrypted.Appdevelopershouldmigratebycallingsave(......
  • 【图像压缩】基于小波结合spiht实现图像压缩附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • Q:Win10关闭内存压缩功能
    微软在Win10中就已经启用了内存压缩机制,在Win11当中继续了这一设定。通过任务管理器查看。taskmgr·通过命令行查看。使用系统管理员权限,打开PowerShell,然后输入以下命令:Get-MMAgent关闭压缩命令:Disable-MMAgent-mc启动压缩命令:Enable-MMAgent-mc......
  • 人工智能领域:面试常见问题超全(深度学习基础、卷积模型、对抗神经网络、预训练模型、计
    人工智能领域:面试常见问题超全(深度学习基础、卷积模型、对抗神经网络、预训练模型、计算机视觉、自然语言处理、推荐系统、模型压缩、强化学习、元学习)人工智能领域:面试常见问题1.深度学习基础为什么归一化能够提高求解最优解的速度?为什么要归一化?归一化与标准化有什么联系......
  • 深度学习实践篇[17]:模型压缩技术、模型蒸馏算法:Patient-KD、DistilBERT、DynaBERT、Ti
    深度学习实践篇[17]:模型压缩技术、模型蒸馏算法:Patient-KD、DistilBERT、DynaBERT、TinyBERT1.模型压缩概述1.2模型压缩原有理论上来说,深度神经网络模型越深,非线性程度也就越大,相应的对现实问题的表达能力越强,但相应的代价是,训练成本和模型大小的增加。同时,在部署时,大模型预测......
  • Alien 的排列题解
    Description求出有多少\(2\simn+1\)的排列\(\{P_{n}\}\),使得对于所有\(1\leqi\leqn\)有\(i|P_{i}\)。对于\(30\%\)的数据\(n\leq10\)。对于\(90\%\)的数据\(n\leq3000\)。对于\(100\%\)的数据\(n\leq10^9\)。Solution如果把\(n+1\)固定在第\(1\)个......