For each \(n\), let \(A(n)\) be the number of binary strings of length \(n\) that avoid every palindromic substring of length at least \(5\). Then the number of length-\(n\) strings that do contain such a palindrome is \(2^n-A(n)\), and the cumulative function is
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right).$$
The required counting function is
$$D(L)=\#\left\{n\in\mathbb{Z}:5\le n\le L,\ F_5(n)\equiv 0 \pmod{87654321}\right\}.$$
With \(L=10^{18}\), direct enumeration is hopeless. The implementations instead convert the problem into a periodic congruence in one auxiliary variable.
The solution first counts palindrome-avoiding strings of one exact length, then turns that count into a closed form for \(F_5(n)\), and finally solves a modular periodicity problem.
A binary string contains a palindrome of length at least \(5\) if and only if it contains a palindrome of length exactly \(5\) or exactly \(6\).
Every odd palindrome of length at least \(5\) has a centered palindrome of length \(5\), and every even palindrome of length at least \(6\) has a centered palindrome of length \(6\). So the avoidance problem is equivalent to forbidding only these two local patterns.
Let \(A(n)\) be the number of valid length-\(n\) strings. When a new bit \(x\) is appended, only suffixes ending at that new bit can create a new forbidden palindrome, so it is enough to remember the last five bits.
If the previous suffix is \(b_1b_2b_3b_4b_5\), then appending \(x\) creates a forbidden palindrome of length \(5\) exactly when
$$b_2=x \land b_3=b_5,$$
and it creates one of length \(6\) exactly when
$$b_1=x \land b_2=b_5 \land b_3=b_4.$$
So after length \(5\), the process is a DP on at most \(32\) suffix states. The exact totals begin as
$$A(5)=24,\quad A(6)=30,\quad A(7)=32,\quad A(8)=32,$$
and from \(n=9\) onward the totals enter a stable period of length \(6\):
$$A(9+6t+u)=a_u,\qquad (a_0,a_1,a_2,a_3,a_4,a_5)=(32,34,36,34,32,32).$$
One complete six-step block therefore contributes
$$a_0+a_1+a_2+a_3+a_4+a_5=200.$$
There are \(2^n\) binary strings of length \(n\), so the number that contain a qualifying palindrome is \(2^n-A(n)\). Summing over all lengths gives
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right)=(2^{n+1}-2)-\sum_{k=1}^{n}A(k).$$
Write
$$n=9+6t+u,\qquad u\in\{0,1,2,3,4,5\}.$$
Because the exact-length avoidance counts are periodic, their cumulative sum is linear in \(t\):
$$\sum_{k=1}^{9+6t+u}A(k)=200t+(C_u-2),$$
with
$$\left(C_0,C_1,C_2,C_3,C_4,C_5\right)=\left(182,216,252,286,318,350\right).$$
Substituting into the previous identity yields the closed form used by all three implementations:
$$F_5(9+6t+u)=2^{10+u}64^t-(200t+C_u).$$
The target condition is \(F_5(n)\equiv 0 \pmod{87654321}\). For fixed \(u\), the closed form becomes
$$2^{10+u}64^t \equiv 200t+C_u \pmod{87654321}.$$
The modulus factors as
$$87654321=9\cdot 1997\cdot 4877.$$
So the implementations solve the congruence modulo \(9\), \(1997\), and \(4877\) separately. For one modulus \(m\), the exponential factor \(64^t\) has period \(\operatorname{ord}_m(64)\), while the linear term \(200t+C_u\) has period \(m\). Hence the local period is
$$P_m=\operatorname{lcm}\left(m,\operatorname{ord}_m(64)\right).$$
In this problem the three local periods are
$$P_9=9,\qquad P_{1997}=1993006,\qquad P_{4877}=11890126.$$
For each fixed \(u\), the implementation enumerates one full local period for each modulus factor and records every residue \(t\) that satisfies the congruence modulo that factor.
Two congruences
$$x\equiv a \pmod{m_1},\qquad x\equiv b \pmod{m_2}$$
are compatible exactly when
$$a\equiv b \pmod{\gcd(m_1,m_2)}.$$
Compatible residues are merged step by step into global residues modulo
$$P=\operatorname{lcm}(P_9,P_{1997},P_{4877}).$$
The important point is that the code never scans all \(P\) residue classes. It scans only the three local periods above and combines the matching classes constructively by CRT.
Take \(n=11\). Then \(n=9+6\cdot 0+2\), so \(t=0\) and \(u=2\). The closed form gives
$$F_5(11)=2^{12}-252=3844.$$
This matches the exact avoidance counts. Up to length \(11\), the valid-string totals are
$$A(1),\dots,A(11)=2,4,8,16,24,30,32,32,32,34,36,$$
so
$$\sum_{k=1}^{11}A(k)=250,$$
and therefore
$$F_5(11)=(2^{12}-2)-250=4094-250=3844.$$
Now move one full six-step block forward to \(n=17\). The avoidance sum grows by another \(200\), so
$$F_5(17)=2^{18}-(200+252)=261692.$$
This illustrates why large \(n\) are naturally parameterized by the pair \((t,u)\).
The C++, Python, and Java implementations begin with a small finite-state DP over the last up to five bits. That DP produces the exact short values, including the checkpoints \(F_5(5)=8\), \(F_5(6)=42\), and \(F_5(11)=3844\), and it also confirms the six-term avoidance cycle used by the closed form.
Next, for every \(u\in\{0,1,2,3,4,5\}\) and every modulus factor \(m\in\{9,1997,4877\}\), the implementation scans one local period \(P_m\) and records the residues satisfying
$$2^{10+u}64^t \equiv 200t+C_u \pmod m.$$
Those local residue sets are merged with CRT into sorted global residue lists. For a query limit \(L\), the code handles \(n=5,6,7,8\) directly and, for each \(u\), counts how many
$$t\le \left\lfloor\frac{L-(9+u)}{6}\right\rfloor$$
fall into the stored global residue classes. With sorted residues, the final count is computed as full periods plus a tail found by binary search.
Let \(R_{m,u}\) be the number of valid residues for modulus factor \(m\) in class \(u\). The local scans cost
$$O\left(\sum_{u=0}^{5}\left(P_9+P_{1997}+P_{4877}\right)\right),$$
which is a one-time preprocessing step independent of \(L\). The CRT phase depends on the residue-set sizes, not on the enormous global period \(P\). After preprocessing, evaluating \(D(L)\) only requires six limit conversions and counts in sorted arrays, so the dependence on \(L\) is effectively \(O(1)\) with small logarithmic factors from binary search. Memory usage is proportional to the total number of stored residue classes.
Für jedes \(n\) sei \(A(n)\) die Anzahl binärer Wörter der Länge \(n\), die kein palindromisches Teilwort der Länge mindestens \(5\) enthalten. Dann ist die Anzahl der Wörter der Länge \(n\), die doch ein solches Palindrom enthalten, gleich \(2^n-A(n)\), und die kumulative Funktion lautet
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right).$$
Gesucht ist
$$D(L)=\#\left\{n\in\mathbb{Z}:5\le n\le L,\ F_5(n)\equiv 0 \pmod{87654321}\right\}.$$
Für \(L=10^{18}\) ist direkte Enumeration unmöglich. Die Implementierungen verwandeln das Problem deshalb in eine periodische Kongruenz in einer Hilfsvariablen.
Die Lösung zählt zuerst palindromfreie Wörter fester Länge, leitet daraus eine geschlossene Form für \(F_5(n)\) ab und löst anschließend ein modulare Periodizitätsproblem.
Ein binäres Wort enthält genau dann ein Palindrom der Länge mindestens \(5\), wenn es ein Palindrom der Länge genau \(5\) oder genau \(6\) enthält.
Jedes ungerade Palindrom ab Länge \(5\) enthält sein zentriertes Palindrom der Länge \(5\), und jedes gerade Palindrom ab Länge \(6\) enthält sein zentriertes Palindrom der Länge \(6\). Daher genügt es, nur diese beiden lokalen Muster zu verbieten.
Sei \(A(n)\) die Anzahl gültiger Wörter der Länge \(n\). Beim Anhängen eines neuen Bits \(x\) können nur Suffixe, die an dieser neuen Position enden, erstmals ein verbotenes Palindrom erzeugen. Deshalb reicht es, die letzten fünf Bits zu speichern.
Ist das bisherige Suffix \(b_1b_2b_3b_4b_5\), dann entsteht ein verbotenes Palindrom der Länge \(5\) genau dann, wenn
$$b_2=x \land b_3=b_5,$$
und eines der Länge \(6\) genau dann, wenn
$$b_1=x \land b_2=b_5 \land b_3=b_4.$$
Ab Länge \(5\) ist das also eine DP auf höchstens \(32\) Zuständen. Die exakten Werte beginnen mit
$$A(5)=24,\quad A(6)=30,\quad A(7)=32,\quad A(8)=32,$$
und ab \(n=9\) tritt eine stabile Periode der Länge \(6\) auf:
$$A(9+6t+u)=a_u,\qquad (a_0,a_1,a_2,a_3,a_4,a_5)=(32,34,36,34,32,32).$$
Ein kompletter Sechserblock liefert also
$$a_0+a_1+a_2+a_3+a_4+a_5=200.$$
Es gibt \(2^n\) binäre Wörter der Länge \(n\), also enthalten \(2^n-A(n)\) davon ein zulässiges Palindrom. Über alle Längen aufsummiert ergibt das
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right)=(2^{n+1}-2)-\sum_{k=1}^{n}A(k).$$
Schreibe
$$n=9+6t+u,\qquad u\in\{0,1,2,3,4,5\}.$$
Wegen der Periodizität von \(A(n)\) ist die kumulative Vermeidungszahl linear in \(t\):
$$\sum_{k=1}^{9+6t+u}A(k)=200t+(C_u-2),$$
wobei
$$\left(C_0,C_1,C_2,C_3,C_4,C_5\right)=\left(182,216,252,286,318,350\right).$$
Einsetzen liefert die von allen drei Implementierungen verwendete geschlossene Form:
$$F_5(9+6t+u)=2^{10+u}64^t-(200t+C_u).$$
Gesucht ist \(F_5(n)\equiv 0 \pmod{87654321}\). Für festes \(u\) wird daraus
$$2^{10+u}64^t \equiv 200t+C_u \pmod{87654321}.$$
Der Modulus zerfällt als
$$87654321=9\cdot 1997\cdot 4877.$$
Darum lösen die Implementierungen die Kongruenz getrennt modulo \(9\), \(1997\) und \(4877\). Für einen Faktor \(m\) hat der Exponentialterm \(64^t\) die Periode \(\operatorname{ord}_m(64)\), der lineare Term \(200t+C_u\) die Periode \(m\). Also ist die lokale Periode
$$P_m=\operatorname{lcm}\left(m,\operatorname{ord}_m(64)\right).$$
Hier sind die drei lokalen Perioden
$$P_9=9,\qquad P_{1997}=1993006,\qquad P_{4877}=11890126.$$
Für jedes feste \(u\) enumeriert die Implementierung genau eine lokale Periode pro Modulfaktor und speichert alle Restklassen \(t\), die die jeweilige Kongruenz erfüllen.
Zwei Kongruenzen
$$x\equiv a \pmod{m_1},\qquad x\equiv b \pmod{m_2}$$
sind genau dann verträglich, wenn
$$a\equiv b \pmod{\gcd(m_1,m_2)}.$$
Verträgliche Restklassen werden schrittweise zu globalen Restklassen modulo
$$P=\operatorname{lcm}(P_9,P_{1997},P_{4877})$$
vereinigt. Wichtig ist: Der Code durchläuft niemals alle \(P\) Restklassen. Er durchsucht nur die drei viel kleineren lokalen Perioden und setzt anschließend die passenden Klassen konstruktiv mit CRT zusammen.
Nehmen wir \(n=11\). Dann gilt \(n=9+6\cdot 0+2\), also \(t=0\) und \(u=2\). Die geschlossene Form liefert
$$F_5(11)=2^{12}-252=3844.$$
Das stimmt mit den exakten Vermeidungszahlen überein. Bis Länge \(11\) sind sie
$$A(1),\dots,A(11)=2,4,8,16,24,30,32,32,32,34,36,$$
also
$$\sum_{k=1}^{11}A(k)=250,$$
und somit
$$F_5(11)=(2^{12}-2)-250=4094-250=3844.$$
Geht man einen vollständigen Sechserblock weiter zu \(n=17\), wächst die Vermeidungssumme um weitere \(200\), also
$$F_5(17)=2^{18}-(200+252)=261692.$$
Genau daran sieht man, warum große \(n\) natürlich durch das Paar \((t,u)\) beschrieben werden.
Die C++-, Python- und Java-Implementierungen beginnen mit einer kleinen endlichen DP über die letzten bis zu fünf Bits. Diese DP erzeugt die exakten kurzen Werte, darunter die Kontrollpunkte \(F_5(5)=8\), \(F_5(6)=42\) und \(F_5(11)=3844\), und bestätigt außerdem den Sechserzyklus der Vermeidungszahlen.
Danach wird für jedes \(u\in\{0,1,2,3,4,5\}\) und jeden Modulfaktor \(m\in\{9,1997,4877\}\) genau eine lokale Periode \(P_m\) durchlaufen, und alle Restklassen mit
$$2^{10+u}64^t \equiv 200t+C_u \pmod m$$
werden gespeichert. Diese lokalen Mengen werden per CRT zu sortierten globalen Restlisten zusammengeführt. Für eine Schranke \(L\) behandelt der Code \(n=5,6,7,8\) direkt und zählt dann für jedes \(u\), wie viele
$$t\le \left\lfloor\frac{L-(9+u)}{6}\right\rfloor$$
in den gespeicherten globalen Restklassen liegen. Mit sortierten Listen ist das am Ende nur noch „volle Perioden plus Reststück via binärer Suche“.
Sei \(R_{m,u}\) die Anzahl gültiger Restklassen für den Modulfaktor \(m\) in der Klasse \(u\). Die lokalen Scans kosten
$$O\left(\sum_{u=0}^{5}\left(P_9+P_{1997}+P_{4877}\right)\right),$$
also eine einmalige Vorberechnung unabhängig von \(L\). Die CRT-Phase hängt von den Größen der Restmengen ab und nicht von der riesigen globalen Periode \(P\). Nach der Vorberechnung benötigt die Auswertung von \(D(L)\) nur sechs Grenzumrechnungen und Zählungen in sortierten Arrays; die Abhängigkeit von \(L\) ist daher effektiv \(O(1)\) mit kleinen logarithmischen Faktoren durch die binäre Suche. Der Speicherverbrauch ist proportional zur Gesamtzahl der gespeicherten Restklassen.
Her \(n\) için \(A(n)\), uzunluğu \(n\) olan ve uzunluğu en az \(5\) olan hiçbir palindromik alt dize içermeyen ikili dizelerin sayısı olsun. O zaman böyle bir palindromu içeren uzunluk-\(n\) dizelerin sayısı \(2^n-A(n)\) olur ve kümülatif fonksiyon
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right)$$
şeklindedir. İstenen sayım fonksiyonu ise
$$D(L)=\#\left\{n\in\mathbb{Z}:5\le n\le L,\ F_5(n)\equiv 0 \pmod{87654321}\right\}.$$
\(L=10^{18}\) için doğrudan tarama mümkün değildir. Uygulamalar bunun yerine problemi tek bir yardımcı değişkende periyodik bir kongruansa dönüştürür.
Çözüm önce sabit bir uzunluk için palindromdan kaçınan dizileri sayar, sonra bu sayımları \(F_5(n)\) için kapalı forma çevirir ve son olarak modüler periyodiklik kullanır.
Bir ikili dizi, uzunluğu en az \(5\) olan bir palindrom içeriyorsa ve ancak o zaman uzunluğu tam \(5\) ya da tam \(6\) olan bir palindrom da içerir.
Uzunluğu en az \(5\) olan her tek palindrom kendi merkezindeki uzunluk-\(5\) palindromunu, uzunluğu en az \(6\) olan her çift palindrom da merkezindeki uzunluk-\(6\) palindromunu içerir. Bu yüzden kaçınma problemi sadece bu iki yerel desenin yasaklanmasına indirgenir.
\(A(n)\), uzunluğu \(n\) olan geçerli dizelerin sayısı olsun. Yeni bir bit \(x\) eklendiğinde, yasak bir palindromu ancak bu yeni konumda biten son ekler oluşturabilir. Bu nedenle son beş biti hatırlamak yeterlidir.
Önceki son ek \(b_1b_2b_3b_4b_5\) ise, \(x\) eklenince uzunluk \(5\) olan yasak palindrom tam olarak şu durumda oluşur:
$$b_2=x \land b_3=b_5,$$
uzunluk \(6\) olan yasak palindrom ise tam olarak şu durumda oluşur:
$$b_1=x \land b_2=b_5 \land b_3=b_4.$$
Böylece uzunluk \(5\)'ten sonra süreç en fazla \(32\) son ek durumuna sahip bir DP olur. İlk değerler
$$A(5)=24,\quad A(6)=30,\quad A(7)=32,\quad A(8)=32$$
şeklindedir ve \(n=9\)'dan itibaren toplamlar uzunluğu \(6\) olan kararlı bir döngüye girer:
$$A(9+6t+u)=a_u,\qquad (a_0,a_1,a_2,a_3,a_4,a_5)=(32,34,36,34,32,32).$$
Dolayısıyla bir tam altılı blok toplamda
$$a_0+a_1+a_2+a_3+a_4+a_5=200$$
katkı yapar.
Uzunluğu \(n\) olan ikili dize sayısı \(2^n\) olduğundan, istenen palindromu içerenlerin sayısı \(2^n-A(n)\)'dir. Tüm uzunluklar boyunca toplayınca
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right)=(2^{n+1}-2)-\sum_{k=1}^{n}A(k)$$
elde edilir. Şimdi
$$n=9+6t+u,\qquad u\in\{0,1,2,3,4,5\}$$
yazalım. \(A(n)\) periyodik olduğu için kümülatif kaçınma sayısı \(t\)'de lineerdir:
$$\sum_{k=1}^{9+6t+u}A(k)=200t+(C_u-2),$$
burada kullanılan sabitler
$$\left(C_0,C_1,C_2,C_3,C_4,C_5\right)=\left(182,216,252,286,318,350\right)$$
şeklindedir. Bunu yerine koyunca üç uygulamanın da kullandığı kapalı form çıkar:
$$F_5(9+6t+u)=2^{10+u}64^t-(200t+C_u).$$
Hedef koşul \(F_5(n)\equiv 0 \pmod{87654321}\)'dir. Sabit bir \(u\) için bu,
$$2^{10+u}64^t \equiv 200t+C_u \pmod{87654321}$$
kongruansına dönüşür. Modül şu şekilde çarpanlara ayrılır:
$$87654321=9\cdot 1997\cdot 4877.$$
Bu yüzden uygulamalar kongruansı önce \(9\), \(1997\) ve \(4877\) modlarında ayrı ayrı çözer. Bir \(m\) modülü için üstel terim \(64^t\), \(\operatorname{ord}_m(64)\) periyoduna; lineer terim \(200t+C_u\) ise \(m\) periyoduna sahiptir. Bu nedenle yerel periyot
$$P_m=\operatorname{lcm}\left(m,\operatorname{ord}_m(64)\right)$$
olur. Bu problemde
$$P_9=9,\qquad P_{1997}=1993006,\qquad P_{4877}=11890126$$
elde edilir.
Her sabit \(u\) için uygulama, her modül çarpanı adına bir tam yerel periyot tarar ve kongruansı sağlayan tüm \(t\) artıklarını kaydeder.
İki kongruans
$$x\equiv a \pmod{m_1},\qquad x\equiv b \pmod{m_2}$$
ancak ve ancak
$$a\equiv b \pmod{\gcd(m_1,m_2)}$$
olduğunda uyumludur. Uyumlu artıklar adım adım
$$P=\operatorname{lcm}(P_9,P_{1997},P_{4877})$$
modundaki küresel artık sınıflarına dönüştürülür. Kritik nokta şudur: kod hiçbir zaman \(P\) tane olası \(t\) değerinin tamamını dolaşmaz. Sadece üç daha küçük yerel periyodu tarar ve uygun sınıfları yapıcı biçimde CRT ile birleştirir.
\(n=11\) alalım. Bu durumda \(n=9+6\cdot 0+2\), yani \(t=0\) ve \(u=2\). Kapalı form
$$F_5(11)=2^{12}-252=3844$$
sonucunu verir. Bu, sabit uzunluk kaçınma sayılarıyla da uyuşur. Uzunluk \(11\)'e kadar geçerli dizilerin sayıları
$$A(1),\dots,A(11)=2,4,8,16,24,30,32,32,32,34,36$$
olduğundan
$$\sum_{k=1}^{11}A(k)=250,$$
dolayısıyla
$$F_5(11)=(2^{12}-2)-250=4094-250=3844.$$
Bir tam altılı blok ilerleyip \(n=17\)'ye geçtiğimizde kaçınma toplamı \(200\) daha artar ve
$$F_5(17)=2^{18}-(200+252)=261692$$
elde edilir. Bu, büyük \(n\) değerlerinin neden doğal olarak \((t,u)\) çiftiyle ifade edildiğini açıkça gösterir.
C++, Python ve Java implementasyonları önce son en fazla beş bit üzerinde küçük bir sonlu durum DP'si kurar. Bu DP kısa uzunluklar için tam değerleri, yani \(F_5(5)=8\), \(F_5(6)=42\) ve \(F_5(11)=3844\) kontrol noktalarını üretir; ayrıca kapalı formda kullanılan altılı kaçınma döngüsünü de doğrular.
Daha sonra her \(u\in\{0,1,2,3,4,5\}\) ve her modül çarpanı \(m\in\{9,1997,4877\}\) için bir yerel periyot \(P_m\) taranır ve
$$2^{10+u}64^t \equiv 200t+C_u \pmod m$$
koşulunu sağlayan artıklar kaydedilir. Bu yerel kümeler CRT ile sıralı küresel artık listelerine dönüştürülür. Bir \(L\) sınırı verildiğinde kod önce \(n=5,6,7,8\) durumlarını doğrudan ele alır, sonra her \(u\) için
$$t\le \left\lfloor\frac{L-(9+u)}{6}\right\rfloor$$
eşitsizliğini sağlayan ve saklanan küresel artık sınıflarına düşen \(t\) sayısını hesaplar. Sıralı listeler sayesinde son adım “tam periyotlar + ikili aramayla kuyruk sayımı” olur.
\(R_{m,u}\), \(u\) sınıfında \(m\) modül çarpanı için geçerli artık sayısı olsun. Yerel taramalar
$$O\left(\sum_{u=0}^{5}\left(P_9+P_{1997}+P_{4877}\right)\right)$$
zamanda tamamlanır; bu, \(L\)'den bağımsız tek seferlik bir ön işlemdir. CRT aşaması devasa küresel periyot \(P\)'ye değil, artık kümelerinin büyüklüklerine bağlıdır. Ön işlemeden sonra \(D(L)\) hesabı sadece altı sınır dönüşümü ve sıralı dizilerde arama gerektirir; bu yüzden \(L\)'ye bağımlılık pratikte küçük logaritmik terimlerle \(O(1)\) düzeyindedir. Bellek kullanımı saklanan toplam artık sınıfı sayısıyla orantılıdır.
Para cada \(n\), sea \(A(n)\) el número de cadenas binarias de longitud \(n\) que evitan todo subpalíndromo de longitud al menos \(5\). Entonces el número de cadenas de longitud \(n\) que sí contienen uno de esos palíndromos es \(2^n-A(n)\), y la función acumulada es
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right).$$
La cantidad pedida es
$$D(L)=\#\left\{n\in\mathbb{Z}:5\le n\le L,\ F_5(n)\equiv 0 \pmod{87654321}\right\}.$$
Con \(L=10^{18}\), enumerar todos los \(n\) es inviable. Por eso las implementaciones convierten el problema en una congruencia periódica en una variable auxiliar.
La idea es contar primero las cadenas que evitan palíndromos para una longitud exacta, después resumir esos conteos en una fórmula cerrada para \(F_5(n)\), y por último resolver una condición modular periódica.
Una cadena binaria contiene un palíndromo de longitud al menos \(5\) si y solo si contiene un palíndromo de longitud exactamente \(5\) o exactamente \(6\).
Todo palíndromo impar de longitud al menos \(5\) contiene su palíndromo central de longitud \(5\), y todo palíndromo par de longitud al menos \(6\) contiene su palíndromo central de longitud \(6\). Por tanto, el problema de evitación se reduce a prohibir solo esos dos patrones locales.
Sea \(A(n)\) el número de cadenas válidas de longitud \(n\). Al añadir un nuevo bit \(x\), solo los sufijos que terminan en ese nuevo bit pueden crear por primera vez un palíndromo prohibido, así que basta con recordar los últimos cinco bits.
Si el sufijo anterior es \(b_1b_2b_3b_4b_5\), añadir \(x\) crea un palíndromo prohibido de longitud \(5\) exactamente cuando
$$b_2=x \land b_3=b_5,$$
y crea uno de longitud \(6\) exactamente cuando
$$b_1=x \land b_2=b_5 \land b_3=b_4.$$
Así, a partir de la longitud \(5\), el proceso es una DP sobre como mucho \(32\) estados de sufijo. Los primeros valores exactos son
$$A(5)=24,\quad A(6)=30,\quad A(7)=32,\quad A(8)=32,$$
y desde \(n=9\) los totales entran en un período estable de longitud \(6\):
$$A(9+6t+u)=a_u,\qquad (a_0,a_1,a_2,a_3,a_4,a_5)=(32,34,36,34,32,32).$$
Por eso un bloque completo de seis pasos aporta
$$a_0+a_1+a_2+a_3+a_4+a_5=200.$$
Hay \(2^n\) cadenas binarias de longitud \(n\), de modo que \(2^n-A(n)\) contienen un palíndromo válido. Sumando sobre todas las longitudes se obtiene
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right)=(2^{n+1}-2)-\sum_{k=1}^{n}A(k).$$
Escribimos
$$n=9+6t+u,\qquad u\in\{0,1,2,3,4,5\}.$$
Como \(A(n)\) es periódico, la suma acumulada de evitadores es lineal en \(t\):
$$\sum_{k=1}^{9+6t+u}A(k)=200t+(C_u-2),$$
con
$$\left(C_0,C_1,C_2,C_3,C_4,C_5\right)=\left(182,216,252,286,318,350\right).$$
Al sustituir, aparece la fórmula cerrada usada por las tres implementaciones:
$$F_5(9+6t+u)=2^{10+u}64^t-(200t+C_u).$$
La condición objetivo es \(F_5(n)\equiv 0 \pmod{87654321}\). Para un \(u\) fijo se transforma en
$$2^{10+u}64^t \equiv 200t+C_u \pmod{87654321}.$$
El módulo factoriza como
$$87654321=9\cdot 1997\cdot 4877.$$
Por eso las implementaciones resuelven la congruencia por separado módulo \(9\), \(1997\) y \(4877\). Para un factor \(m\), el término exponencial \(64^t\) tiene período \(\operatorname{ord}_m(64)\), mientras que el término lineal \(200t+C_u\) tiene período \(m\). El período local es entonces
$$P_m=\operatorname{lcm}\left(m,\operatorname{ord}_m(64)\right).$$
En este problema resulta
$$P_9=9,\qquad P_{1997}=1993006,\qquad P_{4877}=11890126.$$
Para cada \(u\) fijo, la implementación recorre un período local completo para cada factor del módulo y guarda todos los residuos \(t\) que satisfacen la congruencia en ese factor.
Dos congruencias
$$x\equiv a \pmod{m_1},\qquad x\equiv b \pmod{m_2}$$
son compatibles exactamente cuando
$$a\equiv b \pmod{\gcd(m_1,m_2)}.$$
Los residuos compatibles se van fusionando paso a paso en residuos globales módulo
$$P=\operatorname{lcm}(P_9,P_{1997},P_{4877}).$$
El punto importante es que el código nunca recorre los \(P\) valores posibles de \(t\). Solo recorre los tres períodos locales mucho más pequeños y luego combina de forma constructiva las clases compatibles mediante CRT.
Tomemos \(n=11\). Entonces \(n=9+6\cdot 0+2\), así que \(t=0\) y \(u=2\). La fórmula cerrada da
$$F_5(11)=2^{12}-252=3844.$$
Esto coincide con los conteos exactos de evitación. Hasta la longitud \(11\), los totales válidos son
$$A(1),\dots,A(11)=2,4,8,16,24,30,32,32,32,34,36,$$
por lo que
$$\sum_{k=1}^{11}A(k)=250,$$
y entonces
$$F_5(11)=(2^{12}-2)-250=4094-250=3844.$$
Si avanzamos un bloque completo de seis pasos hasta \(n=17\), la suma de evitadores aumenta en otros \(200\), y obtenemos
$$F_5(17)=2^{18}-(200+252)=261692.$$
Eso muestra con claridad por qué los valores grandes de \(n\) quedan parametrizados naturalmente por el par \((t,u)\).
Las implementaciones en C++, Python y Java empiezan con una pequeña DP de estados finitos sobre los últimos hasta cinco bits. Esa DP produce los valores exactos cortos, incluidos los puntos de control \(F_5(5)=8\), \(F_5(6)=42\) y \(F_5(11)=3844\), y además confirma el ciclo de seis términos usado en la fórmula cerrada.
Después, para cada \(u\in\{0,1,2,3,4,5\}\) y cada factor \(m\in\{9,1997,4877\}\), la implementación recorre un período local \(P_m\) y guarda los residuos que satisfacen
$$2^{10+u}64^t \equiv 200t+C_u \pmod m.$$
Esos conjuntos locales se fusionan con CRT en listas globales ordenadas de residuos. Para un límite \(L\), el código trata \(n=5,6,7,8\) de forma directa y, para cada \(u\), cuenta cuántos
$$t\le \left\lfloor\frac{L-(9+u)}{6}\right\rfloor$$
caen en las clases globales almacenadas. Con listas ordenadas, el conteo final se reduce a períodos completos más una cola obtenida por búsqueda binaria.
Sea \(R_{m,u}\) el número de residuos válidos para el factor \(m\) en la clase \(u\). Los recorridos locales cuestan
$$O\left(\sum_{u=0}^{5}\left(P_9+P_{1997}+P_{4877}\right)\right),$$
y constituyen una sola precomputación independiente de \(L\). La fase CRT depende del tamaño de los conjuntos de residuos, no del enorme período global \(P\). Tras esa precomputación, evaluar \(D(L)\) solo requiere seis conversiones de límite y conteos en arreglos ordenados, así que la dependencia respecto de \(L\) es en la práctica \(O(1)\) con pequeños factores logarítmicos por las búsquedas binarias. La memoria es proporcional al número total de clases residuales almacenadas.
对每个 \(n\)，记 \(A(n)\) 为长度恰好为 \(n\) 的二进制串中，不含任何长度至少为 \(5\) 的回文子串的个数。那么长度为 \(n\) 且至少含有一个这类回文的二进制串个数就是 \(2^n-A(n)\)，相应的累计函数为
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right).$$
题目要求计算
$$D(L)=\#\left\{n\in\mathbb{Z}:5\le n\le L,\ F_5(n)\equiv 0 \pmod{87654321}\right\}.$$
当 \(L=10^{18}\) 时，不可能逐个枚举所有 \(n\)。因此实现采用的是“先做精确计数，再提炼出周期同余结构”的路线，而不是线性扫描。
整个方法分成三层：先计算固定长度下“回文规避串”的数量，再把它们累加成 \(F_5(n)\) 的闭式，最后把可整除条件转化为关于一个辅助变量的周期计数问题。
一个二进制串含有长度至少为 \(5\) 的回文，当且仅当它含有长度恰好为 \(5\) 或长度恰好为 \(6\) 的回文。
理由很直接。任意长度至少为 \(5\) 的奇回文，都包含一个以同一中心为中心的长度 \(5\) 回文；任意长度至少为 \(6\) 的偶回文，都包含一个以同一中心为中心的长度 \(6\) 回文。于是“避免所有长度至少 \(5\) 的回文”与“只避免长度 \(5\) 和 \(6\) 的回文”完全等价。
设 \(A(n)\) 为长度 \(n\) 的合法二进制串个数。向当前串末尾追加一个新比特 \(x\) 时，只有那些以这个新位置结尾的后缀才可能新产生禁用回文，因此只需要记住最后五个比特。
若原来的最后五位是 \(b_1b_2b_3b_4b_5\)，那么追加 \(x\) 后，出现长度 \(5\) 的禁用回文当且仅当
$$b_2=x \land b_3=b_5,$$
出现长度 \(6\) 的禁用回文当且仅当
$$b_1=x \land b_2=b_5 \land b_3=b_4.$$
因此从长度 \(5\) 开始，问题就变成一个最多只有 \(32\) 个后缀状态的 DP。按这个自动机推进，可以得到前几项精确值
$$A(5)=24,\quad A(6)=30,\quad A(7)=32,\quad A(8)=32,$$
而从 \(n=9\) 开始，总数进入稳定的 \(6\) 周期：
$$A(9+6t+u)=a_u,\qquad (a_0,a_1,a_2,a_3,a_4,a_5)=(32,34,36,34,32,32).$$
所以一个完整六项块的总贡献为
$$a_0+a_1+a_2+a_3+a_4+a_5=200.$$
长度为 \(n\) 的二进制串总共有 \(2^n\) 个，因此其中包含目标回文的个数是 \(2^n-A(n)\)。对所有长度累加后有
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right)=(2^{n+1}-2)-\sum_{k=1}^{n}A(k).$$
把 \(n\) 写成
$$n=9+6t+u,\qquad u\in\{0,1,2,3,4,5\}.$$
由于 \(A(n)\) 在 \(n\ge 9\) 时是周期 \(6\) 的，所以规避串的累计和对 \(t\) 呈线性：
$$\sum_{k=1}^{9+6t+u}A(k)=200t+(C_u-2),$$
其中实现中使用的常数是
$$\left(C_0,C_1,C_2,C_3,C_4,C_5\right)=\left(182,216,252,286,318,350\right).$$
代回去就得到三个实现共同使用的闭式：
$$F_5(9+6t+u)=2^{10+u}64^t-(200t+C_u).$$
目标条件是 \(F_5(n)\equiv 0 \pmod{87654321}\)。对固定的 \(u\)，闭式变成
$$2^{10+u}64^t \equiv 200t+C_u \pmod{87654321}.$$
模数可分解为
$$87654321=9\cdot 1997\cdot 4877.$$
因此实现先分别在 \(9\)、\(1997\)、\(4877\) 这三个模下求解。对任意一个模 \(m\)，指数项 \(64^t\) 的周期是 \(\operatorname{ord}_m(64)\)，线性项 \(200t+C_u\) 的周期是 \(m\)，所以局部周期为
$$P_m=\operatorname{lcm}\left(m,\operatorname{ord}_m(64)\right).$$
在本题里三者分别是
$$P_9=9,\qquad P_{1997}=1993006,\qquad P_{4877}=11890126.$$
对每个固定的 \(u\)，实现会在每个模因子的一个完整局部周期上枚举所有 \(t\)，把满足该模下同余方程的残基全部保存下来。
两个同余条件
$$x\equiv a \pmod{m_1},\qquad x\equiv b \pmod{m_2}$$
可兼容的充要条件是
$$a\equiv b \pmod{\gcd(m_1,m_2)}.$$
把兼容的局部残基逐步合并，就能得到模
$$P=\operatorname{lcm}(P_9,P_{1997},P_{4877})$$
的全局残基类。这里最关键的一点是：实现并不会在这个巨大的全局周期上逐项扫描。它只扫描三个较小的局部周期，然后用 CRT 构造性地合并那些彼此兼容的残基类。
以 \(n=11\) 为例。此时 \(n=9+6\cdot 0+2\)，所以 \(t=0\)、\(u=2\)。闭式直接给出
$$F_5(11)=2^{12}-252=3844.$$
这和精确的规避计数完全一致。到长度 \(11\) 为止，合法串个数依次为
$$A(1),\dots,A(11)=2,4,8,16,24,30,32,32,32,34,36,$$
因此
$$\sum_{k=1}^{11}A(k)=250,$$
从而
$$F_5(11)=(2^{12}-2)-250=4094-250=3844.$$
如果再向前推进一个完整的六项块，到 \(n=17\)，规避累计和会再增加 \(200\)，于是
$$F_5(17)=2^{18}-(200+252)=261692.$$
这个例子很直观地说明了：一旦进入稳定区间，大 \(n\) 的行为完全可以用 \((t,u)\) 这对参数来描述。
C++、Python 和 Java 实现都先做一个基于“最后至多五位”的有限状态 DP。这个 DP 负责求出短长度的精确值，包括检查点 \(F_5(5)=8\)、\(F_5(6)=42\)、\(F_5(11)=3844\)，同时也验证闭式所依赖的六项周期规律。
接着，对每个 \(u\in\{0,1,2,3,4,5\}\) 以及每个模因子 \(m\in\{9,1997,4877\}\)，实现都会扫描一个局部周期 \(P_m\)，记录所有满足
$$2^{10+u}64^t \equiv 200t+C_u \pmod m$$
的残基 \(t\)。随后把三组局部残基通过 CRT 合并成排好序的全局残基列表。面对给定上界 \(L\) 时，代码先直接处理 \(n=5,6,7,8\)，再对每个 \(u\) 计算有多少个
$$t\le \left\lfloor\frac{L-(9+u)}{6}\right\rfloor$$
落入这些全局残基类。因为列表已排序，所以最后一步就是“完整周期的数量 + 用二分统计尾段”。
设 \(R_{m,u}\) 表示在类别 \(u\) 下、模因子 \(m\) 的有效残基个数。局部枚举的时间代价为
$$O\left(\sum_{u=0}^{5}\left(P_9+P_{1997}+P_{4877}\right)\right),$$
这是一次性的预处理，与 \(L\) 无关。CRT 合并阶段依赖的是残基集合大小，而不是巨大的全局周期 \(P\)。预处理完成后，计算 \(D(L)\) 只需要六次上界换算以及在有序数组中的计数，因此对 \(L\) 的依赖实际上是带很小对数因子的 \(O(1)\)。空间复杂度与保存下来的总残基类数量成正比。
Для каждого \(n\) обозначим через \(A(n)\) число двоичных строк длины \(n\), которые не содержат ни одного палиндромного подслова длины не меньше \(5\). Тогда число строк длины \(n\), которые содержат такой палиндром, равно \(2^n-A(n)\), а накопленная функция имеет вид
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right).$$
Нужно вычислить
$$D(L)=\#\left\{n\in\mathbb{Z}:5\le n\le L,\ F_5(n)\equiv 0 \pmod{87654321}\right\}.$$
При \(L=10^{18}\) перебор всех \(n\) невозможен. Поэтому реализации переводят задачу в периодическую модульную задачу по одной вспомогательной переменной.
Сначала нужно посчитать строки фиксированной длины, избегающие палиндромов, затем свернуть эти значения в замкнутую формулу для \(F_5(n)\), а после этого решить периодическое сравнение по модулю.
Двоичная строка содержит палиндром длины не меньше \(5\) тогда и только тогда, когда она содержит палиндром длины ровно \(5\) или ровно \(6\).
Любой нечетный палиндром длины хотя бы \(5\) содержит свой центральный палиндром длины \(5\), а любой четный палиндром длины хотя бы \(6\) содержит центральный палиндром длины \(6\). Значит, задача избегания полностью сводится к запрету только этих двух локальных конфигураций.
Пусть \(A(n)\) обозначает число допустимых строк длины \(n\). При дописывании нового бита \(x\) новый запрещенный палиндром может появиться только среди суффиксов, оканчивающихся в этой новой позиции, поэтому достаточно помнить последние пять битов.
Если текущий суффикс равен \(b_1b_2b_3b_4b_5\), то после добавления \(x\) запрещенный палиндром длины \(5\) возникает тогда и только тогда, когда
$$b_2=x \land b_3=b_5,$$
а палиндром длины \(6\) возникает тогда и только тогда, когда
$$b_1=x \land b_2=b_5 \land b_3=b_4.$$
Следовательно, начиная с длины \(5\), задача сводится к DP по не более чем \(32\) состояниям суффикса. Первые точные значения таковы:
$$A(5)=24,\quad A(6)=30,\quad A(7)=32,\quad A(8)=32,$$
а начиная с \(n=9\) появляется устойчивый период длины \(6\):
$$A(9+6t+u)=a_u,\qquad (a_0,a_1,a_2,a_3,a_4,a_5)=(32,34,36,34,32,32).$$
Поэтому один полный шестишаговый блок дает вклад
$$a_0+a_1+a_2+a_3+a_4+a_5=200.$$
Всего двоичных строк длины \(n\) ровно \(2^n\), значит строк с нужным палиндромом имеется \(2^n-A(n)\). Суммирование по всем длинам дает
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right)=(2^{n+1}-2)-\sum_{k=1}^{n}A(k).$$
Запишем
$$n=9+6t+u,\qquad u\in\{0,1,2,3,4,5\}.$$
Так как \(A(n)\) периодична, ее накопленная сумма линейна по \(t\):
$$\sum_{k=1}^{9+6t+u}A(k)=200t+(C_u-2),$$
где
$$\left(C_0,C_1,C_2,C_3,C_4,C_5\right)=\left(182,216,252,286,318,350\right).$$
После подстановки получается замкнутая формула, на которую опираются все три реализации:
$$F_5(9+6t+u)=2^{10+u}64^t-(200t+C_u).$$
Целевое условие имеет вид \(F_5(n)\equiv 0 \pmod{87654321}\). Для фиксированного \(u\) оно становится сравнением
$$2^{10+u}64^t \equiv 200t+C_u \pmod{87654321}.$$
Модуль раскладывается так:
$$87654321=9\cdot 1997\cdot 4877.$$
Поэтому реализации сначала решают задачу отдельно по модулям \(9\), \(1997\) и \(4877\). Для одного модуля \(m\) экспоненциальный множитель \(64^t\) имеет период \(\operatorname{ord}_m(64)\), а линейный член \(200t+C_u\) имеет период \(m\). Значит локальный период равен
$$P_m=\operatorname{lcm}\left(m,\operatorname{ord}_m(64)\right).$$
В нашей задаче получается
$$P_9=9,\qquad P_{1997}=1993006,\qquad P_{4877}=11890126.$$
Для каждого фиксированного \(u\) реализация перебирает один полный локальный период для каждого множителя модуля и сохраняет все остатки \(t\), удовлетворяющие сравнению по этому множителю.
Два сравнения
$$x\equiv a \pmod{m_1},\qquad x\equiv b \pmod{m_2}$$
совместимы тогда и только тогда, когда
$$a\equiv b \pmod{\gcd(m_1,m_2)}.$$
Совместимые остатки шаг за шагом объединяются в глобальные классы по модулю
$$P=\operatorname{lcm}(P_9,P_{1997},P_{4877}).$$
Ключевой момент состоит в том, что код никогда не перебирает все \(P\) значений \(t\). Он просматривает только три гораздо меньших локальных периода, а затем конструктивно склеивает подходящие классы при помощи CRT.
Возьмем \(n=11\). Тогда \(n=9+6\cdot 0+2\), значит \(t=0\) и \(u=2\). Замкнутая формула дает
$$F_5(11)=2^{12}-252=3844.$$
Это полностью согласуется с точными значениями избегания. До длины \(11\) числа допустимых строк равны
$$A(1),\dots,A(11)=2,4,8,16,24,30,32,32,32,34,36,$$
следовательно
$$\sum_{k=1}^{11}A(k)=250,$$
и потому
$$F_5(11)=(2^{12}-2)-250=4094-250=3844.$$
Если перейти на один полный шестишаговый блок вперед, к \(n=17\), сумма избегания вырастет еще на \(200\), и получится
$$F_5(17)=2^{18}-(200+252)=261692.$$
Этот пример показывает, почему большие значения \(n\) естественно описываются парой \((t,u)\).
Реализации на C++, Python и Java начинают с небольшой конечной DP по последним максимум пяти битам. Она дает точные малые значения, включая контрольные точки \(F_5(5)=8\), \(F_5(6)=42\) и \(F_5(11)=3844\), а также подтверждает шестичленный цикл, лежащий в основе замкнутой формулы.
Далее для каждого \(u\in\{0,1,2,3,4,5\}\) и каждого множителя \(m\in\{9,1997,4877\}\) реализация проходит один локальный период \(P_m\) и сохраняет остатки, удовлетворяющие
$$2^{10+u}64^t \equiv 200t+C_u \pmod m.$$
Эти локальные множества объединяются CRT в отсортированные глобальные списки остатков. Для заданного предела \(L\) код отдельно обрабатывает \(n=5,6,7,8\), а затем для каждого \(u\) считает, сколько значений
$$t\le \left\lfloor\frac{L-(9+u)}{6}\right\rfloor$$
попадает в сохраненные глобальные классы. Благодаря сортировке финальный подсчет сводится к числу полных периодов плюс хвост, найденный бинарным поиском.
Пусть \(R_{m,u}\) обозначает число допустимых остатков для множителя \(m\) в классе \(u\). Локальные переборы требуют
$$O\left(\sum_{u=0}^{5}\left(P_9+P_{1997}+P_{4877}\right)\right)$$
времени; это единственная предварительная обработка, не зависящая от \(L\). Фаза CRT зависит от размеров наборов остатков, а не от огромного глобального периода \(P\). После предвычисления вычисление \(D(L)\) требует только шести преобразований границы и подсчетов в отсортированных массивах, поэтому зависимость от \(L\) фактически равна \(O(1)\) с малыми логарифмическими множителями из-за бинарного поиска. Память пропорциональна общему числу сохраненных классов остатков.
لكل \(n\)، لنعرّف \(A(n)\) بأنه عدد السلاسل الثنائية ذات الطول \(n\) التي لا تحتوي أي مقطع متناظر طوله على الأقل \(5\). عندئذ يكون عدد السلاسل ذات الطول \(n\) التي تحتوي مثل هذا المقطع هو \(2^n-A(n)\)، والدالة التراكمية هي
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right).$$
والمطلوب هو حساب
$$D(L)=\#\left\{n\in\mathbb{Z}:5\le n\le L,\ F_5(n)\equiv 0 \pmod{87654321}\right\}.$$
عندما يكون \(L=10^{18}\) يصبح الفحص المباشر مستحيلاً عمليًا. لذلك تحوّل التطبيقات المسألة إلى توافق دوري في متغيّر مساعد واحد بدلًا من المرور على كل قيمة ممكنة لـ \(n\).
الفكرة تسير على ثلاث مراحل: عدّ السلاسل التي تتجنب المقاطع المتناظرة لطول ثابت، ثم ضغط هذه الأعداد في صيغة مغلقة لـ \(F_5(n)\)، ثم حل شرط القسمة عبر دورية توافقية.
تحتوي السلسلة الثنائية مقطعًا متناظرًا بطول لا يقل عن \(5\) إذا وفقط إذا احتوت مقطعًا متناظرًا بطول \(5\) تمامًا أو بطول \(6\) تمامًا.
فكل متناظر فردي بطول لا يقل عن \(5\) يحتوي في مركزه متناظرًا بطول \(5\)، وكل متناظر زوجي بطول لا يقل عن \(6\) يحتوي في مركزه متناظرًا بطول \(6\). لذلك يكفي في مسألة التجنّب أن نمنع هذين النمطين المحليين فقط.
ليكن \(A(n)\) عدد السلاسل الصحيحة ذات الطول \(n\). عند إلحاق بت جديد \(x\)، فإن المقطع الممنوع الجديد لا يمكن أن يظهر إلا داخل اللواحق التي تنتهي عند هذا الموضع الجديد، ولهذا يكفي أن نتذكر آخر خمسة بتات.
إذا كان اللاحق السابق هو \(b_1b_2b_3b_4b_5\)، فإن إضافة \(x\) تولّد متناظرًا ممنوعًا بطول \(5\) بالضبط عندما
$$b_2=x \land b_3=b_5,$$
وتولّد متناظرًا ممنوعًا بطول \(6\) بالضبط عندما
$$b_1=x \land b_2=b_5 \land b_3=b_4.$$
إذن بعد الوصول إلى الطول \(5\)، تصبح المسألة برمجة ديناميكية على ما لا يزيد على \(32\) حالة لاحقة. القيم الأولى هي
$$A(5)=24,\quad A(6)=30,\quad A(7)=32,\quad A(8)=32,$$
ومن \(n=9\) فصاعدًا تدخل المجاميع في دورة مستقرة طولها \(6\):
$$A(9+6t+u)=a_u,\qquad (a_0,a_1,a_2,a_3,a_4,a_5)=(32,34,36,34,32,32).$$
وبالتالي فإن كل كتلة كاملة من ست خطوات تساهم بمقدار
$$a_0+a_1+a_2+a_3+a_4+a_5=200.$$
عدد السلاسل الثنائية ذات الطول \(n\) هو \(2^n\)، ولذلك فإن عدد السلاسل التي تحتوي متناظرًا مطلوبًا يساوي \(2^n-A(n)\). وبجمع ذلك على جميع الأطوال نحصل على
$$F_5(n)=\sum_{k=1}^{n}\left(2^k-A(k)\right)=(2^{n+1}-2)-\sum_{k=1}^{n}A(k).$$
اكتب
$$n=9+6t+u,\qquad u\in\{0,1,2,3,4,5\}.$$
بسبب دورية \(A(n)\)، يصبح المجموع التراكمي للسلاسل المتجنبة خطيًا في \(t\):
$$\sum_{k=1}^{9+6t+u}A(k)=200t+(C_u-2),$$
حيث الثوابت المستعملة في التطبيقات هي
$$\left(C_0,C_1,C_2,C_3,C_4,C_5\right)=\left(182,216,252,286,318,350\right).$$
وبالتعويض نحصل على الصيغة المغلقة التي تعتمدها تطبيقات C++ وPython وJava:
$$F_5(9+6t+u)=2^{10+u}64^t-(200t+C_u).$$
الشرط المطلوب هو \(F_5(n)\equiv 0 \pmod{87654321}\). وعند تثبيت \(u\) يصبح
$$2^{10+u}64^t \equiv 200t+C_u \pmod{87654321}.$$
ويتفكك المعيار إلى
$$87654321=9\cdot 1997\cdot 4877.$$
ولهذا تحل التطبيقات التوافق أولًا بترديد \(9\) و\(1997\) و\(4877\) كل على حدة. بالنسبة إلى معيار واحد \(m\)، فإن الحد الأسي \(64^t\) له دورية \(\operatorname{ord}_m(64)\)، بينما الحد الخطي \(200t+C_u\) له دورية \(m\). إذن الدورية المحلية هي
$$P_m=\operatorname{lcm}\left(m,\operatorname{ord}_m(64)\right).$$
وفي هذه المسألة تكون
$$P_9=9,\qquad P_{1997}=1993006,\qquad P_{4877}=11890126.$$
لكل قيمة ثابتة من \(u\)، تقوم التطبيقات بحصر جميع قيم \(t\) داخل دورة محلية كاملة لكل عامل من عوامل المعيار، ثم تحفظ فئات البواقي التي تحقق التوافق بالنسبة إلى ذلك العامل.
التوافقان
$$x\equiv a \pmod{m_1},\qquad x\equiv b \pmod{m_2}$$
يكونان منسجمين إذا وفقط إذا
$$a\equiv b \pmod{\gcd(m_1,m_2)}.$$
ثم تُدمج البواقي المتوافقة خطوةً بعد خطوة إلى بواقي عالمية بترديد
$$P=\operatorname{lcm}(P_9,P_{1997},P_{4877}).$$
والنقطة الحاسمة هنا أن الشيفرة لا تستعرض جميع القيم الممكنة لـ \(t\) ضمن هذا الدور الهائل. بل تستعرض فقط الدورات المحلية الثلاث الأصغر بكثير، ثم تبني البواقي العالمية المتوافقة باستخدام CRT بصورة مباشرة.
لنأخذ \(n=11\). عندئذ \(n=9+6\cdot 0+2\)، أي \(t=0\) و\(u=2\). تعطي الصيغة المغلقة
$$F_5(11)=2^{12}-252=3844.$$
وهذا يطابق تمامًا العدّ الدقيق للسلاسل المتجنبة. حتى الطول \(11\) تكون الأعداد
$$A(1),\dots,A(11)=2,4,8,16,24,30,32,32,32,34,36,$$
ولذلك
$$\sum_{k=1}^{11}A(k)=250,$$
ومن ثم
$$F_5(11)=(2^{12}-2)-250=4094-250=3844.$$
إذا انتقلنا بعد ذلك كتلة كاملة من ست خطوات إلى \(n=17\)، فإن مجموع السلاسل المتجنبة يزيد بمقدار \(200\) إضافية، فنحصل على
$$F_5(17)=2^{18}-(200+252)=261692.$$
وهذا المثال يوضح بدقة لماذا تصبح القيم الكبيرة لـ \(n\) موصوفة طبيعيًا بالزوج \((t,u)\).
تبدأ تطبيقات C++ وPython وJava ببرمجة ديناميكية صغيرة ذات حالات منتهية تعتمد على آخر ما يصل إلى خمسة بتات. هذه المرحلة تنتج القيم الدقيقة للأطوال الصغيرة، بما فيها نقاط الفحص \(F_5(5)=8\) و\(F_5(6)=42\) و\(F_5(11)=3844\)، كما تؤكد أيضًا الدورة السداسية التي تقوم عليها الصيغة المغلقة.
بعد ذلك، لكل \(u\in\{0,1,2,3,4,5\}\) ولكل عامل معياري \(m\in\{9,1997,4877\}\)، تمسح التطبيقات دورة محلية واحدة \(P_m\) وتسجل جميع البواقي التي تحقق
$$2^{10+u}64^t \equiv 200t+C_u \pmod m.$$
ثم تُدمج هذه المجموعات المحلية بوساطة CRT في قوائم عالمية مرتبة. ولأجل حد أعلى \(L\)، تعالج الشيفرة الحالات \(n=5,6,7,8\) مباشرة، ثم تحسب لكل \(u\) عدد القيم
$$t\le \left\lfloor\frac{L-(9+u)}{6}\right\rfloor$$
الواقعة داخل فئات البواقي العالمية المخزنة. ومع وجود القوائم المرتبة، يصبح العد النهائي عبارة عن عدد الدورات الكاملة زائد ذيل يُحسب ببحث ثنائي.
إذا رمزنا بـ \(R_{m,u}\) إلى عدد البواقي الصحيحة للعامل \(m\) ضمن الفئة \(u\)، فإن المسح المحلي يكلف
$$O\left(\sum_{u=0}^{5}\left(P_9+P_{1997}+P_{4877}\right)\right),$$
وهو تحضير واحد لا يعتمد على \(L\). أما مرحلة CRT فتعتمد على أحجام مجموعات البواقي لا على الدورية العالمية الضخمة \(P\). وبعد اكتمال التحضير، فإن حساب \(D(L)\) يحتاج فقط إلى ست تحويلات للحد وإلى عدّ داخل مصفوفات مرتبة، ولذلك تصبح التبعية بالنسبة إلى \(L\) عمليًا \(O(1)\) مع عوامل لوغاريتمية صغيرة بسبب البحث الثنائي. الذاكرة المستخدمة تتناسب مع العدد الكلي لفئات البواقي المخزنة.