[Codeforces]Contest 1009 E. Intercity Travelling

链接

Educational Codeforces Round 47 (Rated for Div. 2) - E. Intercity Travelling
http://codeforces.com/contest/1009/problem/E

思路

n千米,有n段路,共有n-1个可能可以休息的地方,则共有2^(n-1)种可能的休息方式;
要计算 p⋅2^(n−1),也就是计算所有的可能的休息方式下的消耗之和;
分解出来,就是要计算所有的可能的休息方式中所有的a[i]的和;
也就是求和 sum(a[i] * 消耗a[i]出现的总次数) (i->1,2,3,…n);

我们可以按照这种思路,统计a[1]出现的总次数,a[2]出现的次数,这个应该是有规律的;

1
2
3
4
5
例如n=4的情况

0 1 2 3 4
#--#--#--#--#
其中 1,2,3 这几个点既可以是休息,也可以是不休息两种状态

先考虑简单的,要使a[1]出现:

1
2
3
4
5
6
若a[1]出现在 0-1 之间,显然这是必定的,和 1,2,3 休息与不休息都没关系,有所以在 0-1 出现a[1]的次数是 2^3 = 2^(n-1) 次
若a[1]出现在 1-2 之间,则必须是在 1 点处休息了,而 2,3 处则没关系,那么所有在 1-2 出现a[1]的次数是 2^2 = 2^0 * 2^(n-2) = 2^(n-2) 次
若a[1]出现在 2-3 之间,则必须是在 2 点休息了,和在 1,3 的状况没关系,那么所有在 2-3 出现a[1]的次数是 2^2 = 2^1 * 2^(n-3) = 2^(n-2) 次
同理可得a[1]出现在 3-4 之间的次数是 2^2 = 2^2 * 2^(n-4) = 2^(n-2) 次

则a[1]出现的总次数是 2^3 + 2^2 + 2^2 + 2^2

再考虑a[2],a[3],a[4]的情况,
a[2]出现的总次数是 2^2 + 2^1 + 2^1
a[3]出现的总次数是 2^1 + 2^0
a[4]出现的总次数是 2^0

可以发现规律
a[i]出现的次数是 2^(n-i) + 2^(n-i-1) * (n-i)

乘以a[i]加起来就是答案

拙劣代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define MOD 998244353

using namespace std;

// n最大为100000, n^2算法不可取

int n;
// long long an[1000005];
long long _2n[1000005];


int main(int argc, char const *argv[]) {

scanf("%d", &n);

_2n[0] = 1;


int b = 1;
for (int i = 1; i < n; ++i) {
b = (b * 2) % MOD;
_2n[i] = b;
}


long long a;
long long ans = 0;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a);
ans = (ans + ((_2n[n - i] + ((n - i) * _2n[n - i - 1]) % MOD) * a) % MOD) % MOD;
}

printf("%lld\n", ans);


// TL旧代码

// for (int k = 1; k <= n; ++k) {
// ans = (ans + ans) % MOD;
// printf("x2\n");
// for (int i = 1; i < k; ++i) {
// ans = (ans + an[i] * _2n[k - i - 1]) % MOD;
// printf("+a[%d] x 2^%d\n", i, k - i - 1);
// }
// ans = (ans + an[k]) % MOD;
// printf("+a[%d] x 2^0\n", k);
// }


return 0;
}