SpanningNoLine
TCO19 Semifinal 1 · 2019-11-14 · by lg5293
Problem Statement
You are given the
Consider an undirected complete graph with n nodes, labeled 1 through n. Remove the m-1 edges that form a path between nodes 1 and m. The resulting graph will then contain all edges between all pairs of nodes, except for the pairs (1,2), (2,3), ..., (m-1, m).
Count the number of spanning trees in the resulting graph, modulo 998244353.
Constraints
- n will be between 1 and 1,000,000, inclusive.
- m will be between 1 and n, inclusive.
3 1 Returns: 3
This is a complete graph on 3 nodes. There are three spanning trees in this graph.
3 2 Returns: 1
This is a graph on 3 nodes with the edges (1,3) and (2,3). There is only one spanning tree in this graph.
3 3 Returns: 0
4 4 Returns: 1
50 20 Returns: 565865762
Submissions are judged against all 33 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SpanningNoLine with a public method int countSpanning(int n, int m) · 33 test cases · 2 s / 256 MB per case