第三题
func solution3(_ nums: [Int]) -> Int {
let N = nums.count
let K = mypow(N) - 1
let mod = Int(1e9+7)
var sum = 0
for num in nums {
sum = (sum + num) % mod
}
let inverseN = modInverse(N, mod)
let result = (K * sum % mod) * inverseN % mod
return result
}
func mypow(_ n: Int) -> Int {
var _n = n
var a = 2
var res = 1
let mod = Int(1e9+7)
while _n > 0 {
if _n % 2 == 1 { res = (res * a) % mod }
a = (a * a) % mod
_n /= 2
}
return res
}
func modInverse(_ a: Int, _ m: Int) -> Int {
var m0 = m
var a0 = a
var m1 = m
var x0 = 0
var x1 = 1
while a0 > 1 {
let q = a0 / m0
var t = m0
m0 = a0 % m0
a0 = t
t = x0
x0 = x1 - q * x0
x1 = t
}
if x1 < 0 {
x1 += m1
}
return x1
}
