YetAnotherORProblem
SRM 508 · 2010-11-01 · by gojira_tc
SRM 508 · 2010-11-01 · by gojira_tc · Dynamic Programming, Math
Problem Statement
Problem Statement
NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.
You're given along[] 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.
You're given a
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)
{576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488,576460752303423488}
Returns: 161955037
Submissions are judged against all 138 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class YetAnotherORProblem with a public method int countSequences(vector<long long> R) · 138 test cases · 2 s / 256 MB per case