Problem Statement
You’re given ints N and R. Count the number of sequences A0, A1, …, AN-1 such that each Ai is an integer satisfying 0 < 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.
Tutorial
The problem can be solved using dynamic programming but coming up with dp states is tedious. The trick behind the problem is, understanding how the binary ‘|’ & ‘+’ are related. The fun lies in cracking the relation between the operation. To get idea, break the problem and try solving the sub problems. Hint 1: The result of ‘|’ & ‘+’ operation of binary numbers will be same when for any given column, there is total of one or no bit set. So this simple right, we just need to count the number ways we can set the bits so that the constraint of having one or none for any jth column of bit matrix holds true. Hmm, but how do we make sure the bit configuration is always less that R. For that, trick is we need a state that tells if the current configuration is bounded or unbounded.
Code
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class YetAnotherORProblem2 {
int[][] dp = new int[31][11];
int MOD = 1000000009;
int N, R;
public int countSequences(int N, int R) {
this.N = N;
this.R = R;
for(int i = 0 ; i <31 ; i++)
Arrays.fill(dp[i], -1);
return (int) go(30, N);
}
/* n denotes the if previous recursion is from a valid restricted bit state or not */
long go(int i, int n) {
long res = dp[i][n];
if(res == -1)
{
if(i == 0)
{
dp[i][n] = 1;
return 1;
}
int p = i - 1;
int aux = (R & (1<<p));
if(n == N) /* recursion base starts */
{
if(aux > 0 )
{
res = go(i-1, 0); /* set all row of pth column to 0 */
res += N*go(i-1, 1); /* set '1' to one of the N row */
}
else{
res = go(i-1, n); /* not yet reached a bit */
}
}
else if(n == 1)
{
if(aux > 0)
{
res = go(i-1, 1);
res += (N-1) * go(i-1, 0);
res += go(i-1, 0);
}
else
{
res = go(i-1, 1);
res += (N-1) * go(i-1, 1);
}
}
else{
res = go(i-1, 0);
res += (N) * go(i-1, 0);
}
}
res = (res % MOD);
dp[i][n] = (int) res;
return res;
}
}