【题解】HackerRank - Summing Pieces

Posted on In Comments:

题目

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)\)的算法

官方题解

  • https://www.hackerrank.com/challenges/summing-pieces/editorial
  • 将 dp[i] 的和式进行变形，利用前缀和快速转移

题解

  • 考虑长度为 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;
}