「Codeforces 1009E」Intercity Travelling

Codeforces 1009E」Intercity Travelling"/>

「Codeforces 1009E」Intercity Travelling

建议访问原文出处，获得更佳浏览体验。
原文出处：/

题意

Leha 想开车去 Saratov，这段旅途看作 0 0 $0$ 到 n" role="presentation" style="position: relative;">nn$n$ 的一维直线。
如果 Leha 从起点出发或者从休息点出发，连续驾驶 k k $k$ 千米，则需要消耗的体能为 a1+a2+…+ak" role="presentation" style="position: relative;">a1+a2+…+aka1+a2+…+ak$a_1 + a_2 + \ldots + a_k$。
每个整点 t,(1≤t<n) t , ( 1 ≤ t < n ) $t, (1 \le t < n)$ 都可能拥有一个休息点，每个休息点存在或不存在的概率相等。
记 Leha 整个旅程消耗的体能的期望为 p p $p$，求 p&#x22C5;2n&#x2212;1" role="presentation" style="position: relative;">p⋅2n−1p⋅2n−1$p\cdot 2^{n - 1}$。

链接

Codeforces 1009E

题解

旅途中共有 n−1 n − 1 $n - 1$ 个整点，故有 2n−1 2 n − 1 $2^{n - 1}$ 种可能的休息点摆放方案，故 p⋅2n−1 p ⋅ 2 n − 1 $p\cdot 2^{n - 1}$ 为所有可能情况消耗体能之和。

我们先考虑总和中的 a1 a 1 $a_1$ 的数量。由于每个休息点之后紧邻的 1km 1 k m $1km$ 路程一定消耗 a1 a 1 $a_1$ 的体能，因此某种摆放方案中 a1 a 1 $a_1$ 的数量等于休息点个数加一（起点之后一定消耗 a1 a 1 $a_1$）。考虑有 j j $j$ 个休息点时，有 Cn&#x2212;1j" role="presentation" style="position: relative;">Cjn−1Cn−1j$C_{n-1}^{j}$ 种摆放方案，故 j j $j$ 个休息点的情况下 a1" role="presentation" style="position: relative;">a1a1$a_1$ 的数量和为 (j+1)Cjn−1 ( j + 1 ) C n − 1 j $(j + 1)C_{n-1}^j$。

记 N1 N 1 $N_1$ 为所有摆放方案下 a1 a 1 $a_1$ 的数量和，则有

N1=∑i=1ni⋅Ci−1n−1 N 1 = ∑ i = 1 n i ⋅ C n − 1 i − 1 $$N_1 = \sum \limits_{i = 1}^{n} i \cdot C_{n-1}^{i-1}$$
即 N1=1⋅C0n−1+2⋅C1n−1+…+n⋅Cn−1n−1 N 1 = 1 ⋅ C n − 1 0 + 2 ⋅ C n − 1 1 + … + n ⋅ C n − 1 n − 1 $N_1 = 1 \cdot C_{n-1}^{0} + 2 \cdot C_{n - 1}^{1} + \ldots + n \cdot C_{n-1}^{n-1}$

又由于 Cin−1=Cn−1−in−1 C n − 1 i = C n − 1 n − 1 − i $C_{n -1}^{i} = C_{n - 1}^{n-1 -i}$，有 N1=1⋅Cn−1n−1+2⋅Cn−2n−1+…+n⋅C0n−1 N 1 = 1 ⋅ C n − 1 n − 1 + 2 ⋅ C n − 1 n − 2 + … + n ⋅ C n − 1 0 $N_1 = 1 \cdot C_{n-1}^{n-1} + 2 \cdot C_{n - 1}^{n-2} + \ldots + n \cdot C_{n-1}^{0}$

两式加和，有 2N1=(n+1)∑i=1nCi−1n−1=(n+1)⋅2n−1 2 N 1 = ( n + 1 ) ∑ i = 1 n C n − 1 i − 1 = ( n + 1 ) ⋅ 2 n − 1 $2 N_1 = (n + 1)\sum\limits_{i = 1}^{n}C_{n-1}^{i-1} = (n+1)\cdot 2^{n-1}$，即 N1=(n+1)⋅2n−2 N 1 = ( n + 1 ) ⋅ 2 n − 2 $N_1 = (n + 1) \cdot 2^{n - 2}$

同理，有 Ni=(n+2−i)⋅2n−1−i N i = ( n + 2 − i ) ⋅ 2 n − 1 − i $N_i = (n + 2 - i)\cdot 2^{n-1 - i}$，则

p⋅2n−1=∑i=1nNiai=∑i=1n(n+2−i)⋅2n−1−i⋅ai p ⋅ 2 n − 1 = ∑ i = 1 n N i a i = ∑ i = 1 n ( n + 2 − i ) ⋅ 2 n − 1 − i ⋅ a i $$p\cdot 2^{n - 1} = \sum\limits_{i=1}^{n} N_ia_i = \sum\limits_{i = 1} ^n (n + 2 - i) \cdot 2 ^{n - 1 - i} \cdot a_i$$

代码

#include <iostream>
#include <algorithm>using std::iostream;typedef long long LL;const int N = 1000010;
const int mod = 998244353;int n;
LL a[N], p[N];int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n;for (int i = 0; i < n; ++i) {cin >> a[i];}p[0] = 1; p[1] = 3;LL m = 1;for (int i = 2; i < n; ++i) {   // 预处理系数，即 Nim = (m << 1) % mod;         // 2^(i - 1)p[i] = (m * (i + 2)) % mod; // (i + 2) * 2^(i - 1)}LL sum = 0;for (int i = 0; i < n; ++i) {sum = (sum + p[n - i - 1] * a[i]) % mod;}cout << sum << endl;return 0;
}