1969-数组元素的最小非零乘积

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

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

比方说，如果 x = 11 _ **0**_ 1 且 y = 00 _ **1**_ 1 ，交换右边数起第 2 位后，我们得到 x = 11 _ **1**_ 1 和 y = 00 _ **0**_ 1 。

请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。将乘积对 _ _109 + 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, _**1**_ 10, 011, 100, _**0**_ 01, 110, 111] 。
- 第二次操作中，我们交换第三个和第四个元素中间的数位。
    - 结果数组为 [001, 110, 0 _ **0**_ 1, 1 _ **1**_ 0, 001, 110, 111] 。
数组乘积 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512 是最小乘积。

提示：

1 <= p <= 60

首先，两个交换的比特必须是不同的，否则交换无影响。

不失一般性，假设 x 参与交换的比特为 0，y 参与交换的比特为 1，交换的位置为第 k 位。

记 y=y’+2^k，则交换前，两数的乘积为

x\cdot y = x\cdot (y’+2^k) = x\cdot y’+x\cdot 2^k

交换后，两数的乘积为

(x+2^k)\cdot (y-2^k) = (x+2^k)\cdot y’ = x\cdot y’+y’\cdot 2^k

对比两个等式可知，要使交换后乘积变小，需要满足

x>y’

这一不等式表明，对于一个数 y，如果我们不断地将其二进制中的 1 与另一个满足该不等式的数交换，就可以将乘积不断减小。由于题目要求计算最小非零乘积，我们可以先将 y 减小至 0，然后再寻找一个最低位为 1 的数进行交换，从而让 y 变成 1。

由于 nums 包含了 [1, 2^p - 1] 内的所有整数，我们可以将其分为两组，小于 2^{p-1 的为一组，记作 A，其余的为另一组，记作 B。则 B 组中除了 2^p-1 之外，其余的数均可以和 A 组中的数一一配对，要求配对的两个数之和为 2^p-1。对于配对的这两个数，若某个数的一个位置是 1，则另一个数的该位置上必然是 0，因此就可以按照上述交换流程交换，交换后的结果为 1 和 2^p-2。

交换后，每一对的乘积为 2^p-2，这一共有 2^{p-1}-1 对，再算上不参与配对的 2^p-1，得到最小乘积为

(2^p-1)\cdot (2^p-2)^{2^{p-1}-1}

由于幂次很大，计算时需要用到快速幂。不了解的读者可以参考 50. Pow(x, n) 。

const mod int = 1e9 + 7

func minNonZeroProduct(p int) int {
	return (1<<p - 1) % mod * pow(1<<p-2, 1<<(p-1)-1) % mod
}

func pow(x, n int) int {
	res := 1
	for x %= mod; n > 0; n >>= 1 {
		res = res * x % mod // 由于 n 的二进制全是 1，所以无需判断 n 的奇偶性
		x = x * x % mod
	}
	return res
}

时间复杂度：O(p)
空间复杂度：O(1)

附 1：Python 一行解法

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

附 2：打表解法

var ans = []int{0, 1, 6, 1512, 581202553, 202795991, 57405498, 316555604, 9253531, 857438053, 586669277, 647824153, 93512543, 391630296, 187678728, 431467833, 539112180, 368376380, 150112795, 484576688, 212293935, 828477683, 106294648, 618323081, 186692306, 513022074, 109245444, 821184946, 2043018, 26450314, 945196305, 138191773, 505517599, 861896614, 640964173, 112322054, 217659727, 680742062, 673217940, 945471045, 554966674, 190830260, 403329489, 305023508, 229675479, 865308368, 689473871, 161536946, 99452142, 720364340, 172386396, 198445540, 265347860, 504260931, 247773741, 65332879, 891336224, 221172799, 643213635, 926891661, 813987236}

func minNonZeroProduct(p int) int {
	return ans[p]
}