Statistics

Problem Statement for "Sunnygraphs2"

Problem Statement

Hero has just constructed a very specific graph. He started with n isolated vertices, labeled 0 through n-1. For each vertex i Hero then chose a vertex a[i] (other than i) and he added an edge that connected i and a[i]. This way he created a graph with n vertices and n edges. Note that if a[x]=y and a[y]=x, the vertices x and y were connected by two different edges. Hero now wants to perform the following procedure:
  1. Add a new isolated vertex number n.
  2. Choose a subset M of the original vertices.
  3. For each x in M, erase an edge between vertices x and a[x].
  4. For each x in M, add a new edge between vertices x and n.
Hero's goal is to create a final graph in which the vertices 0 through n-1 are all in the same connected component. (I.e., there must be a way to reach any of these vertices from any other of them by following one or more consecutive edges, possibly visiting vertex n along the way.) Note that Hero does not care whether vertex n is in the same component as the other vertices: both possibilities are fine. In step 2 of the above procedure Hero has 2^n possible subsets to choose from. A choice of M is good if it produces a graph with the desired property. Count how many of the 2^n possibilities are good choices. Return that count as a long.

Definition

Class:
Sunnygraphs2
Method:
count
Parameters:
int[]
Returns:
long
Method signature:
long count(int[] a)
(be sure your method is public)

Constraints

  • a will contain n elements.
  • n will be between 2 and 50, inclusive.
  • Each element in a will be between 0 and n - 1, inclusive.
  • For each i between 0 and n - 1 holds a[i] != i.

Examples

  1. {1,0}

    Returns: 4

    The original graph contained the vertices 0 and 1. This pair of vertices was connected by two edges. Next, Hero added a new vertex 2. Then he had to choose one of four possible subsets M: If he chose M = {}, the resulting graph contained the edges 0-1 and 0-1. The vertices 0 and 1 were in the same component. If he chose M = {0}, the resulting graph contained the edges 0-1 and 0-2. The vertices 0 and 1 were in the same component. If he chose M = {1}, the resulting graph contained the edges 0-1 and 1-2. The vertices 0 and 1 were in the same component. Finally, if he chose M = {0, 1}, the resulting graph contained the edges 0-2 and 1-2. And again, the vertices 0 and 1 were in the same component. (In the resulting graph we can still go from vertex 0 to vertex 1, even though we have to go via vertex 2.) As all four choices of M are good, the correct answer is 4.

  2. {1,0,0}

    Returns: 7

    Here, M = {2} is not a good choice. This choice produces a graph with edges 0-1, 0-1, and 2-3. In this graph vertex 2 is not in the same component as vertices 0 and 1. The other seven possible choices of M are all good.

  3. {2,3,0,1}

    Returns: 9

  4. {2,3,0,1,0}

    Returns: 18

  5. {2,3,0,1,0,4,5,2,3}

    Returns: 288

  6. {29,34,40,17,16,12,0,40,20,35,5,13,27,7,29,13,14,39,42,9,30,38,27,40,34,33,42,20,29,42,12,29,30,21,4,5,7,25,24,17,39,32,9}

    Returns: 6184752906240

    "Watch out for integer overflow."

  7. {6,11,27,33,0,13,2,22,15,11,7,19,17,23,30,8,9,22,6,16,16,30,0,20,4,8,5,12,31,26,16,12,25,15,12}

    Returns: 23970447360

  8. {23,24,4,6,20,16,26,11,28,24,9,26,13,17,28,8,12,9,11,3,5,19,18,24,0,27,30,23,6,11,5}

    Returns: 1879048193

  9. {16,6,21,17,21,9,0,10,18,17,12,24,23,15,22,23,4,14,22,21,4,22,24,3,23}

    Returns: 33030145

  10. {12,7,12,25,8,20,9,9,25,21,13,22,21,6,5,13,18,0,16,12,5,10,9,24,12,23}

    Returns: 36569088

  11. {11,9,16,14,3,4,14,12,4,5,4,15,4,4,9,14,5}

    Returns: 126977

  12. {18,18,20,28,7,27,8,13,40,3,7,21,30,17,13,34,29,16,15,11,0,9,39,36,38,23,24,8,4,9,29,22,35,5,13,23,3,27,34,23,8}

    Returns: 1646046216192

  13. {3,3,0,11,8,11,14,8,4,7,12,12,13,7,8,14}

    Returns: 49153

  14. {5,2,11,12,12,4,3,2,6,8,3,0,2}

    Returns: 8065

  15. {1,0}

    Returns: 4

  16. {7,10,14,2,13,8,4,3,11,1,1,0,4,1,7}

    Returns: 23040

  17. {27,30,16,23,5,25,9,24,3,24,11,14,2,24,25,23,4,11,5,25,15,15,31,15,12,19,12,17,4,15,24,26}

    Returns: 2415919104

  18. {9,2,0,43,12,14,39,25,24,3,16,17,22,0,6,21,18,29,34,35,23,43,28,28,20,11,5,12,31,24,8,13,17,10,15,9,15,26,4,13,21,27,36,39}

    Returns: 17317308137473

  19. {1,0,0,2,1}

    Returns: 25

  20. {3,2,1,2,2,6,0}

    Returns: 97

  21. {27,14,25,17,18,1,20,19,29,8,22,29,24,16,7,25,23,0,0,6,5,14,15,6,12,4,1,29,5,22}

    Returns: 795893760

  22. {15,19,18,22,6,10,15,0,10,19,15,6,7,22,7,3,10,1,8,15,13,5,20}

    Returns: 7340033

  23. {7,13,5,13,12,10,8,12,9,12,1,1,8,9}

    Returns: 14337

  24. {11,16,15,0,0,11,5,6,12,14,7,8,3,16,0,14,2}

    Returns: 126977

  25. {16,2,37,12,22,17,4,33,20,25,31,30,16,15,1,38,34,35,21,2,31,39,27,0,4,4,3,16,15,5,12,4,13,26,39,11,38,25,6,26}

    Returns: 1082331758593

  26. {3,3,3,4,0,0,10,4,12,3,13,13,11,14,2}

    Returns: 28673

  27. {44,44,19,44,19,38,5,36,1,46,48,13,47,5,0,42,7,47,40,13,48,45,20,41,7,48,2,12,12,33,24,13,12,7,0,19,4,24,22,7,37,12,32,42,45,30,13,9,39}

    Returns: 562675075514369

  28. {3,2,7,0,7,7,7,0}

    Returns: 193

  29. {7,32,5,21,31,4,24,31,21,2,0,6,30,12,17,1,4,19,15,32,15,19,19,0,3,10,15,30,10,15,21,15,19}

    Returns: 6442450945

  30. {23,8,27,32,34,37,21,4,10,3,25,20,38,14,18,4,36,4,20,18,8,27,39,27,4,12,38,35,38,28,27,35,36,35,21,37,17,31,17,26}

    Returns: 962072674305

  31. {10,27,22,2,5,29,11,0,28,5,30,27,9,10,25,3,24,21,10,24,8,5,29,2,15,4,1,3,19,15,28}

    Returns: 2080374785

  32. {37,29,36,1,27,27,21,9,0,13,14,1,37,15,3,13,32,24,1,32,39,30,28,27,4,35,40,18,10,7,7,4,23,21,23,26,3,10,11,9,0}

    Returns: 1649267441665

  33. {10,13,9,12,9,7,2,9,11,13,5,4,8,12}

    Returns: 16129

  34. {3,13,1,17,17,27,26,11,23,21,14,7,14,26,20,14,3,18,25,20,22,6,16,0,18,10,17,4}

    Returns: 200933376

  35. {3,4,3,4,3}

    Returns: 25

  36. {33,29,15,28,9,2,16,20,20,24,8,17,19,34,20,16,18,20,19,21,37,12,24,31,4,7,16,8,20,22,26,16,36,15,8,11,25,13}

    Returns: 203876728832

  37. {3,19,17,6,20,15,18,6,11,5,15,1,9,16,4,20,4,2,15,13,2}

    Returns: 1572865

  38. {3,25,32,20,33,9,31,6,1,13,4,30,32,31,18,2,25,21,6,33,11,16,33,2,27,9,14,21,6,31,0,28,22,0}

    Returns: 14562623488

  39. {18,28,21,24,12,8,10,1,22,7,2,28,4,8,8,25,13,5,4,24,24,10,2,26,19,1,4,3,8}

    Returns: 264241152

  40. {29,22,9,25,36,34,21,2,12,26,11,39,25,38,3,0,11,19,3,9,37,8,8,45,17,26,21,2,34,48,26,21,42,28,25,23,13,27,21,25,21,10,12,3,8,48,39,27,39}

    Returns: 545357767376897

  41. {4,2,3,2,5,0}

    Returns: 42

  42. {31,24,31,16,13,7,31,29,16,26,6,29,19,15,25,12,10,9,5,16,7,12,28,5,28,6,22,4,29,15,14,33,17,6}

    Returns: 15032385537

  43. {25,25,4,0,23,9,18,11,5,16,24,17,3,4,25,21,5,1,16,16,1,16,12,6,14,15}

    Returns: 58720257

  44. {3,3,0,1}

    Returns: 13

  45. {7,6,1,4,5,1,2,8,3}

    Returns: 449

  46. {3,3,5,2,2,1}

    Returns: 61

  47. {16,32,24,13,25,27,14,8,32,13,31,1,23,17,0,17,33,18,5,5,5,4,32,29,33,21,22,23,0,9,4,26,7,10}

    Returns: 13101957120

  48. {8,8,7,6,2,2,10,12,13,2,12,3,5,12,5,3}

    Returns: 61441

  49. {16,0,10,12,19,15,2,15,16,13,2,1,4,3,8,14,9,5,10,13,16,20,16,3,10}

    Returns: 24379392

  50. {5,12,14,8,18,19,17,36,11,30,19,12,21,23,16,7,15,14,13,12,8,26,18,24,4,26,30,36,18,21,36,20,39,29,3,34,7,30,30,31}

    Returns: 798863917056

  51. {38,21,23,29,41,12,0,19,40,5,7,24,23,11,33,9,5,34,35,36,5,24,28,17,3,23,0,0,16,14,35,14,30,41,0,21,3,16,26,35,23,1}

    Returns: 3833258311680

  52. {3,0,0,0}

    Returns: 13

  53. {1,4,0,6,7,4,2,6,6}

    Returns: 505

  54. {1,3,3,0}

    Returns: 15

  55. {5,4,4,4,2,10,0,4,2,1,2}

    Returns: 1537

  56. {12,4,12,4,6,8,3,13,11,5,6,12,14,3,15,1,12,7,8,9}

    Returns: 917505

  57. {23,10,37,7,27,16,3,32,31,48,3,31,14,29,6,17,23,6,7,29,24,16,47,32,48,17,27,8,45,38,42,37,7,12,18,28,44,30,37,46,30,2,39,3,41,21,34,26,44,15}

    Returns: 844424930131969

  58. {3,5,12,1,22,13,10,15,21,17,17,6,4,21,0,11,22,2,7,21,9,5,3}

    Returns: 7340033

  59. {22,45,10,35,38,7,7,12,14,44,29,18,46,34,28,33,31,4,6,24,10,8,29,13,30,40,25,4,11,2,22,37,27,42,16,9,7,31,10,13,38,25,15,2,34,1,45,2}

    Returns: 121221156962304

  60. {22,42,21,47,20,23,22,1,43,29,11,2,42,9,8,34,32,0,20,1,32,46,7,34,31,29,4,14,32,24,41,44,2,32,36,31,8,31,8,0,41,11,1,31,9,48,20,36,24}

    Returns: 396236502859776

  61. {15,12,13,11,2,0,0,11,5,14,6,7,0,10,5,17,7,5,12}

    Returns: 368640

  62. {28,37,36,30,39,40,42,40,34,40,40,36,27,25,4,23,24,11,7,28,33,0,32,11,1,35,12,33,44,33,29,24,29,9,27,30,8,22,45,42,8,25,27,21,14,42}

    Returns: 69269232549889

  63. {19,14,17,8,3,1,17,1,11,5,14,19,19,3,13,0,17,15,15,6}

    Returns: 1015809

  64. {32,23,4,4,25,14,30,25,18,13,31,6,9,29,31,24,36,18,26,7,2,1,6,3,5,33,7,14,16,33,19,12,13,36,0,16,11}

    Returns: 136902082561

  65. {34,8,15,31,13,2,28,11,26,24,6,17,37,29,36,34,31,29,32,26,13,11,15,29,17,0,12,36,31,7,26,2,35,23,40,20,17,25,25,33,21}

    Returns: 2061584302081

  66. {24,32,25,48,10,30,13,45,44,0,42,37,29,21,20,28,11,39,7,49,47,16,27,46,31,17,33,6,2,5,36,19,18,3,41,15,8,34,43,38,22,14,12,4,26,35,9,23,40,1}

    Returns: 1125899906842624

  67. {1,2,0,2,3,3,2,6,6,2,3,4,2,4,7,0,7,3,7,9,1,6,5,16,9,18,1,17,8,26,2,7,8,13,11,30,21,5,20,37,35,1,13,3,20,32,17,1,44,23}

    Returns: 985162418487297

  68. {1,0,0,2,3,4,5,6,0,2,0,5,9,3,11,3,2,2,10,4,18,20,3,14,21,14,13,18,21,24,28,28,13,26,10,11,19,29,15,38,0,15,26,4,5,10,35,35,40,1}

    Returns: 844424930131969

  69. {9,10,15,16,11,2,7,3,12,8,13,5,6,0,4,1,14,10,15,8,8,1,13,15,12,2,7,24,21,21,9,5,27,13,15,0,25,12,4,3,33,15,3,37,42,2,16,18,42,13}

    Returns: 1125891316908033

  70. {10,9,3,5,0,6,7,11,12,13,8,4,15,14,2,1,15,9,4,11,5,14,21,5,1,24,17,0,22,23,0,11,13,20,17,26,13,20,5,31,34,38,7,40,39,30,43,40,17,26}

    Returns: 1125882726973441

  71. {1,0,0,1,1,0,2,5,4,4,6,0,4,6,5,0,6,0,7,7,1,3,15,22,13,10,18,22,19,28,24,21,29,3,11,25,3,27,9,18,12,10,16,16,0,31,36,35,6,8}

    Returns: 844424930131969

  72. {29, 34, 40, 17, 16, 12, 0, 40, 20, 35, 5, 13, 27, 7, 29, 13, 14, 39, 42, 9, 30, 38, 27, 40, 34, 33, 42, 20, 29, 42, 12, 29, 30, 21, 4, 5, 7, 25, 24, 17, 39, 32, 9 }

    Returns: 6184752906240

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.
This problem was used for: