YetAnotherORProblem2 | Topcoder Archive

Problem Statement

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

You're given ints N and R. Count the number of sequences A₀, A₁, ..., A_N-1 such that each A_i is an integer satisfying 0 &le A_i &le R and A₀ + A₁ + ... + A_N-1 = A₀ | A₁ | ... | A_N-1. The '|' symbol stands for bitwise OR of the operands. Return the number of such sequences modulo 1,000,000,009.

Definition

Class:: YetAnotherORProblem2
Method:: countSequences
Parameters:: int, int
Returns:: int
Method signature:: int countSequences(int N, int 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

N will be between 2 and 10, inclusive.
R will be between 1 and 15000, inclusive.

Examples

```
2
```
```
2
```
```
Returns: 7
```
The possible sequences are: {0,0}, {0,1}, {0,2}, {1,0}, {1,2}, {2,0}, {2,1}.
```
2
```
```
3
```
```
Returns: 9
```
Now we can also have {0,3} and {3,0}.
```
3
```
```
3
```
```
Returns: 16
```
```
7
```
```
1023
```
```
Returns: 73741815
```

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.