The task is to count decimal palindromes of length at most \(32\) that are divisible by \(10{,}000{,}019\). More generally, the implementation solves the same counting problem for any modulus \(M\) and any maximum length \(n\), then evaluates it at \(M=10{,}000{,}019\) and \(n=32\).
If \(A_{\ell}(M)\) denotes the number of length-\(\ell\) palindromes divisible by \(M\), the required quantity is
$$\sum_{\ell=1}^{32} A_{\ell}(10{,}000{,}019).$$
A direct enumeration is still enormous, because even after using palindrome symmetry there are \(9\cdot 10^{15}\) possible 32-digit half-assignments. The solution therefore rewrites each palindrome as a modular linear form in its independent digits and counts matching residues with a meet-in-the-middle split.
Fix a length \(\ell\) and a modulus \(M\). Let
$$h=\left\lceil\frac{\ell}{2}\right\rceil.$$
A palindrome of length \(\ell\) is determined by exactly \(h\) independent digits, so the question becomes: how many assignments of those digits make the resulting number congruent to \(0\pmod M\)?
Number decimal positions from the right, starting at \(0\). For each \(0\le i<h\), let \(d_i\) be the digit placed simultaneously at positions \(i\) and \(\ell-1-i\). If \(\ell\) is odd and \(i=\ell-1-i\), that digit is the center and contributes only once.
Because the highest place \(\ell-1\) belongs to the pair indexed by \(i=0\), the digit \(d_0\) is the leading digit, so
$$d_0\in\{1,\dots,9\},\qquad d_1,\dots,d_{h-1}\in\{0,\dots,9\}.$$
The palindrome value modulo \(M\) is therefore
$$P_{\ell}(d_0,\dots,d_{h-1})\equiv \sum_{i=0}^{h-1} d_i W_i \pmod M,$$
with mirrored weights
$$W_i=\begin{cases} 10^i+10^{\ell-1-i}\pmod M, & i\ne \ell-1-i,\\ 10^i\pmod M, & i=\ell-1-i. \end{cases}$$
So divisibility becomes one linear congruence in the independent digits.
Choose
$$s=\left\lceil\frac{h}{2}\right\rceil.$$
The left block contains \(d_0,\dots,d_{s-1}\), and the right block contains \(d_s,\dots,d_{h-1}\). Define
$$L=\sum_{i=0}^{s-1} d_i W_i \pmod M,\qquad R=\sum_{i=s}^{h-1} d_i W_i \pmod M.$$
Then
$$P_{\ell}\equiv L+R\pmod M,$$
so a palindrome is divisible by \(M\) exactly when
$$L+R\equiv 0\pmod M.$$
This turns the problem into matching left residues against complementary right residues.
The leading-digit restriction affects only \(d_0\). It is therefore natural to separate the leading digit from the remaining \(s-1\) digits in the left block. For each fixed \(a\in\{1,\dots,9\}\), the other left digits vary freely in \(\{0,\dots,9\}^{s-1}\).
If we define
$$C_{\ell}(r)=\#\{(d_0,\dots,d_{s-1}) : L\equiv r\pmod M\},$$
then \(C_{\ell}(r)\) records how many left-half assignments produce residue \(r\). Once this frequency table has been built for the current length, it can be reused for every right-half assignment.
Now enumerate all assignments of the right block. Each one gives some residue \(R\). The divisibility condition requires
$$L\equiv -R\pmod M.$$
Hence the number of full palindromes extending that right block is exactly
$$C_{\ell}((-R)\bmod M).$$
Summing this quantity over all right-half assignments yields \(A_{\ell}(M)\). Finally, summing \(A_{\ell}(M)\) over \(\ell=1,\dots,32\) gives the answer required by the problem.
Without the split, a length-\(\ell\) palindrome requires checking \(9\cdot 10^{h-1}\) independent digit assignments. With the balanced split above, the left side contributes \(9\cdot 10^{s-1}\) assignments and the right side contributes \(10^{h-s}\) assignments.
For the longest case \(\ell=32\), we have \(h=16\) and \(s=8\), so the method works with roughly \(9\cdot 10^7\) left assignments and \(10^8\) right assignments instead of \(9\cdot 10^{15}\) full half-assignments. That reduction is the reason the computation becomes feasible.
For length \(5\), we have \(h=3\) and \(s=2\). The mirrored weights are
$$W_0=10^0+10^4\equiv 1+81\equiv 82\pmod{109},$$
$$W_1=10^1+10^3\equiv 10+19\equiv 29\pmod{109},$$
$$W_2=10^2\equiv 100\pmod{109}.$$
So every 5-digit palindrome has residue
$$P_5(a,b,c)\equiv 82a+29b+100c\pmod{109},$$
with \(a\in\{1,\dots,9\}\) and \(b,c\in\{0,\dots,9\}\). The left table counts residues of \(82a+29b\), while the right side enumerates residues of \(100c\).
Since \(100\equiv -9\pmod{109}\), the left-table queries are the complementary residues \(0,9,18,\dots,81\) as \(c\) runs from \(0\) to \(9\). This illustrates the whole strategy in miniature. The implementations also include the checkpoint that the cumulative count for lengths \(1\) through \(5\) at modulus \(109\) is \(9\).
The implementation first precomputes the powers \(10^i\bmod M\) up to the largest decimal position needed. For each length \(\ell\), it constructs the mirrored weights \(W_i\), chooses the balanced split \(s=\lceil h/2\rceil\), and prepares a frequency table for left-block residues.
To build that table efficiently, it enumerates the non-leading part of the left block once, records those residues, and then combines them with each possible leading digit \(1\) through \(9\). After that, it enumerates all right-block assignments and adds the frequency of the complementary left residue required for divisibility.
Two implementation details matter for speed. First, the digit blocks are traversed in base-10 counter order while maintaining the current residue incrementally, so moving to the next assignment updates only the digits that changed. Second, after one length is finished, only residue classes that actually received counts are cleared; the whole size-\(M\) table is never reset blindly.
The C++, Python, and Java implementations follow the same mathematics. The Python entry point delegates the heavy arithmetic to compiled code, while the Java version reproduces the same residue-counting procedure directly.
For one length \(\ell\), let \(h=\lceil \ell/2\rceil\) and \(s=\lceil h/2\rceil\). Building the mirrored weights costs \(O(h)\). The left-side preparation touches \(10^{s-1}\) assignments for the non-leading digits and then combines them with \(9\) possible leading digits, while the right side touches \(10^{h-s}\) assignments.
The dominant work per length is therefore
$$O\left(10^{s-1}+9\cdot 10^{s-1}+10^{h-s}\right)=O\left(10^{s}+10^{h-s}\right).$$
With the balanced split, this is essentially \(O(10^{\lceil h/2\rceil})\). Memory usage is
$$O\left(M+10^{s-1}\right),$$
coming from the residue-frequency table indexed by modulo classes and from the stored residues of the non-leading part of the left block. Across all lengths up to \(32\), the longest lengths dominate the total running time.
Gesucht ist die Anzahl der dezimalen Palindrome mit Länge höchstens \(32\), die durch \(10{,}000{,}019\) teilbar sind. Allgemeiner lösen die Implementierungen dasselbe Zählproblem für einen beliebigen Modulus \(M\) und eine beliebige Maximallänge \(n\) und setzen anschließend \(M=10{,}000{,}019\) und \(n=32\) ein.
Bezeichnet \(A_{\ell}(M)\) die Anzahl der \(\ell\)-stelligen Palindrome, die durch \(M\) teilbar sind, so ist die gesuchte Größe
$$\sum_{\ell=1}^{32} A_{\ell}(10{,}000{,}019).$$
Selbst unter Ausnutzung der Palindrom-Symmetrie wäre eine vollständige Enumeration riesig, denn bei 32 Stellen gibt es noch immer \(9\cdot 10^{15}\) mögliche Halbbelegungen. Deshalb wird jedes Palindrom als lineare Kongruenz in seinen unabhängigen Ziffern beschrieben und dann per Meet-in-the-middle gezählt.
Fixiere eine Länge \(\ell\) und einen Modulus \(M\). Setze
$$h=\left\lceil\frac{\ell}{2}\right\rceil.$$
Ein \(\ell\)-stelliges Palindrom wird vollständig durch genau \(h\) unabhängige Ziffern bestimmt. Also müssen wir nur noch zählen, wie viele Belegungen dieser Ziffern den Rest \(0\pmod M\) erzeugen.
Nummeriere die Dezimalpositionen von rechts beginnend mit \(0\). Für \(0\le i<h\) sei \(d_i\) die Ziffer, die gleichzeitig an den Positionen \(i\) und \(\ell-1-i\) steht. Bei ungerader Länge und \(i=\ell-1-i\) ist dies die mittlere Ziffer und sie erscheint nur einmal.
Da die höchste Stelle \(\ell-1\) zum Paar mit Index \(0\) gehört, ist \(d_0\) die führende Ziffer. Daher gilt
$$d_0\in\{1,\dots,9\},\qquad d_1,\dots,d_{h-1}\in\{0,\dots,9\}.$$
Der Palindromwert modulo \(M\) ist dann
$$P_{\ell}(d_0,\dots,d_{h-1})\equiv \sum_{i=0}^{h-1} d_i W_i \pmod M,$$
wobei die symmetrischen Gewichte
$$W_i=\begin{cases} 10^i+10^{\ell-1-i}\pmod M, & i\ne \ell-1-i,\\ 10^i\pmod M, & i=\ell-1-i \end{cases}$$
sind. Teilbarkeit ist also genau eine lineare Kongruenz in den unabhängigen Ziffern.
Wähle
$$s=\left\lceil\frac{h}{2}\right\rceil.$$
Der linke Block enthält \(d_0,\dots,d_{s-1}\), der rechte Block enthält \(d_s,\dots,d_{h-1}\). Definiere
$$L=\sum_{i=0}^{s-1} d_i W_i \pmod M,\qquad R=\sum_{i=s}^{h-1} d_i W_i \pmod M.$$
Dann gilt
$$P_{\ell}\equiv L+R\pmod M,$$
und ein Palindrom ist genau dann durch \(M\) teilbar, wenn
$$L+R\equiv 0\pmod M.$$
Damit reduziert sich das Problem auf das Zusammenführen komplementärer linker und rechter Reste.
Die Bedingung für die führende Ziffer betrifft nur \(d_0\). Deshalb trennt man \(d_0\) zweckmäßig von den übrigen \(s-1\) Ziffern des linken Blocks. Für jedes feste \(a\in\{1,\dots,9\}\) laufen die restlichen linken Ziffern frei durch \(\{0,\dots,9\}^{s-1}\).
Mit
$$C_{\ell}(r)=\#\{(d_0,\dots,d_{s-1}) : L\equiv r\pmod M\}$$
bezeichnen wir die Anzahl der linken Belegungen mit Rest \(r\). Ist diese Häufigkeitstabelle für die aktuelle Länge einmal aufgebaut, kann sie für alle rechten Belegungen wiederverwendet werden.
Nun werden alle Belegungen des rechten Blocks enumeriert. Jede davon liefert einen Rest \(R\). Für Teilbarkeit muss gelten
$$L\equiv -R\pmod M.$$
Also ist die Anzahl vollständiger Palindrome, die zu diesem rechten Block passen, genau
$$C_{\ell}((-R)\bmod M).$$
Die Summe über alle rechten Belegungen ergibt \(A_{\ell}(M)\). Danach wird über alle Längen \(\ell=1,\dots,32\) summiert.
Ohne Aufteilung müsste man für Länge \(\ell\) insgesamt \(9\cdot 10^{h-1}\) unabhängige Ziffernbelegungen betrachten. Mit der balancierten Wahl oben erhält man nur \(9\cdot 10^{s-1}\) linke Fälle und \(10^{h-s}\) rechte Fälle.
Im längsten Fall \(\ell=32\) gilt \(h=16\) und \(s=8\). Dann arbeitet das Verfahren mit ungefähr \(9\cdot 10^7\) linken und \(10^8\) rechten Zuständen statt mit \(9\cdot 10^{15}\) vollständigen Halbbelegungen. Genau diese Reduktion macht die Rechnung praktikabel.
Für Länge \(5\) gilt \(h=3\) und \(s=2\). Die gespiegelten Gewichte sind
$$W_0=10^0+10^4\equiv 1+81\equiv 82\pmod{109},$$
$$W_1=10^1+10^3\equiv 10+19\equiv 29\pmod{109},$$
$$W_2=10^2\equiv 100\pmod{109}.$$
Damit hat jedes 5-stellige Palindrom den Rest
$$P_5(a,b,c)\equiv 82a+29b+100c\pmod{109},$$
wobei \(a\in\{1,\dots,9\}\) und \(b,c\in\{0,\dots,9\}\) sind. Die linke Tabelle zählt also Reste von \(82a+29b\), während rechts die Werte \(100c\) durchlaufen werden.
Da \(100\equiv -9\pmod{109}\) ist, werden in der linken Tabelle genau die komplementären Reste \(0,9,18,\dots,81\) abgefragt, wenn \(c\) von \(0\) bis \(9\) läuft. Die Implementierungen verwenden außerdem die Kontrolle, dass der kumulierte Wert für die Längen \(1\) bis \(5\) bei Modulus \(109\) gleich \(9\) ist.
Die Implementierung berechnet zunächst alle Potenzen \(10^i\bmod M\) bis zur größten benötigten Dezimalposition vor. Für jede Länge \(\ell\) werden daraus die gespiegelten Gewichte \(W_i\) aufgebaut und die balancierte Aufteilung \(s=\lceil h/2\rceil\) gewählt.
Danach wird der nichtführende Teil des linken Blocks einmal durchlaufen und seine Restklassen werden gespeichert. Diese Werte werden anschließend mit jeder möglichen führenden Ziffer \(1\) bis \(9\) kombiniert, um die Häufigkeitstabelle der linken Reste zu füllen. Anschließend wird der rechte Block enumeriert und zu jedem rechten Rest die Anzahl der passenden komplementären linken Reste addiert.
Zwei Details sorgen für die Geschwindigkeit. Erstens werden die Ziffernblöcke in Basis-10-Zählerreihenfolge durchlaufen, während der aktuelle Rest inkrementell fortgeschrieben wird; beim Übergang zum nächsten Zustand müssen also nur die geänderten Ziffern berücksichtigt werden. Zweitens werden nach jeder Länge nur die tatsächlich benutzten Restklassen zurückgesetzt, nicht die gesamte Tabelle der Größe \(M\).
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Mathematik. Der Python-Einstieg delegiert die rechenintensive Arbeit an kompilierten Code, während die Java-Version das gleiche Restzählverfahren direkt nachbildet.
Für eine feste Länge \(\ell\) seien \(h=\lceil \ell/2\rceil\) und \(s=\lceil h/2\rceil\). Das Erzeugen der Gewichte kostet \(O(h)\). Auf der linken Seite werden \(10^{s-1}\) Zustände des nichtführenden Teils erzeugt und mit \(9\) möglichen führenden Ziffern kombiniert; auf der rechten Seite werden \(10^{h-s}\) Zustände betrachtet.
Der dominierende Aufwand pro Länge ist daher
$$O\left(10^{s-1}+9\cdot 10^{s-1}+10^{h-s}\right)=O\left(10^s+10^{h-s}\right).$$
Mit der balancierten Aufteilung ist dies im Wesentlichen \(O(10^{\lceil h/2\rceil})\). Der Speicherbedarf beträgt
$$O\left(M+10^{s-1}\right),$$
weil eine Häufigkeitstabelle über die Restklassen modulo \(M\) sowie die Restliste des nichtführenden linken Teilblocks gespeichert werden. Über alle Längen bis \(32\) dominieren die längsten Fälle die Laufzeit.
Aranan şey, uzunluğu en fazla \(32\) olan ve \(10{,}000{,}019\) ile tam bölünen onluk tabandaki palindrom sayıların sayısıdır. Daha genel olarak uygulama, herhangi bir \(M\) modu ve herhangi bir \(n\) üst uzunluğu için aynı sayımı yapar; ardından \(M=10{,}000{,}019\) ve \(n=32\) değerlerini yerine koyar.
\(A_{\ell}(M)\) ile \(M\)'ye bölünen \(\ell\) basamaklı palindromların sayısını gösterirsek istenen büyüklük
$$\sum_{\ell=1}^{32} A_{\ell}(10{,}000{,}019)$$
olur. Doğrudan tarama yine de astronomik boyuttadır; çünkü 32 basamaklı durumda palindrom simetrisini kullansak bile hâlâ \(9\cdot 10^{15}\) farklı yarı-atama vardır. Bu yüzden çözüm, sayıyı bağımsız basamakların modüler lineer birleşimi olarak yazar ve kalıntıları meet-in-the-middle ile eşleştirir.
Sabit bir \(\ell\) uzunluğu ve bir \(M\) modu alalım. Şunu tanımlayalım:
$$h=\left\lceil\frac{\ell}{2}\right\rceil.$$
\(\ell\) basamaklı bir palindrom, tam olarak \(h\) bağımsız basamakla belirlenir. Dolayısıyla soru, bu basamak atamalarından kaç tanesinin sayıyı \(0\pmod M\) kalıntısına götürdüğüdür.
Onluk basamak konumlarını sağdan başlayarak \(0\) ile numaralandıralım. \(0\le i<h\) için \(d_i\), hem \(i\) hem de \(\ell-1-i\) konumuna yerleşen basamak olsun. Eğer \(\ell\) tek ve \(i=\ell-1-i\) ise bu basamak merkez basamaktır ve yalnızca bir kez katkı verir.
En yüksek konum \(\ell-1\), \(i=0\) ile eşleştiği için \(d_0\) aynı zamanda baştaki basamaktır. Bu nedenle
$$d_0\in\{1,\dots,9\},\qquad d_1,\dots,d_{h-1}\in\{0,\dots,9\}.$$
Sayının \(M\)'ye göre kalıntısı
$$P_{\ell}(d_0,\dots,d_{h-1})\equiv \sum_{i=0}^{h-1} d_i W_i \pmod M$$
şeklinde yazılır. Burada simetrik ağırlıklar
$$W_i=\begin{cases} 10^i+10^{\ell-1-i}\pmod M, & i\ne \ell-1-i,\\ 10^i\pmod M, & i=\ell-1-i \end{cases}$$
olarak tanımlanır. Böylece bölünebilirlik koşulu bağımsız basamaklarda tek bir lineer kongruansa dönüşür.
Şunu seçelim:
$$s=\left\lceil\frac{h}{2}\right\rceil.$$
Sol blok \(d_0,\dots,d_{s-1}\), sağ blok ise \(d_s,\dots,d_{h-1}\) basamaklarını içersin. O zaman
$$L=\sum_{i=0}^{s-1} d_i W_i \pmod M,\qquad R=\sum_{i=s}^{h-1} d_i W_i \pmod M$$
diye yazabiliriz. Böylece
$$P_{\ell}\equiv L+R\pmod M$$
olur ve bir palindromun \(M\)'ye bölünmesi için tam olarak
$$L+R\equiv 0\pmod M$$
gereklidir. Problem artık, soldaki kalıntılar ile sağdaki tamamlayıcı kalıntıları eşleştirme problemidir.
Baş basamak kısıtı yalnızca \(d_0\)'ı etkiler. Bu yüzden \(d_0\)'ı, sol bloktaki diğer \(s-1\) basamaktan ayırmak doğaldır. Sabit bir \(a\in\{1,\dots,9\}\) için kalan sol basamaklar \(\{0,\dots,9\}^{s-1}\) kümesinde serbestçe dolaşır.
Şu frekans fonksiyonunu tanımlayalım:
$$C_{\ell}(r)=\#\{(d_0,\dots,d_{s-1}) : L\equiv r\pmod M\}.$$
Bu ifade, sol yarının kaç farklı atamayla \(r\) kalıntısını verdiğini söyler. O anki uzunluk için bu tablo bir kez kurulduktan sonra tüm sağ yarı atamalarında tekrar tekrar kullanılabilir.
Şimdi sağ bloktaki tüm atamaları dolaşalım. Her biri bir \(R\) kalıntısı üretir. Bölünebilirlik koşulu
$$L\equiv -R\pmod M$$
olduğuna göre, bu sağ blokla birleşebilecek tam palindrom sayısı tam olarak
$$C_{\ell}((-R)\bmod M)$$
kadardır. Bunu sağ bloktaki tüm atamalar üzerinde topladığımızda \(A_{\ell}(M)\) elde edilir; sonra \(\ell=1,\dots,32\) için bu değerler toplanır.
Bölme yapılmazsa \(\ell\) uzunluğu için \(9\cdot 10^{h-1}\) bağımsız basamak ataması vardır. Yukarıdaki dengeli seçimle sol taraf \(9\cdot 10^{s-1}\), sağ taraf ise \(10^{h-s}\) durum üretir.
En uzun durum olan \(\ell=32\) için \(h=16\) ve \(s=8\) olur. Böylece yöntem \(9\cdot 10^{15}\) tam yarı-atama yerine yaklaşık \(9\cdot 10^7\) sol ve \(10^8\) sağ durumla çalışır. Hesabı uygulanabilir yapan şey tam olarak bu düşüştür.
\(5\) basamak için \(h=3\) ve \(s=2\) elde edilir. Simetrik ağırlıklar
$$W_0=10^0+10^4\equiv 1+81\equiv 82\pmod{109},$$
$$W_1=10^1+10^3\equiv 10+19\equiv 29\pmod{109},$$
$$W_2=10^2\equiv 100\pmod{109}$$
şeklindedir. Dolayısıyla her 5 basamaklı palindrom
$$P_5(a,b,c)\equiv 82a+29b+100c\pmod{109}$$
biçimindedir; burada \(a\in\{1,\dots,9\}\), \(b,c\in\{0,\dots,9\}\). Sol tablo \(82a+29b\) kalıntılarını sayar, sağ taraf ise \(100c\) kalıntılarını dolaşır.
\(100\equiv -9\pmod{109}\) olduğundan, \(c\) değeri \(0\)'dan \(9\)'a giderken solda sorgulanan tamamlayıcı kalıntılar \(0,9,18,\dots,81\) olur. Bu küçük örnek yöntemin tamamını gösterir. Uygulamalarda ayrıca, \(109\) modu için \(1\) ile \(5\) arasındaki uzunlukların toplam sayısının \(9\) olduğu kontrolü bulunur.
Uygulama önce gereken en büyük konuma kadar \(10^i\bmod M\) değerlerini önceden hesaplar. Her uzunluk \(\ell\) için simetrik ağırlıklar \(W_i\) oluşturulur, sonra dengeli ayrım \(s=\lceil h/2\rceil\) seçilir ve sol blok kalıntıları için bir frekans tablosu hazırlanır.
Bu tabloyu verimli kurmak için önce sol bloğun baş basamak dışındaki kısmı tek başına dolaşılır ve ortaya çıkan kalıntılar saklanır. Ardından bu kalıntılar, olası her baş basamak \(1\) ile \(9\) arasındaki değerlerle birleştirilerek sol taraf frekans tablosu doldurulur. Sonra sağ bloktaki tüm atamalar gezilir ve her sağ kalıntı için gerekli tamamlayıcı sol kalıntının frekansı sonuca eklenir.
Hızı belirleyen iki uygulama ayrıntısı vardır. Birincisi, basamak blokları taban-10 sayaç sırasıyla dolaşılırken mevcut kalıntı artımlı olarak tutulur; böylece yeni bir duruma geçerken sadece değişen basamakların katkısı güncellenir. İkincisi, bir uzunluk bittikten sonra tüm boyutu \(M\) olan tabloyu baştan temizlemek yerine sadece gerçekten dokunulan kalıntı sınıfları sıfırlanır.
C++, Python ve Java uygulamaları aynı matematiği izler. Python giriş noktası ağır aritmetiği derlenmiş koda devreder; Java sürümü ise aynı kalıntı-sayım yordamını doğrudan tekrarlar.
Tek bir \(\ell\) uzunluğu için \(h=\lceil \ell/2\rceil\) ve \(s=\lceil h/2\rceil\) olsun. Simetrik ağırlıkları kurmanın maliyeti \(O(h)\)'dir. Sol tarafta baş basamak dışındaki kısım için \(10^{s-1}\) durum üretilir ve bunlar \(9\) olası baş basamakla birleştirilir; sağ tarafta ise \(10^{h-s}\) durum gezilir.
Dolayısıyla baskın çalışma miktarı
$$O\left(10^{s-1}+9\cdot 10^{s-1}+10^{h-s}\right)=O\left(10^s+10^{h-s}\right)$$
olur. Dengeli ayrım sayesinde bu özünde \(O(10^{\lceil h/2\rceil})\) mertebesindedir. Bellek kullanımı ise
$$O\left(M+10^{s-1}\right)$$
şeklindedir; bunun kaynağı, mod sınıfları için tutulan frekans tablosu ile sol bloğun baş basamak dışındaki kısmından elde edilen kalıntı listesidir. Toplam çalışma süresini en büyük uzunluklar belirler.
Hay que contar los palíndromos decimales de longitud como máximo \(32\) que son divisibles por \(10{,}000{,}019\). De manera más general, la implementación resuelve el mismo problema de conteo para cualquier módulo \(M\) y cualquier longitud máxima \(n\), y después evalúa el caso \(M=10{,}000{,}019\), \(n=32\).
Si \(A_{\ell}(M)\) representa la cantidad de palíndromos de longitud \(\ell\) divisibles por \(M\), la cantidad pedida es
$$\sum_{\ell=1}^{32} A_{\ell}(10{,}000{,}019).$$
Un barrido directo sigue siendo descomunal, porque incluso usando la simetría palindrómica todavía habría \(9\cdot 10^{15}\) medias configuraciones posibles para \(32\) cifras. Por eso la solución reescribe cada palíndromo como una combinación lineal modular de sus cifras independientes y luego cuenta residuos complementarios con un meet-in-the-middle.
Fijemos una longitud \(\ell\) y un módulo \(M\). Sea
$$h=\left\lceil\frac{\ell}{2}\right\rceil.$$
Un palíndromo de longitud \(\ell\) queda determinado por exactamente \(h\) cifras independientes. La pregunta pasa a ser cuántas asignaciones de esas cifras producen residuo \(0\pmod M\).
Numeramos las posiciones decimales desde la derecha, empezando en \(0\). Para \(0\le i<h\), sea \(d_i\) la cifra colocada a la vez en las posiciones \(i\) y \(\ell-1-i\). Si \(\ell\) es impar y \(i=\ell-1-i\), esa cifra es la central y aparece una sola vez.
Como la posición más alta \(\ell-1\) pertenece al par con índice \(0\), la cifra \(d_0\) es la cifra inicial, de modo que
$$d_0\in\{1,\dots,9\},\qquad d_1,\dots,d_{h-1}\in\{0,\dots,9\}.$$
El valor del palíndromo módulo \(M\) puede escribirse como
$$P_{\ell}(d_0,\dots,d_{h-1})\equiv \sum_{i=0}^{h-1} d_i W_i \pmod M,$$
donde los pesos simétricos son
$$W_i=\begin{cases} 10^i+10^{\ell-1-i}\pmod M, & i\ne \ell-1-i,\\ 10^i\pmod M, & i=\ell-1-i. \end{cases}$$
Así, la divisibilidad se convierte en una sola congruencia lineal sobre las cifras independientes.
Elegimos
$$s=\left\lceil\frac{h}{2}\right\rceil.$$
El bloque izquierdo contiene \(d_0,\dots,d_{s-1}\), y el derecho contiene \(d_s,\dots,d_{h-1}\). Definimos
$$L=\sum_{i=0}^{s-1} d_i W_i \pmod M,\qquad R=\sum_{i=s}^{h-1} d_i W_i \pmod M.$$
Entonces
$$P_{\ell}\equiv L+R\pmod M,$$
de modo que un palíndromo es divisible por \(M\) exactamente cuando
$$L+R\equiv 0\pmod M.$$
El problema queda reducido a hacer coincidir residuos izquierdos con residuos derechos complementarios.
La restricción de cifra inicial afecta únicamente a \(d_0\). Por eso conviene separar la cifra inicial de las otras \(s-1\) cifras del bloque izquierdo. Para cada \(a\in\{1,\dots,9\}\), las demás cifras izquierdas recorren libremente \(\{0,\dots,9\}^{s-1}\).
Si definimos
$$C_{\ell}(r)=\#\{(d_0,\dots,d_{s-1}) : L\equiv r\pmod M\},$$
entonces \(C_{\ell}(r)\) es el número de medias partes izquierdas que producen el residuo \(r\). Una vez construida esta tabla para la longitud actual, puede reutilizarse para todas las asignaciones del lado derecho.
Ahora enumeramos todas las asignaciones del bloque derecho. Cada una produce un residuo \(R\). La condición de divisibilidad exige
$$L\equiv -R\pmod M.$$
Por tanto, el número de palíndromos completos que extienden ese bloque derecho es exactamente
$$C_{\ell}((-R)\bmod M).$$
Al sumar esta cantidad sobre todas las asignaciones derechas obtenemos \(A_{\ell}(M)\). Finalmente se suma sobre \(\ell=1,\dots,32\).
Sin partición, un palíndromo de longitud \(\ell\) obliga a revisar \(9\cdot 10^{h-1}\) asignaciones independientes. Con la división equilibrada anterior, el lado izquierdo aporta \(9\cdot 10^{s-1}\) casos y el derecho aporta \(10^{h-s}\) casos.
En el caso más largo, \(\ell=32\), se tiene \(h=16\) y \(s=8\). Así, el método trabaja con aproximadamente \(9\cdot 10^7\) estados izquierdos y \(10^8\) estados derechos en lugar de \(9\cdot 10^{15}\) medias configuraciones completas. Esa diferencia es la clave de la viabilidad.
Para longitud \(5\), tenemos \(h=3\) y \(s=2\). Los pesos reflejados son
$$W_0=10^0+10^4\equiv 1+81\equiv 82\pmod{109},$$
$$W_1=10^1+10^3\equiv 10+19\equiv 29\pmod{109},$$
$$W_2=10^2\equiv 100\pmod{109}.$$
Todo palíndromo de 5 cifras satisface entonces
$$P_5(a,b,c)\equiv 82a+29b+100c\pmod{109},$$
con \(a\in\{1,\dots,9\}\) y \(b,c\in\{0,\dots,9\}\). La tabla izquierda cuenta residuos de \(82a+29b\), mientras que el lado derecho enumera residuos de \(100c\).
Como \(100\equiv -9\pmod{109}\), las búsquedas en la tabla izquierda son los residuos complementarios \(0,9,18,\dots,81\) cuando \(c\) recorre \(0,\dots,9\). Ese ejemplo pequeño muestra toda la idea. Las implementaciones también usan la comprobación de que el total acumulado para longitudes \(1\) a \(5\) con módulo \(109\) es \(9\).
La implementación precalcula primero las potencias \(10^i\bmod M\) hasta la mayor posición decimal necesaria. Para cada longitud \(\ell\), construye los pesos reflejados \(W_i\), fija la partición equilibrada \(s=\lceil h/2\rceil\) y prepara una tabla de frecuencias para los residuos del bloque izquierdo.
Para llenar esa tabla de forma eficiente, primero enumera la parte no inicial del bloque izquierdo y almacena sus residuos. Luego combina esos residuos con cada posible cifra inicial entre \(1\) y \(9\). Después enumera todas las asignaciones del bloque derecho y suma la frecuencia del residuo izquierdo complementario necesario para que el total sea divisible por \(M\).
Hay dos detalles decisivos para el rendimiento. Primero, los bloques de cifras se recorren en orden de contador en base 10 manteniendo el residuo actual de forma incremental, de modo que al pasar al siguiente estado solo se actualizan las cifras que cambiaron. Segundo, al terminar una longitud solo se limpian las clases residuales que realmente recibieron conteos; no se reinicia ciegamente toda la tabla de tamaño \(M\).
Las implementaciones en C++, Python y Java siguen exactamente la misma matemática. La entrada en Python delega el trabajo pesado a código compilado, mientras que la versión en Java reproduce directamente el mismo procedimiento de conteo de residuos.
Para una longitud fija \(\ell\), sean \(h=\lceil \ell/2\rceil\) y \(s=\lceil h/2\rceil\). Construir los pesos reflejados cuesta \(O(h)\). La preparación del lado izquierdo toca \(10^{s-1}\) estados para las cifras no iniciales y luego los combina con \(9\) posibles cifras iniciales, mientras que el lado derecho toca \(10^{h-s}\) estados.
Por tanto, el trabajo dominante por longitud es
$$O\left(10^{s-1}+9\cdot 10^{s-1}+10^{h-s}\right)=O\left(10^s+10^{h-s}\right).$$
Con la partición equilibrada esto equivale esencialmente a \(O(10^{\lceil h/2\rceil})\). La memoria utilizada es
$$O\left(M+10^{s-1}\right),$$
debido a la tabla de frecuencias indexada por clases residuales y al almacenamiento de los residuos de la parte no inicial del bloque izquierdo. Al sumar todas las longitudes hasta \(32\), las más largas dominan el tiempo total.
题目要求统计所有长度不超过 \(32\) 且能被 \(10{,}000{,}019\) 整除的十进制回文数。更一般地说，这个算法先解决“给定模数 \(M\) 和最大长度 \(n\)，有多少个长度不超过 \(n\) 的十进制回文数满足被 \(M\) 整除”这一问题，然后把 \(M=10{,}000{,}019\)、\(n=32\) 代入。
如果记 \(A_{\ell}(M)\) 为长度恰好为 \(\ell\) 的、可被 \(M\) 整除的回文数个数，那么题目要的就是
$$\sum_{\ell=1}^{32} A_{\ell}(10{,}000{,}019).$$
即使利用回文的对称性，暴力枚举依然远远不够快。因为 32 位回文虽然只由 16 个独立数字决定，但仍然有 \(9\cdot 10^{15}\) 种半边取法。真正可行的做法，是把回文数写成这些独立数字在模 \(M\) 下的线性组合，再把独立数字分成两半，用 meet-in-the-middle 统计能够互相补成 \(0\pmod M\) 的余数。
固定一个长度 \(\ell\) 和一个模数 \(M\)。令
$$h=\left\lceil\frac{\ell}{2}\right\rceil.$$
长度为 \(\ell\) 的回文数恰好由 \(h\) 个独立数字决定。因此问题变成：这 \(h\) 个数字的所有合法取值中，有多少种会使整个回文数在模 \(M\) 下余 \(0\)？
把十进制位置从右往左编号，从 \(0\) 开始。对每个 \(0\le i<h\)，令 \(d_i\) 表示同时放在位置 \(i\) 和位置 \(\ell-1-i\) 的那个数字。如果 \(\ell\) 是奇数并且 \(i=\ell-1-i\)，那么这就是中间那一位，只出现一次。
由于最高位 \(\ell-1\) 属于 \(i=0\) 这一对，所以 \(d_0\) 同时也是首位数字，不能为 \(0\)。于是
$$d_0\in\{1,\dots,9\},\qquad d_1,\dots,d_{h-1}\in\{0,\dots,9\}.$$
整个回文数模 \(M\) 的值可以写成
$$P_{\ell}(d_0,\dots,d_{h-1})\equiv \sum_{i=0}^{h-1} d_i W_i \pmod M,$$
其中每个权重 \(W_i\) 表示这个数字在对称位置上的十进制贡献：
$$W_i=\begin{cases} 10^i+10^{\ell-1-i}\pmod M, & i\ne \ell-1-i,\\ 10^i\pmod M, & i=\ell-1-i. \end{cases}$$
这一步的意义在于：回文约束已经被完全吸收到这些权重里，之后只需处理一个线性同余式。
为了做 meet-in-the-middle，取
$$s=\left\lceil\frac{h}{2}\right\rceil.$$
左块由 \(d_0,\dots,d_{s-1}\) 组成，右块由 \(d_s,\dots,d_{h-1}\) 组成。定义它们各自的模贡献
$$L=\sum_{i=0}^{s-1} d_i W_i \pmod M,\qquad R=\sum_{i=s}^{h-1} d_i W_i \pmod M.$$
那么整个回文数满足
$$P_{\ell}\equiv L+R\pmod M.$$
所以可被 \(M\) 整除的条件，等价于
$$L+R\equiv 0\pmod M.$$
也就是说，只要右半部分给出一个余数 \(R\)，左半部分就必须给出它的相反数 \(-R\pmod M\)。
左半部分中唯一带有“不能为 0”限制的只有 \(d_0\)。因此很自然地把首位数字和左块中其余 \(s-1\) 个数字分开处理。对每个固定的首位数字 \(a\in\{1,\dots,9\}\)，剩余左侧数字都可以自由遍历 \(\{0,\dots,9\}^{s-1}\)。
定义
$$C_{\ell}(r)=\#\{(d_0,\dots,d_{s-1}) : L\equiv r\pmod M\}.$$
这个函数表示：当前长度下，左半部分有多少种取法会产生余数 \(r\)。一旦这张频次数组建好，右半部分的每个状态都可以直接去查找自己所需的补余。
接下来遍历右块 \(d_s,\dots,d_{h-1}\) 的所有取值。每一种取值都会产生一个余数 \(R\)。为了让整个回文数在模 \(M\) 下为 \(0\)，左块必须满足
$$L\equiv -R\pmod M.$$
因此，以这个右块为结尾的完整回文数个数，恰好就是
$$C_{\ell}((-R)\bmod M).$$
把所有右块状态对应的这个值加起来，就得到长度为 \(\ell\) 的合法回文数个数 \(A_{\ell}(M)\)。最后再把 \(\ell=1\) 到 \(32\) 的结果求和。
如果不拆分，那么长度为 \(\ell\) 的回文数要检查 \(9\cdot 10^{h-1}\) 种独立数字取法。采用上面的平衡拆分后，左侧只需要处理 \(9\cdot 10^{s-1}\) 种情况，右侧只需要处理 \(10^{h-s}\) 种情况。
在最难的 \(\ell=32\) 情况下，有 \(h=16\)、\(s=8\)。于是算法面对的是大约 \(9\cdot 10^7\) 个左侧状态和 \(10^8\) 个右侧状态，而不是 \(9\cdot 10^{15}\) 个完整半边状态。这就是为什么原本不可行的枚举会变成可行的统计。
当长度为 \(5\) 时，\(h=3\)，\(s=2\)。对应的镜像权重为
$$W_0=10^0+10^4\equiv 1+81\equiv 82\pmod{109},$$
$$W_1=10^1+10^3\equiv 10+19\equiv 29\pmod{109},$$
$$W_2=10^2\equiv 100\pmod{109}.$$
因此每个 5 位回文数都满足
$$P_5(a,b,c)\equiv 82a+29b+100c\pmod{109},$$
其中 \(a\in\{1,\dots,9\}\)，\(b,c\in\{0,\dots,9\}\)。左表统计的是 \(82a+29b\) 的余数，右边枚举的是 \(100c\) 的余数。
由于 \(100\equiv -9\pmod{109}\)，所以当 \(c\) 从 \(0\) 跑到 \(9\) 时，左边需要查询的补余就是 \(0,9,18,\dots,81\)。这个例子已经完整体现了算法的结构。实现中还包含一个小校验：对模数 \(109\) 来说，把长度 \(1\) 到 \(5\) 全部累加后的答案应该是 \(9\)。
实现首先预计算所有需要的 \(10^i\bmod M\)。随后对每个长度 \(\ell\)，构造出相应的镜像权重 \(W_i\)，再按 \(s=\lceil h/2\rceil\) 做平衡拆分，并准备一个按模类索引的左侧余数频次数组。
为了高效构造这张表，程序先枚举左块中除了首位以外的那部分数字，把这些状态对应的余数保存下来。然后再把它们分别与首位数字 \(1\) 到 \(9\) 组合，得到完整左块的余数频次。之后枚举右块的所有状态，并把每个右侧余数所对应的“需要的左侧补余”的出现次数加到答案里。
实现中还有两个关键优化。第一，枚举数字块时不是每次重新计算整个表达式，而是按照十进制计数器顺序递增，并维护当前余数；这样跳到下一个状态时，只需修正那些发生变化的数字贡献。第二，每一轮长度计算结束后，只清理本轮实际用到过的模类，而不是把整个大小为 \(M\) 的频次数组全部重置。
C++、Python 和 Java 实现遵循的是同一套数学思路。Python 入口把真正的大计算交给编译后的代码执行，而 Java 版本则直接重现同样的余数统计流程。
对固定长度 \(\ell\)，记 \(h=\lceil \ell/2\rceil\)，\(s=\lceil h/2\rceil\)。构造镜像权重需要 \(O(h)\) 时间。左侧预处理会遍历 \(10^{s-1}\) 个“非首位部分”状态，再与 \(9\) 个可能的首位数字组合；右侧则遍历 \(10^{h-s}\) 个状态。
因此每个长度的主导时间复杂度是
$$O\left(10^{s-1}+9\cdot 10^{s-1}+10^{h-s}\right)=O\left(10^s+10^{h-s}\right).$$
在平衡拆分下，这基本就是 \(O(10^{\lceil h/2\rceil})\)。空间复杂度为
$$O\left(M+10^{s-1}\right),$$
其中 \(M\) 来自按模类存储的频次数组，而 \(10^{s-1}\) 来自左块非首位部分的余数列表。把所有长度加总时，耗时主要由最长的几种长度决定。
Нужно посчитать десятичные палиндромы длины не более \(32\), которые делятся на \(10{,}000{,}019\). В более общем виде реализация решает ту же задачу для произвольного модуля \(M\) и произвольной максимальной длины \(n\), а затем подставляет \(M=10{,}000{,}019\) и \(n=32\).
Если \(A_{\ell}(M)\) обозначает число палиндромов длины \(\ell\), делящихся на \(M\), то искомая величина равна
$$\sum_{\ell=1}^{32} A_{\ell}(10{,}000{,}019).$$
Прямой перебор все равно слишком велик: даже после использования симметрии палиндрома для 32-значного случая остается \(9\cdot 10^{15}\) возможных назначений половины цифр. Поэтому решение переписывает палиндром как линейную комбинацию независимых цифр по модулю \(M\), а затем считает дополняющие друг друга остатки методом meet-in-the-middle.
Зафиксируем длину \(\ell\) и модуль \(M\). Пусть
$$h=\left\lceil\frac{\ell}{2}\right\rceil.$$
Палиндром длины \(\ell\) полностью задается ровно \(h\) независимыми цифрами. Значит, задача сводится к подсчету того, сколько допустимых наборов этих цифр дают остаток \(0\pmod M\).
Нумеруем десятичные позиции справа налево, начиная с \(0\). Для каждого \(0\le i<h\) пусть \(d_i\) обозначает цифру, стоящую одновременно в позициях \(i\) и \(\ell-1-i\). Если \(\ell\) нечетно и \(i=\ell-1-i\), это центральная цифра, и она входит только один раз.
Поскольку старшая позиция \(\ell-1\) относится к паре с индексом \(0\), цифра \(d_0\) является ведущей цифрой. Следовательно,
$$d_0\in\{1,\dots,9\},\qquad d_1,\dots,d_{h-1}\in\{0,\dots,9\}.$$
Тогда значение палиндрома по модулю \(M\) равно
$$P_{\ell}(d_0,\dots,d_{h-1})\equiv \sum_{i=0}^{h-1} d_i W_i \pmod M,$$
где зеркальные веса задаются формулой
$$W_i=\begin{cases} 10^i+10^{\ell-1-i}\pmod M, & i\ne \ell-1-i,\\ 10^i\pmod M, & i=\ell-1-i. \end{cases}$$
Таким образом, проверка делимости превращается в одну линейную конгруэнцию по независимым цифрам.
Выберем
$$s=\left\lceil\frac{h}{2}\right\rceil.$$
Левый блок содержит цифры \(d_0,\dots,d_{s-1}\), а правый блок содержит \(d_s,\dots,d_{h-1}\). Определим их вклады по модулю:
$$L=\sum_{i=0}^{s-1} d_i W_i \pmod M,\qquad R=\sum_{i=s}^{h-1} d_i W_i \pmod M.$$
Тогда
$$P_{\ell}\equiv L+R\pmod M,$$
и палиндром делится на \(M\) тогда и только тогда, когда
$$L+R\equiv 0\pmod M.$$
Значит, теперь нужно сопоставлять левый остаток с дополняющим его правым остатком.
Ограничение на ведущую цифру затрагивает только \(d_0\). Поэтому удобно отделить ее от остальных \(s-1\) цифр левого блока. Для каждого фиксированного \(a\in\{1,\dots,9\}\) остальные левые цифры свободно перебирают \(\{0,\dots,9\}^{s-1}\).
Определим
$$C_{\ell}(r)=\#\{(d_0,\dots,d_{s-1}) : L\equiv r\pmod M\}.$$
Эта функция показывает, сколько левых половин дают остаток \(r\). После того как таблица частот построена для текущей длины, ее можно использовать для всех состояний правого блока.
Теперь перебираются все назначения цифр правого блока. Каждое из них дает некоторый остаток \(R\). Для делимости необходимо, чтобы
$$L\equiv -R\pmod M.$$
Значит, число полных палиндромов, продолжающих этот правый блок, равно
$$C_{\ell}((-R)\bmod M).$$
Суммируя это значение по всем правым состояниям, получаем \(A_{\ell}(M)\). После этого остается просуммировать результаты по \(\ell=1,\dots,32\).
Без разбиения для длины \(\ell\) пришлось бы рассматривать \(9\cdot 10^{h-1}\) независимых назначений цифр. При выбранном сбалансированном разбиении левая часть дает \(9\cdot 10^{s-1}\) состояний, а правая часть дает \(10^{h-s}\) состояний.
В самом длинном случае \(\ell=32\) имеем \(h=16\) и \(s=8\). Тогда алгоритм работает примерно с \(9\cdot 10^7\) левыми состояниями и \(10^8\) правыми вместо \(9\cdot 10^{15}\) полных назначений половины числа. Именно это и делает задачу вычислимой.
Для длины \(5\) получаем \(h=3\) и \(s=2\). Зеркальные веса равны
$$W_0=10^0+10^4\equiv 1+81\equiv 82\pmod{109},$$
$$W_1=10^1+10^3\equiv 10+19\equiv 29\pmod{109},$$
$$W_2=10^2\equiv 100\pmod{109}.$$
Следовательно, любой 5-значный палиндром удовлетворяет
$$P_5(a,b,c)\equiv 82a+29b+100c\pmod{109},$$
где \(a\in\{1,\dots,9\}\), а \(b,c\in\{0,\dots,9\}\). Левая таблица считает остатки выражения \(82a+29b\), а правая часть перебирает остатки \(100c\).
Поскольку \(100\equiv -9\pmod{109}\), при \(c=0,1,\dots,9\) в левой таблице запрашиваются дополняющие остатки \(0,9,18,\dots,81\). Это небольшой, но полностью показательный пример. В реализациях также есть контрольная проверка: суммарное число палиндромов длины от \(1\) до \(5\), делящихся на \(109\), равно \(9\).
Сначала реализация заранее вычисляет степени \(10^i\bmod M\) вплоть до максимальной нужной позиции. Для каждой длины \(\ell\) она строит зеркальные веса \(W_i\), выбирает сбалансированное разбиение \(s=\lceil h/2\rceil\) и подготавливает таблицу частот остатков левого блока.
Чтобы заполнить эту таблицу эффективно, сначала перебирается неведущая часть левого блока и сохраняются ее остатки. Затем эти остатки комбинируются с каждой возможной ведущей цифрой от \(1\) до \(9\), после чего получается полная частотная таблица для левой стороны. Далее перебирается правый блок, и для каждого его остатка в ответ добавляется частота нужного дополняющего левого остатка.
Скорость обеспечивают две детали. Во-первых, блоки цифр обходятся в порядке десятичного счетчика, а текущий остаток поддерживается инкрементально; значит, при переходе к следующему состоянию нужно исправить только вклад изменившихся цифр. Во-вторых, после обработки очередной длины очищаются только те классы остатков, которые действительно получили ненулевые счетчики, а не вся таблица размера \(M\).
Реализации на C++, Python и Java используют одну и ту же математику. Python-вход делегирует тяжелую арифметику компилируемому коду, а версия на Java напрямую повторяет тот же механизм подсчета остатков.
Для фиксированной длины \(\ell\) положим \(h=\lceil \ell/2\rceil\) и \(s=\lceil h/2\rceil\). Построение зеркальных весов требует \(O(h)\). Подготовка левой стороны затрагивает \(10^{s-1}\) состояний для неведущих цифр и затем объединяет их с \(9\) возможными ведущими цифрами, а правая сторона перебирает \(10^{h-s}\) состояний.
Следовательно, доминирующая трудоемкость на одну длину равна
$$O\left(10^{s-1}+9\cdot 10^{s-1}+10^{h-s}\right)=O\left(10^s+10^{h-s}\right).$$
При сбалансированном разбиении это по существу \(O(10^{\lceil h/2\rceil})\). Память равна
$$O\left(M+10^{s-1}\right),$$
поскольку нужно хранить таблицу частот по классам вычетов modulo \(M\) и список остатков неведущей части левого блока. Если суммировать по всем длинам до \(32\), время в основном определяется самыми длинными случаями.
المطلوب هو عدّ جميع الأعداد المتناظرة العشرية التي لا يزيد طولها على \(32\) رقمًا وتقبل القسمة على \(10{,}000{,}019\). وبصورة أعم، فإن الخوارزمية تحل المسألة نفسها لأي معامل \(M\) وأي حد أعلى للطول \(n\)، ثم تطبقها على الحالة \(M=10{,}000{,}019\) و\(n=32\).
إذا رمزنا إلى عدد الأعداد المتناظرة ذات الطول \(\ell\) والقابلة للقسمة على \(M\) بالرمز \(A_{\ell}(M)\)، فإن المطلوب هو
$$\sum_{\ell=1}^{32} A_{\ell}(10{,}000{,}019).$$
حتى بعد استغلال تماثل الأعداد المتناظرة يبقى التعداد المباشر ضخمًا جدًا، لأن حالة الطول \(32\) ما زالت تترك \(9\cdot 10^{15}\) تعيينًا ممكنًا لنصف الخانات المستقلة. لذلك تعيد الفكرة صياغة كل عدد متناظر على صورة تركيب خطي معياري في خاناته المستقلة، ثم تعدّ البواقي المتكاملة باستخدام meet-in-the-middle.
لنثبت طولًا \(\ell\) ومعاملًا \(M\)، ثم نضع
$$h=\left\lceil\frac{\ell}{2}\right\rceil.$$
العدد المتناظر ذو الطول \(\ell\) يتحدد تمامًا بواسطة \(h\) خانات مستقلة فقط. وهكذا تصبح المسألة: كم عدد التعيينات الممكنة لهذه الخانات التي تجعل العدد الناتج مكافئًا لـ \(0\pmod M\)؟
نرقّم المواضع العشرية من اليمين ابتداءً من \(0\). ولكل \(0\le i<h\)، نرمز بـ \(d_i\) إلى الخانة التي توضع في الموضعين \(i\) و\(\ell-1-i\) معًا. وإذا كان \(\ell\) فرديًا وكان \(i=\ell-1-i\)، فهذه هي الخانة الوسطى وتظهر مرة واحدة فقط.
وبما أن أعلى موضع \(\ell-1\) ينتمي إلى الزوج ذي الفهرس \(0\)، فإن \(d_0\) هي الخانة الأولى أيضًا، ولذلك يجب أن تكون غير صفرية:
$$d_0\in\{1,\dots,9\},\qquad d_1,\dots,d_{h-1}\in\{0,\dots,9\}.$$
وعندئذ يمكن كتابة قيمة العدد المتناظر بترديد \(M\) على الصورة
$$P_{\ell}(d_0,\dots,d_{h-1})\equiv \sum_{i=0}^{h-1} d_i W_i \pmod M,$$
حيث تعطى الأوزان المتناظرة بالعلاقة
$$W_i=\begin{cases} 10^i+10^{\ell-1-i}\pmod M, & i\ne \ell-1-i,\\ 10^i\pmod M, & i=\ell-1-i. \end{cases}$$
وهكذا تختزل قابلية القسمة إلى علاقة توافق خطية واحدة في الخانات المستقلة.
نختار
$$s=\left\lceil\frac{h}{2}\right\rceil.$$
الكتلة اليسرى تحتوي على \(d_0,\dots,d_{s-1}\)، والكتلة اليمنى تحتوي على \(d_s,\dots,d_{h-1}\). ولنعرّف مساهمتيهما المعياريتين:
$$L=\sum_{i=0}^{s-1} d_i W_i \pmod M,\qquad R=\sum_{i=s}^{h-1} d_i W_i \pmod M.$$
عندها يكون
$$P_{\ell}\equiv L+R\pmod M,$$
ومن ثم يكون العدد المتناظر قابلًا للقسمة على \(M\) إذا وفقط إذا تحقق
$$L+R\equiv 0\pmod M.$$
أي إن المسألة أصبحت مطابقة بقايا الجزء الأيسر مع البقايا المتممة القادمة من الجزء الأيمن.
القيد الخاص بعدم السماح بصفر في البداية يؤثر فقط في \(d_0\). لذلك من المناسب فصل الخانة الأولى عن بقية خانات الكتلة اليسرى وعددها \(s-1\). ولكل اختيار ثابت \(a\in\{1,\dots,9\}\) تتحرك الخانات اليسرى الأخرى بحرية في \(\{0,\dots,9\}^{s-1}\).
نعرّف دالة التكرار
$$C_{\ell}(r)=\#\{(d_0,\dots,d_{s-1}) : L\equiv r\pmod M\}.$$
وهذه الدالة تخبرنا بعدد أنصاف اليسار التي تعطي الباقي \(r\). وبعد بناء هذا الجدول لطول معين، يمكن استعماله مباشرة مع كل حالة من حالات الجزء الأيمن.
الآن نعدّد جميع تعيينات الكتلة اليمنى. كل تعيين ينتج باقيًا \(R\). وحتى يكون المجموع كله منعدمًا modulo \(M\)، يجب أن يحقق الجزء الأيسر
$$L\equiv -R\pmod M.$$
وعليه فإن عدد الأعداد المتناظرة الكاملة الموافقة لهذا الجزء الأيمن هو بالضبط
$$C_{\ell}((-R)\bmod M).$$
وبجمع هذه القيمة على جميع حالات الكتلة اليمنى نحصل على \(A_{\ell}(M)\). ثم نجمع هذه النتائج لكل \(\ell\) من \(1\) إلى \(32\).
من دون تقسيم، يجب على الطول \(\ell\) أن يفحص \(9\cdot 10^{h-1}\) تعيينًا مستقلًا للخانات. أما مع التقسيم المتوازن أعلاه، فيكفي التعامل مع \(9\cdot 10^{s-1}\) حالة في اليسار و\(10^{h-s}\) حالة في اليمين.
في أصعب حالة، أي عندما \(\ell=32\)، نجد \(h=16\) و\(s=8\). وبذلك تتعامل الخوارزمية مع نحو \(9\cdot 10^7\) حالة يسارية و\(10^8\) حالة يمينية بدلًا من \(9\cdot 10^{15}\) تعيينًا كاملًا لنصف العدد. وهذا هو سبب تحوّل المسألة من غير عملية إلى عملية.
عند الطول \(5\) يكون \(h=3\) و\(s=2\). وتصبح الأوزان المتناظرة
$$W_0=10^0+10^4\equiv 1+81\equiv 82\pmod{109},$$
$$W_1=10^1+10^3\equiv 10+19\equiv 29\pmod{109},$$
$$W_2=10^2\equiv 100\pmod{109}.$$
إذًا كل عدد متناظر من 5 خانات يحقق
$$P_5(a,b,c)\equiv 82a+29b+100c\pmod{109},$$
حيث \(a\in\{1,\dots,9\}\) و\(b,c\in\{0,\dots,9\}\). جدول اليسار يعدّ بواقي \(82a+29b\)، بينما يعدد اليمين بواقي \(100c\).
ولأن \(100\equiv -9\pmod{109}\)، فإن القيم التي يبحث عنها اليسار هي البواقي المتممة \(0,9,18,\dots,81\) عندما تتدرج \(c\) من \(0\) إلى \(9\). هذا المثال الصغير يوضح البنية الكاملة للفكرة. كما تتضمن التطبيقات نقطة تحقق صغيرة: المجموع التراكمي للأطوال من \(1\) إلى \(5\) عند المعامل \(109\) يساوي \(9\).
تبدأ التطبيقات بحساب قيم \(10^i\bmod M\) مسبقًا حتى أكبر موضع عشري مطلوب. وبعد ذلك، ولكل طول \(\ell\)، تُبنى الأوزان المتناظرة \(W_i\) ويُختار التقسيم المتوازن \(s=\lceil h/2\rceil\) وتُجهّز بنية عدّ لبواقي الكتلة اليسرى.
ولإنشاء هذا الجدول بكفاءة، يُعدَّد أولًا الجزء غير القيادي من الكتلة اليسرى وتُحفظ البواقي الناتجة عنه. ثم تُدمج هذه البواقي مع كل اختيار ممكن للخانة الأولى من \(1\) إلى \(9\) للحصول على تكرارات بواقي اليسار الكاملة. بعد ذلك تُعدَّد جميع حالات الكتلة اليمنى، ولكل باقي يميني تُضاف قيمة تكرار الباقي اليساري المتمم المطلوب لتحقيق القسمة.
هناك تفصيلان مهمان للأداء. الأول أن تعداد كتل الخانات يجري بترتيب عدّاد عشري مع الحفاظ على الباقي الحالي بصورة تراكمية، ولذلك لا يلزم عند الانتقال إلى الحالة التالية إلا تعديل مساهمات الخانات التي تغيرت فعلًا. والثاني أنه بعد الانتهاء من طول معين لا تُصفَّر كل بنية العدّ ذات الحجم \(M\)، بل تُعاد فقط الخانات المعيارية التي استُخدمت في تلك الجولة.
تتبع تطبيقات C++ وPython وJava الرياضيات نفسها. مدخل Python يفوض الجزء الحسابي الثقيل إلى كود مترجم، بينما تعيد نسخة Java تنفيذ آلية عدّ البواقي نفسها مباشرة.
لطول ثابت \(\ell\)، ضع \(h=\lceil \ell/2\rceil\) و\(s=\lceil h/2\rceil\). بناء الأوزان المتناظرة يكلف \(O(h)\). أما تجهيز اليسار فيمر على \(10^{s-1}\) حالة للجزء غير القيادي ثم يدمجها مع \(9\) قيم ممكنة للخانة الأولى، بينما يمر اليمين على \(10^{h-s}\) حالة.
إذًا فإن الكلفة الغالبة لكل طول هي
$$O\left(10^{s-1}+9\cdot 10^{s-1}+10^{h-s}\right)=O\left(10^s+10^{h-s}\right).$$
ومع التقسيم المتوازن تصبح هذه الكلفة في الجوهر \(O(10^{\lceil h/2\rceil})\). أما الذاكرة فهي
$$O\left(M+10^{s-1}\right),$$
وذلك بسبب جدول تكرار البواقي المفهرس حسب الفئات المعيارية، إضافة إلى قائمة بواقي الجزء غير القيادي من الكتلة اليسرى. وعند جمع جميع الأطوال حتى \(32\)، فإن أطول الحالات هي التي تهيمن على زمن التنفيذ.