CF1316F Battalion Strength

在 Byteland 的军队中有 $n$ 名军官。每位军官都有一个与之相关的战斗力，第 $i$ 位军官的战斗力为 $p_i$。由于战争即将来临，将军想要知道军队的整体实力。 在 Byteland，军队的实力计算方式非常奇特。将军会从这 $n$ 名军官中随机选择一个子集，并称之为一个“battalion”（营）。所有 $n$ 名军官的 $2^n$ 个子集都可能被选中（包括空集和全体军官的集合）。 一个营的实力计算方式如下： 设被选中的军官的战斗力为 $a_1, a_2, \ldots, a_k$，其中 $a_1 \leq a_2 \leq \dots \leq a_k$。该营的实力为 $a_1a_2 + a_2a_3 + \dots + a_{k-1}a_k$。（如果营的人数 $\leq 1$，则该营的实力为 $0$。） 军队的实力等于所有营的实力的期望值。 由于战争可能持续很久，军官们的战斗力可能会发生变化。具体来说，会有 $q$ 次变化，每次变化为 $i\ x$，表示 $p_i$ 变为 $x$。 你需要分别输出初始状态以及每次变化后军队的实力。 注意，变化是永久的。 实力的结果需要对 $10^9+7$ 取模。形式化地，设 $M=10^9+7$。可以证明答案可以表示为不可约分数 $p/q$，其中 $p$ 和 $q$ 是整数且 $q\not\equiv 0 \pmod M$。输出等于 $p\cdot q^{-1} \bmod M$ 的整数。换句话说，输出一个整数 $x$，满足 $0\leq x

第一行包含一个整数 $n$（$1\leq n\leq 3\times 10^5$），表示 Byteland 军队的军官人数。 第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$（$1\leq p_i\leq 10^9$）。 第三行包含一个整数 $q$（$1\leq q\leq 3\times 10^5$），表示变化次数。 接下来的 $q$ 行，每行包含两个整数 $i$ 和 $x$（$1\leq i\leq n$，$1\leq x\leq 10^9$），表示将 $p_i$ 更新为 $x$。

第一行输出初始状态下军队的实力。 接下来的 $q$ 行，第 $i$ 行输出第 $i$ 次变化后军队的实力。

在第一个测试点中，初始时有四种可能的营： - $\{\}$，实力 $=0$ - $\{1\}$，实力 $=0$ - $\{2\}$，实力 $=0$ - $\{1,2\}$，实力 $=2$ 所以军队的实力为 $\frac{0+0+0+2}{4} = \frac{1}{2}$。将 $p_1$ 改为 $2$ 后，$\{1,2\}$ 的实力变为 $4$，所以军队的实力变为 $1$。 再将 $p_2$ 改为 $1$ 后，$\{1,2\}$ 的实力又变为 $2$，所以军队的实力又变为 $\frac{1}{2}$。 由 ChatGPT 4.1 翻译