Most Likely And

This problem can be solved in several ways. We will discuss the author’s solution here.

For each $i$ from $1$ to $y$, we will generate how many ways we can take an array of size $n$ such that the elements are between $x$ and $y$ and the bitwise-and value of the array is $i$.

DP approach: (TLE expected)

Let $dp[i][j]$ be the number of ways we can generate an array of size $i$ such that the bitwise-and of the array is $j$, now the transition will look like

$dp[i][p\&q]=dp[i][p\&q]+dp[i-1][q]$

here $p$ is an integer between $x$ and $y$ and $q$ is an integer between $1$ and $y$, and this represents a new element $p$ being added to an array of size $i-1$ that previously had bitwise-and value of $q$.

Notice that the number of ways can be big that it won’t fit in normal $64$ bits integers, we will need structures that can work with larger numbers(BigInt). But there’s an issue Let’s say we are working with an array of size $n$, then the number of ways can contain ~$n*3$ digits. as $n$ can be up to $9*10^{18}$, we can’t store numbers with this many digits.

Observation: For a particular value of $x$ and $y$, let’s the answer for length $i$ be $A_i$​, then $A_i \leq A_j$ for all $i \leq j$, and $A_{infinity}$ will be the bitwise-and value of all integers between $x$ and $y$. Now it can be proven that for all $i \geq (y-x+1)$, $A_i$​ will be the same as $A_{infinity}$ as once $A_i$ reaches that number it won’t change. Turns out that in the given constraints $A_i$ reaches that minimum value within ~$700$ length. So, if a query is given with $n>700$, we can just output that minimum value without any calculations. Otherwise, we can run the DP to generate the result.

The complexity of this approach will be $O(y*y*700*B)$, here $B$ is the time taken for BigInt operations. This will be too slow to pass.

Convolution approach:

Notice that the transition explained in the DP approach is just and-Convolution. Let’s have a polynomial $P$ of degree $y$ where $P_i=1$  for $x \leq i \leq y$, 0 otherwise. Now, and-Convolution of $P$ with itself $n-1$ times will essentially give us $P^n$, now $P^n_i$ represents the number of ways we can generate an array of size $n$ such that the bitwise-and of the array is $i$ and that is what we are after. Do and-Convolution using Fast Walsh Hadamard Transforms and you will have a fast solution. Do the BigInt multiplications in FWHT using Fast Fourier transform and you have a faster solution.

Time Complexity: $O(700*y*log(y)*B)$

Space Complexity: $O(y)$

Bonus Problem:

Given the upper limit of $y$, can you find out what value of $x$, $y$  will take the longest array to reach $A_{infinity}$?