Conjunctive Sequences

Let ‘$\&$’ denote the bitwise AND operation.
For example, $10\,\&\, 12 = 1010_2\,\&\, 1100_2 = 1000_2 = 8$.
We shall call a finite sequence of non-negative integers $(a_1, a_2, \ldots, a_n)$ conjunctive if $a_i\,\&\, a_{i+1} \neq 0$ for all $i=1\ldots n-1$.
Define $c(n,b)$ to be the number of conjunctive sequences of length $n$ in which all terms are $\le b$.
You are given that $c(3,4)=18$, $c(10,6)=2496120$, and $c(100,200) \equiv 268159379 \pmod {998244353}$.
Find $c(123,123456789)$. Give your answer modulo $998244353$.

This problem involves dynamic programming, bitwise operations, and modular arithmetic, which are more advanced mathematical topics.

We use a dynamic programming approach to solve the problem.

Let’s denote by f[i][j] the number of conjunctive sequences of length i , where the last number in the sequence is j.

Then, we have that the total number of conjunctive sequences of length i is sum(f[i][j]) for all j in [0, b]. This is our goal function.

The dynamic programming relation can be deduced from the problem definition. We have the following:

We start by initializing f[0][0] = 1 and f[0][j] = 0 for all other j.

Then, for all i>0 and j in [0, b], we have:

f[i][j] = sum(f[i-1][k] for all k in [0, b] where k&j != 0)

Then, c(n, b) = sum(f[n][j] for all j in [0, b]).

Finally, to calculate $c(123,123456789)$ modulo $998244353$, we simply compute the total number of conjunctive sequences modulo $998244353$:

$c(123,123456789)$ modulo $998244353$ = sum(f[123][j] for all j in [0,123456789]) modulo $998244353$

Please note that the computation efficiency heavily depends on the implementation. The worst-case time complexity is quadratic in b, so it may take quite a while if b is large. A bitwise trick may be applicable to speed up the calculation.

Please note that this is a more abstract mathematical problem and might not be solvable by hand, but rather require an implementation in a programming language with efficient bitwise operators.

More Answers: