SpanningSubgraphs

TCO19 SRM 761 · 2019-06-21 · by lg5293

TCO19 SRM 761 · 2019-06-21 · by lg5293 · Dynamic Programming

Show categories

Class Name: SpanningSubgraphs

Return Type: int[]

Method Name: count

Arg Types: (int, vector<int>, vector<int>)

Problem Statement

You are given an undirected graph with n nodes and m edges. The nodes are numbered 0 through n-1. The edges are given in the int[]s a and b: for each valid index i, there is an edge between a[i] and b[i]. This graph may have self-loops or multiple edges.

Let f(k) denote the number of ways to choose a subset of exactly k edges so the graph consisting of all n nodes and the edges you selected is connected. Let g(k) = f(k) modulo (10^9 + 7).

Return a int[] with exactly m-n+2 elements. For each i starting from 0, element i of the return value should be g(i+n-1).

Constraints

n will be between 1 and 15, inclusive.
m will be between n-1 and 200, inclusive.
a and b will contain exactly m elements each.
Each element of a and b will be between 0 and n-1, inclusive.

Examples

3
{0,1,2}
{1,2,0}
Returns: {3, 1 }

This case is a triangle graph. For k=2, we can choose any subset of 2 edges, for a total of 3 choices. For k=3, we only have one way (choosing all edges).

5
{0,1,4,3}
{0,1,4,3}
Returns: {0 }

Even though m is at least n-1, the graph you are given is not necessarily connected.

6
{0,1,1,2,2,2,3,3,4}
{1,2,3,3,4,5,4,5,5}
Returns: {40, 48, 27, 8, 1 }

15
{7,3,8,2,5,8,5,11,8,3,10,8,6,6,8,8,3,9,4,6,4,6,1,1,5,4,
0,9,4,7,6,0,6,2,2,6,11,4,6,10,9,2,6,0,4,7,6,8,1,3,11,3,
4,8,1,0,12,9,5,14,0,13,7,14,7,9,6,7,8,8,8,4,14,1,13,5,
1,6,13,14,0,4,8,5,13,7,2,10,10,11,8,2,4,13,12,10,5,13,
5,9,6,4,1,11,4,13,6,4,8,8,11,1,14,10,3,1,2,0,10,5,9,5,
10,8,4,2,5,12,7,2,3,2,4,6,9,3,7,9,2,14,14,0,14,3,12,12,
0,11,7,8,6,6,0,10,7,2,0,7,8,10,3,11,11,7,0,0,11,8,6,11,
13,4,11,11,8,5,13,11,9,14,10,1,12,12,3,3,0,13,13,6,2,9,
1,4,2,7,14,5}
{12,8,1,11,1,6,12,3,7,5,1,1,11,11,9,0,7,9,12,8,13,13,11,
0,2,14,12,12,13,10,13,12,2,14,11,13,14,3,12,14,11,5,3,0,
9,0,1,10,5,11,6,6,1,4,0,12,13,1,4,10,9,8,3,4,13,3,10,7,
3,2,13,0,1,13,7,3,3,9,9,10,9,9,0,13,12,3,14,4,1,7,5,0,0,
11,13,0,0,14,13,5,5,0,10,0,3,8,13,4,6,7,4,0,6,7,8,10,7,
4,6,13,0,6,3,2,11,8,7,12,0,14,12,6,10,8,6,9,2,4,14,9,4,
6,3,11,12,8,7,12,14,0,10,11,9,7,4,6,12,13,7,4,13,9,7,13,
2,4,7,6,2,0,10,7,8,13,1,14,13,3,12,14,2,4,6,7,10,11,8,4,
10,13,14,9,0,5,3,0,7,11}
Returns: {165676111, 472152904, 401323420, 92841577, 361806106, 251066093, 860026758, 204774808, 800204699, 78217142, 290847617, 377659363, 799299488, 639266686, 463155556, 542289798, 505455263, 931966095, 332452321, 157494446, 701362585, 4372546, 189983818, 137009880, 456907012, 699388046, 492757156, 402334178, 262521060, 683669243, 218329042, 912344074, 469164876, 951780423, 845657616, 358560958, 877409160, 936645440, 506542339, 711561307, 182417811, 411559656, 609363889, 410499565, 523968597, 808436626, 796861282, 799905851, 332114660, 28142829, 832046308, 515892527, 461122988, 459763203, 639481498, 760842951, 53778152, 531539556, 499281391, 756160187, 408189379, 536177501, 236162240, 932086574, 249801471, 691291871, 305954956, 944526707, 689056121, 509929491, 860012851, 270237338, 530915439, 636690481, 284974622, 213167754, 791793494, 581854637, 515718421, 142304792, 170068497, 175763828, 669814256, 87330307, 657451539, 902803718, 994244944, 710593682, 158314930, 728217704, 428356628, 680806591, 426349961, 578797504, 448716917, 937968991, 727251530, 565010419, 762565871, 373908747, 569188731, 954967822, 83820159, 869337563, 549355611, 927598978, 992408503, 670497964, 348959921, 892858049, 328944072, 946559373, 830835081, 805632932, 389521576, 995252131, 717245242, 882920285, 127735960, 774020953, 299323686, 248711270, 707972648, 824068405, 929290955, 262377161, 603969848, 20319782, 655428762, 772441022, 315946694, 773490199, 63054183, 280718941, 320481045, 714052434, 119312921, 334810041, 844617606, 239955633, 647743078, 159621066, 358764917, 571545322, 29056136, 300270686, 822798951, 841318305, 809733973, 849084831, 542304340, 360014205, 268267900, 461637720, 441483501, 500466014, 722102413, 274028790, 889071123, 456597703, 989359978, 781914152, 339994675, 176509460, 71482668, 940949411, 727100238, 343026545, 279293690, 51741525, 759652847, 198027784, 293410546, 430593193, 339024072, 605239373, 602353448, 433606430, 526225238, 410141720, 62117055, 1274196, 19503, 198, 1 }

11
{9,7,9,10,0,3,2,3,5,2,4,8,8,7,0,0,9,9,5,4,8,3,1,2,0,8,5,9,7,0,10,8,10,3,3,6,2,8,9,3,3,4,0,2,5,6,1,9,8,8,4,7,7,8,6,10,1,8,10,10,10,6,4,1,6,0,0,6,1,2,3,3,5,2,10,5,3,1,3,4,3,1,0,5,7,9,4,3,8,8,5,8,2,6,2,7,7,6,1,2,0,8,3,3,6,0,6,10,7,0,8,5,4,9,10,3,8,0,7,4,6,7,3,3,1,2,3,9,3,2,6,5,4,8,6,4,7,10,4,4,1,5,0,0,1,8,2,8,6,1,8,8,4,2,0,4,2,2,1,9,5,10,0,2,3,0,0,4,9,10,8,1,5,1,0,1,1,4,6,0,4,6,7,5,1,1,1,2,3,7,1}
{3,4,1,5,0,6,2,1,6,1,6,6,3,6,4,9,8,5,8,10,6,0,4,5,4,7,4,7,6,2,8,2,8,8,5,6,3,7,0,9,3,6,7,2,1,4,6,9,10,2,5,8,5,7,5,9,5,2,3,0,9,9,9,9,2,3,4,0,4,4,2,4,9,2,2,6,2,4,10,7,9,2,2,6,9,2,0,9,7,2,3,8,5,4,10,8,0,8,2,7,8,1,2,5,1,7,5,6,9,1,8,8,7,1,10,7,2,3,7,6,9,8,8,9,0,7,4,4,9,9,9,1,8,4,2,6,2,8,3,8,5,4,8,9,8,4,10,3,10,2,5,2,7,6,7,7,3,3,7,7,3,9,4,2,8,6,3,1,2,0,1,9,4,10,1,5,6,9,1,3,2,10,8,10,1,0,9,5,5,9,3}
Returns: {893669088, 511476181, 282512084, 204868369, 827684458, 753623853, 779479514, 130868091, 295494047, 917851370, 854875531, 958814765, 240849975, 157845883, 622102195, 913263283, 405315794, 809012826, 813515696, 191070296, 590867168, 919567021, 47828500, 30826952, 355521257, 602673207, 983619024, 163283563, 620984798, 437817207, 543277797, 964337289, 172635231, 450854901, 941014602, 789367971, 233602073, 140307308, 817318575, 176469587, 489172694, 703109863, 204330722, 238550446, 589162790, 699374184, 325358096, 767340729, 629085176, 921953706, 642214322, 586099720, 603016227, 810683177, 262588912, 527284057, 91910148, 88002331, 230107207, 321567931, 456509489, 804038940, 637894181, 549340450, 523746612, 407552985, 392510391, 580264675, 617617647, 548967397, 324471128, 205848941, 541443883, 871724605, 264648536, 341058372, 744313114, 196536486, 672386217, 787395862, 132773522, 354224286, 856232773, 896814207, 505371352, 793625345, 715976191, 55859557, 916580845, 270440360, 237456920, 584372195, 993074347, 762136722, 300158097, 989580701, 315088889, 622479523, 273337088, 533852003, 96943652, 308767574, 543107532, 473545425, 91576676, 471929027, 95302820, 590595310, 912268096, 854366785, 278603417, 916957034, 384943096, 970993378, 310329205, 344160454, 186054755, 320956801, 391079590, 899147276, 469157721, 824819320, 827835853, 307183699, 355673479, 847674931, 955516777, 334736895, 699697175, 718652576, 986205872, 348244540, 903221557, 38032435, 572721671, 279932471, 337718296, 839234008, 770599557, 112449652, 203508874, 54728043, 389821452, 391114059, 782994181, 962188083, 68390657, 905554819, 749887675, 894064096, 447135777, 37339811, 156577456, 363319287, 662114010, 192784078, 50771722, 197452611, 885450934, 747725881, 355588078, 78756431, 102180981, 80586351, 525577902, 982484717, 180225884, 15273380, 911313643, 842721108, 456181410, 834353572, 902986466, 323097697, 274917293, 291483359, 9402689, 53727345, 1143135, 18145, 191, 1 }

Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SpanningSubgraphs with a public method vector<int> count(int n, vector<int> a, vector<int> b) · 63 test cases · 2 s / 256 MB per case