Get Time

   Problem Statement  

 Problem Statement for ConnectedStates

Problem Statement


A faraway land is divided into n states, numbered 0 through n-1. You are given a int[] a with n elements. For each i, the value a[i] is the number of cities which lie in state i.

Each state has its own connected road network. (The topology of that network does not matter in this problem.) There are no roads between different states. The n states have now decided to form a federation. Therefore, they need to connect all their road networks. They will do so by building exactly n-1 federal roads. Each federal road will be a bidirectional road that connects two cities in different states.

Consider all possible ways of building a set of exactly n-1 federal roads in such a way that it will be possible to travel between any two cities in the federation. For each such set S of n-1 federal roads, compute a single integer V(S) by following the steps listed below:

  1. For each i, let x[i] be the number of federal roads that have one endpoint in state i.
  2. The integer V(S) is the product of all x[i].

Compute the sum of V(S) over all possible choices of the set S. Return the answer modulo 10^9 + 7.



Method signature:int getSum(int[] a)
(be sure your method is public)


-a will contain between 2 and 2000 elements, inclusive.
-Each element of a will be between 1 and 1,000,000,000, inclusive.


{3, 10}
Returns: 30
There will be exactly one federal road, and there are 30 distinct ways to build it. For each of those ways we have x[0]=x[1]=1, so the integer we get is 1*1 = 1. Hence, the answer is 30 * 1 = 30.
{2, 2, 2}
Returns: 96
Here we have 48 distinct ways to choose the two federal roads. For each of those ways, one of the x[i] will be 2 and the other two will be 1. Hence, in each of the 48 ways the integer we'll compute will be 1*1*2 = 2. The final answer is therefore 48 * 2 = 96.
{1, 1, 1, 1}
Returns: 60

Here we have four states, each with a single city. Let's label the cities A, B, C, and D.

One possible way of building three federal roads is to build the roads A-B, A-C, and A-D. In this case the values x[i] will be {3, 1, 1, 1}, so the integer we'll compute will be 3*1*1*1 = 3. There are four different sets of federal roads that produce the value 3.

Another way is to build the roads A-B, A-C, and B-D. Here, the values x[i] are {2, 2, 1, 1}, and therefore the computed integer is 2*2*1*1 = 4. There are twelve sets of federal roads that look like this one.

The final answer is the sum over all possible sets of roads: 4 * 3 + 12 * 4 = 60.

{205659656, 888625810}
Returns: 118040021
Watch out for integer overflow.
{2, 1, 2, 1, 2}
Returns: 27808
{14204721, 921856626, 804287587, 304606131, 277490604, 
310739929, 900757841, 818413665, 155154829, 836327185, 
602928524, 26132484, 587345385, 936362852, 92603422}
Returns: 376924431

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 697 Round 1 - Division I, Level Three