PROBLEM STATEMENT
NOTE: This problem statement contains subscripts that may not display properly if viewed outside
of the applet.
You're given a vector 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:vector
Returns:int
Method signature:int countSequences(vector R)
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
0)
{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}.
1)
{3,3,3}
Returns: 16
2)
{1,128}
Returns: 194
3)
{26,74,25,30}
Returns: 8409
4)
{1000000000,1000000000}
Returns: 420352509
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)2010, TopCoder, Inc. All rights reserved.