「SHOI2016」随机序列 题解 题意 有 $n$ 个数 $a_1,a_2,\dots,a_n$

每两个数之间可以填 $+,-,×$ 三种符号，共 $3^{n-1}$ 个表达式

需要支持修改 $a_i$，求所有表达式值的和 $\bmod 10^9+7$

核心观察

1. 关键性质 考虑一个表达式，从第一个加减号出现的位置开始分割：

设第一个加减号在第 $k$ 个位置（$a_k$ 和 $a_{k+1}$ 之间）

那么表达式形式为：$[a_1×a_2×\cdots×a_k] \ \text{符号} \ [\text{后面的部分}]$

前面的部分是连续乘积，后面是任意的表达式

2. 统计贡献 对于每个位置 $i$（$1 \le i < n$）：

以 $i$ 结尾的连续乘积：$P_i = a_1 × a_2 × \cdots × a_i$

在 $a_i$ 和 $a_{i+1}$ 之间填 $+$ 或 $-$：

$P_i$ 对总和的贡献：$+P_i$ 或 $-P_i$

两种情况出现的次数相等：各 $3^{n-i-1}$ 次

所以总贡献抵消为 $0$！

3. 唯一有贡献的项 如果在 $a_i$ 和 $a_{i+1}$ 之间填 $×$，则 $P_i$ 会被继续乘下去

实际上，只有整个表达式都是乘号时（$a_1×a_2×\cdots×a_n$）的项会保留

但这样不对...让我们仔细分析

正确推导 公式 令 $P_i = a_1 × a_2 × \cdots × a_i$（前缀乘积）

总和的公式为：

总和

P 1 × 2 × 3 n − 2 + P 2 × 2 × 3 n − 3 + ⋯ + P n − 1 × 2 × 3 0 + P n 总和=P 1 ​ ×2×3 n−2 +P 2 ​ ×2×3 n−3 +⋯+P n−1 ​ ×2×3 0 +P n ​

其中 $P_n$ 是全乘积项（全是乘号）。

简化 可以写成：

总和

∑ i

1 n − 1 2 × P i × 3 n − i − 1 + P n 总和= i=1 ∑ n−1 ​ 2×P i ​ ×3 n−i−1 +P n ​

或更简洁：

总和

∑ i

1 n f ( i ) × P i 总和= i=1 ∑ n ​ f(i)×P i ​

其中 $f(i) = \begin{cases} 2 × 3^{n-i-1} & i < n \ 1 & i = n \end{cases}$

算法实现

1. 预处理 计算 $P_i = a_1 × a_2 × \cdots × a_i$（前缀积）

预处理 $3^k \bmod M$

2. 线段树维护 每个修改影响：

$a_t$ 改变 → $P_t, P_{t+1}, \dots, P_n$ 都改变

建立线段树，每个节点维护：

区间乘积 $prod$

区间和 $sum = \sum_{i=l}^{r} f(i) × P_i'$，其中 $P_i'$ 是相对于区间起点的乘积

合并时：

$prod = left.prod × right.prod$

$sum = left.sum + left.prod × right.sum$

3. 查询 根节点的 $sum$ 就是答案。

复杂度 预处理：$O(n)$

每次修改：$O(\log n)$

总复杂度：$O(n + Q \log n)$