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.
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.
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\).
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.
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.
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.
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.
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.
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.
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)\).
Sei \(C(N,B)\) die Anzahl der Folgen \((a_1,\dots,a_N)\) mit \(0 \le a_i \le B\), für die jedes benachbarte Paar im bitweisen Sinn konjunktiv ist:
$$a_i \mathbin{\&} a_{i+1} \gt 0 \qquad (1 \le i \lt N).$$
Gesucht ist dieser Wert modulo \(998244353\). Eine direkte Enumeration müsste \((B+1)^N\) Kandidaten prüfen und ist daher unbrauchbar; die Implementierung arbeitet stattdessen mit einer memoisierten binären Zerlegung der erlaubten Werte.
Die Rekursion zählt nicht sofort ganze Folgen, sondern Segmente mit Randbedingungen, die festhalten, womit der erste und der letzte Wert noch einen gemeinsamen 1-Bit teilen müssen.
Definiere \(D(\ell,B;\lambda,\rho)\) als die Anzahl der Folgen \((x_1,\dots,x_\ell)\) der Länge \(\ell\) mit \(0 \le x_i \le B\), positiven inneren Konjunktionen und zwei zusätzlichen Randauflagen:
$$x_i \mathbin{\&} x_{i+1} \gt 0 \qquad (1 \le i \lt \ell).$$
Der linke Zustand \(\lambda\) beschränkt \(x_1\), der rechte Zustand \(\rho\) beschränkt \(x_\ell\). Es gibt drei Arten von Randzuständen:
$$\top \text{ (keine offene Bedingung)}, \qquad \mathsf{odd} \text{ (der Endwert muss ungerade sein)}, \qquad [v] \text{ (der Endwert muss mit } v \text{ einen 1-Bit teilen).}$$
Der markierte Zustand \([0]\) ist unmöglich, denn keine Zahl kann eine positive bitweise Konjunktion mit \(0\) besitzen. Die gesuchte Zielgröße ist
$$C(N,B)=D(N,B;\top,\top).$$
Kleine Schranken werden direkt behandelt. Für \(B=0\) steht nur die Zahl \(0\) zur Verfügung, also überlebt nur der triviale unbelastete Fall der Länge \(0\) oder \(1\). Für \(B=1\) lassen sich alle Randauflagen durch explizite Prüfung der Werte \(0\) und \(1\) auswerten.
Jede Zahl ist entweder gerade, also \(2y\), oder ungerade, also \(2y+1\). Damit lässt sich die Schranke \(B\) auf ungefähr die Hälfte reduzieren. Entscheidend ist nur, wie sich eine Randbedingung ändert, wenn die Parität eines Endpunkts festgelegt wird.
Ist der Endpunkt gerade, bezeichne den reduzierten Randzustand mit \(\Phi_0(\sigma)\); ist er ungerade, mit \(\Phi_1(\sigma)\). Es gilt
$$\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{ ungerade},\\ [v/2], & v \text{ gerade}. \end{cases}$$
Diese Regeln folgen direkt aus der Bitarithmetik. Muss ein Endpunkt zum Beispiel mit \(v\) einen Bit teilen und ist er ungerade, dann ist die Bedingung automatisch erfüllt, sobald \(v\) ebenfalls ungerade ist.
Setze nun
$$m=\left\lfloor \frac{B-1}{2} \right\rfloor.$$
Nehmen wir zuerst an, dass in der Folge kein benachbartes Paar gleichzeitig ungerade ist. Dann hängt jede innere Kante weiterhin von höheren Bits ab; nach dem Entfernen des niederwertigsten Bits erhält man also wieder ein Segment derselben Länge mit der kleineren Schranke \(m\).
Übrig bleibt das Zählen von Paritätsmustern der Länge \(\ell\) ohne zwei aufeinanderfolgende ungerade Werte und mit vorgegebener erster und letzter Parität. Genau hier treten die Fibonacci-Zahlen auf. Für
$$F_0=0,\qquad F_1=1,\qquad F_{k}=F_{k-1}+F_{k-2},$$
und die Fortsetzung auf negative Indizes
$$F_{-q}=(-1)^{q+1}F_q$$
lautet der stabile Beitrag
$$\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}$$
Die Koeffizienten entsprechen den vier Randparitäten: gerade-gerade, gerade-ungerade, ungerade-gerade und ungerade-ungerade.
Tritt ein Nachbarpaar ungerade-ungerade auf, dann ist seine Konjunktion bereits im niederwertigsten Bit positiv. Diese Kante muss daher auf höheren Ebenen nicht mehr überprüft werden, und die Folge zerfällt an dieser Stelle in zwei unabhängige Teile.
Liegt der erste solche Schnitt zwischen den Positionen \(x\) und \(x+1\), endet der linke Block mit einem ungeraden Wert und der rechte Block beginnt mit einem ungeraden Wert. Dadurch entsteht der Zusatzterm
$$\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).$$
Der rechte Faktor zählt Präfixe, die mit einem ungeraden Element enden und keinen früheren ungerade-ungerade-Schnitt enthalten. Der linke Faktor zählt das Suffix, dessen erster Eintrag ungerade sein muss.
Ist \(B\) gerade, dann besitzt der Wert \(B\) selbst keinen Repräsentanten im gemeinsamen reduzierten Bereich \(0,\dots,m\), denn es gilt \(B=2(m+1)\). Folgen, die den Wert \(B\) enthalten, müssen deshalb separat addiert werden.
Dafür gibt es drei Lagen:
Erstens kann \(B\) im Inneren stehen und die Folge in Präfix und Suffix teilen. Dann beginnt das Suffix mit der Auflage „muss \(B\) schneiden“, während das Präfix rechts die reduzierte Auflage „muss \(B/2\) schneiden“ erhält.
Zweitens kann \(B\) ganz links stehen, eine Position verbrauchen und die verbleibende linke Randbedingung in „muss \(B\) schneiden“ umwandeln.
Drittens kann \(B\) ganz rechts stehen; nach der Reduktion entsteht dadurch noch ein Fibonacci-gewichteter Randterm. Genau diese Zusatzbeiträge erscheinen nur im geraden Zweig der Implementierungen.
Für \(N=3\) und \(B=4\) sind die erlaubten Werte \(0,1,2,3,4\). Die Zahl \(0\) kann in keiner gültigen Folge auftreten, denn ihre Konjunktion mit jedem Nachbarn ist \(0\).
Man klassifiziert nach dem mittleren Wert:
Ist der Mittelwert \(1\), dann müssen beide Nachbarn Bit \(1\) enthalten; jeder Nachbar liegt also in \(\{1,3\}\), was \(2^2=4\) Folgen ergibt.
Ist der Mittelwert \(2\), dann müssen beide Nachbarn Bit \(2\) enthalten; damit liegt jeder Nachbar in \(\{2,3\}\), erneut also \(4\) Folgen.
Ist der Mittelwert \(3\), dann darf ein Nachbar \(1\), \(2\) oder \(3\) sein, also gibt es \(3^2=9\) Folgen.
Ist der Mittelwert \(4\), dann müssen beide Nachbarn ebenfalls \(4\) sein, also bleibt genau \(1\) Folge.
Somit gilt
$$4+4+9+1=18,$$
genau wie im Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Strategie. Zuerst werden die Fibonacci-Zahlen modulo \(998244353\) bis zur benötigten Folgenlänge vorab berechnet; für negative Indizes wird die Vorzeichenregel benutzt, damit die Rekursion auch an kurzen Rändern einheitlich bleibt.
Anschließend memoisiert die Implementierung den Zustand \(D(\ell,B;\lambda,\rho)\). Bei jeder Anfrage werden zuerst unmögliche Randauflagen verworfen, dann die expliziten Klein-\(B\)-Fälle behandelt und schließlich die drei Rekursionsteile addiert: der stabile Teil ohne Schnitt, die Summe über den ersten ungerade-ungerade-Schnitt und die Sonderterme für gerades \(B\).
Memoisierung ist hier entscheidend. Ohne Wiederverwendung gleicher Teilprobleme würde der Rekursionsbaum explodieren; mit Memoisierung wird jeder unterschiedliche Zustand nur einmal ausgerechnet.
Sei \(|\mathcal S|\) die Anzahl der tatsächlich erreichten memoisierten Zustände. Jeder Zustand benötigt \(O(\ell)\) Rechenarbeit, weil alle Schnittstellen \(x=1,\dots,\ell-1\) betrachtet werden können und im geraden Zweig noch eine zweite Schleife derselben Größenordnung dazukommt. Insgesamt ergibt sich also ungefähr \(O(|\mathcal S| \cdot N)\) Zeit und \(O(|\mathcal S|)\) Speicher für die Memo-Tabelle. Die Vorberechnung der Fibonacci-Zahlen kostet nur \(O(N)\).
\(C(N,B)\), \(0 \le a_i \le B\) koşulunu sağlayan ve her komşu çifti bit düzeyinde konjonktif olan \((a_1,\dots,a_N)\) dizilerinin sayısı olsun:
$$a_i \mathbin{\&} a_{i+1} \gt 0 \qquad (1 \le i \lt N).$$
İstenen değer \(998244353\) modundadır. Doğrudan arama \((B+1)^N\) aday gerektireceği için uygulanabilir değildir; bu yüzden çözüm, izin verilen değerleri ikili yapısına göre parçalayan memoization'lı bir DP kurar.
Rekürans, tüm dizileri bir anda saymak yerine, uç noktalarında hangi bit kesişiminin hâlâ sağlanması gerektiğini tutan segmentleri sayar.
\(D(\ell,B;\lambda,\rho)\), \(0 \le x_i \le B\) olan uzunluğu \(\ell\) olan \((x_1,\dots,x_\ell)\) dizilerinin ve şu iç koşulun sayısı olsun:
$$x_i \mathbin{\&} x_{i+1} \gt 0 \qquad (1 \le i \lt \ell).$$
Burada sol durum \(\lambda\), \(x_1\) üzerinde; sağ durum \(\rho\) ise \(x_\ell\) üzerinde ek bir kısıt uygular. Üç sınır durumu vardır:
$$\top \text{ (bekleyen koşul yok)}, \qquad \mathsf{odd} \text{ (uç değer tek olmak zorunda)}, \qquad [v] \text{ (uç değer } v \text{ ile ortak bir 1-bit taşımak zorunda).}$$
\([0]\) durumu imkansızdır; çünkü hiçbir sayı \(0\) ile pozitif bit düzeyi kesişimi vermez. Nihai cevap
$$C(N,B)=D(N,B;\top,\top)$$
şeklindedir. Küçük üst sınırlar doğrudan ele alınır. \(B=0\) olduğunda elde yalnızca \(0\) vardır; dolayısıyla sadece boş ya da uzunluğu \(1\) olan serbest durum yaşayabilir. \(B=1\) olduğunda ise \(0\) ve \(1\) açıkça denenerek tüm sınır koşulları sayılabilir.
Her sayı ya çifttir, yani \(2y\), ya da tektir, yani \(2y+1\). Bu sayede üst sınır \(B\) yaklaşık yarıya iner. Asıl kritik nokta, uçtaki bir elemanın paritesi sabitlenince sınır koşulunun nasıl dönüştüğüdür.
Uç değer çift seçilirse indirgenmiş sınır durumu \(\Phi_0(\sigma)\), tek seçilirse \(\Phi_1(\sigma)\) olsun. Kurallar şunlardır:
$$\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{ tek},\\ [v/2], & v \text{ çift}. \end{cases}$$
Bunlar doğrudan bit aritmetiğinden gelir. Örneğin uç değer \(v\) ile kesişmek zorundaysa ve seçilen sayı tekse, \(v\) de tek olduğunda en düşük bit zaten ortak olduğu için ek koşul kalmaz.
Şimdi
$$m=\left\lfloor \frac{B-1}{2} \right\rfloor$$
olsun. Önce, dizi boyunca yan yana iki tek sayı hiç oluşmadığını varsayalım. Bu durumda her komşu kenar hâlâ daha yüksek bitlere bağlıdır; dolayısıyla her elemanın en düşük biti atılınca aynı uzunlukta, ama üst sınırı \(m\) olan yeni bir alt problem elde edilir.
Geriye, uzunluğu \(\ell\) olan, yan yana iki tek içermeyen ve ilk-son paritesi sabitlenmiş desenleri saymak kalır. Bunların sayısı Fibonacci ile gelir. Eğer
$$F_0=0,\qquad F_1=1,\qquad F_{k}=F_{k-1}+F_{k-2}$$
ve negatif indisler için
$$F_{-q}=(-1)^{q+1}F_q$$
alınırsa, kararlı katkı
$$\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}$$
olur. Katsayılar dört sınır paritesi olasılığına karşılık gelir: çift-çift, çift-tek, tek-çift ve tek-tek.
Komşu bir çift tek-tek olduğunda, bu iki sayı arasındaki konjonksiyon en düşük bitte zaten pozitiftir. Yani bu kenarın daha yüksek bitlerde yeniden doğrulanmasına gerek yoktur; dizi burada iki bağımsız parçaya ayrılabilir.
İlk böyle kesim \(x\) ve \(x+1\) konumları arasında olsun. O zaman soldaki blok tek bir değerle biter, sağdaki blok da tek bir değerle başlar. Eklenen toplam
$$\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)$$
şeklindedir. Sağdaki çarpan, daha önce tek-tek kesimi oluşmadan tek ile biten öneki; soldaki çarpan ise ilk elemanı tek olmak zorunda olan soneki sayar.
\(B\) çift olduğunda \(B\) sayısının kendisi ortak indirgenmiş aralık \(0,\dots,m\) içine düşmez; çünkü \(B=2(m+1)\) olur. Bu yüzden \(B\) değerini içeren diziler ayrıca eklenir.
Üç yerleşim vardır:
Birincisi, \(B\) dizinin içinde bulunup solu ve sağı ayırabilir. Bu durumda sağ parça “\(B\) ile kesişmek zorunda” sınırıyla başlar; sol parça ise sağ uçta indirgenmiş “\(B/2\) ile kesişmek zorunda” koşulu taşır.
İkincisi, \(B\) en solda durabilir; böylece bir pozisyon tüketir ve kalan sol sınırı “\(B\) ile kesiş” biçimine dönüştürür.
Üçüncüsü, \(B\) en sağda durabilir; bu da indirgeme sonrası ek bir Fibonacci-ağırlıklı sınır terimi üretir. Uygulamadaki yalnızca çift-\(B\) dalında görülen ek katkılar tam olarak bunlardır.
\(N=3\) ve \(B=4\) için izinli değerler \(0,1,2,3,4\)'tür. \(0\) sayısı hiçbir geçerli dizide yer alamaz; çünkü her komşusuyla bit düzeyi kesişimi sıfırdır.
Ortadaki terime göre sınıflandıralım:
Orta terim \(1\) ise, iki komşu da bit \(1\)'i taşımalıdır; dolayısıyla her komşu \(\{1,3\}\) kümesinden gelir ve \(2^2=4\) dizi vardır.
Orta terim \(2\) ise, iki komşu da bit \(2\)'yi taşımalıdır; bu kez her komşu \(\{2,3\}\) kümesinden gelir ve yine \(4\) dizi oluşur.
Orta terim \(3\) ise, komşu \(1\), \(2\) ya da \(3\) olabilir; yani \(3^2=9\) dizi vardır.
Orta terim \(4\) ise, iki komşu da \(4\) olmak zorundadır; bu da yalnızca \(1\) dizi verir.
Dolayısıyla
$$4+4+9+1=18$$
elde edilir; bu da uygulamanın kontrol değeriyle aynıdır.
C++, Python ve Java implementasyonları aynı planı izler. Önce Fibonacci sayıları \(998244353\) modunda gereken uzunluğa kadar önceden hesaplanır; kısa uzunluklarda tek tip formül kullanabilmek için negatif indislerde işaret kuralı uygulanır.
Daha sonra implementasyon \(D(\ell,B;\lambda,\rho)\) durumunu memoize eder. Her durum çağrısında önce imkansız sınırlar elenir, sonra küçük \(B\) taban durumları çözülür, ardından yukarıdaki üç rekürans parçası toplanır: kesimsiz kararlı bölüm, ilk tek-tek ayrımına göre toplam ve \(B\) çift olduğunda gelen özel ekleme terimleri.
Memoization burada belirleyicidir. Aynı alt problemler çok sık tekrarlandığı için, bu önbellekleme olmadan rekürsiyon ağacı hızla patlar; önbelleklemeyle ise her farklı durum yalnızca bir kez hesaplanır.
\(|\mathcal S|\), gerçekten oluşan farklı memo durumlarının sayısı olsun. Her durum \(O(\ell)\) iş yapar; çünkü olası tüm kesim noktaları \(x=1,\dots,\ell-1\) taranabilir ve \(B\) çiftse aynı mertebede ikinci bir döngü daha vardır. Bu nedenle toplam süre yaklaşık \(O(|\mathcal S| \cdot N)\), bellek ise memo tablosu için \(O(|\mathcal S|)\) olur. Fibonacci önişlemesi ise yalnızca \(O(N)\) zaman alır.
Sea \(C(N,B)\) el número de secuencias \((a_1,\dots,a_N)\) con \(0 \le a_i \le B\) tales que cada par adyacente sea conjuntivo en sentido bit a bit:
$$a_i \mathbin{\&} a_{i+1} \gt 0 \qquad (1 \le i \lt N).$$
Hay que calcular este conteo módulo \(998244353\). Un barrido directo tendría que revisar \((B+1)^N\) candidatos, así que la implementación utiliza una descomposición binaria con memoización.
La recurrencia no cuenta secuencias completas desde el principio. Cuenta segmentos acompañados por obligaciones de borde que indican con qué patrón de bits aún debe intersectar el primer o el último término.
Definimos \(D(\ell,B;\lambda,\rho)\) como el número de secuencias \((x_1,\dots,x_\ell)\) de longitud \(\ell\) con \(0 \le x_i \le B\), conjunciones internas positivas y dos reglas extra en los extremos:
$$x_i \mathbin{\&} x_{i+1} \gt 0 \qquad (1 \le i \lt \ell).$$
El estado izquierdo \(\lambda\) restringe a \(x_1\), y el estado derecho \(\rho\) restringe a \(x_\ell\). Hay tres clases de estados de borde:
$$\top \text{ (sin condición pendiente)}, \qquad \mathsf{odd} \text{ (el extremo debe ser impar)}, \qquad [v] \text{ (el extremo debe compartir algún bit 1 con } v).$$
El estado \([0]\) es imposible, porque ningún entero tiene conjunción bit a bit positiva con \(0\). La cantidad final es
$$C(N,B)=D(N,B;\top,\top).$$
Las cotas pequeñas se resuelven directamente. Cuando \(B=0\), el único valor disponible es \(0\), así que solo sobrevive la situación trivial sin restricciones de longitud \(0\) o \(1\). Cuando \(B=1\), basta enumerar explícitamente los valores \(0\) y \(1\).
Cada número es par, \(2y\), o impar, \(2y+1\). Eso permite reducir la cota \(B\) aproximadamente a la mitad. Lo delicado es cómo cambia una condición de borde cuando fijamos la paridad de un extremo.
Si el extremo se fuerza a ser par, escribimos el estado reducido como \(\Phi_0(\sigma)\); si se fuerza a ser impar, usamos \(\Phi_1(\sigma)\). Las reglas son
$$\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{ impar},\\ [v/2], & v \text{ par}. \end{cases}$$
Estas identidades salen directamente de la aritmética binaria. Por ejemplo, si un extremo debe intersectar a \(v\) y el extremo es impar, la condición queda satisfecha automáticamente cuando \(v\) también es impar, porque ambos comparten el bit menos significativo.
Ahora ponemos
$$m=\left\lfloor \frac{B-1}{2} \right\rfloor.$$
Supongamos primero que al recorrer la secuencia no aparece ningún par adyacente impar-impar. En ese caso, cada arista interna sigue dependiendo de bits más altos, y al quitar el bit menos significativo de todos los elementos obtenemos otro segmento de la misma longitud con la cota reducida \(m\).
Solo queda contar los patrones de paridad de longitud \(\ell\) sin dos impares consecutivos y con la primera y la última paridad fijadas. Esos conteos son números de Fibonacci. Si
$$F_0=0,\qquad F_1=1,\qquad F_{k}=F_{k-1}+F_{k-2},$$
y se prolongan a índices negativos mediante
$$F_{-q}=(-1)^{q+1}F_q,$$
la contribución estable es
$$\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}$$
Los coeficientes corresponden a las cuatro posibilidades de paridad en los extremos: par-par, par-impar, impar-par e impar-impar.
Si dos vecinos son impar-impar, entonces su conjunción ya es positiva en el bit menos significativo. Esa arista ya no necesita comprobarse en niveles superiores, de modo que la secuencia puede cortarse en ese punto en dos piezas independientes.
Si el primer corte de este tipo ocurre entre las posiciones \(x\) y \(x+1\), el bloque izquierdo termina en un impar y el bloque derecho empieza en un impar. Esto añade
$$\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).$$
El factor de la derecha cuenta prefijos que terminan en impar y que no contienen antes ningún corte impar-impar. El factor de la izquierda cuenta el sufijo cuyo primer elemento debe ser impar.
Si \(B\) es par, el propio valor \(B\) no aparece dentro del rango reducido común \(0,\dots,m\), porque \(B=2(m+1)\). Por eso, todas las secuencias que contienen el valor \(B\) se suman aparte.
Hay tres ubicaciones posibles:
Primero, \(B\) puede aparecer en el interior y partir la secuencia en prefijo y sufijo. Entonces el sufijo empieza con la obligación “debe intersectar a \(B\)”, mientras que el prefijo termina con la obligación reducida “debe intersectar a \(B/2\)”.
Segundo, \(B\) puede quedar en el extremo izquierdo, consumir una posición y transformar la condición de borde restante en “debe intersectar a \(B\)”.
Tercero, \(B\) puede quedar en el extremo derecho; tras la reducción aparece un término adicional ponderado por Fibonacci. Esos son exactamente los sumandos extra que solo existen en la rama par de la implementación.
Para \(N=3\) y \(B=4\), los valores permitidos son \(0,1,2,3,4\). El valor \(0\) nunca puede aparecer en una secuencia válida porque su conjunción con cualquier vecino es \(0\).
Clasificamos por el término central:
Si el término central es \(1\), ambos vecinos deben compartir el bit \(1\), de modo que cada vecino pertenece a \(\{1,3\}\), lo que da \(2^2=4\) secuencias.
Si el término central es \(2\), ambos vecinos deben contener el bit \(2\), así que cada uno pertenece a \(\{2,3\}\), otra vez \(4\) secuencias.
Si el término central es \(3\), entonces un vecino puede ser \(1\), \(2\) o \(3\), y obtenemos \(3^2=9\) secuencias.
Si el término central es \(4\), ambos vecinos tienen que ser \(4\), por lo que solo hay \(1\) secuencia.
Por tanto,
$$4+4+9+1=18,$$
exactamente el valor de comprobación producido por la implementación.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero precalculan los números de Fibonacci módulo \(998244353\) hasta la longitud necesaria y usan la regla de signo para índices negativos, lo que mantiene uniforme la recurrencia incluso en longitudes pequeñas.
Después, la implementación memoriza el estado \(D(\ell,B;\lambda,\rho)\). Cada vez que aparece un estado, primero descarta obligaciones imposibles, luego resuelve los casos base de \(B\) pequeño y por último suma los tres bloques de la recurrencia: la parte estable sin corte, la suma sobre el primer corte impar-impar y los términos especiales cuando \(B\) es par.
La memoización es imprescindible. Sin reutilizar subproblemas idénticos, el árbol recursivo crecería de forma explosiva; con memoización, cada estado distinto se evalúa una sola vez.
Sea \(|\mathcal S|\) el número de estados memoizados distintos que realmente aparecen. Cada estado hace \(O(\ell)\) trabajo aritmético, porque puede recorrer todos los puntos de corte \(x=1,\dots,\ell-1\), y en la rama par hay un segundo bucle del mismo orden. En consecuencia, el tiempo total es aproximadamente \(O(|\mathcal S| \cdot N)\), con \(O(|\mathcal S|)\) memoria para la tabla de memoización. El precálculo de Fibonacci cuesta solo \(O(N)\).
记 \(C(N,B)\) 为满足 \(0 \le a_i \le B\) 的序列 \((a_1,\dots,a_N)\) 的个数，并且每一对相邻元素都要满足按位与为正：
$$a_i \mathbin{\&} a_{i+1} \gt 0 \qquad (1 \le i \lt N).$$
要求输出这个计数对 \(998244353\) 取模后的结果。若直接暴力枚举，就要检查 \((B+1)^N\) 个候选序列，显然不可行，所以实现采用的是基于二进制分层的记忆化递推。
递推并不是一开始就数完整序列，而是数“带边界义务的区间段”。所谓边界义务，就是记录该段的第一个元素和最后一个元素还需要与什么样的外部值共享某个 1-bit。
定义 \(D(\ell,B;\lambda,\rho)\) 为长度为 \(\ell\) 的序列 \((x_1,\dots,x_\ell)\) 的个数，其中 \(0 \le x_i \le B\)，内部相邻条件为
$$x_i \mathbin{\&} x_{i+1} \gt 0 \qquad (1 \le i \lt \ell).$$
左边状态 \(\lambda\) 约束 \(x_1\)，右边状态 \(\rho\) 约束 \(x_\ell\)。边界状态分为三类：
$$\top \text{（没有未完成的约束）}, \qquad \mathsf{odd} \text{（端点必须是奇数）}, \qquad [v] \text{（端点必须与 } v \text{ 共享某个 1-bit）}. $$
其中 \([0]\) 是不可能状态，因为任何整数与 \(0\) 的按位与都不可能为正。最终要求的目标就是
$$C(N,B)=D(N,B;\top,\top).$$
当上界很小时可以直接处理。若 \(B=0\)，唯一可用的值是 \(0\)，因此只有没有额外边界义务的长度 \(0\) 或长度 \(1\) 的平凡情形可能成立。若 \(B=1\)，则只需显式检查 \(0\) 与 \(1\) 这两个值即可。
每个整数要么是偶数 \(2y\)，要么是奇数 \(2y+1\)。这意味着我们可以把上界 \(B\) 大致减半。真正需要仔细处理的是：一旦端点的奇偶性被固定，边界约束该如何在缩小后的问题中继续表达。
若端点被固定为偶数，把对应的缩减后状态记为 \(\Phi_0(\sigma)\)；若端点被固定为奇数，记为 \(\Phi_1(\sigma)\)。具体规则是
$$\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{ 为奇数},\\ [v/2], & v \text{ 为偶数}. \end{cases}$$
这些规则直接来自按位运算。例如，如果端点必须与 \(v\) 有正的按位与，而端点本身是奇数，那么当 \(v\) 也是奇数时，最低位的 1 已经保证条件自动成立，剩下就不再需要额外边界义务。
令
$$m=\left\lfloor \frac{B-1}{2} \right\rfloor.$$
先考虑一种“稳定”情形：整段序列中不存在相邻的奇数-奇数对。在这种情况下，每一条内部相邻边仍然要靠更高位来决定是否满足条件，所以把所有元素的最低位去掉之后，会得到一个长度仍为 \(\ell\)、但上界变成 \(m\) 的同类子问题。
剩下的问题就是：长度为 \(\ell\) 的奇偶模式中，不允许出现连续两个奇数，并且首元素与末元素的奇偶性已经固定，这样的模式有多少个。这个计数正好由 Fibonacci 数给出。若定义
$$F_0=0,\qquad F_1=1,\qquad F_k=F_{k-1}+F_{k-2},$$
并把它延拓到负下标
$$F_{-q}=(-1)^{q+1}F_q,$$
那么这部分的贡献为
$$\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}$$
四个系数分别对应首尾奇偶性的四种组合：偶-偶、偶-奇、奇-偶、奇-奇。
如果某一对相邻元素是奇-奇，那么它们的按位与在最低位就已经为正了。也就是说，这条边不需要再交给更高位去验证，于是序列可以在这里被切成两个独立部分。
若第一个这样的切点发生在位置 \(x\) 与 \(x+1\) 之间，那么左边那段以奇数结束，右边那段以奇数开始。由此得到额外求和
$$\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).$$
括号中的右因子负责计数“以奇数结尾、且在此之前没有更早奇-奇切点”的前缀；左因子负责计数“第一个元素必须是奇数”的后缀。
若 \(B\) 为偶数，则数值 \(B\) 本身不会落在共同缩减后的区间 \(0,\dots,m\) 内，因为 \(B=2(m+1)\)。因此，所有包含数值 \(B\) 的序列都必须单独补上。
需要分三种位置讨论：
第一，\(B\) 可以出现在序列内部，把原序列分成前缀和后缀。此时后缀的左边界义务变成“必须与 \(B\) 相交”，而前缀的右边界义务则变成缩减后的“必须与 \(B/2\) 相交”。
第二，\(B\) 可以正好出现在最左端。这样会消耗一个位置，并把剩余部分的左边界条件改写成“必须与 \(B\) 相交”。
第三，\(B\) 可以出现在最右端。经过缩减后，这又会产生一个额外的 Fibonacci 加权边界项。实现里只在 \(B\) 为偶数的分支中出现的那些额外项，正是在处理这三种情况。
取 \(N=3\)、\(B=4\)。允许的值是 \(0,1,2,3,4\)。数值 \(0\) 不会出现在任何合法序列中，因为它与任意邻居的按位与都等于 \(0\)。
按照中间项分类：
若中间项是 \(1\)，那么两侧都必须含有 bit \(1\)，所以每个邻居都只能从 \(\{1,3\}\) 中选择，共有 \(2^2=4\) 个序列。
若中间项是 \(2\)，那么两侧都必须含有 bit \(2\)，所以每个邻居只能从 \(\{2,3\}\) 中选择，也有 \(4\) 个序列。
若中间项是 \(3\)，邻居可以是 \(1\)、\(2\) 或 \(3\)，因此有 \(3^2=9\) 个序列。
若中间项是 \(4\)，则两侧都只能是 \(4\)，所以只有 \(1\) 个序列。
因此
$$4+4+9+1=18,$$
这与实现中的小规模校验值完全一致。
C++、Python 和 Java 实现使用完全相同的思路。首先预计算所需长度范围内的 Fibonacci 数，并在模 \(998244353\) 下保存；为了让短长度的递推式保持统一，还使用了负下标的符号规则。
随后，整个实现对状态 \(D(\ell,B;\lambda,\rho)\) 做记忆化搜索。每次请求一个状态时，先排除不可能的边界义务，再处理 \(B\) 很小时的显式基例，然后依次累加上面三类贡献：稳定的无切分部分、按第一个奇-奇切点划分的部分，以及 \(B\) 为偶数时的特殊插入项。
记忆化是核心。因为同一个子问题会在不同路径中反复出现，如果不缓存结果，递归树会迅速膨胀；缓存之后，每个不同状态只会被真正计算一次。
设 \(|\mathcal S|\) 为实际访问到的不同记忆化状态数量。每个状态都需要 \(O(\ell)\) 的运算量，因为它可能遍历所有切分点 \(x=1,\dots,\ell-1\)，而在 \(B\) 为偶数时还会再做一个同阶循环。因此总时间大约是 \(O(|\mathcal S| \cdot N)\)，记忆化表占用 \(O(|\mathcal S|)\) 空间。Fibonacci 的预处理只需要 \(O(N)\) 时间。
Пусть \(C(N,B)\) обозначает число последовательностей \((a_1,\dots,a_N)\), где \(0 \le a_i \le B\), и каждая соседняя пара является конъюнктивной в побитовом смысле:
$$a_i \mathbin{\&} a_{i+1} \gt 0 \qquad (1 \le i \lt N).$$
Нужно вычислить это количество по модулю \(998244353\). Прямой перебор требовал бы проверки \((B+1)^N\) последовательностей, поэтому в реализации используется мемоизированная бинарная рекурсия.
Рекурсия считает не целые последовательности сразу, а отрезки с граничными обязательствами: они описывают, с каким внешним значением первый и последний элемент еще должны иметь общий единичный бит.
Определим \(D(\ell,B;\lambda,\rho)\) как число последовательностей \((x_1,\dots,x_\ell)\) длины \(\ell\), где \(0 \le x_i \le B\), внутренние соседние связи положительны, а также действуют два крайних условия:
$$x_i \mathbin{\&} x_{i+1} \gt 0 \qquad (1 \le i \lt \ell).$$
Левое состояние \(\lambda\) ограничивает \(x_1\), правое состояние \(\rho\) ограничивает \(x_\ell\). Используются три типа граничных состояний:
$$\top \text{ (нет незавершенного условия)}, \qquad \mathsf{odd} \text{ (крайний элемент обязан быть нечетным)}, \qquad [v] \text{ (крайний элемент должен иметь общий 1-bit с } v).$$
Состояние \([0]\) невозможно, потому что положительная побитовая конъюнкция с \(0\) недостижима. Искомая величина равна
$$C(N,B)=D(N,B;\top,\top).$$
Малые значения верхней границы обрабатываются явно. При \(B=0\) доступно только число \(0\), поэтому остается лишь тривиальный свободный случай длины \(0\) или \(1\). При \(B=1\) все ограничения можно разобрать непосредственным перебором значений \(0\) и \(1\).
Каждое число либо четное, \(2y\), либо нечетное, \(2y+1\). Это позволяет примерно вдвое уменьшить верхнюю границу \(B\). Важнее всего понять, как меняется граничное обязательство после фиксации четности крайнего элемента.
Если крайний элемент должен быть четным, обозначим уменьшенное состояние через \(\Phi_0(\sigma)\); если нечетным, через \(\Phi_1(\sigma)\). Тогда
$$\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{ нечетно},\\ [v/2], & v \text{ четно}. \end{cases}$$
Эти правила напрямую следуют из побитовой арифметики. Например, если крайний элемент обязан пересекаться с \(v\), а сам он нечетен, то при нечетном \(v\) условие автоматически выполняется за счет младшего бита.
Теперь положим
$$m=\left\lfloor \frac{B-1}{2} \right\rfloor.$$
Сначала рассмотрим случай, когда в последовательности нет соседней пары нечетное-нечетное. Тогда каждая внутренняя связь по-прежнему зависит от старших битов, и после удаления младшего бита у всех элементов мы получаем новый отрезок той же длины с меньшей границей \(m\).
Остается сосчитать шаблоны четности длины \(\ell\), в которых нет двух подряд идущих нечетных значений, а четность первого и последнего элемента зафиксирована. Эти числа выражаются через последовательность Фибоначчи. Если
$$F_0=0,\qquad F_1=1,\qquad F_k=F_{k-1}+F_{k-2},$$
и отрицательные индексы определяются как
$$F_{-q}=(-1)^{q+1}F_q,$$
то стабильный вклад равен
$$\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}$$
Коэффициенты соответствуют четырем комбинациям четностей на концах: чет-чет, чет-нечет, нечет-чет и нечет-нечет.
Если соседняя пара имеет вид нечетное-нечетное, то их побитовая конъюнкция уже положительна на младшем бите. Значит, эту связь не нужно проверять на более высоких уровнях, и последовательность можно разрезать в этом месте на две независимые части.
Если первый такой разрез расположен между позициями \(x\) и \(x+1\), то левый блок оканчивается нечетным значением, а правый блок начинается с нечетного значения. Получаем дополнительную сумму
$$\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).$$
Правый множитель считает префиксы, которые заканчиваются нечетным элементом и не содержат более раннего разреза нечетное-нечетное. Левый множитель считает суффикс, чей первый элемент обязан быть нечетным.
Когда \(B\) четно, само число \(B\) не попадает в общий уменьшенный диапазон \(0,\dots,m\), потому что \(B=2(m+1)\). Поэтому все последовательности, содержащие значение \(B\), нужно добавлять отдельно.
Есть три варианта расположения:
Во-первых, \(B\) может стоять внутри последовательности и делить ее на префикс и суффикс. Тогда суффикс начинает с условия «должен пересекаться с \(B\)», а префикс получает справа уменьшенное условие «должен пересекаться с \(B/2\)».
Во-вторых, \(B\) может стоять в самом начале, занимая одну позицию и превращая оставшееся левое граничное условие в «должен пересекаться с \(B\)».
В-третьих, \(B\) может стоять в самом конце; после уменьшения это дает еще один граничный член с весами Фибоначчи. Именно эти слагаемые присутствуют только в четной ветви реализации.
Возьмем \(N=3\) и \(B=4\). Допустимые значения: \(0,1,2,3,4\). Число \(0\) не встречается ни в одной корректной последовательности, потому что его побитовая конъюнкция с любым соседом равна \(0\).
Разобьем случаи по среднему элементу:
Если средний элемент равен \(1\), оба соседа должны содержать бит \(1\), значит каждый сосед выбирается из \(\{1,3\}\), и всего получается \(2^2=4\) последовательности.
Если средний элемент равен \(2\), оба соседа обязаны содержать бит \(2\), следовательно каждый сосед выбирается из \(\{2,3\}\), что снова дает \(4\) последовательности.
Если средний элемент равен \(3\), сосед может быть равен \(1\), \(2\) или \(3\), и получается \(3^2=9\) последовательностей.
Если средний элемент равен \(4\), оба соседа должны быть равны \(4\), так что остается ровно \(1\) последовательность.
Следовательно,
$$4+4+9+1=18,$$
что в точности совпадает с проверочным значением реализации.
Реализации на C++, Python и Java устроены одинаково. Сначала они заранее вычисляют числа Фибоначчи по модулю \(998244353\) до нужной длины последовательности и используют правило знака для отрицательных индексов, чтобы формулы оставались единообразными даже на коротких отрезках.
Затем реализация мемоизирует состояние \(D(\ell,B;\lambda,\rho)\). При каждом обращении сначала отбрасываются невозможные граничные требования, затем обрабатываются явные базовые случаи для малых \(B\), а потом суммируются три блока рекурсии: стабильная часть без разреза, сумма по первому разрезу нечетное-нечетное и специальные добавки для четного \(B\).
Мемоизация здесь критична. Одни и те же подзадачи возникают много раз, и без кеширования дерево рекурсии росло бы лавинообразно; с кешированием каждый различный state вычисляется лишь однажды.
Пусть \(|\mathcal S|\) — число различных мемоизированных состояний, которые реально появляются. Каждое состояние требует \(O(\ell)\) операций, потому что может перебирать все точки разреза \(x=1,\dots,\ell-1\), а в четной ветви выполняется еще один цикл того же порядка. Поэтому полное время работы примерно равно \(O(|\mathcal S| \cdot N)\), а память составляет \(O(|\mathcal S|)\) для таблицы мемоизации. Предвычисление Фибоначчи занимает лишь \(O(N)\).
لنعرّف \(C(N,B)\) بأنه عدد المتتاليات \((a_1,\dots,a_N)\) التي تحقق \(0 \le a_i \le B\)، بحيث يكون كل زوج متجاور متلازماً على مستوى البتات:
$$a_i \mathbin{\&} a_{i+1} \gt 0 \qquad (1 \le i \lt N).$$
المطلوب هو حساب هذا العدد بترديد \(998244353\). الفحص المباشر يحتاج إلى تجربة \((B+1)^N\) متتالية، ولذلك تعتمد الشيفرة على تفكيك ثنائي مع حفظ للنتائج الوسيطة.
العودية لا تعدّ المتتاليات الكاملة دفعة واحدة، بل تعدّ مقاطع مزودة بالتزامات حدّية توضّح ما الذي يجب أن يتقاطع معه أول عنصر وآخر عنصر في البتات.
لنعرّف \(D(\ell,B;\lambda,\rho)\) بأنه عدد المتتاليات \((x_1,\dots,x_\ell)\) ذات الطول \(\ell\) حيث \(0 \le x_i \le B\)، وتحقق الشروط الداخلية
$$x_i \mathbin{\&} x_{i+1} \gt 0 \qquad (1 \le i \lt \ell).$$
الحالة اليسرى \(\lambda\) تقيّد \(x_1\)، والحالة اليمنى \(\rho\) تقيّد \(x_\ell\). توجد ثلاثة أنواع من الحالات الحدّية:
$$\top \text{ (لا يوجد قيد معلّق)}, \qquad \mathsf{odd} \text{ (العنصر الطرفي يجب أن يكون فردياً)}, \qquad [v] \text{ (العنصر الطرفي يجب أن يشترك مع } v \text{ في بت واحد على الأقل).}$$
الحالة \([0]\) مستحيلة، لأنه لا يوجد عدد يعطي اقتراناً بتياً موجباً مع \(0\). أما الجواب النهائي فهو
$$C(N,B)=D(N,B;\top,\top).$$
القيم الصغيرة للحد الأعلى تُعالج مباشرة. عندما يكون \(B=0\)، لا يتاح سوى العدد \(0\)، ولذلك لا ينجو إلا الوضع التافه غير المقيّد بطول \(0\) أو \(1\). وعندما يكون \(B=1\)، يمكن فحص القيمتين \(0\) و\(1\) صراحة.
كل عدد إما زوجي ويكتب \(2y\)، أو فردي ويكتب \(2y+1\). هذا يسمح بتقليص الحد الأعلى \(B\) إلى نحو النصف. والمسألة الدقيقة هنا هي: كيف يتغير قيد الحافة عندما نثبت زوجية أو فردية الطرف؟
إذا فُرض أن الطرف زوجي، نرمز للحالة المختزلة بـ \(\Phi_0(\sigma)\)، وإذا فُرض أنه فردي نرمز لها بـ \(\Phi_1(\sigma)\). والقواعد هي
$$\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{ فردي},\\ [v/2], & v \text{ زوجي}. \end{cases}$$
هذه العلاقات ناتجة مباشرة من حساب البتات. فإذا كان الطرف مطالباً بالتقاطع مع \(v\) وكان هذا الطرف فردياً، فإن الشرط يتحقق فوراً عندما يكون \(v\) فردياً أيضاً، لأن البت الأقل مشترك تلقائياً.
لنضع الآن
$$m=\left\lfloor \frac{B-1}{2} \right\rfloor.$$
لننظر أولاً إلى الحالة التي لا يظهر فيها أي زوج متجاور من الشكل فردي-فردي. عندئذٍ تبقى كل علاقة داخلية معتمدة على البتات الأعلى، ولذلك فإن حذف أقل بت من جميع العناصر يعطي مسألة فرعية من الطول نفسه وبحد أعلى أصغر هو \(m\).
يبقى عندها عدّ أنماط الزوجية بطول \(\ell\) التي لا تحتوي فرديين متتاليين، مع تثبيت زوجية أول عنصر وآخر عنصر. هذه الأعداد هي أعداد فيبوناتشي. إذا عرّفنا
$$F_0=0,\qquad F_1=1,\qquad F_k=F_{k-1}+F_{k-2},$$
ومددناها إلى الفهارس السالبة بالعلاقة
$$F_{-q}=(-1)^{q+1}F_q,$$
فإن المساهمة المستقرة تساوي
$$\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}$$
هذه المعاملات تمثل الحالات الأربع لزوجية الطرفين: زوجي-زوجي، زوجي-فردي، فردي-زوجي، وفردي-فردي.
إذا ظهر زوج متجاور من الشكل فردي-فردي، فإن اقترانهما البتي يكون موجباً بالفعل عند أقل بت. لذا لا حاجة لإعادة التحقق من هذه الحافة في المستويات الأعلى، ويمكن شطر المتتالية عند هذا الموضع إلى جزأين مستقلين.
إذا وقع أول هذا الشطر بين الموضعين \(x\) و\(x+1\)، فإن الجزء الأيسر ينتهي بعدد فردي، والجزء الأيمن يبدأ بعدد فردي. وهذا يولّد الجمع الإضافي
$$\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).$$
العامل الموجود داخل القوس يحسب البوادئ التي تنتهي بعدد فردي من دون أن يظهر قبلها شطر فردي-فردي أسبق، أما العامل الآخر فيحسب اللاحقة التي يجب أن يبدأ عنصرها الأول فردياً.
إذا كان \(B\) زوجياً، فإن القيمة \(B\) نفسها لا تظهر داخل المجال المختزل المشترك \(0,\dots,m\)، لأن \(B=2(m+1)\). لذلك يجب إضافة جميع المتتاليات التي تحتوي على القيمة \(B\) على نحو منفصل.
وهنا توجد ثلاث وضعيات:
أولاً، قد تقع \(B\) في داخل المتتالية فتقسمها إلى بادئة ولاحقة. عندئذ تبدأ اللاحقة بالقيد «يجب أن يتقاطع مع \(B\)»، بينما تنتهي البادئة بالقيد المختزل «يجب أن يتقاطع مع \(B/2\)».
ثانياً، قد تقع \(B\) في أقصى اليسار، فتستهلك موضعاً واحداً وتحول القيد الحدّي الباقي إلى «يجب أن يتقاطع مع \(B\)».
ثالثاً، قد تقع \(B\) في أقصى اليمين، وبعد الاختزال يظهر حد إضافي موزون بأعداد فيبوناتشي. وهذه هي بالضبط الحدود الزائدة التي لا تظهر إلا في فرع \(B\) الزوجي داخل الشيفرة.
لنأخذ \(N=3\) و\(B=4\). القيم المسموح بها هي \(0,1,2,3,4\). العدد \(0\) لا يمكن أن يظهر في أي متتالية صحيحة، لأن اقترانه البتي مع أي جار يساوي \(0\).
نصنف حسب العنصر الأوسط:
إذا كان العنصر الأوسط هو \(1\)، فيجب على الجارين أن يشتركا في البت \(1\)، أي إن كل جار ينتمي إلى \(\{1,3\}\)، فنحصل على \(2^2=4\) متتاليات.
إذا كان العنصر الأوسط هو \(2\)، فيجب على الجارين أن يحتوي كل منهما على البت \(2\)، أي إن كل جار ينتمي إلى \(\{2,3\}\)، وهذا يعطي أيضاً \(4\) متتاليات.
إذا كان العنصر الأوسط هو \(3\)، فيمكن أن يكون الجار \(1\) أو \(2\) أو \(3\)، ومن ثم نحصل على \(3^2=9\) متتاليات.
إذا كان العنصر الأوسط هو \(4\)، فلا بد أن يكون الجاران كلاهما \(4\)، ولذلك لا توجد إلا متتالية واحدة.
إذن
$$4+4+9+1=18,$$
وهو تماماً مقدار التحقق الصغير الذي تنتجه الشيفرة.
تنفذ إصدارات C++ وPython وJava الخطة نفسها. فهي تبدأ بحساب أعداد فيبوناتشي مسبقاً بترديد \(998244353\) حتى الطول المطلوب، وتستخدم قاعدة الإشارة للفهارس السالبة لكي تبقى صيغة العودية موحدة حتى في الأطوال الصغيرة.
بعد ذلك تحفظ الشيفرة الحالة \(D(\ell,B;\lambda,\rho)\) في الذاكرة. وعند طلب أي حالة، تُستبعد أولاً الالتزامات الحدّية المستحيلة، ثم تُعالج الحالات الأساسية الصغيرة لـ \(B\)، ثم تُجمع الكتل الثلاث في العودية: الجزء المستقر بلا شطر، ومجموع الشطر الأول من نوع فردي-فردي، وحدود الإدراج الخاصة عندما يكون \(B\) زوجياً.
حفظ النتائج الوسيطة أساسي هنا. فالمسألة نفسها تظهر مراراً من مسارات مختلفة، ومن دون هذا الحفظ سينمو شجر الاستدعاء بسرعة انفجارية، أما معه فإن كل حالة مختلفة تُحسب مرة واحدة فقط.
ليكن \(|\mathcal S|\) عدد الحالات المختلفة المحفوظة فعلاً. كل حالة تحتاج إلى \(O(\ell)\) عملية حسابية، لأنها قد تمر على جميع نقاط الشطر \(x=1,\dots,\ell-1\)، ويوجد في الفرع الزوجي حلقة ثانية من المرتبة نفسها. لذلك يكون الزمن الكلي تقريباً \(O(|\mathcal S| \cdot N)\)، بينما تكون الذاكرة \(O(|\mathcal S|)\) لجدول الحفظ. أما حساب فيبوناتشي المسبق فلا يتجاوز \(O(N)\).