SpanningNoLine | Topcoder Archive

Problem Statement

You are given the ints n and m.

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.

Definition

Class:: SpanningNoLine
Method:: countSpanning
Parameters:: int, int
Returns:: int
Method signature:: int countSpanning(int n, int m)
(be sure your method is public)

Constraints

n will be between 1 and 1,000,000, inclusive.
m will be between 1 and n, inclusive.

Examples

```
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
```
```
1000000
```
```
1000000
```
```
Returns: 747129624
```
```
1
```
```
1
```
```
Returns: 1
```

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)2024, Topcoder, Inc. All rights reserved.