Problem Statement
This problem has a non-standard time limit: 7 seconds.
You have a complete undirected graph with N labeled vertices. You have to assign a positive integer weight less than or equal to K to each of its N*(N-1)/2 edges.
Count all those assignments of weights such that the graph has a unique minimum spanning tree. Return the count modulo a prime number M .
Definition
- Class:
- UniqueMST
- Method:
- count
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int count(int N, int K, int M)
- (be sure your method is public)
Notes
- A tree is a connected graph with no cycles.
- A spanning subgraph of G is a subgraph that contains all vertices of the original graph G.
- A spanning tree of G is a spanning subgraph of G that is a tree.
- A minimum spanning tree of G is a spanning tree such that the sum of its edge weights is the smallest among all spanning trees of G.
Constraints
- N will be between 2 and 50, inclusive.
- K will be between 1 and 10 9 , inclusive.
- M will be a prime number between max(N, K) + 1 and 10 9 , inclusive.
Examples
2
5
29
Returns: 5
With just two vertices and a single edge between them the MST is always unique.
3
3
11
Returns: 4
As there are three vertices, the MST is unique if and only if the edge with maximum weight is unique. This happens for the following assignments of weights: There are 3 assignments where the edge weights are 1, 1, 2 in some order. There are 3 assignments where the edge weights are 1, 1, 3 in some order. There are 6 assignments where the edge weights are 1, 2, 3 in some order. There are 3 assignments where the edge weights are 2, 2, 3 in some order. Thus, the total number of good assignments of weights is 3 + 3 + 6 + 3 = 15 and the returned answer is (15 mod 11) = 4.
42
919191919
999999937
Returns: 440488107
2
1
928456201
Returns: 1
2
909162575
951257777
Returns: 909162575
3
1
250085021
Returns: 0
3
11642860
493068613
Returns: 304156807
4
6
221772839
Returns: 28380
4
550301221
779604101
Returns: 301025198
5
4
220369169
Returns: 318980
5
800442071
857828639
Returns: 451426624
6
6
968425789
Returns: 428192577
6
70655756
980781293
Returns: 500985141
7
18
676865867
Returns: 305408735
7
47912778
743895547
Returns: 85948516
8
11
874228727
Returns: 147073895
8
940574733
995241547
Returns: 187331877
9
32
214894151
Returns: 116676764
9
245335607
422631533
Returns: 366754759
10
39
764872649
Returns: 86482968
10
463577972
584780023
Returns: 20979911
11
19
838005877
Returns: 181226472
11
187900365
938581993
Returns: 214310082
12
1
141065651
Returns: 0
12
705685934
779746763
Returns: 358689516
13
30
390017933
Returns: 69824924
13
902320204
987309131
Returns: 291070568
14
9
626592839
Returns: 57465573
14
529591666
635947729
Returns: 4155685
15
93
718043101
Returns: 509698071
15
588166901
851574001
Returns: 653239712
16
57
496177853
Returns: 51680458
16
338024498
791122909
Returns: 189111442
17
85
461019943
Returns: 237811585
17
948967812
988908209
Returns: 223040231
18
96
217652791
Returns: 153562164
18
774812158
780460951
Returns: 761833670
19
151
79213369
Returns: 53345485
19
595664103
874482823
Returns: 208129538
20
41
552261377
Returns: 329784392
20
646715786
751803659
Returns: 520308255
20
322056404
378207943
Returns: 2414326
21
6
797806517
Returns: 168830911
21
906238042
976883849
Returns: 507422379
21
739801292
794632417
Returns: 467316099
22
102
821390341
Returns: 754294059
22
167116650
175175527
Returns: 133926690
22
426027352
680910577
Returns: 154700578
23
232
586225117
Returns: 368361403
23
120780915
433847377
Returns: 70082064
23
35045202
944931749
Returns: 410831448
24
62
199573733
Returns: 96253579
24
807518587
938350577
Returns: 193408357
24
458146652
820693121
Returns: 545256888
25
129
537044537
Returns: 108221039
25
613967476
923719777
Returns: 238825909
25
521097471
557411027
Returns: 487233871
26
195
515324647
Returns: 463048899
26
666866643
965835029
Returns: 194121870
26
601102508
829474573
Returns: 405746544
27
320
625188631
Returns: 483462980
27
993893007
999950033
Returns: 966261496
27
306380519
333968819
Returns: 281522642
28
345
700762999
Returns: 507386260
28
448690393
830000467
Returns: 318372227
28
465598336
837996193
Returns: 161762391
29
277
746667461
Returns: 252510643
29
316687775
336293519
Returns: 89538271
29
371811873
649908197
Returns: 590866173
30
187
612355309
Returns: 585985233
30
376503710
574915067
Returns: 447121233
30
511071978
805292051
Returns: 221474196
30
416781937
449668889
Returns: 170821864
31
432
260618977
Returns: 93889243
31
641105119
741754229
Returns: 727220842
31
998285052
999580223
Returns: 872561035
31
807087801
837997397
Returns: 813931456
32
131
961319561
Returns: 257896100
32
465543630
899442521
Returns: 658486134
32
592258815
737205671
Returns: 157312908
32
255947943
885446957
Returns: 853269686
33
299
868620143
Returns: 747205832
33
470244382
585562673
Returns: 294765092
33
321969146
921562583
Returns: 276956003
33
665142829
998005037
Returns: 688644495
34
92
770820251
Returns: 403733622
34
692269405
833254801
Returns: 480265207
34
809022116
816706663
Returns: 231944565
34
677963490
712005103
Returns: 37570437
35
177
104842753
Returns: 283178
35
527250190
875702383
Returns: 433767570
35
250626345
785702201
Returns: 67831715
35
56854256
828686321
Returns: 702394134
36
148
688276313
Returns: 296982311
36
730286868
801138197
Returns: 730256389
36
908599635
951570443
Returns: 822456899
36
242213084
412000033
Returns: 357333537
37
510
65055847
Returns: 36340461
37
455872664
469803463
Returns: 271713077
37
859861004
958456633
Returns: 427051061
37
909680561
961417937
Returns: 250723357
38
444
474388331
Returns: 461331443
38
254173221
330042941
Returns: 76069173
38
853941360
972412979
Returns: 376604062
38
640223460
795776669
Returns: 201151100
39
66
994957811
Returns: 928806241
39
223632047
959650541
Returns: 877448602
39
425216836
700899313
Returns: 297818604
39
941352494
945933929
Returns: 519628980
40
750
374351119
Returns: 299689947
40
414029835
843176639
Returns: 193808940
40
831406519
895316633
Returns: 292166307
40
665109470
958402441
Returns: 664365313
40
935037073
939822173
Returns: 634393652
40
980250264
994074113
Returns: 932259527
41
346
526571939
Returns: 403054299
41
316392723
910122571
Returns: 624230064
41
303724844
446676001
Returns: 85840560
41
368884513
823751261
Returns: 684422652
41
509788656
992106571
Returns: 541981592
41
489205864
537222857
Returns: 195765595
42
643
782150911
Returns: 487864008
42
74657600
686312351
Returns: 227271742
42
94183072
480875363
Returns: 262804180
42
745995972
851924449
Returns: 492902532
42
722808622
881757077
Returns: 265801718
42
911431672
919842229
Returns: 780054376
43
823
174882599
Returns: 82230906
43
723068171
968094277
Returns: 582442067
43
794982165
861569407
Returns: 313736602
43
293286313
834939109
Returns: 314236215
43
723254691
957398441
Returns: 213426465
43
870394207
967300291
Returns: 763369334
44
426
419588537
Returns: 395991736
44
509187911
932028917
Returns: 903029178
44
343765918
685719553
Returns: 462036175
44
729604605
859484363
Returns: 156718665
44
431454240
714542359
Returns: 344108794
44
304083450
558786391
Returns: 331626648
45
440
89740303
Returns: 26675191
45
980561035
998301527
Returns: 826654080
45
71367255
199251263
Returns: 120617055
45
580377597
827925317
Returns: 59547856
45
76232232
192349057
Returns: 106532394
45
98605966
931780133
Returns: 592764973
45
519570485
766432439
Returns: 319580110
45
229058297
793106021
Returns: 293799683
45
352342759
443463113
Returns: 287626717
46
405
635942449
Returns: 314043708
46
339472025
530172367
Returns: 302358337
46
624678238
783708559
Returns: 661538165
46
597332024
602843863
Returns: 415661251
46
726389953
801463667
Returns: 604374199
46
99013527
914166263
Returns: 628143860
46
927508908
953638897
Returns: 360893317
46
256011341
899860499
Returns: 185088278
46
66607112
683644501
Returns: 162746569
47
1000
809454067
Returns: 84134281
47
518085241
766081483
Returns: 694270054
47
487023804
924512009
Returns: 658813054
47
818505264
838969531
Returns: 681823535
47
823623954
830879149
Returns: 518450330
47
191649394
341770757
Returns: 267951786
47
658707113
762025279
Returns: 733343622
47
850933855
948080299
Returns: 413086176
47
810438353
919822727
Returns: 612421022
48
365
496673557
Returns: 339028355
48
728170229
739296191
Returns: 50723255
48
255871603
923853737
Returns: 214112068
48
627353994
853810171
Returns: 216661309
48
112581233
705072967
Returns: 328523943
48
350169527
494829277
Returns: 475276678
48
463320132
953398987
Returns: 636924083
48
568491441
700484947
Returns: 649303727
48
472651547
940194973
Returns: 497706103
49
73
57972727
Returns: 23610753
49
250120875
896884649
Returns: 1586999
49
374832543
882633877
Returns: 863673716
49
633962794
877979153
Returns: 601070814
49
786685768
911330201
Returns: 713537231
49
131015166
994147283
Returns: 933073915
49
203972239
640856431
Returns: 184837963
49
179156148
262157737
Returns: 74644902
49
604244670
926279429
Returns: 883043780
50
52
488091803
Returns: 450240851
50
897855406
926554117
Returns: 301269068
50
681664193
711235033
Returns: 526562681
50
143353497
173313271
Returns: 128035502
50
521777532
591817081
Returns: 156742627
50
194526937
555921497
Returns: 350900342
50
778266700
804399587
Returns: 584044910
50
898412708
968405131
Returns: 673749454
50
808235706
809205653
Returns: 543028812
7
2
998244353
Returns: 16807
For N = 7 and K = 2 the MST is unique if and only if all edges with weight 1 form exactly a spanning tree.