Why down vote ? Please dont down vote if you dont want to help. Is there any problem in asking for help on CF ?
Please provide hint to solve LineMSTDiv2. I looked into code of some participants but could not understand. I also posted same on topcoder's forum but it seams forum is inactive.TC forum linkk
Given is an N.
A complete graph is a graph in which each pair of vertices is connected by exactly one undirected edge.
A graph is called beautiful if:
It is a complete graph on N vertices. Each edge has an associated cost, and each of these costs is either 1 or 2. Hence, there are exactly 2^(N*(N-1)/2) different beautiful graphs. The minimum spanning tree (MST) of a beautiful graph is its subgraph with the following properties:
The subgraph contains all N vertices. The subgraph is connected. (I.e., it is possible to get from any vertex to any other vertex using only edges that belong to the subgraph.) The total cost of edges in the subgraph is as small as possible. A single beautiful graph can have multiple MSTs. (Each of these MSTs will contain a different set of edges, but they will have the same total cost.) An MST is called a line if the degree of each of its vertices is at most 2. Hibiki likes MSTs. She also likes lines. For each beautiful graph G, let f(G) be the number of its MSTs that are lines. (Note that for some beautiful graphs it may be the case that f(G)=0.)
Let X be the sum of the values f(G) over all beautiful graphs G. Please calculate X for her. As X can be very large, compute and return the value (X modulo 1,000,000,007).
Definition Class: LineMSTDiv2 Method: count Parameters: int Returns: int Method signature: int count(int N) (be sure your method is public) Limits Time limit (s): 2.000 Memory limit (MB): 256 Constraints - N will be between 2 and 16, inclusive. Examples 0) 3 Returns: 15 Beautiful graphs are complete graphs on 3 vertices in which each edge has cost either 1 or 2. There are 8 such graphs. Some of these graphs have more than one MST. For example, the graph in which each edge has cost 1 has three different MSTs. In this case, each of those three MSTs is a line, so we count each of them. 1) 2 Returns: 2 There are only 2 beautiful graphs. The value of f is 1 for both graphs, so the answer is 2. 2) 16 Returns: 682141922 Don't forget to take modulo.
