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.
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
827421
775313
Returns: 736123117
212436
121412
Returns: 188360077
640235
377632
Returns: 720512749
62362
43138
Returns: 185497916
615650
69414
Returns: 559070067
31126
5813
Returns: 307521596
802752
754811
Returns: 310856111
783987
131547
Returns: 604034955
349448
91532
Returns: 571954254
178679
108511
Returns: 207393333
161094
37275
Returns: 323100736
477973
85831
Returns: 156079258
772652
510179
Returns: 136796807
876501
301185
Returns: 980559818
171380
152753
Returns: 207623635
633301
555729
Returns: 420775089
178
157
Returns: 391219835
258039
47006
Returns: 369279582
46231
29323
Returns: 320651413
883637
521988
Returns: 643339842
2
1
Returns: 1
2
2
Returns: 0
1000000
1
Returns: 227835248
1000000
31
Returns: 230401008
1000000
999986
Returns: 336133727
1000000
999997
Returns: 950105778