412小S的子序列平均数之和

题目描述

小 S 得到了一个由 n 个元素组成的数组，她想求出所有子序列的平均数之和。由于子序列的数量非常多，因此需要对结果取模 (10^9 + 7) 来避免结果过大。子序列是从原数组中选择部分元素，保持原数组的顺序形成的新数组。

你需要输出所有子序列的平均数之和对 (10^9 + 7) 取模的值。

可以证明，最终的答案一定是一个有理数 (\frac{a}{b})，对 (p) 取模的意义是在 ([0, p-1]) 区间找到一个满足 (x \cdot b \mod p = a) 的 (x)。

解题思路

题目要求计算所有子序列的平均数之和。由于子序列的数量指数级增长，直接枚举所有子序列会导致时间复杂度过高。因此，我们需要找到一种高效的方法来计算结果。

考虑到子序列的平均数可以表示为子序列元素之和除以子序列的长度，我们可以将问题转化为计算所有子序列元素之和的加权和，其中权重是子序列长度的倒数。

具体步骤如下：

1. 组合数学：对于长度为i的子序列，一共有C(n, i)中，而每个元素在子序列中的出现的次数为C(n-1, i-1)，因此可以直接计算出子序列元素之和的加权和。

2. 预处理组合数：为了快速计算组合数 C(n, k)，我们提前计算阶乘和逆阶乘，并利用模反元素进行组合数的计算。

代码实现

N = int(1e5 + 10)
fac = [1] * N
infac = [1] * N
mod = int(1e9 + 7)
for i in range(1, N):
    fac[i] = fac[i - 1] * i % mod
    infac[i] = infac[i - 1] * pow(i, mod - 2, mod) % mod

def comb(n, k):
    return fac[n] * infac[n - k] % mod * infac[k] % mod

inv = lambda x: pow(x, mod - 2, mod)

def solution(n: int, arr: list) -> int:
    s = sum(arr)
    res = 0
    for i in range(1, n + 1):
        res = (res + s * comb(n - 1, i - 1) * inv(i)) % mod
    return res

if __name__ == '__main__':
    print(solution(3, [1, 2, 3]) == 14)
    print(solution(2, [2, 1]) == 500000008)
    print(solution(4, [1, 1, 1, 1]) == 15)

复杂度分析

时间复杂度: $O(n)$, 预处理组合数的时间复杂度为$O(n)$，计算结果的时间复杂度为$O(n)$。pow可以再预处理一下。
空间复杂度: $O(n)$