Cerinta completa

HackerRank-city is an acyclic connected graph (or tree). Its not an ordinary place, the construction of the whole tree takes place in steps. The process is described below:

  • It initially has node.
  • At each step, you must create duplicates of the current tree, and create new nodes to connect all copies in the following H shape:

At each step, the tree becomes times bigger plus new nodes, as well as new edges connecting everything together. The length of the new edges being added at step is denoted by input .

Calculate the sum of distances between each pair of nodes; as these answers may run large, print your answer modulo .

Input Format

The first line contains an integer, (the number of steps). The second line contains space-separated integers describing , .

Constraints

Subtask
For score

Output Format

Print the sum of distances between each pair of nodes modulo .

Sample Input 0

1
1

Sample Output 0

29

Sample Input 1

2
2 1

Sample Output 1

2641

Explanation

Sample 0
In this example, our tree looks like this:

Let denote the distance between nodes and .




.

We print the result of as our answer.

Sample 1

In this example, our tree looks like this:

We calculate and sum the distances between nodes in the same manner as Sample 0 above, and print the result of our , which is .

Limbajul de programare folosit: cpp14

Cod:

/*
*
* Tag: DP
* Time: O(n)
* Space: O(1)
*/
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
int n, ne;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    long long nv = 1;
    long long sd = 0;
    long long dtc = 0;
    long long diam = 0;
    scanf("%d",&n);
    for(int i = 1; i <= n; ++ i){
        scanf("%d",&ne);
        long long nnv = nv * 4 + 2;
        long long nsd = 4 * sd + 4 * dtc * (2 + 3 * nv % MOD) % MOD + 4 * ne * nv % MOD * (nv * 3 + 2) % MOD +
            ne * (2 * nv + 1) % MOD * (2 * nv + 1) % MOD;
        long long ndtc = 4 * dtc + 8 * ne * nv % MOD + 3 * ne + (3 * nv + 2) * diam % MOD;
        long long ndiam = 2 * diam + 3 * ne;
        nv = nnv % MOD;
        sd = nsd % MOD;
        dtc = ndtc % MOD;
        diam = ndiam % MOD;
    }
    printf("%lld\n",sd);
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464656112

Link challenge: https://www.hackerrank.com/challenges/hr-city/problem

HackerRank City