【题解】HackerRank - Summing Pieces

题目

https://www.hackerrank.com/challenges/summing-pieces

题意

给定一列数,分割成任意多段,某一种分法的值为每一段的数字和和段长之积之和,求所有方案的值的总和。

题解

  • 首先写一个会超时的$O(n^2)$的算法
1
2
3
4
5
FOR(i, 1, n + 1)
FOR(j, 0, i) {
cnt[i] += cnt[j]; // cnt[i] = 2 ^ (i - 1)
dp[i] += dp[j] + (p[i] - p[j]) * (i - j) * cnt[j]; // p[i]: prefix sum
}
  • 发现$n$个数有$2^{n-1}$种方案(可以理解为有$n-1$个空隙,每个空隙都可以选择是否插板)
  • 根据数据范围,这道题目要求$O(n)$的算法

官方题解

题解

  • 考虑长度为 l 的一段
  • 它所有的位置覆盖每一个数的次数是这样的:
    1, 2, … , m - 1, m, m, … , m, m - 1, …, 2, 1 (m = min(l, n + 1 - l))
  • 对于某一个位置
    • 如果有一端在头或者尾,则被计算的次数为$2^{n-l-1}$
    • 如果在中间,则被计算的次数为$2^{n-l-2}$
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
#include <bits/stdc++.h>
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
using namespace std;
typedef long long LL;
const LL MOD = 1E9 + 7;
const int maxn = 1E6 + 10;
LL n, a[maxn], l[maxn], r[maxn], s[maxn], p[maxn] = {1};
LL dp[maxn], cnt[maxn] = {1};

inline LL go(LL x) {
return l[x] + r[n + 1 - x] + (s[n - x] - s[x]) * x;
}

int main() {
FOR(i, 1, maxn) p[i] = (p[i - 1] * 2) % MOD;
cin >> n;
FOR(i, 1, n + 1) {
scanf("%lld", &a[i]);
l[i] = (i * a[i] + l[i - 1]) % MOD;
s[i] = (a[i] + s[i - 1]) % MOD;
}
FORD(i, n, 0)
r[i] = (r[i + 1] + a[i] * (n + 1 - i)) % MOD;
LL ans = n * s[n] % MOD;
FOR(i, 1, n) {
int t = ((s[i] + s[n] - s[n - i]) % MOD + MOD) % MOD;
if (i != n - 1) ans += (go(min(i, n + 1 - i)) - t) % MOD * i % MOD * p[n - i - 2];
ans += p[n - i - 1] * t % MOD * i % MOD;
ans = (ans % MOD + MOD) % MOD;
}
cout << ans << endl;
}