Detailed mathematical approach

Problem Summary

Let \(C(N,B)\) denote the number of sequences \((a_1,\dots,a_N)\) with \(0 \le a_i \le B\) such that every adjacent pair is conjunctive in the bitwise sense:

$a_i \mathbin{\&} a_{i+1} \gt 0 \qquad (1 \le i \lt N).$

The task is to compute this count modulo \(998244353\). A brute-force search would examine \((B+1)^N\) candidates, so the implementations instead perform a memoized binary decomposition of the allowed values.

Mathematical Approach

The recurrence does not count complete sequences immediately. It counts segments together with boundary obligations that describe what the first and last entries still need to intersect.

Step 1: State Definition and Boundary Obligations

Define \(D(\ell,B;\lambda,\rho)\) as the number of length-\(\ell\) sequences \((x_1,\dots,x_\ell)\) with \(0 \le x_i \le B\), all internal conjunctions positive, and two extra boundary rules:

$x_i \mathbin{\&} x_{i+1} \gt 0 \qquad (1 \le i \lt \ell).$

The left state \(\lambda\) constrains \(x_1\), and the right state \(\rho\) constrains \(x_\ell\). There are three kinds of boundary states:

$\top \text{ (no pending constraint)}, \qquad \mathsf{odd} \text{ (the endpoint must be odd)}, \qquad [v] \text{ (the endpoint must share a 1-bit with } v).$

The marked state \([0]\) is impossible, because no integer can have a positive bitwise conjunction with \(0\). The final answer is simply

$C(N,B)=D(N,B;\top,\top).$

Small bounds are handled directly. When \(B=0\), the only available value is \(0\), so only the trivial length-\(0\) or length-\(1\) unconstrained situation survives. When \(B=1\), every endpoint condition can be checked by explicit enumeration of the values \(0\) and \(1\).

Step 2: Strip Off the Lowest Bit

Every number is either even, \(2y\), or odd, \(2y+1\). This lets us move from the bound \(B\) to roughly half the size. The only subtlety is how a boundary condition changes after fixing the parity of an endpoint.

If the endpoint is forced to be even, write its reduced boundary state as \(\Phi_0(\sigma)\); if it is forced to be odd, write \(\Phi_1(\sigma)\). The rules are

$\Phi_0(\top)=\top,\qquad \Phi_1(\top)=\top,$

$\Phi_0(\mathsf{odd})=[0],\qquad \Phi_1(\mathsf{odd})=\top,$

$\Phi_0([v])=[\lfloor v/2 \rfloor],\qquad \Phi_1([v])= \begin{cases} \top, & v \text{ odd},\\ [v/2], & v \text{ even}. \end{cases}$

These identities come straight from bitwise arithmetic. For example, if an endpoint must intersect \(v\) and the endpoint is odd, then the conjunction is already positive when \(v\) is odd, because the least significant bit is shared automatically.

Step 3: Stable Parity Patterns and Fibonacci Weights

Now let

$m=\left\lfloor \frac{B-1}{2} \right\rfloor.$

Suppose first that, when we read the sequence from left to right, no adjacent pair is simultaneously odd. Then every internal edge still depends on higher bits, so after removing the lowest bit from every entry we obtain another segment of the same length at the smaller bound \(m\).

The only thing that remains is to count parity patterns of length \(\ell\) with no consecutive odd entries and prescribed first and last parity. Those counts are Fibonacci numbers. If \((F_k)\) is given by

$F_0=0,\qquad F_1=1,\qquad F_{k}=F_{k-1}+F_{k-2},$

and extended to negative indices by

$F_{-q}=(-1)^{q+1}F_q,$

then the stable contribution is

$\begin{aligned} D(\ell,m;\Phi_0(\lambda),\Phi_0(\rho))\,F_\ell &+D(\ell,m;\Phi_0(\lambda),\Phi_1(\rho))\,F_{\ell-1}\\ &+D(\ell,m;\Phi_1(\lambda),\Phi_0(\rho))\,F_{\ell-1}\\ &+D(\ell,m;\Phi_1(\lambda),\Phi_1(\rho))\,F_{\ell-2}. \end{aligned}$

The coefficients match the four possibilities for the first and last parity: even-even, even-odd, odd-even, and odd-odd.

Step 4: Split at the First Odd-Odd Pair

If a neighboring pair is odd-odd, then its conjunction is already positive at the lowest bit. That edge needs no further higher-bit verification, so the sequence can be cut there into two independent pieces.

If the first such cut happens between positions \(x\) and \(x+1\), the left block ends with an odd value and the right block begins with an odd value. This yields the additional sum

$\sum_{x=1}^{\ell-1} D(\ell-x,B;\mathsf{odd},\rho)\left( D(x,m;\Phi_1(\lambda),\top)\,F_{x-2} \begin{cases} +D(x,m;\Phi_0(\lambda),\top)\,F_{x-1}, & x \gt 1,\\ 0, & x=1. \end{cases} \right).$

The right factor counts parity patterns in the prefix that end with an odd element and contain no earlier odd-odd cut. The left factor counts the suffix whose first element is forced to be odd.

Step 5: The Exceptional Top Value When \(B\) Is Even

When \(B\) is even, the value \(B\) itself has no representative inside the common reduced range \(0,\dots,m\), because \(B=2(m+1)\). Therefore sequences containing the value \(B\) must be added separately.

There are three placements to consider:

First, \(B\) may appear inside the sequence and split it into a prefix and a suffix. The suffix then begins with the obligation “intersect \(B\)”, while the prefix ends with the reduced obligation “intersect \(B/2\)”.

Second, \(B\) may sit at the far left, consuming one position and turning the remaining left boundary rule into “must intersect \(B\)”.

Third, \(B\) may sit at the far right, which after reduction produces one more Fibonacci-weighted boundary term. These are exactly the extra terms that appear only in the even-\(B\) branch of the implementations.

Worked Example: \(C(3,4)=18\)

For the small checkpoint \(N=3\) and \(B=4\), the allowed values are \(0,1,2,3,4\). The number \(0\) never appears in a valid sequence, because it has zero conjunction with every neighbor.

Classify by the middle term:

If the middle term is \(1\), then both neighbors must share bit \(1\), so each neighbor is in \(\{1,3\}\), giving \(2^2=4\) sequences.

If the middle term is \(2\), both neighbors must contain bit \(2\), so each neighbor is in \(\{2,3\}\), again giving \(4\) sequences.

If the middle term is \(3\), then a neighbor may be \(1\), \(2\), or \(3\), so we get \(3^2=9\) sequences.

If the middle term is \(4\), then both neighbors must be \(4\), so there is only \(1\) sequence.

Therefore

$4+4+9+1=18,$

which matches the checkpoint produced by the implementation.

How the Code Works

The C++, Python, and Java implementations all follow the same plan. They precompute Fibonacci numbers modulo \(998244353\) up to the required sequence length and use the sign rule for negative indices so that the recurrence stays uniform even at short lengths.

After that, the implementation memoizes the state \(D(\ell,B;\lambda,\rho)\). Every time a state is requested, it first discards impossible boundary obligations, then handles the explicit small-\(B\) cases, and finally applies the three recurrence blocks above: the stable no-cut part, the sum over the first odd-odd split, and the special insertion terms when \(B\) is even.

Because identical subproblems occur constantly, memoization is essential. Without it the recursion tree would explode; with it, each distinct state is evaluated once and then reused.

Complexity Analysis

Let \(|\mathcal S|\) be the number of distinct memoized states that actually occur. Each state performs \(O(\ell)\) arithmetic because it may scan all split points \(x=1,\dots,\ell-1\), and in the even-\(B\) branch it performs one more loop of the same order. Hence the total running time is approximately \(O(|\mathcal S| \cdot N)\), with \(O(|\mathcal S|)\) memory for the memo table. The Fibonacci precomputation itself is only \(O(N)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=774
2. Bitwise operation: Wikipedia — Bitwise operation
3. Dynamic programming: Wikipedia — Dynamic programming
4. Fibonacci number: Wikipedia — Fibonacci number
5. Memoization: Wikipedia — Memoization