Statistics

Problem Statement for "PSequence"

Problem Statement

You are given a int[] S containing a set of distinct integers. A sequence is called a p-sequence of S if it satisfies both of the following conditions:

1. It contains each element of S exactly once.
2. For each pair of consecutive sequence elements s1 and s2, (s1 - s2) is not divisible by p.

Return the number of p-sequences of S, modulo 1234567891.

Definition

Class:
PSequence
Method:
count
Parameters:
int[], int
Returns:
int
Method signature:
int count(int[] S, int p)
(be sure your method is public)

Constraints

  • S will contain between 1 and 30 elements, inclusive.
  • All elements of S will be distinct.
  • Each element of S will be between -1,000,000 and 1,000,000, inclusive.
  • p will be between 1 and 1,000, inclusive.

Examples

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

    10

    Returns: 120

    All permutations of numbers are valid, so we have 5! = 120 sequences.

  2. {6,2}

    4

    Returns: 0

    Both numbers have the same remainder modulo 4 and so we cannot create a valid 4-sequence from them.

  3. {1,2,3,4}

    3

    Returns: 12

  4. {4,6,8,-3,7}

    2

    Returns: 12

  5. {0,-5,1,2,3,4,5,6,7,8,9,10,12,213,123,122,21,2136,4534,2312,12312,34543,2765,56756,462346,46434,4235,2353,352342,23433}

    4

    Returns: 681816692

  6. {796052,191918,480107,-830356,-895423,-515041,591413,-107359,-433144,-199405,641543,926798,579866}

    4

    Returns: 470634624

  7. {807395,227594,972638,777467,-103510,-71395,247016,250862,214823,-410032,357815}

    6

    Returns: 86400

  8. {-252280,-368452,-303262,-374344,441497,-359356,-210649,-267136,-213643,740639,653444,951005,329633,929117,69836,903329,685898,219437,-612394,-20521,-67453,940187,-93178,-90208,-280285,282425,-659722,479129,-509179}

    64

    Returns: 224458919

  9. {-131224,-835102,-195724,727175,-618208,-933280,-199303,166328,-649837,-810067,-656524,520925,-529534,878546,560873,412826,-17371,-390262}

    4

    Returns: 965607765

  10. {-220576,-546970}

    9

    Returns: 0

  11. {935846,307874}

    2

    Returns: 0

  12. {-225805,108893,-297289,-378832,-649054,-987451,946373,145268,879800,836174,205970,-281833,-976081,562139,279278}

    450

    Returns: 266971431

  13. {60875,711167,786086,740843,-296986,-202264,-450232,1280,656498,-101014,888056,-451798}

    4

    Returns: 10160640

  14. {356048,-549295,650300,69389,-367054,-934147,840023,567719,164588,633239,-149836,-710620,-388705,231293,-555004,-339886,-567820,310628,943397,-460231}

    5

    Returns: 10088554

  15. {174539,95375,-729121,453926,-324496,83600,-46240,-302272,895631,-37600,-673405,168968,-596572,-87658,-160654}

    2

    Returns: 0

  16. {866570,591971,-118828,824093,314495,-308128,413843,832694,772121,-961372,915728,742880,-199069,-806224,909650,824795,-603160,370331,-681574,992786,320339,582509,-741553,21278,309980,-978769,144269,416462,101444}

    240

    Returns: 194500727

  17. {-4399,-355810,-25468,-19537,406946,318539,-90172,493169,-862270,-562051,-743431,-993886,-308461,259397,-78883,-631336,347303,-100735,-117679,-823180,612998,-24130,-606178,195803,-384691,471371,811568,-449575,-883192,-734176}

    1

    Returns: 0

  18. {181481,576347,202304,-378526,-74698,282647,776576,-246487,-240208,329660,509207,-288685,476582,-231022,355907,754679,300353,520178,421304,130955,-965800,-219067,-459706,-212596,-431419,528581,624935,773531,-1105}

    4

    Returns: 20947336

  19. {415196,234992,-82645}

    3

    Returns: 0

  20. {542762,967871,692651,-360223,828677,134255,600782,183944,-839869,-280540,470462,281864,953960,150617,135449,920327,551579,66218,-828760,727688,-596494,254825,-307492,744857,-56908}

    3

    Returns: 0

  21. {-835693,-559921,-314092,-388306,-862930,-75367,-424033,-117853,105128,479021,-829540,-697141,871886,-528046,181295,-86497,-216775,-549826,241859,453632,692300,-901396,-510553}

    9

    Returns: 48165572

  22. {-318037,520736,409835,-611809,-451900,831263,-972661,40232,-466693,-660385,568025,738944,-96664,-319633,897626,491288,-275221,-251767,-346738,884843,-482533,-979975,233573}

    6

    Returns: 0

  23. {-236275,-170533,951341,881867,911969,314765,-507226,828635,565226,-397075,403328,586451,-48382,-322762,4949}

    6

    Returns: 0

  24. {-849022}

    720

    Returns: 1

  25. {68879,9020,949025,-210316,-112690,697934,144095,-655231,-32533,-809809,-446773,650615,-162892,116870,-579526,142628,826535,113765,-289900,-627478,-97585,-440488,16058,159206,-998077,-18019,-312427,383924,-305047}

    7

    Returns: 133068197

  26. {941915,-967405,964460,407921,-400426,74354,-28243,26747}

    848

    Returns: 40320

  27. {-522859,-43597,148781,689315,-700258,-429640,416747,-108715,-233230,-415915,295937,976535,-496180}

    2

    Returns: 0

  28. {-516682,-998515,-95038,-718645,-471073,569426}

    317

    Returns: 720

  29. {505847,188978,648062,-680311,461450,-672691,842465,366989,182816,-408082,919886,76772,588725,-525229,-295960,-158836,-74023,-215098,-186445,-915157,836804,-258592,686015,-266839,-832651,796910}

    5

    Returns: 122824684

  30. {-40771,864890,-169198,-33088,-400552,-632734,978188,684899,-243901,652877,-230890,-141430,-109201,-674854,37460}

    484

    Returns: 266971431

  31. {-22621,-518914,-952639,876017,-774244,-672391}

    874

    Returns: 720

  32. {621245,-505465,330074,-596077,-452671,599798,-290455,-218221,-283546,-112915,863849,-201565,234326,-391537,719609,160958,-690001,-393148,-892441,886034,-560776,316385}

    535

    Returns: 781471490

  33. {298187,-682615,960419,587753,591524,610790,-795952,935081,871985,598952,-466615,-317902,421187,617231,-745543,963503,-486388,-137299,-355399,471461,745202,-311311}

    7

    Returns: 334149367

  34. {360986}

    7

    Returns: 1

  35. {209426,-30286}

    5

    Returns: 2

  36. {-866746,-61450,913577,-470974,-303577,-142063,-42427}

    1

    Returns: 0

  37. {-713977,486746,-525952,-162820,-336223,-868915,337970,381416,-855649,-644374}

    2

    Returns: 0

  38. {-438481,136097,842492,-52921,-175705,-834829,2966,213242,-44203,-204355,291671,-677719}

    6

    Returns: 0

  39. {150110,909311,-125227}

    5

    Returns: 6

  40. {342713,-716071,830861,-276226,489320,775982,991529,-352750,-281911,681437,708977,400991,709754,-571969,170099,-630571,-216808,-925492,457829}

    916

    Returns: 182701988

  41. {-802567,-187021,709586,-848086,178673,246965,-511531,3140,-715066,89774,601055,382634,646199,293465,-800614,772838,109913,950564,-145174,-548377,373367,-120319,-876445,-109411}

    1

    Returns: 0

  42. {-520000,-951823,-925702,612683,208151,909899,-158818,312704,212555,862391,473564,-405550}

    9

    Returns: 1900800

  43. {652790,233264,791582,-511906,279665,-624499,905702,-663952,-401671,992417,-607561,815627,-242680,552512,-221776,337910,425660}

    4

    Returns: 1160923153

  44. {-281158,526175,-400882,-389392,-862114,122915,962894,762689,393782,825668,-846910,111491,186947,-654280,66200,784514}

    4

    Returns: 527847412

  45. {300035,354671,866105}

    2

    Returns: 0

  46. {934862,-166525,395843,105887,-880666,203153,195422,-903742,419387,-55450}

    7

    Returns: 947520

  47. {489179,79955,641582,98039,506447,-253462,903155,-385795,85460,582197,-111484,608630,796832,-383254,-988273,-47485}

    137

    Returns: 1048107835

  48. {615791,316313,751280,-393226,765077,-967129,-439063,965264,-984949,701399,-410995}

    5

    Returns: 7871040

  49. {667931,-131704,-481150,400202,91562,-317416,862811,163856,-426985,458951,-29929,470003,-579670,-951187,-594688,-276919,600338,-688651,611363,-818482,-451306,-406753,-860119}

    7

    Returns: 167016689

  50. {651803,-638923,341954,643616,-201832,831212,264947,-171451,-771727,-928426,-578641,-509971,852797,348176,-344485}

    693

    Returns: 1219029553

  51. {-376519,45341,965933,-278269,-404173,-762610,-51298,-972505,725198,-760369,-903811,-729733,-694786,-864691,423194,737270,-62257,-91342}

    1

    Returns: 0

  52. {-644074,-659701,-736357,989750}

    8

    Returns: 8

  53. {1,2,3}

    2

    Returns: 2

  54. {-39687,-281936,-882818,26407,-566116,-381732,-463021,31625,407388,443584,268996,882876,-312395,-905282,876727,539349,177195,745574,-558322,-396565,538984,-663682,-543516,-174447,528229,758347,142477,596116,722187,212599}

    9

    Returns: 53652803

  55. {171317,-105894,-719045,336427,-744666,687127,-560935,-230358,699209,-781040,-479805,958797,929564,-425375,424731,122937,-587136,981475,-904134,936173,-199634,876557,142145,-50860,425576,340477,-341213,932327,174451,535960}

    10

    Returns: 379672316

  56. {0,1,2,3,4,185,5,186,6,187,368,7,188,369,550,8,189,370,551,732,913,9,190,371,552,733,914,1095,1276,1457}

    181

    Returns: 342434875

  57. {0, 1, 2, 3, 4, 5, 6, 10, 11, 12, 13, 14, 15, 20, 21, 22, 23, 24, 30, 31, 32, 33, 40, 41, 42, 50, 51, 60, 61, 70 }

    10

    Returns: 1215150421

  58. {1, 11, 21, 2, 12, 22, 32, 3, 13, 23, 33, 43, 4, 14, 24, 34, 44, 54, 64, 5, 15, 25, 35, 45, 55, 65, 75, 85, 95, 105 }

    10

    Returns: 823292257

  59. {1, 21, 2, 22, 3, 23, 4, 24, 5, 25, 6, 26, 7, 27, 8, 28, 9, 29, 10, 30, 11, 31, 12, 32, 13, 33, 14, 34, 15, 35 }

    20

    Returns: 761219535

  60. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }

    5

    Returns: 796532187

  61. {1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 39, 42, -42, 1337, 666, 12835, 65, 71, 101, 102, 103, 104, 105, 106, 107, 108, 110 }

    42

    Returns: 1154946839

  62. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15 }

    15

    Returns: 761219535

  63. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }

    30

    Returns: 767765455

  64. {-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19 }

    12

    Returns: 18950806

  65. {8744, 6025, 7384, 3333, 27355, 31287, 30144, 22970, 28604, 22231, 6479, 20737, 14664, 27723, 493, 7796, 13385, 25984, 6888, 31738, 32658, 16462, 7108, 28631, 16879, 7071, 11730, 11237, 7260, 12500 }

    298

    Returns: 305058461

  66. {-15, -14, -13, -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }

    15

    Returns: 761219535

  67. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }

    1000

    Returns: 767765455

  68. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }

    33

    Returns: 767765455

  69. {1, -1 }

    1000

    Returns: 2

  70. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 }

    1000

    Returns: 767765455

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: