Cerinta completa

Consider an array, , of length . We can split into contiguous segments called pieces and store them as another array, . For example, if , we have the following arrays of pieces:

  • contains three -element pieces.
  • contains two pieces, one having elements and the other having element.
  • contains two pieces, one having element and the other having elements.
  • contains one -element piece.

We consider the value of a piece in some array to be , and we consider the total value of some array to be the sum of the values for all pieces in that . For example, the total value of is .

Given , find the total values for all possible ‘s, sum them together, and print this sum modulo on a new line.

Input Format

The first line contains a single integer, , denoting the size of array .
The second line contains space-separated integers describing the respective values in (i.e., ).

Constraints

Output Format

Print a single integer denoting the sum of the total values for all piece arrays (‘s) of , modulo .

Sample Input 0

3
1 3 6

Sample Output 0

73

Explanation 0
Given , our piece arrays are:

  • , and .
  • , and .
  • , and .
  • , and .

When we sum all the total values, we get . Thus, we print the result of on a new line.

Sample Input 1

5
4 2 9 10 1

Sample Output 1

971

Limbajul de programare folosit: java8

Cod:

import java.io.*;

public class Solution {
    static final long MOD = 1_000_000_007L;

    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        long nextLong() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            long val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return sign == 1 ? val : -val;
        }
        int nextInt() throws IOException { return (int) nextLong(); }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = fs.nextLong() % MOD;

        long[] pow2 = new long[Math.max(1, n)];
        pow2[0] = 1;
        for (int i = 1; i < n; i++) pow2[i] = (pow2[i - 1] * 2L) % MOD;

        long[] preA = new long[n];
        long[] preLA = new long[n];
        long sA = 0, sLA = 0;
        for (int i = 0; i < n; i++) {
            long alpha = (i == 0) ? 1L : pow2[i - 1];
            sA = (sA + alpha) % MOD;
            sLA = (sLA + alpha * i) % MOD;
            preA[i] = sA;
            preLA[i] = sLA;
        }

        long[] sufB = new long[n];
        long[] sufRB = new long[n];
        long sB = 0, sRB = 0;
        for (int r = n - 1; r >= 0; r--) {
            long beta = (r == n - 1) ? 1L : pow2[n - r - 2];
            sB = (sB + beta) % MOD;
            sRB = (sRB + beta * (r + 1)) % MOD;
            sufB[r] = sB;
            sufRB[r] = sRB;
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long coef = (preA[i] * sufRB[i]) % MOD;
            coef = (coef - (preLA[i] * sufB[i]) % MOD + MOD) % MOD;
            ans = (ans + a[i] * coef) % MOD;
        }

        System.out.println(ans);
    }
}

Scor obtinut: 1.0

Submission ID: 464617318

Link challenge: https://www.hackerrank.com/challenges/summing-pieces/problem

Summing Pieces