TopCoder Statistics - Problem Statement

Problem Statement

Two sequences A and B are called similar if they are both non-empty, have the same length, and have the following property: we can obtain two identical sequences by deleting one element of A and one element of B. (The deleted elements do not necessarily have to have the same index. The order of the remaining elements in each sequence has to be preserved.)

You are given a int[] seq and a int bound. Consider all sequences such that each element is an integer between 1 and bound, inclusive. Count how many of such sequences are similar to seq. Return this count modulo 1,000,000,009.

Definition

Class:: SimilarSequences
Method:: count
Parameters:: int[], int
Returns:: int
Method signature:: int count(int[] seq, int bound)
(be sure your method is public)

Constraints

seq will contain between 1 and 40 elements, inclusive.
bound will be between 1 and 1,000,000,000, inclusive.
Each element in seq will be between 1 and bound, inclusive.

Examples

{1, 1}

3

Returns: 5

We need to count the number of sequences which consist of elements in [1, 3] and are similar to (1, 1). These sequences are (1, 1), (1, 2), (2, 1), (1, 3) and (3, 1).
{1, 2}

2

Returns: 4

Any valid sequence is similar to (1, 2).
{999999999}

1000000000

Returns: 1000000000

Note that after deleting the elements from the sequences, the resulting sequences may be empty.
{1, 2, 3, 4, 5}

5

Returns: 97
{5, 8, 11, 12, 4, 1, 7, 9}

1000000000

Returns: 999999363
{1,1,1,1,1,1}

2

Returns: 7
{311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476,311476}

327225

Returns: 13088961
{152}

188

Returns: 188
{355295364}

467785888

Returns: 467785888
{314785899,456227311,456227311,387030055,387030055,314785899,387030055,314785899}

535678367

Returns: 712561336
{77896336,97856729,77896336,172194539,77896336,483105017,311518108}

495602040

Returns: 284499688
{426918,267237}

701597

Returns: 2806384
{179817489,179817489,179817489}

189454190

Returns: 568362568
{5524982,96934745,96934745,91536031,91536031,96934745,5524982,91536031,5524982}

601655575

Returns: 904300823
{28840973,100900673,149105710,149105710,73293865,73293865,100900673,149105710,73293865}

158389845

Returns: 978560086
{423802278,423802278,720349103,720349103}

946668217

Returns: 573345665
{23481830,54909654,49466230,49466230,34811664}

60727593

Returns: 214551829
{50817228,50817228,50817228,50817228,50817228,50817228,50817228,50817228}

382314201

Returns: 58513574
{312654710,382206564,234317551,234317551,136169275,312654710,382206564}

958217502

Returns: 245134678
{460134999,460134999,684526512,446481170,108375363,684526512,684526512,697641630,697641630,204008343,204008343,108375363,108375363,684526512}

759133616

Returns: 650834628
{624178786,351214399,534187106,21081452,21081452,21081452,253966573,733264929,351214399,342075387,822693591,733264929,624178786,552873565,822693591}

903310548

Returns: 145555070
{152075424,90292833,90292833,90292833,152075424,90292833,90292833,349609872,464509685,90292833,90292833,152075424,349609872,152075424,349609872,349609872,349609872,152075424,90292833}

576425677

Returns: 377140679
{55213166,119519197,281938666,281938666,252052455,281938666,11355087,11355087,55213166,292819678,119519197,119519197,11355087,252052455,8965365}

361932364

Returns: 147824744
{4385994,6932324,16146240,11309229,4596521,11309229,6932324,11309229,4596521,4596521,4596521,16146240,16146240,7514034,7514034,16146240,7514034,4596521,11309229}

20952730

Returns: 971527704
{6513444,6513444,6513444,6513444,6513444,6513444,6513444,6513444,6513444,6513444,6513444,6513444,6513444,6513444,6513444,6513444,6513444,6513444}

24104423

Returns: 433879597
{564772106,564772106,388633852,356770401,182914934,491319203,312535904,409921433,65984178,388633852,243890480,243890480,76761568,76761568,491319203}

760739098

Returns: 933036226
{435155876,145306372}

742725204

Returns: 970900794
{352918630,521471746,418243024,24232007,707568266,418243024,281354155,24232007,334576513,119415944,57536633,394604456,24232007,110500723,521471746,707568266}

744723726

Returns: 649271876
{46955439,7491560,12436217,12436217,60980665,31219717}

88482707

Returns: 654481159
{261402713,367628347,310680160,173538770,176903409,69502076,176903409,173538770,69502076,296016800,367628347,351568055,241336963,241336963,173538770,57603788,176903409,285837713,241336963,351568055}

383642119

Returns: 784003517
{378896466,227781653,378896466,378896466,378896466,307521285,307521285,150747568,150747568,378896466,227781653,365298582,150747568,130074499,130074499,307521285}

407028950

Returns: 637094375
{331628303,318449991,318449991,250395369,331628303,318449991,318449991,331628303,331628303,331628303,331628303,331628303,250395369,318449991,318449991,331628303,318449991,331628303}

607263673

Returns: 238205964
{705192536,705192536}

870874678

Returns: 741749346
{313322257,313322257}

785870805

Returns: 571741600
{143023563,398238073,398238073,647542489,211209984,49405637,396680076,396680076,396680076,126096982,211209984,396680076}

682436191

Returns: 703107856
{961792,1398411,6790912,1383905,6498720,1315388,1315388,8398347}

10550379

Returns: 590821163
{76460145,510964121,76460145,510964121,510964121,639775931,510964121,510964121,76460145,639775931,336536047,76460145,336536047,510964121,76460145,76460145,336536047,510964121,510964121,76460145}

704307437

Returns: 378377476
{429525903,147176730,429525903,147176730,429525903,429525903,147176730,152794401,152794401,386170902}

459241702

Returns: 739335744
{201504580,105323256,68841510,259775602,105323256,68841510,105323256,197700593,201504580,321527073,197700593,201504580,205401741,201504580,20487878,105323256,196063198}

337397009

Returns: 507734422
{857455420,361169985,286497454,192235460,192235460,156835124,958047204,506656844,958047204,286497454,924448485,485598693,205903630,485598693,857455420,205903630,192235460,506656844,924448485,205903630}

968064416

Returns: 864474378
{281258353,85442326,7480515,281258353,368835239,85442326,85442326,368835239,85442326,85442326}

508088524

Returns: 647081473
{253844461,253844461,253844461,253844461,253844461,253844461,253844461,253844461,253844461,253844461}

256103283

Returns: 561032803
{316771623,99061608,48158756,47099751,47099751,441353526,497394034,497394034,176216929,48158756,176216929,99061608,397668435,176216929,324055195}

513875039

Returns: 205631498
{510062054,334481083,477436123,92417848,229524971,92417848,92417848}

648403818

Returns: 232960066
{388266939,388266939,162295965,162295965,388266939,174864638,162295965,294145925}

407186668

Returns: 544959841
{120478498,120478498,120478498,44933311,120478498,44933311,44933311,120478498}

140331302

Returns: 613251989
{106609238,46890456,46890456,95072200,95072200,46890456,46890456,106609238,44569711,106609238,46890456,53399413,44569711}

129789963

Returns: 872694907
{75970725,75970725,76857816,75970725,143173775,72296637,75970725}

164984432

Returns: 929346043
{725839236,455410551,175764875,725839236,175764875,699598498,725839236}

734759629

Returns: 3221442
{166513230,282989353,166513230,282989353,166513230,282989353,285290553,24016171,24016171,2815403,24016171,24016171,2815403,282989353,285290553,24016171,24016171,285290553}

323153811

Returns: 251527893
{737325759,123710081,759580850,22245436,257319923,737325759,433590736,257319923,371640667,257319923,123710081,685466377,759580850,371640667,257319923,759580850,147189341,123710081,22245436}

873961791

Returns: 500203337
{737304220,236511253,241143167}

848128908

Returns: 633160099
{10935984,35176827,39276193,47883900,10935984,22012295,10935984,10935984,16516298,10935984,74393640,86695577,86695577,60895344}

127053901

Returns: 345054999
{267017443,190866784,250456531,297340335,3870817,267017443,247595873,206574009,86076165}

629259542

Returns: 970022364
{61480676,173573506,14506680,210029614,206136647,122205289,215927598,122205289,206136647,154409298,154409298,210029614,136417899,206136647,210601066,14506680,215927598}

255220360

Returns: 419937012
{420542152,52211967,420542152,420542152,52211967,52211967,214611769,52211967,52211967,420542152,420542152,420542152,52211967,420542152}

686767827

Returns: 532745292
{6557014,143495678,144486612,173388833,173388833,198420273,143495678,143495678,241082368,6557014,66011,143495678,59581171,241082368,241082368,144486612,66011,6557014,143495678}

265646357

Returns: 756491490
{602369348,252947154,732276691,248747210,1046788,732276691,151657658,241867700,252947154,8218012,732276691,241867700,151657658,8218012,262421244}

831935570

Returns: 185501329
{300239631,87542416,300239631}

327919232

Returns: 951273059
{296054118,77223857,471792342}

604982204

Returns: 444839781
{148861230,854979311,770020742,801900174,801900174,717634204,647967741,637050944}

929332795

Returns: 42635991
{229469772,254714283,228690173,9010048,9010048,180094970,352390110}

437177169

Returns: 361440890
{626582091,626582091,926607281,899070128,13531590,899070128,640233625,737651621,13531590,354658313,540048087,926607281,926607281,640233625,640233625,878276212,737651621}

939247446

Returns: 540889890
{90968505,148523934,363664416,6750864,195192800,90968505,141890521,26499660,419180744,419180744,26499660,195192800,500272899,321026777,223200795,90968505,419180744,419180744}

632880860

Returns: 269685740
{284571499,121862127,278915041,223986024,223986024,80135867,319239250,196635717,197084049,98689724,319239250,197084049,291152401,197084049,196635717}

351708003

Returns: 858679750
{322368674,135399014,179897726,133651387,322368674,198210017,142311732,198210017,179897726,133651387,156635940,142311732}

336782658

Returns: 496702165
{692780377,503395668,558706975,530705574,76455068,692780377,558706975,503395668,72827323}

731012029

Returns: 211973730
{309354157,309354157,310199814,55751917,9241164,291031510,9241164,310199814,310199814,9241164}

353777480

Returns: 302198061
{426332680,318516459,426332680,426332680,426332680,426332680,540102626,540102626,331776920,98589199,426332680,486626288,207375188,680819525,486626288,680819525,331776920,540102626,486626288}

733209373

Returns: 964669133
{183893162,322853522,322853522,340070111,340070111,327238359,322289081,240615113,66291227,148511729,134091344,327238359,327238359,240615113,33907750,239642008,340070111,322853522,340070111,141588617,240615113,327238359,322853522,148511729,183893162,148511729,33907750,33907750,240615113,141588617,327238359,141588617,322853522,141588617,327238359,338562667}

348784995

Returns: 800309445
{431460730,103190409,738139991,107321069,45491145,321917088,372671422,219526913,25633755,251652765,431460730,431879050,431879050,357583115,294861628,680345489,680345489,397431490,431460730,680345489,107321069,234034260,251652765,103190409,321917088,738139991,310652494,107321069,738139991,25633755,234034260,45491145,25633755,431879050,357583115,738139991,738139991,25633755,738139991,372671422}

790906595

Returns: 541748554
{130808489,242383739,243277603,243277603,150976863,130808489,34130941,84971559,84971559,356334030,356334030,150976863,150976863,405931485,150976863,363466141,150976863,405931485,315663216,198392044,356334030,242383739,363466141,242383739,106483719,167393447,405931485,160961319,130808489,34130941,214608236,160961319,84971559,34130941,315663216,31801155}

412446056

Returns: 137851052
{758647646,814043244,606653896,606653896,552579951,360057050,758647646,840000042,840000042,278813513,468408356,510402574,138420398,468408356,626753389,468408356,814043244,840000042,138420398,151615879,814043244,468408356,138420398,278813513,360057050,151615879,151615879,814043244,27277580,27277580,626753389,840000042}

881362013

Returns: 700355624
{131285537,131285537,265090113,98032399,1782029,134613277,98032399,98032399,133804563,134613277,1782029,15666576,133804563,15666576,90363034,90363034,232576681,131285537,134613277,296105210,3889118,274041738,221088426,296105210}

423339376

Returns: 363043063
{113803855,334804036,334804036,113803855,334804036,334804036,429050294,429050294,334804036,113803855,113803855,113803855,113803855,429050294,429050294,429050294,429050294,334804036,334804036,383963571,334804036,334804036,334804036}

515326666

Returns: 377645064
{31195610,82169130,15470185,31195610,90242053,36271819,22935603,31195610,43700923,90242053,22935603,15470185,36271819,92009043,43700923,43700923,82169130,15470185,90242053,60792428,61776716,61776716,92009043,36271819,60792428,61776716,22935603}

93172424

Returns: 891384944
{114526468,45390475,67785658,133269460,72433466,72433466,72602602,123551601,123140506,22208949,67785658,123551601,22208949,45390475,22208949,93651263,32561893,72602602,72433466,98496998,72602602,67785658,133269460,72433466,93651263,125225759,123551601}

135540034

Returns: 149102286
{81660910,483573580,483573580,193749894,193749894,342592345,483573580,342592345,342592345,483573580,342592345,193749894,483573580,81660910,81660910,483573580,81660910,342592345,483573580,81660910,342592345,483573580,81660910,81660910,342592345,483573580,81660910,342592345,342592345,342592345,193749894,342592345,483573580,342592345,193749894,483573580,342592345,483573580}

557078612

Returns: 238597819
{395574525,120276221,120276221,395574525,395574525,279041021,361019657,279041021,40490239,40490239,361601341,279041021,361601341,389201310,361019657,279041021,395574525,389201310,395574525,120276221,279041021,279041021,395574525}

411779300

Returns: 947552032
{150256098,261801063,379316499,261801063,213220285,379316499,124885434,361402964,379316499,221414550,244764363,409588863,101867455,235938812,235938812,218573915,124885434,261801063,323411612,213220285,235938812,261801063,101867455,124885434,150256098}

416020633

Returns: 612376936
{80654724,294288930,80654724,758651294,80654724,393781423,482449450,700430892,294288930,758651294,393781423,758651294,393781423,393781423,700430892,393781423,758651294,700430892,466966632,482449450,466966632,482449450,700430892,700430892,700430892,393781423,482449450,700430892,482449450,80654724,758651294,80654724,466966632,700430892,700430892,393781423,393781423,294288930,80654724,393781423}

786757662

Returns: 460715447
{324243,86951065,324243,97900223,48970705,48970705,30413174,47582615,48970705,324243,47582615,108722918,39493520,54489262,48970705,47582615,30413174,54489262,108722918,108722918,108722918,324243,54489262,30413174,324243,97900223,86951065,54489262,86951065,54489262,324243,324243}

152064452

Returns: 249746842
{130995295,100276905,199682884,120442786,87796242,30937664,30937664,25362166,25362166,140661413,100276905,75743329,78013781,100276905,57153413,120442786,25362166,100276905,100276905,140661413,87796242,87796242,199682884,140661413,169981682,116901432,75743329,147581665,120442786}

240390966

Returns: 283448036
{12941973,7725757,7725757,7725757,7725757,7725757,12941973,12941973,12941973,12941973,7725757,7725757,7725757,7725757,7725757,7725757,7725757,7725757,7725757,7725757,7725757,7725757,12941973}

26571455

Returns: 55717180
{127515447,636087818,112347116,112347116,574661255,638259506,638259506,636087818,127515447,483771270,636087818,483771270,871283715,127515447,239555847,260630312,260630312,636087818,638259506,871283715,636087818,871283715,636087818,871283715,636087818,483771270,636087818,239555847,127515447,574661255,239555847,638259506,112347116,871283715,112347116,127515447,638259506}

880541149

Returns: 720754176
{10388604,92781452,92691408,22446229,22446229,35941949,143321265,10164459,74034593,10164459,43423956,139504300,92691408,12376127,139504300,12376127,22446229,40527239,139504300,139504300,35941949,40527239,103128543,92781452,143321265,22446229,139504300,63262053}

145444265

Returns: 883423221
{111968492,127200517,127200517,111968492,221479656,257390770,221479656,127200517,111968492,111968492,111968492,257390770,221479656,221479656,111968492,526625351,221479656,221479656,526625351,127200517,127200517,471252163,526625351,75037056,257390770,221479656,257390770,127200517,75037056,257390770,75037056,221479656,111968492,526625351,75037056}

698788410

Returns: 270228724
{227569451,135550793,135550793,170005384,229915026,170005384,229915026,174915489,353382353,353382353,227569451,170005384,227569451,135550793,170005384,249065146,353382353,227569451,168851825,249065146,353382353,135550793,168851825,249065146,170005384,174915489,249065146,271339113,227569451,170005384,271339113,227569451,353382353,170005384,174915489}

390333699

Returns: 835417105
{29331688,449745846,259043650,259043650,449745846,29331688,185474073,4931334,331329046,46563574,4931334,142605751,259043650,331329046,435214361,435214361,46563574,259043650,259043650,46563574,540575054,4931334}

617467735

Returns: 101510473
{473951544,358368287,470797244,473951544,537729948,268597629,216234387,495481498,216234387,85033952,121927036,247042854,216234387,121927036,495481498,473951544,334614868,358368287,121927036,121927036,412757628}

584509925

Returns: 494165856
{111159188,106214708,106214708,111159188,136748203,28366178,28366178,47017696,111159188,136748203,174739403,174739403,47017696,28366178,47017696,28366178,106214708,277390507,106214708,136748203,174739403,28366178,111159188,28366178,174739403,28366178,28366178,47017696,111159188,28366178,174739403,47017696,277390507,47017696,277390507,174739403,47017696,277390507}

299878579

Returns: 443119252
{350657849,310925384,350657849,337617934,337617934,535226013,354661427,27968787,535226013,535226013,310925384,27968787,350657849,535226013,354661427,310925384,535226013,129632828,337617934,129632828,337617934,535226013,354661427,535226013,535226013,354661427,27968787}

723280879

Returns: 686004705
{466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594,466550594}

564044867

Returns: 357300971
{119812014,72672977,25414363,33552466,41839462,102102437,72672977,102102437,102102437,22759316,36630708,119812014,41839462,102102437,119812014,41839462,102102437,36630708,36630708,33552466,33552466,22759316,25414363,33552466}

152045568

Returns: 630965064
{230177970,230177970,230177970,230177970,230177970,213181679,230177970,230177970,230177970,213181679,213181679,213181679,213181679,213181679,213181679,213181679,213181679,230177970,213181679,213181679,213181679,230177970,230177970,230177970,230177970}

350413765

Returns: 322408144
{106419490,118482450,106419490,118482450,392195797,118482450,118482450,118482450,106419490,106419490,256272944,118482450,118482450,212323698,106419490,256272944,256272944,118482450,392195797,392195797,315745060,315745060,256272944,118482450,212323698,212323698,118482450,256272944,106419490,256272944,118482450,256272944,256272944,392195797,212323698,256272944,315745060}

548974373

Returns: 737444248
{427623634,283467600,916110067,427623634,283467600,325979717,348521572,243840830,594107712,7810416,58602595,325979717,243840830,243840830,469376906,89044344,325979717,325979717,545066141,518835423,243840830,283467600,651797186,916110067,651797186,325979717,916110067,594107712,545066141,451425250,518835423,89044344,243840830,7810416,58602595,7810416,545066141}

978869947

Returns: 636568632
{182838415,337629542,29105165,424675851,424675851,424675851,309255845,281030062,182838415,426583378,29105165,82667440,309255845,207865783,309255845,207865783,182838415,424675851,426583378,343353967,337629542}

437634692

Returns: 616240123
{104868217,348798957,104868217,342382295,417937255,113868647,74872629,486174202,348798957,74872629,417937255,104868217,486174202,221471841,348798957,526074549,526074549,104868217,140638752,74872629,378956157,74872629}

542491773

Returns: 631196393
{185842314,39659214,188946594,224313631,185842314,185842314,465675526,474764337,188946594,39659214,185842314,100957204,169903488,224313631,339442093,487831417,487831417,188946594,430423419,341337715,38048627,465675526,430423419,430423419,430423419}

521004095

Returns: 527146874
{13151496,3761708,38195548,32274514,3761708,34659775,34659775,3761708,12011250,34659775,14351132,12011250,49493434,14351132,21009924,40235533,11198766,40235533,34659775,13151496,11198766,49493434,12011250,48071216,49493434,11198766,40235533,53029096}

64831566

Returns: 12662673
{60181436,572198075,230546961,680709508,230546961,572198075,230546961,572198075,680709508,60181436,639601831,230546961,363235368,458970214,60181436,639601831,639601831,639601831,572198075,60181436,60181436,639601831,458970214,572198075,363235368,230546961,434101870,458970214,639601831,572198075,301161827,230546961,639601831,301161827,434101870,680709508,230546961,572198075,572198075,434101870}

834100329

Returns: 104461473
{703176658,505544559,911591587,667970463,272113205,483082443,483082443,903585183,590292587,8374840,590292587,590292587,505544559,794515427,590292587,911591587,667970463,130149988,794515427,505544559,505544559,23489946,23489946,667970463,599710838,8374840,272113205,599710838,130149988,733446210}

938806524

Returns: 269081327
{359889003,337651076,337651076,730078926,730078926,337651076,730078926,359889003,359889003,337651076,359889003,337651076,337651076,337651076,359889003,730078926,359889003,359889003,337651076,730078926,730078926,359889003,337651076,337651076,730078926}

769528984

Returns: 49814812
{22452979,22039757,23395511,46211940,22039757,15208192,12020721,26685282,15208192,19625589,15208192,33704184,7025316,22452979,5338589,7025316,48324722,33704184,12020721,21168778,46211940,22452979,46885980,46885980,21168778,1139639,1139639,15208192,7025316,25279906,47803087,25279906,33704184}

48751657

Returns: 872943616
{321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014,321135014}

892078763

Returns: 409890100
{1007704,2225645,2369708,4249340,463967,297645,2859882,1007704,4249340,4658537,4658537,50801,2013097,1054349,4249340,297645,4249340,3270217,2259132,3447027,4857588,50801,3857175,3270217,3654485,1054349,1054349,50801,2013097}

5370396

Returns: 205019223
{5017041,465721675,495128964,400386205,72037260,629084013,648264287,750429253,548946652,428424166,622581151,312048985,121818197,71011445,258526472,312048985,465721675,312048985,495128964,548946652,5017041,5017041,72037260,72037260,629084013,71011445,465721675,360074059,71011445}

785203903

Returns: 814649714
{609794288,703645023,703645023,299378584,137933023,409498509,180653553,180653553,409498509,609794288,137933023,409498509,137933023,409498509,409498509,703645023,180653553,299378584,137933023,703645023,409498509,409498509,703645023,609794288,299378584,137933023,299378584,137933023,299378584,609794288,137933023,703645023,180653553,299378584,409498509,703645023,409498509,609794288,180653553}

942416116

Returns: 397985358
{7582368,74865801,70452172,73723781,73723781,3622374,7582368,10885070,10885070,74865801,3622374,70452172,30023899,7582368,3622374,70452172,70452172,61617666,30023899,62397178,73723781,62397178,62397178,30138493,61617666,74865801,73723781,30138493,30023899,62397178,57232213,3622374,62397178,70452172,30138493,2666194}

99081550

Returns: 141943391
{879287761,855214960,872681195,789165875,694942644,911669467,872681195,791904952,130506976,130506976,791904952,789165875,130506976,694942644,866403188,199938172,911669467,130506976,694942644,720318487,789165875,720318487,791904952,720318487,199938172,789165875,720318487,720318487}

957547655

Returns: 94685813
{566748790,409959137,566748790,566748790,566748790,409959137,669934136,669934136,669934136,566748790,409959137,409959137,566748790,566748790,669934136,409959137,409959137,669934136,566748790,566748790,566748790,669934136,566748790,409959137,566748790,566748790,566748790,409959137,566748790}

675216727

Returns: 463127784
{74149488,74149488,11341960,58121760,38109282,31052641,45507404,57040934,36036779,57717802,54233467,57040934,32154805,72924888,57040934,825634,72924888,74149488,74149488,44113608,45507404,36894779,32154805,57040934,36036779,3154435,72924888,36894779,11341960,36894779}

76884736

Returns: 583176797
{572554943,439117043,488975446,488975446,488975446,439117043,572554943,504730542,572554943,504730542,504730542,439117043,439117043,572554943,504730542,488975446,504730542,504730542,504730542,572554943,439117043,488975446,504730542,504730542,439117043,504730542,572554943}

587898930

Returns: 465418784
{35817289,61164456,530712399,530712399,35817289,61164456,35817289,35817289,35817289,410494044,35817289,530712399,61164456,35817289,410494044,530712399,35817289,61164456,35817289,61164456,35817289,530712399,530712399,35817289,410494044,35817289,530712399,35817289,61164456,61164456,530712399,410494044,35817289,61164456,410494044,61164456,530712399,530712399,35817289}

681689018

Returns: 333756944
{6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622,6646622}

170788315

Returns: 660744193
{253021976,294566146,202342348,202342348,202342348,14129743,294566146,202342348,24655040,217906896,217906896,297265206,176902239,251990370,176902239,313831737,313831737,14129743,202342348,4781292,253021976,83293756,176902239,202342348,297265206,297265206,294566146}

360435081

Returns: 98435573
{590139349,590139349,628490430,585989208,382936537,585989208,644242147,590139349,418918529,419574756,382936537,628490430,419574756,622402478,644242147,172595697,146380225,418918529,622402478,628490430,644242147,622402478,220805505,94823359,585989208,419574756,419574756,382936537,419574756,382936537,628490430,590139349,585989208,585989208}

702798642

Returns: 749760921
{901242582,875484824,875484824,566032417,901242582,475741054,848264709,156405468,656981650,194719844,874118504,875484824,482315865,875484824,639692898,875484824,475741054,848264709,566032417,901242582,639692898,656981650,156405468,848264709,194719844,639692898,482315865,848264709,566032417,901242582,848264709,875484824,156405468,639692898,566032417,639692898}

925249071

Returns: 813817679
{48638838,15132412,47160092,15132412,1192127,47160092,35762571,1192127,35762571,43287794,23077437,48638838,35762571,15132412,1192127,3815455,27571062,43287794,13798466,55352722,48638838,35762571,15132412,27514622,23077437,1192127,23077437,3815455,15132412,48841808,5338348,48638838,48841808,27514622,23077437,54824245,55352722,13798466,23077437,53357807}

55588435

Returns: 941493567
{99060926,274970597,77974636,349577040,178149598,114882798,201906069,289790427,203205273,88844831,326816085,120983903,326816085,77974636,203205273,398258965,463933846,326816085,99060926,387781876,172871082,132397762,326816085,201906069,605963,289790427,297109642,380228017,132397762,111115969,326816085,22289658,387781876,59553877,605963,236887670,271344421,363511166,114882798,297109642}

466077057

Returns: 723282856
{177565649,95468793,177565649,177565649,442164191,177565649,95468793,177565649,442164191,442164191,95468793,177565649,442164191,442164191,95468793,177565649,95468793,95468793,442164191,95468793,95468793,177565649,442164191,177565649,177565649,95468793,177565649,442164191,442164191,95468793,442164191,177565649,177565649,442164191,442164191,95468793,442164191,177565649,95468793,95468793}

842141255

Returns: 569495673
{96722191,96722191,120499893,27690325,71672667,76416534,140650801,77865800,71672667,96722191,20488507,27690325,27690325,77865800,120499893,20062508,96722191,76416534,17444216,20062508,8067620,78279219,140650801,52023874,20062508,71672667,140650801,20488507,17444216,137939517,71672667,137939517,52023874,120499893,20062508,137939517,120499893,78279219,71672667,58280555}

152189752

Returns: 328419404
{481163110,381121510,381121510,63761886,63761886,63761886,496378288,612393740,381121510,63761886,553049572,63761886,63761886,496378288,449548158,496378288,612393740,381121510,496378288,381121510,381121510,449548158,63761886,553049572,63761886,481163110,496378288,449548158,553049572,381121510,449548158,481163110,481163110,449548158,449548158,449548158,612393740,63761886,449548158,63761886}

635367093

Returns: 269870408
{171812158,171812158,159922519,192788398,248241881,159922519,25001988,157353640,101023009,111926827,248241881,153719630,161186296,31043529,181155094,215618603,159922519,58519056,153719630,243444244,101023009,215618603,58519056,101023009,31043529,171812158,99830271,99830271,168601079,58519056,99830271,168601079,153719630,181155094,58519056,205247537,192788398,129384851,84626096,4629875}

249047938

Returns: 552860802
{636909036,643735640,660165811,30229717,660165811,177397575,492971392,492971392,30229717,403727599,565230429,46694466,343041705,636909036,177397575,30229717,486101116,177397575,46694466,643735640,352773847,177397575,119330280,348615107,486101116,119330280,592771934,420199060,46694466,285044098,592771934,467808366,636909036,524275891,660165811,216192949,131685087,5879990,30229717,451285507}

704602709

Returns: 180214551
{126147896,198807409,94885060,126147896,78208957,6430926,198807409,100755964,198515641,153491828,100755964,100177889,124772036,23680381,78208957,190248677,213581589,199271483,65517820,144138146,211078397,113677836,52271311,23525812,124772036,199271483,23525812,94885060,31220314,126147896,52271311,116565787,124772036,20407919,213581589,78208957,52271311,82260119,9206875,39073867}

234491104

Returns: 185761387
{353767808,353767808,353767808,238876581,353767808,316275234,353767808,353767808,238876581,316275234,353767808,353767808,353767808,353767808,238876581,353767808,353767808,238876581,316275234,353767808,316275234,238876581,238876581,353767808,353767808,353767808,238876581,316275234,353767808,316275234,353767808,353767808,353767808,316275234,316275234,353767808,353767808,238876581,353767808,316275234}

631749243

Returns: 19205735
{74847977,449715060,404874014,4984669,74847977,60316097,4984669,4984669,449715060,183253329,173597066,35147156,449715060,250038845,74847977,449715060,90521533,83672155,74847977,199263001,60316097,314443723,417109182,199263001,272368194,30918961,12879938,199263001,109864135,74847977,109864135,90521533,35147156,68365150,445733874,183253329,68365150,445733874,109864135,417109182}

533445002

Returns: 174194034
{196436720,214039012,152858490,214039012,62903483,128873763,52252522,196436720,126550194,62659976,21306507,84474461,157816452,116256525,84474461,152858490,134695300,126550194,134695300,126550194,47341011,21306507,69887298,52252522,157816452,21306507,126550194,52252522,62659976,126550194,69887298,152858490,52252522,69887298,69887298,84474461,196436720,84474461,62659976,157816452}

214420073

Returns: 495309272
{184069611,522668704,184069611,416991023,131754133,42452547,131754133,147181281,184069611,80578739,80578739,131754133,147181281,529851465,416991023,169268552,522668704,184069611,147181281,130400423,131754133,184069611,42452547,42452547,385784458,30777794,147181281,130400423,42452547,529851465,416991023,529851465,169268552,522668704,147181281,42452547,42452547,416991023,147181281,110130764}

531243589

Returns: 240503128
{395497498,395497498,74993207,435988940,217669648,620108790,620108790,432357034,435988940,395497498,441100522,614707241,397062366,62627074,316269116,618108491,435988940,14426804,620108790,162901778,418666323,397062366,189358856,14426804,620108790,614707241,14426804,618108491,397062366,395497498,62627074,435988940,97752365,614707241,162901778,316269116,316269116,407171541,614707241,62627074}

649187803

Returns: 797938285
{561779819,326299502,277567604,244383703,163263927,326081034,31888888,163263927,16257560,288474479,305845705,394772158,199127910,201238992,477128902,244383703,562886148,313121583,305845705,160038631,160038631,226146996,350392405,199127910,305845705,477128902,198739446,60246359,60246359,415359831,16257560,60246359,31888888,31888888,163263927,446784119,326299502,277567604,151832340,400745422}

605239347

Returns: 754223990
{55264316,20831316,215442036,663075174,706455268,20831316,728229134,535250424,252376862,130007591,678279696,706455268,706455268,663075174,364477891,706455268,215442036,535250424,252376862,20831316,706455268,184504729,252376862,416627872,663075174,657478642,62379628,593149784,657478642,663075174,570063248,130007591,205784183,706455268,535250424,416627872,570063248,55264316,205784183,252376862}

802943088

Returns: 591204415
{282363077,297193831,297193831,161682824,282363077,144483897,282363077,297193831,297193831,144483897,54583554,297193831,209712362,54583554,54583554,108279463,54583554,108279463,209712362,144483897,54583554,282363077,297193831,297193831,209712362,209712362,144483897,211575524,54583554,54583554,144483897,297193831,144483897,297193831,54583554,282363077,297193831,144483897,108279463,108279463}

303345805

Returns: 416457642
{531204208,250779947,734260681,262760895,250779947,531204208,262760895,262760895,734260681,751517887,751517887,250779947,734260681,734260681,250779947,751517887,531204208,751517887,250779947,531204208,531204208,734260681,531204208,250779947,751517887,734260681,751517887,734260681,250779947,250779947,734260681,250779947,250779947,734260681,250779947,751517887,751517887,250779947,250779947,250779947}

910567126

Returns: 103224803
{37231880,26579944,20128076,75445113,18438229,59428141,41601157,37231880,72513985,24931867,49787867,41601157,30825587,36417891,30231559,819865,69267156,58593852,75445113,30231559,25181538,72361103,42697286,18438229,72513985,206858,19991131,74092629,36595703,69267156,26579944,24931867,49787867,72513985,20128076,52193014,74092629,20128076,42697286,18586244}

88318425

Returns: 309477093
{13524273,9200475,37365413,26306810,5243574,2608847,40900063,9364218,20056483,25787076,10251341,9200475,20056483,12068173,37365413,2608847,20291228,13524273,56260100,26306810,11405766,20291228,12068173,13524273,51330846,26306810,20291228,2608847,11405766,10251341,40900063,37365413,40900063,26306810,22249791,26306810,9364218,40900063,10251341,9200475}

62090274

Returns: 344435869
{179936825,179936825,179936825,179936825,153128503,153128503,153128503,179936825,179936825,153128503,179936825,153128503,153128503,179936825,179936825,179936825,153128503,153128503,179936825,179936825,153128503,153128503,179936825,153128503,179936825,179936825,179936825,179936825,179936825,153128503,153128503,179936825,153128503,179936825,153128503,179936825,179936825,153128503,153128503,153128503}

285085248

Returns: 68195514
{980602456,74340529,309215468,84832226,507867262,763470531,679296374,976859646,806579699,72278565,330660619,81609875,259697994,197215600,735553447,989695591,935938879,129078563,343475409,393872738,379425939,503612371,372538256,490273344,832784046,585516402,124431239,800595099,309603805,823508377,167143918,566278769,15207617,629918420,890725547,284650839,103907737,910356655,8743139,532203008}

1000000000

Returns: 999983971
{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}

1000000000

Returns: 999983971
{7, 7, 5, 5, 1, 2, 3 }

8

Returns: 242
{1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 2, 2, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1 }

1000000000

Returns: 999991577
{2, 3, 5, 1, 5, 5, 4, 4, 3, 5 }

160567230

Returns: 845378205
{1, 2, 1, 2 }

2

Returns: 11
{2, 4, 7, 5, 2, 5, 7, 7, 3, 1, 2, 2, 2, 4, 2, 4, 4, 7, 4, 5, 8, 5, 7, 2, 5, 7, 6, 5, 7, 8, 8, 7, 4, 3, 6, 1, 4, 4, 4, 7 }

1000000000

Returns: 999986772
{1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 }

999999999

Returns: 999981630
{222, 148, 206, 2, 72, 209, 153, 232, 214, 197, 135, 49, 224, 85, 181, 210, 27, 69, 219, 254, 112, 237, 201, 105, 235, 167, 103, 190, 138, 190, 175, 152, 154, 237, 179, 73, 12, 13, 161, 24 }

1000000000

Returns: 999983970
{2, 1, 1234568 }

100000000

Returns: 899999990
{1, 1, 2, 2, 1, 2, 1 }

100

Returns: 3459
{5, 8, 1, 12, 4, 1, 7, 9, 9, 7, 9, 2, 3, 2, 6, 7, 8 }

941235467

Returns: 16044432

Statistics

Problem Statement for "SimilarSequences"

Problem Statement

Definition

Constraints

Examples