Problem 774: Conjunctive Sequences

Mathematical Foundation

Definition. Let $B = \lfloor \log_2 b \rfloor + 1$ be the number of bits needed to represent integers up to $b$. For a non-negative integer $x \le b$, define its bit-set $\text{bits}(x) = \{j : \text{bit } j \text{ of } x \text{ is } 1\} \subseteq \{0, 1, \ldots, B-1\}$.

Lemma 1 (AND Condition via Bit-sets). $x \mathbin{\&} y \ne 0$ if and only if $\text{bits}(x) \cap \text{bits}(y) \ne \emptyset$.

Proof. $x \mathbin{\&} y$ has a $1$ in bit position $j$ iff both $x$ and $y$ have a $1$ in position $j$. So $x \mathbin{\&} y \ne 0$ iff some bit position is shared, i.e., $\text{bits}(x) \cap \text{bits}(y) \ne \emptyset$. $\square$

Definition. For a subset $T \subseteq \{0, 1, \ldots, B-1\}$, define $w(T) = |\{x : 0 \le x \le b, \text{bits}(x) \supseteq T\}|$ — the count of integers up to $b$ that have all bits in $T$ set.

Lemma 2 (Inclusion-Exclusion for Compatible Counts). For a given $x$ with $\text{bits}(x) = S$, the number of integers $y \le b$ with $x \mathbin{\&} y \ne 0$ is

Proof. By inclusion-exclusion on the events “bit $j$ of $y$ is set” for $j \in S$:

Theorem 1 (Subset-based Transfer Matrix). Define for each non-empty subset $S \subseteq \{0, \ldots, B-1\}$ the count $\alpha(S) = |\{x : 0 \le x \le b, \text{bits}(x) = S\}|$. The number of conjunctive sequences of length $n$ is

This is equivalent to computing the $(n-1)$-th power of a transfer matrix $M$ indexed by non-empty subsets of $\{0, \ldots, B-1\}$, where $M[S, S'] = \mathbf{1}[S \cap S' \ne \emptyset]$.

Proof. Each term $x_i$ with $\text{bits}(x_i) = S_i$ contributes $\alpha(S_i)$ choices. The conjunctive condition $x_i \mathbin{\&} x_{i+1} \ne 0$ is equivalent to $S_i \cap S_{i+1} \ne \emptyset$ by Lemma 1. The matrix product formulation follows from the standard transfer matrix method. $\square$

Theorem 2 (Mobius Inversion on the Boolean Lattice). The transfer matrix $M$ can be diagonalized using the Mobius function of the Boolean lattice (i.e., the zeta/Mobius transforms). Specifically, $M[S, S'] = 1 - \mathbf{1}[S \cap S' = \emptyset]$, so

where $J[S, S'] = 1$ for all $S, S'$ and $D[S, S'] = \mathbf{1}[S \cap S' = \emptyset]$. The matrix $D$ factors over bits: $D[S, S'] = \prod_{j=0}^{B-1} d_j(S, S')$ where $d_j = 1$ if $j \notin S$ or $j \notin S'$, i.e., $d_j = 1 - \mathbf{1}[j \in S]\mathbf{1}[j \in S']$. This tensor product structure enables efficient computation via subset convolution and the “sum over supersets” (SOS) transform.

Proof. $S \cap S' = \emptyset$ iff for every bit $j$, at least one of $S, S'$ does not contain $j$. This gives the product decomposition. The SOS transform diagonalizes each factor, reducing the matrix power to pointwise exponentiation in the transform domain. $\square$

Lemma 3 (Efficient Computation via Ranked Mobius Transform). Using the ranked Mobius transform (subset convolution), the matrix power $M^{n-1}$ applied to the initial vector $\alpha$ can be computed in $O(2^B \cdot B^2)$ time per step and $O(B)$ matrix power steps (via polynomial multiplication in the rank variable), giving total time $O(2^B \cdot B^2 \cdot \log n)$ with repeated squaring.

Proof. The subset convolution framework of Bjorklund et al. (2007) allows computing the “OR-convolution restricted to disjoint sets” in $O(2^B \cdot B^2)$ time. The transfer matrix multiplication in the transform domain becomes pointwise polynomial multiplication (polynomials in the rank variable of degree at most $B$). Matrix exponentiation via repeated squaring requires $O(\log n)$ multiplications. $\square$

Editorial

Sequence of non-negative integers where consecutive terms have nonzero bitwise AND. $c(n,b)$ = count of length-$n$ sequences with terms $\le b$. Find $c(123, 123456789) \bmod 998244353$. We compute alpha(S) for all non-empty S via digit DP. We then alpha(S) = count of x in [0, b] with bits(x) = S. Finally, where w(T) = floor(b / 2^{bits in T positions}) … (digit DP for upper bound).

Pseudocode

Compute alpha(S) for all non-empty S via digit DP
alpha(S) = count of x in [0, b] with bits(x) = S
Use inclusion-exclusion: alpha(S) = sum_{T supseteq S} (-1)^{|T|-|S|} w(T)
where w(T) = floor(b / 2^{bits in T positions}) ... (digit DP for upper bound)
Actually, compute w(T) = |{x <= b : T subseteq bits(x)}| via digit DP
Then Mobius invert: alpha(S) = sum_{T supseteq S} (-1)^{|T\S|} w(T)
Set up the transfer matrix in subset convolution domain
Transform alpha into the ranked Mobius domain
f_hat[S][rank] = ranked zeta transform of alpha
Compute the n-th power
In the transform domain, perform pointwise polynomial exponentiation
Each point has a polynomial of degree <= B, raise to power (n-1)
Use matrix exponentiation or polynomial repeated squaring
Inverse transform to get c(n, b)
Sum over all S of the result vector
Detailed subset convolution approach:
Ranked zeta transform
In transform domain: g_hat[S] = polynomial, raise to power n-1
Then multiply by f_hat to get the convolution
This requires O(2^B * B^2 * log(n)) operations
Count x in [0, b] such that T is a subset of bits(x)
Standard digit DP on the binary representation of b

Complexity Analysis

• Time: $O(2^B \cdot B^2 \cdot \log n)$ where $B = 27$ (since $\log_2(123456789) \approx 26.9$). This gives approximately $2^{27} \cdot 27^2 \cdot 7 \approx 6.8 \times 10^{10}$, which is tight but feasible with constant-factor optimizations. Alternatively, an eigenvalue-based approach exploiting the symmetric structure reduces this further.
• Space: $O(2^B \cdot B) \approx 2^{27} \cdot 27 \approx 3.6 \times 10^9$ bits $\approx 450$ MB, which is tight. Optimizations (e.g., working in compressed representations) may be needed.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 774: Conjunctive Sequences
 *
 * Sequence of non-negative integers where consecutive terms have nonzero bitwise AND. $c(n,b)$ = count of length-$n$ sequences with terms $\le b$. Find 
 */

int main() { printf("Problem 774: Conjunctive Sequences\n"); return 0; }

"""
Problem 774: Conjunctive Sequences

Sequence of non-negative integers where consecutive terms have nonzero bitwise AND. $c(n,b)$ = count of length-$n$ sequences with terms $\le b$. Find $c(123, 123456789) \bmod 998244353$.
"""

print("Problem 774: Conjunctive Sequences")