湖北建设部网站,上海网络开发公司,南京网站建设 w,加微信群网站怎么做的lc1969. 数组元素的最小非零乘积
题目描述
给你一个正整数 p 。你有一个下标从 1 开始的数组 nums #xff0c;这个数组包含范围 [1, 2p - 1] 内所有整数的二进制形式#xff08;两端都 包含#xff09;。你可以进行以下操作 任意 次#xff1a;
从 nums 中选择两个元素…lc1969. 数组元素的最小非零乘积
题目描述
给你一个正整数 p 。你有一个下标从 1 开始的数组 nums 这个数组包含范围 [1, 2p - 1] 内所有整数的二进制形式两端都 包含。你可以进行以下操作 任意 次
从 nums 中选择两个元素 x 和 y 。 选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数 相同位置 的二进制位。 比方说如果 x 1101 且 y 0011 交换右边数起第 2 位后我们得到 x 1111 和 y 0001 。
请你算出进行以上操作 任意次 以后nums 能得到的 最小非零 乘积。将乘积对 109 7 取余 后返回。
注意答案应为取余 之前 的最小值。
1 p 60
思路
我们注意到每一次操作并不会改变元素的和而在元素和不变的情况下要想使得乘积最小应该尽可能最大化元素的差值。 由于最大的元素为 2^p−1无论与哪个元素交换都不会使得差值变大因此我们不需要考虑与最大元素交换的情况。
对于其它的[1,..2^p−2]的元素我们依次将首尾元素两两配对即 x 与 [1,..2^p−1-x] 进行配置那么经过若干次操作过后每一对元素都变成了 (1,2^p−2)那么最终的乘积为 (2^p−1)×(2^p−2)^(2^(p-1)-1)
代码
class Solution:def minNonZeroProduct(self, p: int) - int:mod 10**97def qpow(a,b):res 1while b0:if (b1)1:res res * a%moda a * a%modb1return reskk 2**p-1bb 2**(p-1)-1return kk%mod * qpow((kk-1),bb)%mod # 也可以用python自带的pow(a,b,mod)
