Statistics

Problem Statement for "CountSubarrays"

Problem Statement

You are given an array A containing N elements. You are also given an integer X. Count the number of ordered pairs (L, R), such that:

  • 0 ≤ L ≤ R < N.
  • (A[L] * A[L+1] * ... * A[R]) modulo 744,444,499 = X.

The array A is given in the following format: You are given the int[] Aprefix and the ints n, a, b, and m. Use the following pseudocode to generate A: 

for i = 0 to length(Aprefix)-1:
    A[i] = Aprefix[i]
for i = length(Aprefix) to n-1:
    A[i] = ( A[i-length(Aprefix)] * a + b ) modulo m

Definition

Class:
CountSubarrays
Method:
count
Parameters:
int[], int, int, int, int, int
Returns:
long
Method signature:
long count(int[] Aprefix, int n, int a, int b, int m, int X)
(be sure your method is public)

Constraints

  • n will be between 1 and 94,749, inclusive.
  • Aprefix will contain between 1 and n elements, inclusive.
  • Aprefix will contain at most 200 elements.
  • Each element of Aprefix will be between 0 and 744,444,498, inclusive.
  • m will be between 1 and 744,444,499, inclusive.
  • Each of a and b will be between 0 and m-1, inclusive.
  • X will be between 0 and 744,444,498, inclusive.

Examples

  1. {2,1,2}

    3

    5

    7

    11

    2

    Returns: 4

    We are looking for all subarrays of {2,1,2} that have product (modulo 744,444,499) equal to 2. There are four such subarrays. The corresponding pairs (L,R) are (0,0), (0,1), (1,2), and (2,2).

  2. {1}

    3

    0

    0

    744444499

    0

    Returns: 5

    The array you should generate is {1,0,0}, and we are counting subarrays whose product is 0. There are five such subarrays: all of them, except for (0,0).

  3. {332561219,121884851,427632830,369957091,549417829,685227621,436551677,351304445,243813223,371998688}

    94749

    330563283

    311776610

    744444499

    222370756

    Returns: 8

  4. {35828110,300357300,191011600,527986654,415569791,725672838,190156296,463922833,573251140,479251458,49076642,305285101,226658648,535061251,340108009,337072284,324710641,197385849,691064495,486979567,233626036,510537426,329787224,540184586,552934843,473485542,162834789,319948368,177935440,543937403,236082224,698309840,681221525,437102554,349926815,15236521,142872311,504082258,612944708,94456611,222664208,27773577,194613842,103338974,270702420,334463309,577120441,232099245,606615432,543411229,535242657,651415329,462235251,552781226,255220605,686019139,63153350,284507479,639257318,427922808,719983500,238084469,661213618,191288994,366182406,521203673,199578216,162038913,115677507,420719156,225954897,390528592,533997682,21505642,327643990,637337490,158079254,324299791,455651610,202660228,501706940,640968709,181429278,353863711,185780035,477690014,383281213,281352956,443140453,346417612,419464686,158201693,194549867,318373691,237906359,567594330,354823318,196740282,577879399,370429071}

    94749

    278084788

    265616225

    744444499

    607723945

    Returns: 3

  5. {476954577,370173635,30905049,722823112,578527209,229685557,498220579,253798363,689274976,422746075,274045439,49053368,39267706,682430721,106098889,115383543,589046807,409120140,532408504,51397597,673588242,560973763,73143982,350002329,321525875,346463645,318978921,2021102,90971253,460183324,596452415,584608960,97770626,471072653,54383122,296125193,403426787,401293411,336295522,726662999,203484631,42849260,163678066,50651358,341560741,465391343,230266416,402567647,230854868,344828799,490251686,537905734,322387272,501177102,512529640,165488371,81011741,333652400,398785182,280175080,628346239,211709077,338270907,206884971,14083111,357274768,266703079,369892674,679318196,716905393,115914632,277584988,296815088,249985280,567506266,164053008,631666933,138278535,404113742,75337621,720573544,716237219,306987375,91849629,585591625,606401480,500917857,529248811,527437200,30485750,377849398,8137133,447742270,302689726,714466757,106079022,230431795,554038095,574951280,399317628}

    94749

    138316247

    79107884

    744444499

    347061333

    Returns: 2

  6. {709443009,479744926,251067061,432753741,522284094,668859715,133579119,501613447,253476039,50171040,132808853,529776226,298946149,275625530,140954168,143862804,681022628,134828128,675483706,727671247,528284351,78481913,726175771,213560091,403330190,632069409,317975169,649175029,386700860,360235585,161787428,123183288,310171564,391756898,187566645,602633072,79522774,740951310,304129297,207797710,630703567,684277436,631598584,323019232,349945961,497210320,513149791,346352338,451809418,547007843,64453037,630717661,689031647,373758363,554254364,721041628,551493189,54109341,643930237,369343651,389392312,296818603,475249971,62794665,539990711,655522118,423625305,55738379,68904934,296387837,219759326,444267894,193954224,340369031,283361085,724714706,39276553,567810524,447294442,693026922,608809992,385543040,355476761,535269996,447281717,583500464,537699419,182310429,29737851,467001544,548604947,452649079,91851321,323863027,252034403,382804884,183322862,275275492,190538867,218235158}

    94749

    512142041

    323038315

    744444499

    576039717

    Returns: 6

  7. {408344944,656135333,731387942,258256965,739886252,503058813,205901897,128639893,559572317,702776382,108402883,492033766,407498067,409170803,224781620,644360659,604117382,686422811,632215351,131011012,715081685,269594376,485172580,322514723,471121306,441499286,324306381,254566650,525480274,240046915,625098972,260619449,211341244,589306687,266586217,149369961,55818585,304065246,106925299,495943003,363031848,385357428,45942930,736865083,599923182,227227207,357651764,156710246,540207695,491551813,508020824,399423858,477914943,719798268,498516312,517728666,253587275,728020912,454852393,61145450,509425787,549239071,279651248,656896319,513806762,231208982,165224448,441178650,575763462,110628387,502426028,62664187,180968876,607258832,676662367,605425389,600586799,209144402,426249341,489336892,418652051,197889489,40911646,475607866,472396201,168099131,325004843,398655780,738549595,545586113,470226781,676307381,42865331,731058582,93057646,373399604,278170874,268196235,67845745,637816543}

    94749

    393668227

    454311932

    744444499

    657814277

    Returns: 8

  8. {576906240,706062338,135614779,503555507,43706027,465037886,571373745,412940215,404944749,531839926,15498774,485850642,433117628,193073386,284945915,104601448,165688899,234475471,273508706,310105470,162295167,660596574,79686321,606252575,226041907,516200492,211268362,283478707,472799373,698844330,417626577,455156108,248635848,132233625,27756252,201134639,630460367,510558072,456945329,215467838,328988927,124306030,732869726,694707653,501568081,371773763,634204941,489055164,186911823,139967937,129754355,507231566,377132545,684642846,434810264,28518031,26143348,683901568,593254307,41257979,206786976,638118945,367428244,160860953,152879496,471603803,482266888,479888070,364782000,306998739,373611818,628177448,283626464,430870967,647140627,532282115,50544520,743738899,439928719,685730454,294102899,528705048,672307377,361551639,63957313,249541686,165655917,44218521,481285371,648975044,625867172,528570793,523413638,89980229,627935882,572883462,379642041,457025084,79230632,251694294}

    94749

    484865072

    8512598

    744444499

    114904657

    Returns: 6

  9. {0,0,1,0,0,0,1,0,0,0,1,1,0,1,1,1,0,1,1,0,1,0,1,0,0,0,0,1,1,1,0,1,0,1,1,1,0,1,1,0,1,0,1,0,0,0,1,0,1,1,0,1,0,1,1,0,1,1,0,1,1,0,0,1,1,0,1,0,1,1,0,0,0,1,0,1,1,0,1,0,1,0,1,1,0,0,0,0,1,1,1,0,1,0,1,0,0,0,1,1,1,0,0,0,1,0,0,1,1,1,0,1,0,1,0,1,1,0,1,0,0,1,1,1,0,0,0,1,0,1,0,1,1,0,1,1,0,0,0,1,1,1,0,1,0,1,1,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,1,1,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,1,1,0,0,0,0,1,1,0,1,1,0,1,1,0,0}

    94749

    0

    0

    2

    0

    Returns: 4488733721

  10. {0,0,1,0,0,0,1,0,0,0,1,1,0,1,1,1,0,1,1,0,1,0,1,0,0,0,0,1,1,1,0,1,0,1,1,1,0,1,1,0,1,0,1,0,0,0,1,0,1,1,0,1,0,1,1,0,1,1,0,1,1,0,0,1,1,0,1,0,1,1,0,0,0,1,0,1,1,0,1,0,1,0,1,1,0,0,0,0,1,1,1,0,1,0,1,0,0,0,1,1,1,0,0,0,1,0,0,1,1,1,0,1,0,1,0,1,1,0,1,0,0,1,1,1,0,0,0,1,0,1,0,1,1,0,1,1,0,0,0,1,1,1,0,1,0,1,1,1,0,1,0,0,1,1,0,1,0,0,1,1,0,0,1,1,1,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,1,1,0,0,0,0,1,1,0,1,1,0,1,1,0,0}

    94749

    0

    0

    2

    1

    Returns: 154

  11. {1,0,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,1,0,1,0,1,0,0,1,1,1,1,0,1,0,1,0,1,1,1,0,0,1,0,0,1,1,1,0,0,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,0,1,1,0,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,1,0,1,1,0,1,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,0,0,1,1,1,1,0,1,0,0,1,0,1,0,1,1,0,1,1,0,0,0,1,1,0,0,0,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,1,1,0,1,1,1,1,0,0,0,0,0,0,1}

    94749

    0

    1

    2

    0

    Returns: 18835182

  12. {1,0,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,1,0,1,0,1,0,0,1,1,1,1,0,1,0,1,0,1,1,1,0,0,1,0,0,1,1,1,0,0,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,0,1,1,0,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,0,0,0,0,0,1,0,1,0,1,0,1,1,0,1,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,0,0,1,1,1,1,0,1,0,0,1,0,1,0,1,1,0,1,1,0,0,0,1,1,0,0,0,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,1,1,0,1,1,1,1,0,0,0,0,0,0,1}

    94749

    0

    1

    2

    1

    Returns: 4469898693

  13. {1,0,1,1,0,0,1,1,0,1,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,0,1,1,0,0,1,0,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,0,0,1,1,0,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,1,1,0,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,1,0,0,1,0,1,1,1,1,0,1,1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,0,1,0,1,1,0,1,1,0,0}

    94749

    1

    0

    2

    0

    Returns: 4488649527

  14. {1,0,1,1,0,0,1,1,0,1,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,0,1,1,0,0,1,0,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,0,0,1,1,0,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,1,1,0,0,1,1,0,1,0,1,1,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,1,0,0,1,0,1,1,1,1,0,1,1,0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,0,1,0,1,1,0,1,1,0,0}

    94749

    1

    0

    2

    1

    Returns: 84348

  15. {1,1,1,1,1,1,0,1,0,0,0,1,0,0,0,0,0,1,1,1,1,1,0,0,1,1,0,0,1,1,1,1,1,0,0,1,0,1,0,0,1,0,0,1,0,1,0,1,0,1,0,0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,0,0,0,1,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,0,0,1,0,0,1,1,0,0,0,1,1,1,0,1,1,0,0}

    94749

    1

    1

    2

    0

    Returns: 4488635801

  16. {1,1,1,1,1,1,0,1,0,0,0,1,0,0,0,0,0,1,1,1,1,1,0,0,1,1,0,0,1,1,1,1,1,0,0,1,0,1,0,0,1,0,0,1,0,1,0,1,0,1,0,0,0,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,0,0,0,1,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,0,0,1,0,0,1,1,0,0,0,1,1,1,0,1,1,0,0}

    94749

    1

    1

    2

    1

    Returns: 98074

  17. {0}

    94749

    0

    0

    1

    0

    Returns: 4488733875

  18. {0}

    94749

    0

    0

    2

    1

    Returns: 0

  19. {1,2}

    94749

    2

    0

    3

    2

    Returns: 142121

  20. {1}

    94749

    1

    0

    2

    1

    Returns: 4488733875

  21. {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,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199}

    94749

    1

    744444498

    744444499

    0

    Returns: 2985980100

  22. {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,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199}

    94749

    1

    744444498

    744444499

    182

    Returns: 405

  23. {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,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199}

    94749

    1

    744444498

    744444499

    72

    Returns: 518

  24. {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,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199}

    94749

    1

    744444498

    744444499

    182

    Returns: 405

  25. {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,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199}

    94749

    1

    744444498

    744444499

    56

    Returns: 537

  26. {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,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199}

    94749

    1

    744444498

    744444499

    90

    Returns: 500

  27. {1 }

    3

    0

    0

    744444499

    0

    Returns: 5

  28. {332561219, 121884851, 427632830, 369957091, 549417829, 685227621, 436551677, 351304445, 243813223, 371998688 }

    94749

    330563283

    311776610

    744444499

    222370756

    Returns: 8

  29. {2, 1, 2 }

    94700

    5

    7

    74444444

    2

    Returns: 7

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: