Problem: 1969. 数组元素的最小非零乘积
思路
结论
( 2 p − 1 ) × ( 2 p − 2 ) 2 p − 1 − 1 (2^p-1)\times (2^p-2)^{2^{p-1}-1} (2p−1)×(2p−2)2p−1−1
复杂度
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
Code
class Solution {
static int MOD = 1_000_000_007;
long pow(long x, int p) //改版快速幂(这里的幂的二进制是 全 1 的,换而言之,p 即是需要传统快速幂多少次)
{
x %= MOD;
long res = 1;
while(p-- > 0)
{
res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
public int minNonZeroProduct(int p) {
long k = (1L << p ) -1;
return (int)(k % MOD * pow(k-1,p-1) % MOD);
}
}