数组元素的最小非零乘积

难度: Medium

给你一个正整数 p 。你有一个下标从 1 开始的数组 nums ，这个数组包含范围 [1, 2^p - 1] 内所有整数的二进制形式（两端都包含）。你可以进行以下操作任意次：

从 nums 中选择两个元素 x 和 y 。
选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数 相同位置 的二进制位。

比方说，如果 x = 1101 且 y = 0011 ，交换右边数起第 2 位后，我们得到 x = 1111 和 y = 0001 。

请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。将乘积对 10⁹ + 7 取余后返回。

注意：答案应为取余之前的最小值。

示例 1：

输入：p = 1
输出：1
解释：nums = [1] 。
只有一个元素，所以乘积为该元素。

示例 2：

输入：p = 2
输出：6
解释：nums = [01, 10, 11] 。
所有交换要么使乘积变为 0 ，要么乘积与初始乘积相同。
所以，数组乘积 1 * 2 * 3 = 6 已经是最小值。

示例 3：

输入：p = 3
输出：1512
解释：nums = [001, 010, 011, 100, 101, 110, 111]
- 第一次操作中，我们交换第二个和第五个元素最左边的数位。
    - 结果数组为 [001, 110, 011, 100, 001, 110, 111] 。
- 第二次操作中，我们交换第三个和第四个元素中间的数位。
    - 结果数组为 [001, 110, 001, 110, 001, 110, 111] 。
数组乘积 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512 是最小乘积。

提示：

1 <= p <= 60

Submission

运行时间: 15 ms

内存: 16.0 MB

class Solution:
    def minNonZeroProduct(self, p: int) -> int:
        
        mod = 10**9 + 7
        return  pow(2 ** p - 2, 2 ** (p - 1) - 1, mod) * (2 ** p - 1) % mod

Explain

题解的思路是基于数学推导和观察。给定一个正整数p，数组nums包含了从1到2^p - 1的所有整数。要得到最小非零乘积，可以考虑将nums数组中的最大值(2^p - 1)与其余较小值的乘积最小化。由于可以通过位交换自由地调整nums中的任意两个数，观察到当nums中最大值(2^p - 1)保持不变，其余所有的数(从1到2^p - 2)都设置为次大值(2^p - 2)时，可以得到最小乘积。因此，问题转化为计算(2^p - 2)^(2^(p-1) - 1) * (2^p - 1) % (10^9 + 7)。这个公式的推导基于组合数学中的排列组合理论，考虑到位操作的自由度和模运算的性质。

时间复杂度: O(log(2^(p-1))) 或 O(p)

空间复杂度: O(1)

# 定义解决方案类

class Solution:
    def minNonZeroProduct(self, p: int) -> int:
        # 模数
        mod = 10**9 + 7
        # 计算2^p - 1
        max_val = 2 ** p - 1
        # 计算2^p - 2
        second_max_val = max_val - 1
        # 计算2^(p-1) - 1
        count = 2 ** (p - 1) - 1
        # 使用快速幂计算(second_max_val^count) % mod
        part1 = pow(second_max_val, count, mod)
        # 计算最终结果
        return (part1 * max_val) % mod

Explore

在给定的问题中，要最小化最大值(2^p - 1)与其他数的乘积。由于乘积的大小直接受到乘数大小的影响，选择次大值(2^p - 2)作为其他数，可以有效减小乘积的大小。这种选择是因为2^p - 2接近于2^p - 1，而其他较小的数如1, 2, ..., 这些数与2^p - 1的乘积将会更大。因此，将其他值设置为次大值可以最小化整体乘积，从而得到题目要求的最小非零乘积。

题解中的位交换可能指的是理论上的操作，意在说明我们可以考虑数组中任意两数的组合。实际应用中，并非通过直接的位交换来调整数组。例如，对于p=3的情况，原数组为[1, 2, 3, 4, 5, 6, 7]，最大值为7，次大值为6。题目理论上假设我们可以将数组调整为[6, 6, 6, 6, 6, 6, 7]，通过这样的调整来最小化乘积。这种调整实际上是从数学角度简化问题，而非真实执行位交换。

这个公式的推导基于以下思考：考虑到数组中最大值为2^p - 1，其余都调整为次大值2^p - 2。数组中从1到2^p - 1的数的总数是2^p - 1个，因此除了最大值外，有2^p - 2个数。由于我们将这些数都调整为次大值，每个数出现的次数为2^(p-1) - 1（因为总数为2^(p-1), 减去一个最大值）。因此，我们需要计算次大值的这么多次幂，再乘以最大值。最后，由于结果需要在模10^9 + 7的条件下进行，因此整个表达式需要取模。