Statistics

Problem Statement for "YetAnotherORProblem"

Problem Statement

NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.

You're given a long[] R containing N elements. Count the number of sequences A0, A1, ..., AN-1 such that each Ai is an integer satisfying 0 &le Ai &le R[i] and A0 + A1 + ... + AN-1 = A0 | A1 | ... | AN-1. The '|' symbol stands for bitwise OR of the operands. Return the number of such sequences modulo 1,000,000,009.

Definition

Class:
YetAnotherORProblem
Method:
countSequences
Parameters:
long[]
Returns:
int
Method signature:
int countSequences(long[] R)
(be sure your method is public)

Notes

  • If a and b are single bits then a | b is defined as max(a, b). For two integers, A and B, in order to calculate A | B, they need to be represented in binary: A = (an...a1)2, B = (bn...b1)2 (if the lengths of their representations are different, the shorter one is prepended with the necessary number of leading zeroes). Then A | B = C = (cn...c1)2, where ci = ai | bi. For example, 10 | 3 = (1010)2 | (0011)2 = (1011)2 = 11.

Constraints

  • R will contain between 2 and 10 elements, inclusive.
  • Each element of R will be between 1 and 10^18, inclusive.

Examples

  1. {3,5}

    Returns: 15

    All the possible sequences are: {0,0}, {0,1}, {0,2}, {0,3}, {0,4}, {0,5}, {1,0}, {1,2}, {1,4}, {2,0}, {2,1}, {2,4}, {2,5}, {3,0}, {3,4}.

  2. {3,3,3}

    Returns: 16

  3. {1,128}

    Returns: 194

  4. {26,74,25,30}

    Returns: 8409

  5. {576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488}

    Returns: 161955037

  6. {1000000000000000000,1000000000000000000,1000000000000000000,1000000000000000000,1000000000000000000,1000000000000000000,1000000000000000000,1000000000000000000,1000000000000000000,1000000000000000000}

    Returns: 990348470

  7. {1,1}

    Returns: 3

  8. {1,2}

    Returns: 5

  9. {1,3}

    Returns: 6

  10. {1,100000000000000}

    Returns: 998650011

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

    Returns: 11

  12. {486211148307164070,501974443494127483,546109314111885682,25345366503733289,467109698224593900,773245526169189607,255302906723634372,396294198631725069,502394460171932757,925946187501080508}

    Returns: 969176119

  13. {850341934789835835,140906788628005596,867764780898644033,662426890409338628,133999403774198975,698982670257830763,642352388451400490,696393751092254370,239102317172067966,247872578895163570}

    Returns: 743496776

  14. {937508594066117248,980092273090134188,677010200342741556,365028454416048405,143563413081327338,615967991662629691,278038892600093731,145633846551401351,191144690724546952,278872880611125588}

    Returns: 679561707

  15. {894046344715134069,347687198792039840,719538930376619224,99075637843956381,335722352840844417,512845350869404159,600849075685463247,553506913669576251,654932379060027147,8593902250271113}

    Returns: 11875638

  16. {683066667926680470,556248935248633525,453474558769328097,475065863843290951,850745313582021854,204929657709514607,764975648555601843,523551236768895619,606238530649926101,269225426653479939}

    Returns: 988699198

  17. {937928638053108520,440742153764585425,631901608425066777,409375337491295697,55821926214613369,216039497982178404,980928693082282013,97866237585466160,108946666999987281,367722142884809048}

    Returns: 251942611

  18. {112245628696232905,392790401510825741,747015484314669905,267403993190812779,180598810636772899,78249002023528552,43678818172702840,587096233706243036,697285092765355726,533508901985030046}

    Returns: 91153622

  19. {82,52,85,86}

    Returns: 50421

  20. {602,13,803,935}

    Returns: 2144657

  21. {602,737,700}

    Returns: 778636

  22. {286,820,288}

    Returns: 347619

  23. {781,583,619,108}

    Returns: 3605293

  24. {751,858,276,281}

    Returns: 4191859

  25. {987,437}

    Returns: 37515

  26. {528,118,923,500}

    Returns: 2862567

  27. {550,41}

    Returns: 5423

  28. {249,870,81,48}

    Returns: 621007

  29. {531115030899290881,947601149273011713,991349567020840193}

    Returns: 704948445

  30. {514701342182032257,551137292578942401}

    Returns: 168651770

  31. {571879271664657217,768393171830683393,664062644097263361,355743360981049217}

    Returns: 956595861

  32. {281942348671178177,296524174576598401,621221659367249793,789309979030026113}

    Returns: 484600327

  33. {52814234944074561,167665818550075009}

    Returns: 199513113

  34. {754547046746258817,759330137062651777}

    Returns: 673512845

  35. {682980468448377345,193548385845690337,489415678812105025,900842041599889025}

    Returns: 573655195

  36. {956152983057168257,685066470136012289,423533785513627777,801762889749067777}

    Returns: 535218139

  37. {529582270537187201,737236092366456321,678115500642184705,646531872293652225}

    Returns: 469886763

  38. {30820494264921173,123529810047987905,239192881194985601}

    Returns: 972375168

  39. {610672758913349377,682130155468148225,355306369015803905,568446742487323201,602170999880562177,545440606274798529}

    Returns: 374282364

  40. {94663704934456193,11022267787787255,623270779903079425,718053191054786561,757284307425175553,838510416841380481}

    Returns: 519589403

  41. {370823944597555393,959817906078117505,661926524832346497,375339575752686529,854592808273831553,967989738817605505,10180887591681565}

    Returns: 420329606

  42. {548786640528232257,230468608997888577,291036470589611457,602010944762470401,989934578970582145,535510500688701185}

    Returns: 360900708

  43. {990989409908369793,369219186497175873,672493243651861377,64729355504270945,266672080077714145,927428625227020417}

    Returns: 489971662

  44. {484205650146120513,994843496676061697,81080301795162577,586634036715579137,907819667623232769,661522450006260481,598838517595794817}

    Returns: 361203554

  45. {467779822377700545,777699403526018305,913949833525302145,222652993249928161,226651140659680513,447964742094548737}

    Returns: 807307128

  46. {270842110321156353,32222913565892465,280500068910451201,216571934306577185,996770687519372929,383226433576174273,212193546213289345}

    Returns: 315590430

  47. {583243144536534401,602075641395925761,550178961838258625,646240318537363585,203794790548301185,518030629532349825}

    Returns: 619847316

  48. {915198356369810305,547981906165575745,552660027899496065,559744664424480129,694182369981934593}

    Returns: 105822572

  49. {953464322231618433,424597586603095105,802766948182089729,986508967365234177,655558074561796993,792713312977855361,290227543890245633,574678888784088321,781981828042526977}

    Returns: 42732412

  50. {19564963732824793,731320615399862913,374075907989330881,862559090482217089,449728360128615617,480016004369430721,767331865069813377,966052224255870337,972090874302522881,275638593717801985}

    Returns: 755106812

  51. {415624240298450369,155434710298624225,77234208294951537,955025955104481409,576829691483942017,996346446483722881,839069545243658497,236466444963801537,844176723060579329}

    Returns: 108049657

  52. {226764098559482657,804264921332996865,292962656324613249,895831173544852481,866397406014807297,304505006815591873,98475309119277265,724127577618571521,716709661493862657}

    Returns: 552108928

  53. {434259918875988225,177260966212917537,217991183696925825,835315432368728833,390254167392124609,230841016457116289,715981789964010497,641381713093305857}

    Returns: 867282434

  54. {310273763549385985,285078427524640961,846272581803176577,353299536964801089,294726449174559681,482375751789420609,93212649453745745,709085599163968897,827528090227223681}

    Returns: 559247321

  55. {36357859193478113,946275254206211841,705497036630788225,173248715244439073,616460779730903169,589606117646702849,331601022376007297,981886988381499137,410992156039859265,632952779397591937}

    Returns: 805058687

  56. {856453635950069121,919588957759670145,446024376193420737,725091595753653505,237062425568849601,60738596790608665,625002368978720513,293297730890701441,69185693980055809,601897409503310337}

    Returns: 839797796

  57. {230336259972718785,225746599601057025,722781284958371201,222501611105992545,148521421203463137,522397652544219329,420355024778754497,788430747170501249,15142121967169687}

    Returns: 250831300

  58. {4085864728089251,537317396930776833,975085695935915649,798440260017564673,501316123965390913,927487449637385729,490944664383960769,940511086234745729,395148759760898561,134517657051514529}

    Returns: 688870764

  59. {67108864,33554432,4503599627370496,4503599627370496,1099511627776,8589934592,4096,65536,68719476736,8}

    Returns: 611826201

  60. {4194304,2251799813685248,268435456,1125899906842624,1125899906842624,16777216,140737488355328,2147483648,1024}

    Returns: 63444929

  61. {1048576,536870912,35184372088832,536870912,34359738368,32768,268435456,35184372088832}

    Returns: 636970334

  62. {1099511627776,524288,8388608,8,16,67108864,33554432,131072}

    Returns: 983884892

  63. {144115188075855872,65536,8589934592,4096,72057594037927936,8388608,33554432,262144,65536}

    Returns: 276635641

  64. {268435456,8,524288,288230376151711744,32768,33554432,17592186044416,2147483648}

    Returns: 517162972

  65. {1024,1073741824,137438953472,17179869184,8589934592,33554432,262144,512}

    Returns: 964350662

  66. {134217728,512,2097152,1,4,1073741824,16777216,281474976710656,32,2199023255552}

    Returns: 606433757

  67. {1,16777216,1125899906842624,36028797018963968,33554432,18014398509481984,17592186044416,274877906944,8192}

    Returns: 593553735

  68. {137438953472,4294967296,65536,64,140737488355328,128,256,256,512,576460752303423488}

    Returns: 698154063

  69. {130,8796126580736,4096,274877906944}

    Returns: 787531764

  70. {2199023255556,132104,2147483648,17592186044736}

    Returns: 984712403

  71. {35184372089344,18014432936361984,16388,9895671758976,576462951326744592,8,633318697598978,4644337115987968,144115188210073600,262144}

    Returns: 847226242

  72. {1099511631872,32,70918768427008,276220084224}

    Returns: 841342628

  73. {8796093022225,1024,9007233614479360}

    Returns: 729701138

  74. {262145,2199031644160,576478344489533504,2147483648,545259520,262144,4503600709509120,1048577,3298534883360,8589937666}

    Returns: 301765921

  75. {1125899906842624,4504699139014720,144396663054663680,68719509504,1266637395200000,262144,1052928,1126999418486784,289356276058562592}

    Returns: 563322887

  76. {139586437121,562949957648896,72057594574798848,562949953421312,2129920}

    Returns: 37654930

  77. {2162752,20266232682905604,9007199254741056,17179877376,1143494240371712}

    Returns: 84241184

  78. {18014402808643712,2147483776}

    Returns: 232733171

  79. {1024,18014948265295872,268437504,144115188075855872,549756862464}

    Returns: 396661272

  80. {137438953472,70377334112776,281749854617608,576495936675512352}

    Returns: 86732404

  81. {2251812832804864,1125899906842624}

    Returns: 933283462

  82. {144115188344291328,135172,36033469943382018,576460752303423488,36310340715151360,34360803328}

    Returns: 456994935

  83. {9007199254740992,145241087982698496,540431955284459520,585467951558164480,24769797950537728,360287970189639680}

    Returns: 901394256

  84. {613615449229230080,351280770934898688,38280596832649216,9007199254740992,2251799813685248,153122387330596864,9007199254740992,81064793292668928}

    Returns: 416673946

  85. {657525545596092416,36028797018963968,164381386399023104,93449692267937792,216172782113783808,585467951558164480,36028797018963968}

    Returns: 465320915

  86. {686798943174000640,109212290963734528,72057594037927936,41658296553177088,612489549322387456,592223350999220224,42784196460019712,797137134044577792}

    Returns: 901096207

  87. {288230376151711744,145241087982698496,144115188075855872,173388585653764096,117093590311632896,584342051651321856,4503599627370496,216172782113783808}

    Returns: 984638509

  88. {324259173170675712,288230376151711744,12384898975268864,144115188075855872,792633534417207296,612489549322387456,144115188075855872}

    Returns: 368605550

  89. {36028797018963968,65302194596872192,40532396646334464,4503599627370496,622622648483971072,594475150812905472,292733975779082240,666532744850833408}

    Returns: 110082755

  90. {794885334230892544,229683580995895296,22517998136852480,4503599627370496,20266198323167232,184647584722190336,22517998136852480,594475150812905472}

    Returns: 297645102

  91. {290482175965396992,874824227616718848,4503599627370496,866942928268820480,604608249974489088,596726950626590720,157625986957967360,450359962737049600,12384898975268864}

    Returns: 724193785

  92. {290482175965396992,731834939447705600,292733975779082240,216172782113783808,433471464134410240,648518346341351424}

    Returns: 125301651

  93. {9147936743096320,67108864,2256197860196352,18084767253659648,720857432535859200,9007199321849856,34359738368,2684354560,8661237760}

    Returns: 751423767

  94. {18874368,4483950051328,67108864,72128237660012544,281474976710656,2200096997376,18155136015663104,144186656331661312,70368744177664,11399775212535808}

    Returns: 178118816

  95. {18014398509481984,16777216,144185730900426752,4299161600,6755536880009216,4415226380288,9895613038592,144115224583077888,216172782131609600,4503608217305088}

    Returns: 209449825

  96. {288802259704217600,281475043819520,5066549581840384,283753054208,1125899973951488,2256249399803904,2289187772432384,144115188621115392,145523662471036928,70514773065728}

    Returns: 328377439

  97. {4194304,9042383626829824,362592546561458176,270532608,288230376151711744,72057594037927936,289074826853744640,148618968091852800,4194304}

    Returns: 763980195

  98. {45317746130419712,612489549326581760,12582912,144115188075855872,1048576,576478348784435200,649784985078726656,2147483648,76703030677864448,581597670632587264}

    Returns: 474517515

  99. {180146218477813760,576460889746571264,4503608257150976,35433480192,1688854155231232,281474978807808,577586652344483840,5075519619989504,288230376151711744,5070964807172096}

    Returns: 562296830

  100. {35185466802176,268435456,171807080448,288305169249075200,67108864,288236973775126528,36178330600341504,18014399583223808,22536827273478144,72567901650944}

    Returns: 576500105

  101. {549755813888,11267795161448448,216172784261267456,598142916493312,17626612891648,1116693594112,4294967296,144396663052566528,19140401512316928,9570698963976192}

    Returns: 640085266

  102. {11258999068426240,8589934592,18014399314788352,18014403341320192,162694735595569152,36046406451986432,4948083343360,2322238653071360,585467951561310208,19791754559488}

    Returns: 479198810

  103. {43997644980224,8797300981760,288230376151711744,1301821918281728,73341892342841344,5629499536310272,72198331543060480,9147937279967232,9007199254740992,288793330416877568}

    Returns: 713200500

  104. {564222337482752,1407374883553280,18155136132055040,2253998837989376,268435456,4503668355235840,2251801961168896,9007199791611904,36028797153181696}

    Returns: 390194980

  105. {290517403287158784,1660004859904,2674023049723904,2260598121299968,4503737066323968,18014398509481984,612489549391593472,72057594037927936,34359738368,2233382993920}

    Returns: 860842665

  106. {70892126208,72057594574798848,2251816993554432,35184376283136,576460752303423488,288230383670001664,36301214580736,426619369947136,4294967296}

    Returns: 718980453

  107. {70371059433472,9020393394274304,4194304,328784797390340096,937874828558336000,176093659136000,108095187149914112,2339146563584,72128237660012544}

    Returns: 263015795

  108. {18014399591612416,17729625063424,2251801961168896,2147483648,2199023321088,1073750016,33554432,108086391056891904,8796093022208}

    Returns: 378210287

  109. {72057594037927936,17592454483968,281475043819520,1125899906842624,4194304,65536,69793218560,1024,4202496,70368744177664}

    Returns: 131409824

  110. {144115188075855872,4303355904,4400195043328,17596489400320,68719476736,131072,34359742464,10240,1073741824}

    Returns: 142603706

  111. {4503668615282688,17314086912,570425344,140738025228288,2748779134976,8798240505856,558345748480,36028797018963968,562949953486848}

    Returns: 581583272

  112. {2269392536600576,2147491840,17594333528064,4503599628423168,562949986979840,144115188075855872,288230513590665216,21474836480}

    Returns: 389230807

  113. {576460752303423488,36028797018963968,17592739692544,75497472,18295873487241216,563224831393792,68992106496,576460752303423488,134217728,2251799822073856}

    Returns: 25722158

  114. {2199023255552,18014398509481984,20266198323167232,36028797018963968,1125899915231232,4503603922337792,274880135168,8796101935104}

    Returns: 95103521

  115. {2048,18014398509481984,2251799813685248,549755813888,72842645340160,8796093022208,137440002048,2253998836957184}

    Returns: 80522044

  116. {549755813888,1125899906875392,17408,68719493120,2814749767106560,9007199254740992,13510798883160064,140874927341568,72057594079870976}

    Returns: 586749071

  117. {35184372154368,146366987893735424,34896613376,10133099161583616,281474976776192,69793218560,576460754450907136,16384,409600,1024}

    Returns: 532751987

  118. {1000000000000000000,999999999999999989,999999999999999965,1000000000000000000,999999999999999993,999999999999999982,999999999999999956,999999999999999957,999999999999999995}

    Returns: 69929909

  119. {146366987893735424,999999999999999989,576460752303423487,1000000000000000000,10133099161583616,999999999999999982,576460752303423490,999999999999999957,12384898975268864,576460752303423488}

    Returns: 575448435

  120. {576460752303423488,288230376151711744,144115188075855872,72057594037927936,36028797018963968,18014398509481984,9007199254740992,4503599627370496,2251799813685248,1125899906842624}

    Returns: 219370084

  121. {576460752303423488,1111111111111111,144115188075855872,72057594037927936,36028797018963968,18014398509481984,9007199254740992,4503599627370496,2251799813685248,1125899906842624}

    Returns: 318732939

  122. {576460752303423488,288230376151711744,144115188075855872,72057594037927936,36028797018963968,18014398509481984,9007199254740992,4503599627370496}

    Returns: 431422661

  123. {612499275440640769,732381150095815937,144115188075855872,72057594037927936,36028797018963968,18014398509481984,9007199254740992,4503599627370496,2251799813685248}

    Returns: 224412639

  124. {576460752303423488,288230376151711744,231045964591683585,344699701299547521,36028797018963968,18014398509481984,9007199254740992,4503599627370496,2251799813685248,1125899906842624}

    Returns: 533995859

  125. {1000000000,1000000000}

    Returns: 420352509

  126. {12345678987456526, 4587546231587956, 56485231524856975, 53216548951235687, 5689745213698521, 99999999999999999, 25487546321597856, 1265489856423154, 56213548756425879, 21358777456225876 }

    Returns: 200091287

  127. {99988877766655544, 99988877766655544, 99988877766655544, 88877766655544, 99855544, 99988877766655544, 998887776665554, 999888777655544, 99988877766655544, 99988817766655544 }

    Returns: 420816458

  128. {1000000000000000000, 999999999999999999, 999999999999999999, 1000000000000000000, 999999999999999999, 999999999999999999, 1000000000000000000, 999999999999999999, 999999999999999999, 1000000000000000000 }

    Returns: 990309104

  129. {100000000000000, 100000000000000000, 100000000000000000, 1000000000000000000, 100000000000000, 100000000000000, 100000000000000000, 1000000000000000, 10000000000000000, 100000000000000000 }

    Returns: 959835785

  130. {698592418393878689, 41176158769631317, 5928437347348326, 627483485536712, 56556167864743, 1612168692743, 232947913547, 41334996277, 3447279799, 459298488 }

    Returns: 747758942

  131. {576460752303423488, 576460752303423488, 576460752303423488, 576460752303423488, 576460752303423488, 576460752303423488, 576460752303423488, 576460752303423488, 576460752303423488, 576460752303423488 }

    Returns: 161955037

  132. {528108405744583338, 883492515133062955, 830551664052244655, 187638468590969912, 709640913966518229, 384525565537843774, 863679694317552710, 23364825948747538, 102901477313730040, 396366775498890592 }

    Returns: 467327797

  133. {100000000000000001, 100000000000000002, 100000000000000003, 100000000000000004, 100000000000000005, 100000000000000006, 100000000000000007, 100000000000000008, 100000000000000009, 100000000000000010 }

    Returns: 673187124

  134. {40000000000000, 40000000000000, 40000000000000, 40000000000000, 40000000000000, 40000000000000, 40000000000000, 40000000000000, 40000000000000, 40000000000000 }

    Returns: 927135074

  135. {10000000001230020, 1000000000132020, 100010000100100, 200303000100230020 }

    Returns: 372675200

  136. {1382875696, 1843654050, 1436430328, 951656720, 120033498 }

    Returns: 620810307

  137. {576460752303423487, 576460752303423487, 576460752303423487, 576460752303423487, 576460752303423487, 576460752303423487, 576460752303423487, 576460752303423487, 576460752303423487, 576460752303423487 }

    Returns: 720959825

  138. {718875778883073113, 902657733719666992, 100147082697904823, 918454075161672321, 206480380521277765, 861227749240591490, 582528414116888542, 189470114334510366, 144328622062251997, 585226965461233378 }

    Returns: 163076795

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: