A positive integer is balanced when the sum of its first half digits equals the sum of its last half digits. For odd length, the two halves overlap at the center, so a number with digits \(a_1a_2\cdots a_hma_{h+2}\cdots a_{2h+1}\) is balanced when \(a_1+\cdots+a_h+m=m+a_{h+2}+\cdots+a_{2h+1}\). The middle digit appears on both sides and cancels.
Let \(T(n)\) be the sum of all balanced positive integers below \(10^n\). The original problem asks for \(T(47)\bmod 3^{15}\), but the derivation used by the implementations works for general \(n\) and general modulus \(M\). Brute force is hopeless at this scale, so the solution groups numbers by length and digit sum instead of examining them one by one.
Write \(\sigma(X)\) for the sum of the digits of a block \(X\). For each exact length \(L\), let \(U_L\) denote the sum of all balanced \(L\)-digit numbers. Then
$$T(n)=\sum_{L=1}^{n}U_L.$$
The whole problem is therefore to compute \(U_L\) efficiently for every length.
If \(L=2h\) is even, every \(L\)-digit number can be written as
$$x=A\cdot 10^h+B,$$
where \(A\) is an \(h\)-digit block whose first digit is nonzero, and \(B\) is an \(h\)-digit block in which leading zeros are allowed. The number is balanced exactly when \(\sigma(A)=\sigma(B)\).
If \(L=2h+1\) is odd, every number has the form
$$x=A\cdot 10^{h+1}+m\cdot 10^h+B,\qquad m\in\{0,1,\dots,9\}.$$
Now the balance condition is
$$\sigma(A)+m=m+\sigma(B),$$
so once again the real condition is just \(\sigma(A)=\sigma(B)\). The center digit is free.
For every block length \(\ell\) and digit sum \(s\), the implementations keep two aggregated quantities:
$$C_L(\ell,s),\ V_L(\ell,s),\qquad C_R(\ell,s),\ V_R(\ell,s).$$
\(C_L(\ell,s)\) counts left blocks of length \(\ell\) with digit sum \(s\), and \(V_L(\ell,s)\) is the sum of their numeric values. The corresponding right-table quantities allow leading zeros, because numbers such as \(1203\) really do have a right block equal to \(03\). The base state is the empty block: length \(0\), digit sum \(0\), count \(1\), total value \(0\).
Suppose a state already contains all blocks of length \(\ell\) and digit sum \(s\). Appending a digit \(d\) on the right creates blocks of length \(\ell+1\) and digit sum \(s+d\), so the count update is
$$C(\ell+1,s+d)\leftarrow C(\ell+1,s+d)+C(\ell,s).$$
If a previous block has value \(x\), the new block has value \(10x+d\). Summing that identity over the whole state gives
$$V(\ell+1,s+d)\leftarrow V(\ell+1,s+d)+10\,V(\ell,s)+d\,C(\ell,s).$$
For left blocks, the very first appended digit must lie in \(\{1,\dots,9\}\); afterwards digits \(0\) through \(9\) are all allowed. For right blocks, digits \(0\) through \(9\) are allowed from the beginning. This recurrence is the core of the solution, because it tracks not only how many compatible blocks exist but also the sum of all their decimal values.
Fix \(L=2h\) and a digit sum \(s\). Every balanced number with that outer sum is formed by choosing a left block \(A\) from the left table and a right block \(B\) from the right table, both with digit sum \(s\). Summing
$$A\cdot 10^h+B$$
over all such pairs yields
$$U_{2h}(s)=10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s).$$
Therefore
$$U_{2h}=\sum_{s=0}^{9h}\left(10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s)\right).$$
For \(L=2h+1\), the outer blocks are still matched only by digit sum. Once \(A\) and \(B\) satisfy \(\sigma(A)=\sigma(B)\), every middle digit \(m\) from \(0\) to \(9\) produces a balanced number. Summing
$$A\cdot 10^{h+1}+m\cdot 10^h+B$$
over all \(A\), \(B\), and \(m\) gives
$$U_{2h+1}=\sum_{s=0}^{9h}\left(10^{h+1}V_L(h,s)\cdot 10\,C_R(h,s)+45\cdot 10^h\,C_L(h,s)C_R(h,s)+10\,V_R(h,s)C_L(h,s)\right).$$
The factor \(10\) comes from the ten middle-digit choices, and the factor \(45\) is \(0+1+\cdots+9\). No modular division is needed anywhere, which is important because the target modulus \(3^{15}\) is not prime.
Take \(h=2\), left block \(A=52\), and right block \(B=25\). Both blocks have digit sum \(7\), so every number of the form \(52m25\) is balanced. The ten members of the family are \(52025,52125,\dots,52925\).
Their total is
$$10\cdot 52\cdot 10^3+45\cdot 10^2+10\cdot 25=524750.$$
This tiny example is exactly the odd-length formula in miniature: one term for the repeated left block, one for the changing middle digit, and one for the repeated right block.
The C++, Python, and Java implementations first build the four DP tables up to half-length \(\lceil n/2\rceil\). At the same time they precompute the powers \(10^k\bmod M\), because each block sum must later be shifted into its proper decimal position.
After precomputation, the implementation loops through the exact lengths \(1,2,\dots,n\). For each length it sets \(h=\lfloor L/2\rfloor\), reads the row for that half-length from the left and right tables, and accumulates the matching digit-sum contributions. Even lengths use the two-term formula for \(A\cdot 10^h+B\); odd lengths use the three-term formula that also contains the middle-digit contribution \(45\cdot 10^h\).
Every recurrence and every final contribution uses only addition and multiplication, so intermediate values can be reduced modulo \(M\) immediately without changing the final residue. One implementation also checks small cases such as \(T(1)=45\), \(T(2)=540\), and a brute-force comparison for a small input size before running the full computation.
Let \(m=\lceil n/2\rceil\). The largest possible digit sum is \(9m\). Building one DP table visits states \((\ell,s)\) with \(0\le \ell\le m\) and \(0\le s\le 9\ell\), and from each state it tries at most 10 next digits. Hence the preprocessing cost is \(O(m\cdot 9m\cdot 10)=O(n^2)\).
The final sweep over all lengths and feasible digit sums is also \(O(n^2)\). Memory usage is \(O(n^2)\) for the count and value-sum tables. For the actual target \(n=47\), the maximum half-length is only \(24\) and the largest digit sum is \(216\), so the DP is tiny compared with the original search space below \(10^{47}\).
Eine positive ganze Zahl heißt balanciert, wenn die Summe ihrer ersten Halbziffern gleich der Summe ihrer letzten Halbziffern ist. Bei ungerader Länge überlappen diese Hälften in der Mitte, also gilt für eine Zahl mit Ziffern \(a_1a_2\cdots a_hma_{h+2}\cdots a_{2h+1}\) die Bedingung \(a_1+\cdots+a_h+m=m+a_{h+2}+\cdots+a_{2h+1}\). Die Mittelziffer erscheint auf beiden Seiten und hebt sich weg.
Sei \(T(n)\) die Summe aller balancierten positiven Zahlen kleiner als \(10^n\). Im Originalproblem wird \(T(47)\bmod 3^{15}\) verlangt, aber die Herleitung der Implementierungen funktioniert für allgemeines \(n\) und einen allgemeinen Modul \(M\). Eine direkte Durchmusterung aller Kandidaten unter \(10^{47}\) ist völlig unrealistisch; deshalb werden Zahlen nach Länge und Ziffernsumme zusammengefasst.
Bezeichne mit \(\sigma(X)\) die Ziffernsumme eines Blocks \(X\). Für jede exakte Länge \(L\) sei \(U_L\) die Summe aller balancierten \(L\)-stelligen Zahlen. Dann gilt
$$T(n)=\sum_{L=1}^{n}U_L.$$
Man muss also für jede Länge effizient die Gesamtsumme aller passenden Zahlenfamilien bestimmen.
Ist \(L=2h\) gerade, dann hat jede \(L\)-stellige Zahl die Form
$$x=A\cdot 10^h+B,$$
wobei \(A\) ein \(h\)-stelliger Block mit führender Nichtnullziffer ist und \(B\) ein \(h\)-stelliger Block, bei dem führende Nullen erlaubt sind. Balanciert ist die Zahl genau dann, wenn \(\sigma(A)=\sigma(B)\).
Ist \(L=2h+1\) ungerade, dann gilt
$$x=A\cdot 10^{h+1}+m\cdot 10^h+B,\qquad m\in\{0,1,\dots,9\}.$$
Die Balancebedingung wird zu
$$\sigma(A)+m=m+\sigma(B),$$
also erneut einfach zu \(\sigma(A)=\sigma(B)\). Die Mittelziffer ist frei wählbar.
Für jede Blocklänge \(\ell\) und jede Ziffernsumme \(s\) speichern die Implementierungen zwei aggregierte Größen:
$$C_L(\ell,s),\ V_L(\ell,s),\qquad C_R(\ell,s),\ V_R(\ell,s).$$
\(C_L(\ell,s)\) zählt linke Blöcke der Länge \(\ell\) mit Ziffernsumme \(s\), und \(V_L(\ell,s)\) ist die Summe ihrer numerischen Werte. Die rechten Tabellen erlauben führende Nullen, weil etwa die Zahl \(1203\) rechts tatsächlich den Block \(03\) besitzt. Der Startzustand ist der leere Block: Länge \(0\), Ziffernsumme \(0\), Anzahl \(1\), Wertsumme \(0\).
Angenommen, ein Zustand enthält alle Blöcke der Länge \(\ell\) mit Ziffernsumme \(s\). Hängt man rechts eine Ziffer \(d\) an, entstehen Blöcke der Länge \(\ell+1\) und Ziffernsumme \(s+d\). Für die Anzahl gilt daher
$$C(\ell+1,s+d)\leftarrow C(\ell+1,s+d)+C(\ell,s).$$
Hat ein alter Block den Wert \(x\), dann besitzt der neue Block den Wert \(10x+d\). Summiert man diese Identität über den ganzen Zustand, erhält man
$$V(\ell+1,s+d)\leftarrow V(\ell+1,s+d)+10\,V(\ell,s)+d\,C(\ell,s).$$
Bei linken Blöcken muss nur die allererste angehängte Ziffer aus \(\{1,\dots,9\}\) stammen; danach sind \(0\) bis \(9\) erlaubt. Bei rechten Blöcken sind \(0\) bis \(9\) von Anfang an zulässig. Gerade diese zweite Rekurrenz macht aus einer Zähl-DP sofort auch eine Summations-DP.
Fixiere \(L=2h\) und eine Ziffernsumme \(s\). Jede balancierte Zahl mit dieser Außensumme entsteht durch die Wahl eines linken Blocks \(A\) und eines rechten Blocks \(B\), beide mit Ziffernsumme \(s\). Die Summe aller Zahlen
$$A\cdot 10^h+B$$
über alle solchen Paare ist
$$U_{2h}(s)=10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s).$$
Damit folgt
$$U_{2h}=\sum_{s=0}^{9h}\left(10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s)\right).$$
Für \(L=2h+1\) werden die Außenblöcke wieder nur über gleiche Ziffernsummen gekoppelt. Sobald \(\sigma(A)=\sigma(B)\) gilt, liefert jede Mittelziffer \(m\) von \(0\) bis \(9\) eine weitere balancierte Zahl. Summiert man
$$A\cdot 10^{h+1}+m\cdot 10^h+B$$
über alle \(A\), \(B\) und \(m\), so entsteht
$$U_{2h+1}=\sum_{s=0}^{9h}\left(10^{h+1}V_L(h,s)\cdot 10\,C_R(h,s)+45\cdot 10^h\,C_L(h,s)C_R(h,s)+10\,V_R(h,s)C_L(h,s)\right).$$
Der Faktor \(10\) kommt von den zehn Möglichkeiten für die Mittelziffer, und \(45\) ist \(0+1+\cdots+9\). Eine modulare Division ist nirgends nötig, was wichtig ist, weil \(3^{15}\) kein Primmodul ist.
Setze \(h=2\), \(A=52\) und \(B=25\). Beide Blöcke haben die Ziffernsumme \(7\), daher ist jede Zahl der Form \(52m25\) balanciert. Die zehn Werte lauten \(52025,52125,\dots,52925\).
Ihre Summe beträgt
$$10\cdot 52\cdot 10^3+45\cdot 10^2+10\cdot 25=524750.$$
Dieses Miniaturbeispiel ist genau dieselbe Struktur wie in der allgemeinen Formel für ungerade Längen: ein Term für den wiederholten linken Block, einer für die wechselnde Mittelziffer und einer für den wiederholten rechten Block.
Die C++-, Python- und Java-Implementierungen bauen zuerst die vier DP-Tabellen bis zur Halblänge \(\lceil n/2\rceil\) auf. Zusätzlich werden die Potenzen \(10^k\bmod M\) vorbereitet, damit jeder Blockbeitrag sofort an seine richtige Dezimalposition verschoben werden kann.
Anschließend läuft die Implementierung über die exakten Längen \(1,2,\dots,n\). Für jede Länge wird \(h=\lfloor L/2\rfloor\) bestimmt, dann werden aus linker und rechter Tabelle die Zeilen dieser Halblänge gelesen und die Beiträge gleicher Ziffernsummen addiert. Gerade Längen benutzen die Zweiterm-Formel für \(A\cdot 10^h+B\); ungerade Längen verwenden die Dreiterm-Formel mit dem zusätzlichen Mittelziffernbeitrag \(45\cdot 10^h\).
Sämtliche Rekurrenzen und Endformeln enthalten nur Addition und Multiplikation. Deshalb dürfen Zwischenwerte sofort modulo \(M\) reduziert werden, ohne den Endrest zu verändern. Eine Implementierung überprüft außerdem kleine Fälle wie \(T(1)=45\), \(T(2)=540\) sowie einen Brute-Force-Vergleich für einen kleinen Eingabewert, bevor die volle Rechnung gestartet wird.
Setze \(m=\lceil n/2\rceil\). Die größte mögliche Ziffernsumme ist \(9m\). Eine DP-Tabelle besucht Zustände \((\ell,s)\) mit \(0\le \ell\le m\) und \(0\le s\le 9\ell\), und von jedem Zustand aus werden höchstens 10 nächste Ziffern ausprobiert. Damit kostet die Vorberechnung insgesamt \(O(m\cdot 9m\cdot 10)=O(n^2)\).
Auch die abschließende Summation über alle Längen und zulässigen Ziffernsummen ist \(O(n^2)\). Der Speicherbedarf beträgt \(O(n^2)\) für die Tabellen mit Anzahlen und Wertsummen. Für das eigentliche Ziel \(n=47\) ist die maximale Halblänge nur \(24\) und die größte Ziffernsumme \(216\), also ist die DP winzig im Vergleich zum Suchraum unter \(10^{47}\).
Pozitif bir tamsayı, ilk yarısındaki rakamların toplamı ile son yarısındaki rakamların toplamı eşitse dengelidir. Uzunluk tek olduğunda iki yarı ortada çakışır; yani rakamları \(a_1a_2\cdots a_hma_{h+2}\cdots a_{2h+1}\) olan bir sayı için koşul \(a_1+\cdots+a_h+m=m+a_{h+2}+\cdots+a_{2h+1}\) biçimindedir. Orta rakam iki tarafa da girdiği için sadeleşir.
\(T(n)\), \(10^n\)'den küçük bütün dengeli pozitif sayıların toplamı olsun. Asıl soru \(T(47)\bmod 3^{15}\) değeridir; fakat uygulamaların kullandığı türetim genel \(n\) ve genel bir \(M\) modu için de aynıdır. \(10^{47}\)'ye kadar tek tek sayı denemek imkansız olduğu için çözüm, sayıları uzunluk ve rakam toplamına göre topluca işler.
Bir blok \(X\) için rakam toplamını \(\sigma(X)\) ile gösterelim. Tam uzunluğu \(L\) olan dengeli sayıların toplamına \(U_L\) dersek
$$T(n)=\sum_{L=1}^{n}U_L$$
olur. Dolayısıyla asıl iş, her uzunluk için bu toplamı verimli biçimde çıkarmaktır.
\(L=2h\) çift ise her \(L\) basamaklı sayı
$$x=A\cdot 10^h+B$$
şeklinde yazılır. Burada \(A\), ilk rakamı sıfır olmayan \(h\) basamaklı sol bloktur; \(B\) ise başında sıfır bulunmasına izin verilen \(h\) basamaklı sağ bloktur. Denge koşulu tam olarak \(\sigma(A)=\sigma(B)\) olur.
\(L=2h+1\) tek ise sayı
$$x=A\cdot 10^{h+1}+m\cdot 10^h+B,\qquad m\in\{0,1,\dots,9\}$$
biçimindedir. Bu durumda
$$\sigma(A)+m=m+\sigma(B)$$
olduğu için yine gerçekte sadece \(\sigma(A)=\sigma(B)\) gerekir. Orta basamak serbesttir.
Her blok uzunluğu \(\ell\) ve rakam toplamı \(s\) için uygulamalar iki toplu nicelik tutar:
$$C_L(\ell,s),\ V_L(\ell,s),\qquad C_R(\ell,s),\ V_R(\ell,s).$$
\(C_L(\ell,s)\), uzunluğu \(\ell\) ve rakam toplamı \(s\) olan sol blokların sayısıdır; \(V_L(\ell,s)\) ise bu blokların sayısal değerleri toplamıdır. Sağ tablo başta sıfıra izin verir; çünkü örneğin \(1203\) sayısının sağ bloğu gerçekten \(03\)'tür. Başlangıç durumu boş bloktur: uzunluk \(0\), rakam toplamı \(0\), adet \(1\), değer toplamı \(0\).
Elimizde uzunluğu \(\ell\), rakam toplamı \(s\) olan bütün bloklar bulunsun. Sağa \(d\) rakamı eklenirse yeni blokların uzunluğu \(\ell+1\), rakam toplamı \(s+d\) olur. Sayı güncellemesi
$$C(\ell+1,s+d)\leftarrow C(\ell+1,s+d)+C(\ell,s)$$
şeklindedir. Eski bloklardan birinin değeri \(x\) ise yeni blok \(10x+d\) olur; bütün durum üzerinden toplarsak
$$V(\ell+1,s+d)\leftarrow V(\ell+1,s+d)+10\,V(\ell,s)+d\,C(\ell,s)$$
elde edilir. Sol blokta yalnızca ilk eklenen rakam \(\{1,\dots,9\}\) içinden seçilir; daha sonra \(0\) ile \(9\) arasındaki tüm rakamlar serbesttir. Sağ blokta ise en baştan itibaren \(0\) ile \(9\) arası kullanılabilir. Çözümün kalbi bu ilişkidir; çünkü aynı anda hem kaç blok olduğunu hem de bu blokların değer toplamını taşır.
\(L=2h\) ve sabit bir \(s\) için, dengeli her sayı aynı rakam toplamına sahip bir sol blok \(A\) ile bir sağ blok \(B\) seçilerek elde edilir. Bütün
$$A\cdot 10^h+B$$
terimlerini toplarsak
$$U_{2h}(s)=10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s)$$
bulunur. O halde
$$U_{2h}=\sum_{s=0}^{9h}\left(10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s)\right).$$
\(L=2h+1\) olduğunda dış bloklar yine sadece rakam toplamlarına göre eşleşir. \(\sigma(A)=\sigma(B)\) sağlandıktan sonra \(0\) ile \(9\) arasındaki her orta rakam yeni bir dengeli sayı üretir. Şu ifadenin
$$A\cdot 10^{h+1}+m\cdot 10^h+B$$
bütün \(A\), \(B\) ve \(m\) değerleri üzerindeki toplamı
$$U_{2h+1}=\sum_{s=0}^{9h}\left(10^{h+1}V_L(h,s)\cdot 10\,C_R(h,s)+45\cdot 10^h\,C_L(h,s)C_R(h,s)+10\,V_R(h,s)C_L(h,s)\right)$$
olur. Buradaki \(10\) katsayısı orta basamağın on farklı seçeneğinden, \(45\) katsayısı ise \(0+1+\cdots+9\) toplamından gelir. Hiçbir yerde modüler bölme gerekmez; bu önemlidir çünkü hedef mod \(3^{15}\) asaldır değil, asal kuvvetidir.
\(h=2\), \(A=52\), \(B=25\) alalım. Her iki bloğun rakam toplamı da \(7\) olduğundan \(52m25\) biçimindeki her sayı dengelidir. Bu ailenin üyeleri \(52025,52125,\dots,52925\) olur.
Toplamları
$$10\cdot 52\cdot 10^3+45\cdot 10^2+10\cdot 25=524750$$
çıkar. Bu küçük hesap, tek uzunluk formülünün birebir minyatürüdür: tekrarlanan sol blok, değişen orta rakam ve tekrarlanan sağ blok.
C++, Python ve Java uygulamaları önce dört DP tablosunu \(\lceil n/2\rceil\) yarı uzunluğuna kadar kurar. Bunun yanında \(10^k\bmod M\) değerleri de önceden hesaplanır; çünkü her blok katkısı daha sonra doğru onluk basamağa kaydırılacaktır.
Ön hesaplamadan sonra uygulama \(1,2,\dots,n\) tam uzunlukları üzerinden döner. Her uzunluk için \(h=\lfloor L/2\rfloor\) alınır, sol ve sağ tablolardan bu yarı uzunluğa karşılık gelen satırlar okunur ve aynı rakam toplamına ait katkılar eklenir. Çift uzunluklarda \(A\cdot 10^h+B\) için iki terimli formül; tek uzunluklarda ise buna ek olarak \(45\cdot 10^h\) orta-basamak terimini içeren üç terimli formül kullanılır.
Bütün özyinelemeler ve son katkılar yalnızca toplama ve çarpma içerir. Bu yüzden ara değerler anında \(M\) moduna indirilebilir; son kalan değişmez. Uygulamalardan biri ayrıca \(T(1)=45\), \(T(2)=540\) gibi küçük değerleri ve küçük bir giriş için kaba kuvvet karşılaştırmasını denetleyerek formülleri doğrular.
\(m=\lceil n/2\rceil\) olsun. En büyük rakam toplamı \(9m\)'dir. Bir DP tablosu, \(0\le \ell\le m\) ve \(0\le s\le 9\ell\) durumlarını ziyaret eder; her durumdan en fazla 10 yeni rakam denenir. Bu nedenle ön işlem maliyeti toplamda \(O(m\cdot 9m\cdot 10)=O(n^2)\) olur.
Bütün uzunluklar ve mümkün rakam toplamları üzerindeki son toplama da \(O(n^2)\) düzeyindedir. Bellek kullanımı adet ve değer tabloları için \(O(n^2)\)'dir. Gerçek hedef \(n=47\) için en büyük yarı uzunluk yalnızca \(24\), en büyük rakam toplamı ise \(216\) olduğundan DP, \(10^{47}\)'lik arama alanına kıyasla çok küçüktür.
Un entero positivo es equilibrado cuando la suma de sus dígitos de la primera mitad coincide con la suma de sus dígitos de la última mitad. Si la longitud es impar, las dos mitades se solapan en el centro; por eso, para una cifra de la forma \(a_1a_2\cdots a_hma_{h+2}\cdots a_{2h+1}\), la condición es \(a_1+\cdots+a_h+m=m+a_{h+2}+\cdots+a_{2h+1}\). El dígito central aparece en ambos lados y se cancela.
Sea \(T(n)\) la suma de todos los enteros positivos equilibrados menores que \(10^n\). El problema original pide \(T(47)\bmod 3^{15}\), aunque la derivación usada por las implementaciones vale para cualquier \(n\) y cualquier módulo \(M\). Probar todos los candidatos por fuerza bruta bajo \(10^{47}\) es imposible, así que la solución agrupa los números por longitud y por suma de dígitos.
Denotemos por \(\sigma(X)\) la suma de los dígitos de un bloque \(X\). Para cada longitud exacta \(L\), sea \(U_L\) la suma de todos los números equilibrados de \(L\) cifras. Entonces
$$T(n)=\sum_{L=1}^{n}U_L.$$
El objetivo real es calcular \(U_L\) de forma eficiente para cada longitud posible.
Si \(L=2h\) es par, todo número de \(L\) cifras puede escribirse como
$$x=A\cdot 10^h+B,$$
donde \(A\) es un bloque izquierdo de \(h\) cifras con primer dígito no nulo y \(B\) es un bloque derecho de \(h\) cifras en el que se permiten ceros iniciales. El número es equilibrado exactamente cuando \(\sigma(A)=\sigma(B)\).
Si \(L=2h+1\) es impar, todo número tiene la forma
$$x=A\cdot 10^{h+1}+m\cdot 10^h+B,\qquad m\in\{0,1,\dots,9\}.$$
La condición de equilibrio pasa a ser
$$\sigma(A)+m=m+\sigma(B),$$
y por tanto vuelve a reducirse a \(\sigma(A)=\sigma(B)\). El dígito central es libre.
Para cada longitud de bloque \(\ell\) y cada suma de dígitos \(s\), las implementaciones guardan dos cantidades agregadas:
$$C_L(\ell,s),\ V_L(\ell,s),\qquad C_R(\ell,s),\ V_R(\ell,s).$$
\(C_L(\ell,s)\) cuenta los bloques izquierdos de longitud \(\ell\) con suma \(s\), y \(V_L(\ell,s)\) es la suma de sus valores numéricos. Las tablas derechas permiten ceros iniciales, porque números como \(1203\) tienen realmente un bloque derecho igual a \(03\). El estado base es el bloque vacío: longitud \(0\), suma \(0\), cantidad \(1\), suma de valores \(0\).
Supongamos que ya conocemos todos los bloques de longitud \(\ell\) y suma de dígitos \(s\). Si añadimos un dígito \(d\) por la derecha, los nuevos bloques tienen longitud \(\ell+1\) y suma \(s+d\), así que
$$C(\ell+1,s+d)\leftarrow C(\ell+1,s+d)+C(\ell,s).$$
Si un bloque anterior tenía valor \(x\), el nuevo vale \(10x+d\). Al sumar esa identidad sobre todo el estado obtenemos
$$V(\ell+1,s+d)\leftarrow V(\ell+1,s+d)+10\,V(\ell,s)+d\,C(\ell,s).$$
En la tabla izquierda, solo el primer dígito añadido debe pertenecer a \(\{1,\dots,9\}\); después se permiten \(0\) a \(9\). En la tabla derecha, \(0\) a \(9\) están permitidos desde el principio. Esta recurrencia es la pieza esencial, porque convierte una DP de conteo en una DP que además suma directamente los valores decimales.
Fijemos \(L=2h\) y una suma \(s\). Cada número equilibrado con esa suma exterior se obtiene escogiendo un bloque izquierdo \(A\) y un bloque derecho \(B\), ambos con suma de dígitos \(s\). Al sumar
$$A\cdot 10^h+B$$
sobre todos esos pares, resulta
$$U_{2h}(s)=10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s).$$
Por lo tanto,
$$U_{2h}=\sum_{s=0}^{9h}\left(10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s)\right).$$
Para \(L=2h+1\), los bloques exteriores siguen emparejándose únicamente por suma de dígitos. Una vez que \(\sigma(A)=\sigma(B)\), cualquier dígito central \(m\) entre \(0\) y \(9\) produce otro número equilibrado. Sumando
$$A\cdot 10^{h+1}+m\cdot 10^h+B$$
sobre todos los \(A\), \(B\) y \(m\), aparece la fórmula
$$U_{2h+1}=\sum_{s=0}^{9h}\left(10^{h+1}V_L(h,s)\cdot 10\,C_R(h,s)+45\cdot 10^h\,C_L(h,s)C_R(h,s)+10\,V_R(h,s)C_L(h,s)\right).$$
El factor \(10\) proviene de las diez opciones para el dígito central, y el factor \(45\) es \(0+1+\cdots+9\). No hace falta ninguna división modular, algo importante porque el módulo objetivo \(3^{15}\) no es primo.
Tomemos \(h=2\), \(A=52\) y \(B=25\). Ambos bloques tienen suma de dígitos \(7\), así que todo número de la forma \(52m25\) es equilibrado. Los diez miembros de la familia son \(52025,52125,\dots,52925\).
La suma de toda la familia es
$$10\cdot 52\cdot 10^3+45\cdot 10^2+10\cdot 25=524750.$$
Este cálculo pequeño reproduce exactamente la fórmula general de longitudes impares: un término para el bloque izquierdo repetido, otro para el dígito central cambiante y otro para el bloque derecho repetido.
Las implementaciones en C++, Python y Java construyen primero las cuatro tablas DP hasta la semilongitud \(\lceil n/2\rceil\). También precalculan las potencias \(10^k\bmod M\), porque cada contribución de un bloque debe desplazarse a su posición decimal correcta.
Después de esa fase previa, la implementación recorre las longitudes exactas \(1,2,\dots,n\). Para cada longitud calcula \(h=\lfloor L/2\rfloor\), toma la fila correspondiente de las tablas izquierda y derecha, y suma las contribuciones de todas las sumas de dígitos posibles. Las longitudes pares usan la expresión de dos términos para \(A\cdot 10^h+B\); las impares usan la expresión de tres términos que añade el aporte del dígito central \(45\cdot 10^h\).
Todas las recurrencias y todas las fórmulas finales emplean solo sumas y productos. Por eso se puede reducir cada valor intermedio módulo \(M\) en cuanto aparece, sin alterar el residuo final. Una de las implementaciones también verifica casos pequeños como \(T(1)=45\), \(T(2)=540\) y una comparación por fuerza bruta para una entrada reducida antes de ejecutar el cálculo completo.
Sea \(m=\lceil n/2\rceil\). La mayor suma de dígitos posible es \(9m\). Una tabla DP visita estados \((\ell,s)\) con \(0\le \ell\le m\) y \(0\le s\le 9\ell\), y desde cada estado prueba como mucho 10 dígitos siguientes. Por tanto, el coste de precomputación es \(O(m\cdot 9m\cdot 10)=O(n^2)\).
La acumulación final sobre todas las longitudes y todas las sumas de dígitos viables también es \(O(n^2)\). La memoria necesaria es \(O(n^2)\) para las tablas de cantidades y sumas de valores. En el caso real \(n=47\), la semilongitud máxima es solo \(24\) y la suma máxima de dígitos es \(216\), así que la DP es diminuta frente al espacio de búsqueda original bajo \(10^{47}\).
如果一个正整数前半部分数字之和等于后半部分数字之和，就称它为平衡数。长度为奇数时，两半会在中间重叠；也就是说，形如 \(a_1a_2\cdots a_hma_{h+2}\cdots a_{2h+1}\) 的数满足 \(a_1+\cdots+a_h+m=m+a_{h+2}+\cdots+a_{2h+1}\) 时就是平衡的。中间数字同时出现在左右两边，因此会被直接抵消。
记 \(T(n)\) 为所有小于 \(10^n\) 的平衡正整数之和。原题要求的是 \(T(47)\bmod 3^{15}\)，不过实现中的推导实际上适用于一般的 \(n\) 和一般的模数 \(M\)。由于 \(10^{47}\) 级别的暴力枚举根本不可行，解法必须按位数和数位和把大量数字整体处理。
用 \(\sigma(X)\) 表示一个数字块 \(X\) 的数位和。对每个确切长度 \(L\)，记 \(U_L\) 为所有 \(L\) 位平衡数的总和，那么
$$T(n)=\sum_{L=1}^{n}U_L.$$
因此问题变成：怎样对每个长度快速求出这一整类数字的和。
如果 \(L=2h\) 是偶数，那么每个 \(L\) 位数都可以写成
$$x=A\cdot 10^h+B,$$
其中 \(A\) 是一个首位非零的 \(h\) 位左块，\(B\) 是一个允许前导零的 \(h\) 位右块。数字平衡当且仅当 \(\sigma(A)=\sigma(B)\)。
如果 \(L=2h+1\) 是奇数，那么每个数都可以写成
$$x=A\cdot 10^{h+1}+m\cdot 10^h+B,\qquad m\in\{0,1,\dots,9\}.$$
此时平衡条件变成
$$\sigma(A)+m=m+\sigma(B),$$
也就是仍然只要求 \(\sigma(A)=\sigma(B)\)。这说明奇数长度的中心位完全独立，它只影响数值，不影响是否平衡。
对于每个块长度 \(\ell\) 和每个数位和 \(s\)，实现会维护两类汇总量：
$$C_L(\ell,s),\ V_L(\ell,s),\qquad C_R(\ell,s),\ V_R(\ell,s).$$
\(C_L(\ell,s)\) 表示长度为 \(\ell\)、数位和为 \(s\) 的左块个数，\(V_L(\ell,s)\) 表示这些左块作为十进制整数时的数值总和。右块对应的 \(C_R\) 和 \(V_R\) 允许前导零，因为像 \(1203\) 这样的数字，其右半块确实是 \(03\)。基础状态是空块：长度 \(0\)、数位和 \(0\)、计数 \(1\)、数值和 \(0\)。
假设我们已经知道所有长度为 \(\ell\)、数位和为 \(s\) 的块。如果在右侧追加一个数字 \(d\)，新块的长度变成 \(\ell+1\)，数位和变成 \(s+d\)，所以计数满足
$$C(\ell+1,s+d)\leftarrow C(\ell+1,s+d)+C(\ell,s).$$
若旧块的数值是 \(x\)，新块的数值就是 \(10x+d\)。把这条关系在整个状态上求和，就得到
$$V(\ell+1,s+d)\leftarrow V(\ell+1,s+d)+10\,V(\ell,s)+d\,C(\ell,s).$$
左块表只在第一位追加时限制 \(d\) 不能为 \(0\)；之后 \(0\) 到 \(9\) 都可以。右块表从一开始就允许 \(0\) 到 \(9\)。这正是题目的关键：同一个 DP 状态既记录“有多少种块”，也记录“这些块的值加起来是多少”。
固定 \(L=2h\) 和某个数位和 \(s\)。所有对应的平衡数，都是把左块表中数位和为 \(s\) 的一个 \(A\) 与右块表中数位和同样为 \(s\) 的一个 \(B\) 配对得到的。把所有
$$A\cdot 10^h+B$$
累加起来，可得
$$U_{2h}(s)=10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s).$$
于是
$$U_{2h}=\sum_{s=0}^{9h}\left(10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s)\right).$$
第一项负责高位左块，第二项负责低位右块。
对 \(L=2h+1\) 而言，外层两块仍然只按数位和匹配。一旦 \(\sigma(A)=\sigma(B)\)，中心位 \(m\) 的十个取值都会产生一个平衡数。把
$$A\cdot 10^{h+1}+m\cdot 10^h+B$$
对所有 \(A\)、\(B\)、\(m\) 求和，就得到
$$U_{2h+1}=\sum_{s=0}^{9h}\left(10^{h+1}V_L(h,s)\cdot 10\,C_R(h,s)+45\cdot 10^h\,C_L(h,s)C_R(h,s)+10\,V_R(h,s)C_L(h,s)\right).$$
这里的 \(10\) 来自中心位的十种选择，\(45\) 来自 \(0+1+\cdots+9\)。整个推导只涉及加法和乘法，因此完全不需要模逆，这一点和目标模数 \(3^{15}\) 很契合。
取 \(h=2\)，左块 \(A=52\)，右块 \(B=25\)。二者的数位和都等于 \(7\)，所以所有形如 \(52m25\) 的五位数都是平衡数。这个族包含 \(52025,52125,\dots,52925\) 这十个数。
它们的总和是
$$10\cdot 52\cdot 10^3+45\cdot 10^2+10\cdot 25=524750.$$
这正是奇数长度公式的缩影：左块重复出现，中心位在变化，右块也重复出现，各自贡献一项。
C++、Python 和 Java 实现都会先把四张 DP 表预处理到半长度 \(\lceil n/2\rceil\)。与此同时，还会预先算好 \(10^k\bmod M\)，因为后面在合并左右块时，需要把左块整体移到正确的十进制位置上。
预处理完成后，实现会遍历精确长度 \(1,2,\dots,n\)。对每个长度先计算 \(h=\lfloor L/2\rfloor\)，再取出对应半长度的左右 DP 行，并对所有可行的数位和进行累加。偶数长度使用两项公式 \(A\cdot 10^h+B\)，奇数长度使用三项公式，其中额外包含中心位的贡献 \(45\cdot 10^h\)。
所有递推式和最终公式都只用到了加法与乘法，所以每一步都可以立即对 \(M\) 取模，而不会改变最终余数。有一个实现还会在正式计算前检查若干小规模结果，例如 \(T(1)=45\)、\(T(2)=540\)，以及一个小输入上的暴力对照，以确认 DP 推导无误。
设 \(m=\lceil n/2\rceil\)。最大的数位和是 \(9m\)。构造一张 DP 表时，需要访问所有满足 \(0\le \ell\le m\)、\(0\le s\le 9\ell\) 的状态，并从每个状态尝试最多 10 个下一位，因此预处理时间是 \(O(m\cdot 9m\cdot 10)=O(n^2)\)。
最后对所有长度和所有可行数位和做累加，同样是 \(O(n^2)\)。计数表与数值和表占用的空间也是 \(O(n^2)\)。在真实目标 \(n=47\) 下，最大半长度只有 \(24\)，最大数位和只有 \(216\)，因此这个 DP 与原问题小于 \(10^{47}\) 的搜索空间相比几乎可以忽略不计。
Положительное целое число называется сбалансированным, если сумма цифр в его первой половине равна сумме цифр в его второй половине. При нечетной длине половины перекрываются в центре: для числа вида \(a_1a_2\cdots a_hma_{h+2}\cdots a_{2h+1}\) условие имеет вид \(a_1+\cdots+a_h+m=m+a_{h+2}+\cdots+a_{2h+1}\). Средняя цифра входит в обе суммы и сокращается.
Пусть \(T(n)\) обозначает сумму всех сбалансированных положительных чисел, меньших \(10^n\). В исходной задаче требуется \(T(47)\bmod 3^{15}\), но сама схема решения из реализаций работает для произвольных \(n\) и модуля \(M\). Полный перебор всех чисел ниже \(10^{47}\) невозможен, поэтому решение группирует числа по длине и сумме цифр.
Обозначим через \(\sigma(X)\) сумму цифр блока \(X\). Для каждой точной длины \(L\) пусть \(U_L\) — сумма всех сбалансированных чисел длины \(L\). Тогда
$$T(n)=\sum_{L=1}^{n}U_L.$$
Значит, задача сводится к тому, чтобы быстро находить \(U_L\) для каждого возможного числа цифр.
Если \(L=2h\) четно, то любое \(L\)-значное число записывается как
$$x=A\cdot 10^h+B,$$
где \(A\) — левый блок длины \(h\) с ненулевой первой цифрой, а \(B\) — правый блок длины \(h\), в котором разрешены ведущие нули. Число сбалансировано тогда и только тогда, когда \(\sigma(A)=\sigma(B)\).
Если \(L=2h+1\) нечетно, то число имеет вид
$$x=A\cdot 10^{h+1}+m\cdot 10^h+B,\qquad m\in\{0,1,\dots,9\}.$$
Условие баланса становится
$$\sigma(A)+m=m+\sigma(B),$$
то есть снова сводится к \(\sigma(A)=\sigma(B)\). Центральная цифра не влияет на сам факт баланса.
Для каждой длины блока \(\ell\) и каждой суммы цифр \(s\) реализации хранят две агрегированные величины:
$$C_L(\ell,s),\ V_L(\ell,s),\qquad C_R(\ell,s),\ V_R(\ell,s).$$
\(C_L(\ell,s)\) — число левых блоков длины \(\ell\) с суммой цифр \(s\), а \(V_L(\ell,s)\) — сумма их десятичных значений. Правые таблицы допускают ведущие нули, потому что у числа вроде \(1203\) правый блок действительно равен \(03\). Базовое состояние — пустой блок: длина \(0\), сумма цифр \(0\), количество \(1\), сумма значений \(0\).
Предположим, что нам известны все блоки длины \(\ell\) с суммой цифр \(s\). Если приписать справа цифру \(d\), новые блоки будут иметь длину \(\ell+1\) и сумму цифр \(s+d\), значит
$$C(\ell+1,s+d)\leftarrow C(\ell+1,s+d)+C(\ell,s).$$
Если старый блок имел значение \(x\), то новый блок имеет значение \(10x+d\). Просуммировав это тождество по всему состоянию, получаем
$$V(\ell+1,s+d)\leftarrow V(\ell+1,s+d)+10\,V(\ell,s)+d\,C(\ell,s).$$
Для левых блоков только самая первая добавленная цифра обязана лежать в \(\{1,\dots,9\}\); затем разрешены цифры от \(0\) до \(9\). Для правых блоков цифры от \(0\) до \(9\) допустимы сразу. Именно этот переход позволяет одновременно считать количество блоков и сумму их значений.
Зафиксируем \(L=2h\) и сумму цифр \(s\). Каждое сбалансированное число с такой внешней суммой получается из левого блока \(A\) и правого блока \(B\), у которых одна и та же сумма цифр \(s\). Если просуммировать
$$A\cdot 10^h+B$$
по всем таким парам, выйдет
$$U_{2h}(s)=10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s).$$
Следовательно,
$$U_{2h}=\sum_{s=0}^{9h}\left(10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s)\right).$$
Для \(L=2h+1\) внешние блоки по-прежнему согласуются только по сумме цифр. Как только выполнено \(\sigma(A)=\sigma(B)\), любая средняя цифра \(m\) от \(0\) до \(9\) дает новое сбалансированное число. Суммирование выражения
$$A\cdot 10^{h+1}+m\cdot 10^h+B$$
по всем \(A\), \(B\) и \(m\) приводит к формуле
$$U_{2h+1}=\sum_{s=0}^{9h}\left(10^{h+1}V_L(h,s)\cdot 10\,C_R(h,s)+45\cdot 10^h\,C_L(h,s)C_R(h,s)+10\,V_R(h,s)C_L(h,s)\right).$$
Множитель \(10\) появляется из-за десяти вариантов средней цифры, а множитель \(45\) равен \(0+1+\cdots+9\). Никакого деления по модулю не требуется, что удобно, поскольку целевой модуль \(3^{15}\) не является простым.
Положим \(h=2\), \(A=52\), \(B=25\). У обоих блоков сумма цифр равна \(7\), поэтому любое число вида \(52m25\) сбалансировано. Это десять чисел \(52025,52125,\dots,52925\).
Их сумма равна
$$10\cdot 52\cdot 10^3+45\cdot 10^2+10\cdot 25=524750.$$
В этом маленьком примере уже видна вся общая формула для нечетной длины: отдельный вклад повторяющегося левого блока, меняющейся средней цифры и повторяющегося правого блока.
Реализации на C++, Python и Java сначала строят четыре DP-таблицы до полу длины \(\lceil n/2\rceil\). Одновременно предвычисляются степени \(10^k\bmod M\), потому что при сборке полного числа вклад каждого блока нужно сдвигать в правильный десятичный разряд.
После предвычисления код проходит по точным длинам \(1,2,\dots,n\). Для каждой длины вычисляется \(h=\lfloor L/2\rfloor\), затем берутся строки левой и правой таблиц для этой полу длины, и по всем допустимым суммам цифр накапливаются вклады. Для четных длин используется двухчленная формула для \(A\cdot 10^h+B\), для нечетных — трехчленная формула с дополнительным вкладом средней цифры \(45\cdot 10^h\).
Все рекуррентные переходы и все конечные формулы используют только сложение и умножение. Поэтому промежуточные значения можно сразу брать по модулю \(M\), не меняя окончательного остатка. Одна из реализаций также проверяет малые случаи вроде \(T(1)=45\), \(T(2)=540\), а еще сравнивает результат с грубой силой на маленьком входе.
Пусть \(m=\lceil n/2\rceil\). Максимальная сумма цифр равна \(9m\). Построение одной DP-таблицы перебирает состояния \((\ell,s)\) с \(0\le \ell\le m\) и \(0\le s\le 9\ell\), а из каждого состояния пробует не более 10 следующих цифр. Поэтому стоимость предвычисления составляет \(O(m\cdot 9m\cdot 10)=O(n^2)\).
Итоговое суммирование по всем длинам и всем допустимым суммам цифр тоже занимает \(O(n^2)\). Память \(O(n^2)\) требуется для таблиц количеств и сумм значений. В реальной задаче \(n=47\), так что максимальная полу длина равна всего \(24\), а максимальная сумма цифр — \(216\); по сравнению с пространством поиска ниже \(10^{47}\) это очень маленькая DP.
يُسمّى العدد الصحيح الموجب متوازنًا إذا كان مجموع أرقام نصفه الأول مساويًا لمجموع أرقام نصفه الأخير. وعندما يكون الطول فرديًا تتداخل النصفان عند الخانة الوسطى؛ أي إن العدد ذي الصورة \(a_1a_2\cdots a_hma_{h+2}\cdots a_{2h+1}\) يكون متوازنًا عندما يتحقق \(a_1+\cdots+a_h+m=m+a_{h+2}+\cdots+a_{2h+1}\). وبما أن الخانة الوسطى تظهر في الطرفين فهي تُلغى مباشرة.
لنرمز بـ \(T(n)\) إلى مجموع جميع الأعداد الموجبة المتوازنة الأصغر من \(10^n\). المطلوب في المسألة الأصلية هو \(T(47)\bmod 3^{15}\)، لكن الاشتقاق الذي تستعمله التطبيقات صالح في الحقيقة لأي \(n\) وأي مودولو \(M\). الفحص المباشر لكل الأعداد الأصغر من \(10^{47}\) غير ممكن، ولذلك يجمع الحل الأعداد بحسب طولها وبحسب مجموع أرقامها.
لنكتب \(\sigma(X)\) لمجموع أرقام الكتلة \(X\). ولكل طول دقيق \(L\)، نرمز بـ \(U_L\) إلى مجموع جميع الأعداد المتوازنة ذات الطول \(L\). عندئذ
$$T(n)=\sum_{L=1}^{n}U_L.$$
وهكذا تصبح المهمة الحقيقية هي حساب \(U_L\) بكفاءة لكل طول ممكن.
إذا كان \(L=2h\) زوجيًا، فإن كل عدد ذي \(L\) خانات يمكن كتابته على الصورة
$$x=A\cdot 10^h+B,$$
حيث \(A\) كتلة يسارية طولها \(h\) وخانتها الأولى غير صفرية، و\(B\) كتلة يمينية طولها \(h\) يُسمح فيها بالأصفار البادئة. يكون العدد متوازنًا بالضبط عندما يتحقق \(\sigma(A)=\sigma(B)\).
أما إذا كان \(L=2h+1\) فرديًا، فإن العدد يأخذ الصورة
$$x=A\cdot 10^{h+1}+m\cdot 10^h+B,\qquad m\in\{0,1,\dots,9\}.$$
وعندئذ يصبح شرط التوازن
$$\sigma(A)+m=m+\sigma(B),$$
أي إنه يعود مرة أخرى إلى الشرط الأبسط \(\sigma(A)=\sigma(B)\). الخانة الوسطى حرة تمامًا من جهة التوازن.
لكل طول كتلة \(\ell\) ولكل مجموع أرقام \(s\)، تحتفظ التطبيقات بكمّيتين مجمعتين:
$$C_L(\ell,s),\ V_L(\ell,s),\qquad C_R(\ell,s),\ V_R(\ell,s).$$
\(C_L(\ell,s)\) هو عدد الكتل اليسارية ذات الطول \(\ell\) ومجموع الأرقام \(s\)، و\(V_L(\ell,s)\) هو مجموع قيمها العشرية. أما الجداول اليمنى فتسمح بالأصفار البادئة، لأن عددًا مثل \(1203\) يملك فعلًا كتلة يمينية تساوي \(03\). حالة البداية هي الكتلة الفارغة: طول \(0\)، مجموع أرقام \(0\)، عدد \(1\)، ومجموع قيم \(0\).
لنفترض أننا نعرف جميع الكتل ذات الطول \(\ell\) ومجموع الأرقام \(s\). إذا ألحقنا رقمًا \(d\) من اليمين، صار طول الكتلة الجديدة \(\ell+1\) ومجموع أرقامها \(s+d\)، ولذلك يكون تحديث العد
$$C(\ell+1,s+d)\leftarrow C(\ell+1,s+d)+C(\ell,s).$$
وإذا كانت قيمة كتلة قديمة هي \(x\)، فالقيمة الجديدة تصبح \(10x+d\). وبجمع هذه العلاقة على كامل الحالة نحصل على
$$V(\ell+1,s+d)\leftarrow V(\ell+1,s+d)+10\,V(\ell,s)+d\,C(\ell,s).$$
في الجدول اليساري فقط، يجب أن يكون أول رقم ملحوق من المجموعة \(\{1,\dots,9\}\)، ثم تصبح الأرقام \(0\) إلى \(9\) كلها مسموحة. أما الجدول اليميني فيسمح بـ \(0\) إلى \(9\) منذ البداية. هذه العلاقة هي قلب الحل، لأنها تجعلنا نعد الكتل ونجمع قيمها في الوقت نفسه.
ثبّت \(L=2h\) ومجموع أرقام \(s\). كل عدد متوازن بهذه القيمة الخارجية ينشأ من اختيار كتلة يسارية \(A\) وكتلة يمينية \(B\) بحيث يملك كلاهما مجموع الأرقام نفسه \(s\). عند جمع
$$A\cdot 10^h+B$$
على جميع هذه الأزواج نحصل على
$$U_{2h}(s)=10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s).$$
ومن ثم
$$U_{2h}=\sum_{s=0}^{9h}\left(10^h\,V_L(h,s)\,C_R(h,s)+V_R(h,s)\,C_L(h,s)\right).$$
عندما يكون \(L=2h+1\)، تظل الكتلتان الخارجيتان مقترنتين فقط عبر مجموع الأرقام. فإذا تحقق \(\sigma(A)=\sigma(B)\)، فإن كل اختيار للخانة الوسطى \(m\) من \(0\) إلى \(9\) يعطي عددًا متوازنًا جديدًا. وجمع المقدار
$$A\cdot 10^{h+1}+m\cdot 10^h+B$$
على جميع \(A\) و\(B\) و\(m\) ينتج
$$U_{2h+1}=\sum_{s=0}^{9h}\left(10^{h+1}V_L(h,s)\cdot 10\,C_R(h,s)+45\cdot 10^h\,C_L(h,s)C_R(h,s)+10\,V_R(h,s)C_L(h,s)\right).$$
العامل \(10\) يأتي من الخيارات العشرة للخانة الوسطى، والعامل \(45\) هو \(0+1+\cdots+9\). ولا يظهر أي احتياج إلى قسمة معيارية، وهذا مناسب لأن المودولو المستهدف \(3^{15}\) ليس أوليًا.
خذ \(h=2\) و\(A=52\) و\(B=25\). مجموع أرقام الكتلتين يساوي \(7\)، ولذلك فإن كل عدد من الشكل \(52m25\) متوازن. هذه العائلة تتكون من \(52025,52125,\dots,52925\).
مجموعها يساوي
$$10\cdot 52\cdot 10^3+45\cdot 10^2+10\cdot 25=524750.$$
وهذا المثال الصغير يطابق تمامًا صيغة الطول الفردي: حد للكتلة اليسارية المكررة، وحد للخانة الوسطى المتغيرة، وحد للكتلة اليمينية المكررة.
تبدأ تطبيقات C++ وPython وJava ببناء الجداول الأربعة للبرمجة الديناميكية حتى نصف الطول \(\lceil n/2\rceil\). كما تحسب مسبقًا القيم \(10^k\bmod M\)، لأن مساهمة كل كتلة يجب أن تُنقل لاحقًا إلى موضعها العشري الصحيح.
بعد ذلك تمرّ الشيفرة على الأطوال الدقيقة \(1,2,\dots,n\). ولكل طول تحسب \(h=\lfloor L/2\rfloor\)، ثم تقرأ الصف الموافق من الجداول اليسرى واليمنى وتجمع مساهمات جميع مجاميع الأرقام الممكنة. الأطوال الزوجية تستعمل الصيغة ذات الحدين لـ \(A\cdot 10^h+B\)، أما الأطوال الفردية فتستعمل الصيغة ذات الحدود الثلاثة التي تضيف مساهمة الخانة الوسطى \(45\cdot 10^h\).
جميع العلاقات التكرارية وجميع الصيغ النهائية تعتمد على الجمع والضرب فقط. لذلك يمكن أخذ كل قيمة وسيطة بتوافق \(M\) مباشرة من غير أن يتغير الباقي النهائي. كما أن إحدى التطبيقات تتحقق من حالات صغيرة مثل \(T(1)=45\) و\(T(2)=540\)، وتنفذ مقارنة بالقوة الغاشمة على مدخل صغير قبل الحساب الكامل.
لنضع \(m=\lceil n/2\rceil\). أكبر مجموع أرقام ممكن هو \(9m\). بناء جدول DP واحد يزور الحالات \((\ell,s)\) التي تحقق \(0\le \ell\le m\) و\(0\le s\le 9\ell\)، ومن كل حالة يجرّب ما يصل إلى 10 أرقام تالية. لذلك تكون كلفة التحضير \(O(m\cdot 9m\cdot 10)=O(n^2)\).
أما التجميع النهائي على جميع الأطوال وجميع مجاميع الأرقام الممكنة فهو أيضًا \(O(n^2)\). واستهلاك الذاكرة \(O(n^2)\) من أجل جداول العد وجداول مجموع القيم. في الهدف الفعلي \(n=47\)، لا يتجاوز نصف الطول \(24\) ولا يتجاوز مجموع الأرقام \(216\)، ولذلك يكون هذا الـ DP صغيرًا جدًا مقارنة بفضاء البحث تحت \(10^{47}\).