ConnectedStates
SRM 697 · 2016-07-09 · by Arterm
Problem Statement
A faraway land is divided into n states, numbered 0 through n-1.
You are given a
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:
- For each i, let x[i] be the number of federal roads that have one endpoint in state i.
- 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.
Constraints
- 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
Submissions are judged against all 25 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ConnectedStates with a public method int getSum(vector<int> a) · 25 test cases · 2 s / 256 MB per case