考点：组合数学 · 前缀和

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 1e5
• 元素值域：a_i ≤ 1e5（注意整数类型选择，避免溢出）
• 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：组合数学

用计数原理（加法/乘法原理）与组合数公式统计方案数。

思路框架（组合数学 通法 · 非本题专属）

1. 判断是分类计数（相加）还是分步计数（相乘）。
2. 识别是否重复/是否有序，决定用排列 A(n,m) 还是组合 C(n,m)。
3. 组合数递推 C[i][j] = C[i-1][j-1] + C[i-1][j]，或预处理阶乘与逆元。
4. 答案通常要求对 1e9+7 取模。

实现要点：阶乘预处理 + 费马小定理求逆元可以在 O(1) 内算任意组合数。

复杂度：时间 O(n) 预处理 / O(1) 查询 ｜ 空间 O(n)

该范式的通法易错点

• 把排列和组合搞混。
• 取模意义下直接做除法（应乘逆元）。
• 方案数溢出未取模。

对照本题

• 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 元素值域最大到 1e5 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 3 / 1 2 3 → 输出 33

子数组[1]的权值是1。

子数组[1,2]的权值是5。

子数组[1,2,3]的权值是14。

子数组[2]的权值是2。

子数组[2,3]的权值是8。

子数组[3]的权值是3。