YetAnotherORProblem2
SRM 508 · 2010-11-01 · by gojira_tc
SRM 508 · 2010-11-01 · by gojira_tc · Dynamic Programming
Problem Statement
Problem Statement
NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.
You're givenint s N and R. Count the number of sequences A0, A1, ..., AN-1 such that each Ai is an integer satisfying 0 &le Ai &le R 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
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
- N will be between 2 and 10, inclusive.
- R will be between 1 and 15000, inclusive.
Examples
0)
2 2 Returns: 7
The possible sequences are: {0,0}, {0,1}, {0,2}, {1,0}, {1,2}, {2,0}, {2,1}.
1)
2 3 Returns: 9
Now we can also have {0,3} and {3,0}.
2)
3 3 Returns: 16
3)
7 1023 Returns: 73741815
4)
2 1 Returns: 3
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class YetAnotherORProblem2 with a public method int countSequences(int N, int R) · 78 test cases · 2 s / 256 MB per case