Let \(F(n)\) denote the number of true decimal equations of the form
\[ A_1+\cdots+A_\ell = B_1+\cdots+B_r, \]
where every term is a positive integer written without leading zeros. The total length counts every digit, every plus sign, and the equality sign:
\[ |E|=\sum_{i=1}^{\ell}\operatorname{len}(A_i)+\sum_{j=1}^{r}\operatorname{len}(B_j)+(\ell-1)+(r-1)+1. \]
The problem asks for \(F(50)\bmod 10^9+7\). The implementations verify themselves against the small values
\[ F(3)=9,\qquad F(5)=171,\qquad F(7)=4878. \]
Brute force is not realistic: even before checking arithmetic, the number of possible strings explodes with the number of terms, their lengths, and all digit choices. The successful approach is to read the equation from right to left, one decimal column at a time, and count only the data that can still affect higher columns.
The key simplification is that decimal addition is local. After the low columns have been fixed, the unfinished part of the equation is determined only by the terms that still have digits left and by the carry coming from below.
A term is active in a column if it still contributes a digit in that column. If the equation has \(T=\ell+r\) total terms, then even the shortest possible equation has \(T\) digits and \(T-1\) separators, so
\[ |E|\ge 2T-1. \]
Therefore \(|E|\le 50\) implies \(T\le 25\). This is exactly the bound used by the implementations: there are never more than 25 active terms in total, and that keeps the state space finite and small.
Before any digit column is processed, the only committed characters are the separators. If there are \(\ell\) terms on the left and \(r\) on the right, the initial committed length is
\[ (\ell-1)+(r-1)+1=\ell+r-1. \]
Suppose a column begins with \(a\) active terms on one side, and exactly \(a'\le a\) of them survive to the next higher column. Then \(a-a'\) terms end in the current column, so their current digit is the leading digit of that number and must lie in \(\{1,\dots,9\}\). The surviving \(a'\) terms may contribute any digit in \(\{0,\dots,9\}\).
This gives the generating polynomial
\[ P_{a,a'}(x)=\bigl(x+x^2+\cdots+x^9\bigr)^{a-a'}\bigl(1+x+x^2+\cdots+x^9\bigr)^{a'}. \]
If we write
\[ c_{a,a'}(s)=[x^s]\,P_{a,a'}(x), \]
then \(c_{a,a'}(s)\) counts the admissible digit assignments on that side whose column sum is \(s\). Because the terms are distinguishable by their positions in the written equation, choosing which \(a'\) of the \(a\) active terms survive contributes the factor \(\binom{a}{a'}\).
Let \(L\) and \(R\) be the left and right digit sums in the current column, and let \(\delta\) be the carry entering this column from the already processed lower columns. Valid base-10 arithmetic is equivalent to
\[ L-R+\delta=10\delta', \]
where \(\delta'\) is the carry passed to the next higher column. So only differences
\[ d=L-R \]
with \(d\equiv -\delta \pmod{10}\) are feasible for the current state.
For fixed survivor counts on both sides it is convenient to precompute
\[ T_{a,a',b,b'}(d)=\sum_{s-t=d} c_{a,a'}(s)\,c_{b,b'}(t), \]
the number of digit assignments that produce column difference \(d\). This is the real combinatorial object used by the implementations: once \(T_{a,a',b,b'}(d)\) is known, the individual digit sums \(s\) and \(t\) no longer have to be revisited during the DP.
Define \(D(u,a,b,\delta)\) as the number of partially constructed equations whose lower columns are already fixed, whose committed total length is \(u\), which still have \(a\) active left terms and \(b\) active right terms, and whose carry into the current column is \(\delta\).
The initial states are
\[ D(\ell+r-1,\ell,r,0)=1 \]
for every \(\ell\ge 1\), \(r\ge 1\), \(\ell+r\le 25\). Processing one new column appends one digit for every active term, so the length update is
\[ u'=u+a+b. \]
If the next column leaves \(a'\le a\) active terms on the left and \(b'\le b\) on the right, then the transition is
\[ D(u+a+b,a',b',\delta') \;+\!=\; D(u,a,b,\delta)\binom{a}{a'}\binom{b}{b'}T_{a,a',b,b'}(d), \]
whenever \(d+\delta=10\delta'\). An equation is complete exactly when
\[ a=b=0,\qquad \delta=0, \]
so the final count is
\[ F(n)=\sum_{u=0}^{n} D(u,0,0,0). \]
At any moment there are at most 25 active terms in total, so the column difference always satisfies
\[ |L-R|\le 9\cdot 25=225. \]
If \(|\delta|\le 25\), then
\[ |\delta'|=\left|\frac{L-R+\delta}{10}\right|\le \frac{225+25}{10}=25. \]
Since the process starts with carry \(0\), every reachable carry remains inside \([-25,25]\). That is why all three implementations can use a fixed carry dimension instead of an unbounded map.
The length-5 check is a good sanity test because it already uses the same machinery as the full problem. Consider equations of the shape \(a+b=c\) with all three numbers one-digit. The separators contribute length 2, so one processed column gives total length 5. The initial state is \(D(2,2,1,0)=1\), and the only possible survivor counts are \(a'=0\), \(b'=0\).
The relevant polynomials are
\[ P_{2,0}(x)=\bigl(x+\cdots+x^9\bigr)^2,\qquad P_{1,0}(x)=x+\cdots+x^9. \]
Because the final carry must be zero, we need difference \(d=0\). For each right-hand digit \(c\in\{1,\dots,9\}\), there are exactly \(c-1\) ordered pairs \((a,b)\) with \(a+b=c\). Therefore
\[ T_{2,0,1,0}(0)=\sum_{c=2}^{9}(c-1)=36. \]
The mirrored shape \(c=a+b\) contributes another 36. Together with the 9 one-digit identities \(d=d\) and the 90 two-digit identities \(m=m\), we obtain
\[ F(5)=9+90+36+36=171, \]
which matches the checkpoint exactly.
The C++, Python, and Java implementations first build all binomial coefficients up to 25. They then compute the coefficient lists \(c_{a,a'}(s)\) for every possible pair \((a,a')\) by multiplying the nonzero-leading-digit polynomial with the unrestricted-digit polynomial.
For every quadruple \((a,a',b,b')\), the implementation combines the two one-side tables into the difference counts \(T_{a,a',b,b'}(d)\). These counts are grouped by \(d\bmod 10\), so a DP state with incoming carry \(\delta\) only has to inspect the compatible residue class \(d\equiv -\delta \pmod{10}\). This is the reason the transition step stays compact.
The DP starts from every admissible split of the total terms between the two sides. States are processed in increasing committed length. Each update chooses survivor counts, multiplies by the corresponding binomial factors, reads the precomputed difference table, computes the next carry \((d+\delta)/10\), and adds the contribution to the state with length \(u+a+b\). After the sweep finishes, the answer is the sum of all completed states with length at most \(n\). The three implementations follow this same recurrence; the C++ version can additionally spread part of the preprocessing across multiple worker threads.
The decisive fact is that \(|E|\le 50\) forces at most 25 total terms and only 51 possible carry values. The DP storage therefore has \((n+1)(26)(26)(51)\) slots; for \(n=50\) this is about \(1.76\times 10^6\) entries, and many of them are unreachable because \(a+b\le 25\).
The main work is the sweep over reachable states together with all survivor choices \((a',b')\) and the short precomputed lists of feasible differences in the matching residue class. Memory usage is linear in the number of stored states plus the finite family of difference tables. In practice this is fast because the algorithm never enumerates actual equation strings; it counts them indirectly through column sums, carries, and survivor sets.
Sei \(F(n)\) die Anzahl aller wahren Dezimalgleichungen der Form
\[ A_1+\cdots+A_\ell = B_1+\cdots+B_r, \]
wobei jeder Summand eine positive ganze Zahl ohne führende Nullen ist. Zur Gesamtlänge zählen alle Ziffern, alle Pluszeichen und das Gleichheitszeichen:
\[ |E|=\sum_{i=1}^{\ell}\operatorname{len}(A_i)+\sum_{j=1}^{r}\operatorname{len}(B_j)+(\ell-1)+(r-1)+1. \]
Gesucht ist \(F(50)\bmod 10^9+7\). Die Implementierungen prüfen sich an den Werten
\[ F(3)=9,\qquad F(5)=171,\qquad F(7)=4878. \]
Eine direkte Enumeration aller möglichen Zeichenketten ist hoffnungslos. Die Lösung betrachtet die Gleichung stattdessen spaltenweise von rechts nach links und speichert nur diejenigen Informationen, die für die höheren Stellen noch relevant sind.
Die entscheidende Beobachtung lautet: Dezimale Addition ist lokal. Wenn die niedrigeren Stellen bereits feststehen, hängt die Zukunft nur noch davon ab, wie viele Summanden auf jeder Seite noch aktiv sind und welcher Übertrag aus den bereits verarbeiteten Stellen ankommt.
Ein Term ist in einer Spalte aktiv, wenn er dort noch eine Ziffer besitzt. Hat die Gleichung insgesamt \(T=\ell+r\) Terme, dann hat selbst die kürzeste mögliche Gleichung \(T\) Ziffern und \(T-1\) Trennzeichen. Also gilt
\[ |E|\ge 2T-1. \]
Aus \(|E|\le 50\) folgt daher \(T\le 25\). Genau diese Schranke verwenden die Programme: Mehr als 25 aktive Terme zusammen kann es nie geben.
Bevor überhaupt eine Ziffernspalte verarbeitet wird, stehen nur die Trennzeichen fest. Für \(\ell\) linke und \(r\) rechte Terme ist die anfänglich festgelegte Länge
\[ (\ell-1)+(r-1)+1=\ell+r-1. \]
Nehmen wir an, eine Spalte beginnt auf einer Seite mit \(a\) aktiven Termen, und genau \(a'\le a\) davon leben in der nächsten höheren Spalte weiter. Dann enden \(a-a'\) Terme in der aktuellen Spalte; ihre momentane Ziffer ist also die führende Ziffer ihrer Zahl und muss in \(\{1,\dots,9\}\) liegen. Die \(a'\) weiterlaufenden Terme dürfen jede Ziffer aus \(\{0,\dots,9\}\) beitragen.
Damit ergibt sich das erzeugende Polynom
\[ P_{a,a'}(x)=\bigl(x+x^2+\cdots+x^9\bigr)^{a-a'}\bigl(1+x+x^2+\cdots+x^9\bigr)^{a'}. \]
Mit
\[ c_{a,a'}(s)=[x^s]\,P_{a,a'}(x) \]
zählt man die zulässigen Ziffernbelegungen dieser Seite mit Spaltensumme \(s\). Da die Terme durch ihre Position in der Gleichung unterscheidbar sind, liefert die Wahl der \(a'\) Überlebenden den Faktor \(\binom{a}{a'}\).
Seien \(L\) und \(R\) die linken bzw. rechten Ziffernsummen der aktuellen Spalte, und sei \(\delta\) der Übertrag aus den bereits verarbeiteten niedrigeren Stellen. Korrekte Dezimalarithmetik ist genau die Bedingung
\[ L-R+\delta=10\delta', \]
wobei \(\delta'\) der Übertrag in die nächste höhere Spalte ist. Also sind nur Differenzen
\[ d=L-R \]
mit \(d\equiv -\delta \pmod{10}\) möglich.
Für feste Überlebenszahlen auf beiden Seiten ist es praktisch, die Größe
\[ T_{a,a',b,b'}(d)=\sum_{s-t=d} c_{a,a'}(s)\,c_{b,b'}(t) \]
vorab zu berechnen. Sie zählt, wie viele Ziffernbelegungen genau die Differenz \(d\) erzeugen. Genau diese Tabellen bilden den Kern der Implementierungen.
Definiere \(D(u,a,b,\delta)\) als die Anzahl partiell konstruierter Gleichungen, bei denen die niedrigeren Stellen bereits festgelegt sind, die bisher festgeschriebene Gesamtlänge \(u\) beträgt, links noch \(a\) und rechts noch \(b\) aktive Terme vorhanden sind und der aktuelle Spaltenübertrag \(\delta\) lautet.
Die Anfangszustände sind
\[ D(\ell+r-1,\ell,r,0)=1 \]
für alle \(\ell\ge 1\), \(r\ge 1\), \(\ell+r\le 25\). Eine weitere Spalte fügt für jeden aktiven Term genau eine Ziffer hinzu, also
\[ u'=u+a+b. \]
Bleiben in der nächsten Spalte links \(a'\le a\) und rechts \(b'\le b\) Terme aktiv, so lautet der Übergang
\[ D(u+a+b,a',b',\delta') \;+\!=\; D(u,a,b,\delta)\binom{a}{a'}\binom{b}{b'}T_{a,a',b,b'}(d), \]
wenn \(d+\delta=10\delta'\) gilt. Eine Gleichung ist genau dann vollständig, wenn
\[ a=b=0,\qquad \delta=0, \]
also
\[ F(n)=\sum_{u=0}^{n} D(u,0,0,0). \]
Zu jedem Zeitpunkt gibt es insgesamt höchstens 25 aktive Terme. Daher gilt stets
\[ |L-R|\le 9\cdot 25=225. \]
Ist \(|\delta|\le 25\), dann folgt
\[ |\delta'|=\left|\frac{L-R+\delta}{10}\right|\le \frac{225+25}{10}=25. \]
Da der Prozess mit Übertrag 0 startet, bleiben alle erreichbaren Überträge innerhalb dieses festen Fensters. Deshalb reicht eine kleine, feste Übertragsdimension.
Die Kontrolle für Länge 5 zeigt die Methode bereits im Kleinen. Betrachte Gleichungen der Form \(a+b=c\), bei denen alle drei Zahlen einstellig sind. Die Trennzeichen liefern Länge 2, eine verarbeitete Ziffernspalte bringt Gesamtlänge 5. Der Startzustand ist \(D(2,2,1,0)=1\), und möglich sind nur \(a'=0\), \(b'=0\).
Die zugehörigen Polynome sind
\[ P_{2,0}(x)=\bigl(x+\cdots+x^9\bigr)^2,\qquad P_{1,0}(x)=x+\cdots+x^9. \]
Da der Endübertrag verschwinden muss, brauchen wir die Differenz \(d=0\). Für jede rechte Ziffer \(c\in\{1,\dots,9\}\) gibt es genau \(c-1\) geordnete Paare \((a,b)\) mit \(a+b=c\). Also ist
\[ T_{2,0,1,0}(0)=\sum_{c=2}^{9}(c-1)=36. \]
Die gespiegelte Form \(c=a+b\) liefert weitere 36. Zusammen mit den 9 einstelligen Identitäten \(d=d\) und den 90 zweistelligen Identitäten \(m=m\) erhält man
\[ F(5)=9+90+36+36=171, \]
genau wie in den Prüfwerten.
Die C++-, Python- und Java-Implementierungen berechnen zuerst alle Binomialkoeffizienten bis 25 vor. Danach erzeugen sie für jedes Paar \((a,a')\) die Koeffizientenlisten \(c_{a,a'}(s)\), also die Ziffernsummenverteilungen einer einzelnen Seite.
Für jedes Tupel \((a,a',b,b')\) werden die beiden Ein-Seiten-Tabellen zu den Differenzzahlen \(T_{a,a',b,b'}(d)\) kombiniert. Diese Werte werden nach \(d\bmod 10\) gruppiert, sodass ein Zustand mit Übertrag \(\delta\) nur die kompatible Restklasse \(d\equiv -\delta \pmod{10}\) durchsuchen muss.
Die Dynamik startet mit allen zulässigen Aufteilungen der Gesamttermzahl auf linke und rechte Seite. Danach werden die Zustände in aufsteigender festgelegter Länge verarbeitet. Jeder Übergang wählt Überlebende, multipliziert mit den passenden Binomialfaktoren, liest die vorberechnete Differenzzahl ab, bestimmt den neuen Übertrag \((d+\delta)/10\) und addiert den Beitrag zum Zustand mit Länge \(u+a+b\). Nach Abschluss des Durchlaufs wird über alle vollständigen Zustände mit Länge höchstens \(n\) summiert. Die drei Sprachen verwenden dieselbe Rekurrenz; die C++-Version kann einen Teil der Vorberechnung zusätzlich auf mehrere Worker verteilen.
Die entscheidende Schranke ist \(T\le 25\). Damit besitzt der DP-Speicher \((n+1)\cdot 26\cdot 26\cdot 51\) Plätze; für \(n=50\) sind das ungefähr \(1{,}76\times 10^6\) Einträge, wobei wegen \(a+b\le 25\) viele davon nie erreicht werden.
Der Hauptaufwand liegt im Durchlauf über die erreichbaren Zustände, die möglichen Überlebenszahlen \((a',b')\) und die kurzen vorberechneten Listen zulässiger Differenzen in der passenden Restklasse. Der Speicherverbrauch ist linear in der Zahl der Zustände plus den endlich vielen Differenztabellen. Praktisch ist das schnell, weil nicht echte Gleichungszeichenketten erzeugt werden, sondern nur Summenverteilungen und Überträge gezählt werden.
\(F(n)\),
\[ A_1+\cdots+A_\ell = B_1+\cdots+B_r \]
biçimindeki doğru onluk eşitliklerin sayısı olsun. Burada her terim, başında sıfır bulunmayan pozitif bir tamsayıdır. Toplam uzunluk bütün rakamları, bütün artı işaretlerini ve eşittir işaretini birlikte sayar:
\[ |E|=\sum_{i=1}^{\ell}\operatorname{len}(A_i)+\sum_{j=1}^{r}\operatorname{len}(B_j)+(\ell-1)+(r-1)+1. \]
İstenen büyüklük \(F(50)\bmod 10^9+7\)'dir. Uygulamalar şu küçük değerlerle doğrulanır:
\[ F(3)=9,\qquad F(5)=171,\qquad F(7)=4878. \]
Doğrudan kaba kuvvet uygun değildir; çünkü hem terim sayıları hem de terim uzunlukları hızla dallanır. Doğru bakış açısı, eşitliği en sağ sütundan başlayarak basamak basamak kurmak ve yalnızca üst basamakları etkileyebilecek bilgileri taşımaktır.
Temel sadeleşme şudur: onluk toplama yereldir. Alt basamaklar sabitlendiğinde, geriye kalan kısmı belirleyen tek şey her iki tarafta hâlâ kaç terimin “yaşadığı” ve alttan gelen eldenin değeri olur.
Bir terim, içinde bulunulan sütunda hâlâ bir rakam veriyorsa o sütunda aktiftir. Toplam terim sayısı \(T=\ell+r\) olsun. En kısa denklem bile \(T\) rakam ve \(T-1\) ayırıcı içerir; dolayısıyla
\[ |E|\ge 2T-1. \]
Buradan \(|E|\le 50\) için \(T\le 25\) çıkar. Kodun kullandığı 25 sınırı tam olarak budur: solda ve sağda birlikte hiçbir zaman 25'ten fazla aktif terim olamaz.
Daha hiçbir rakam sütunu işlenmeden önce sabit olan tek karakterler ayırıcılardır. Solda \(\ell\), sağda \(r\) terim varsa başlangıçta kesinleşmiş uzunluk
\[ (\ell-1)+(r-1)+1=\ell+r-1 \]
olur.
Bir sütun, bir tarafta \(a\) aktif terimle başlasın ve bunların tam \(a'\le a\) tanesi bir sonraki daha anlamlı basamağa taşınsın. O zaman \(a-a'\) terim bu sütunda bitiyor demektir; dolayısıyla verdikleri rakam kendi sayılarının en soldaki rakamıdır ve \(\{1,\dots,9\}\) içinde olmak zorundadır. Hayatta kalan \(a'\) terim ise \(\{0,\dots,9\}\) içinden herhangi bir rakam verebilir.
Buna karşılık gelen üretici polinom
\[ P_{a,a'}(x)=\bigl(x+x^2+\cdots+x^9\bigr)^{a-a'}\bigl(1+x+x^2+\cdots+x^9\bigr)^{a'} \]
olur. Eğer
\[ c_{a,a'}(s)=[x^s]\,P_{a,a'}(x) \]
yazarsak, \(c_{a,a'}(s)\) o taraftaki rakam atamalarından sütun toplamı \(s\) verenlerin sayısını gösterir. Terimler denklem içindeki konumlarıyla ayırt edildiği için, hangi \(a'\) terimlerin hayatta kalacağını seçmenin çarpanı da \(\binom{a}{a'}\) olur.
Mevcut sütunda soldaki rakam toplamı \(L\), sağdaki rakam toplamı \(R\), alttan gelen elde \(\delta\) olsun. Onluk aritmetiğin doğru olması için
\[ L-R+\delta=10\delta' \]
olmalıdır; burada \(\delta'\) bir üst sütuna giden yeni eldedir. Yani yalnızca
\[ d=L-R \]
farkının \(d\equiv -\delta \pmod{10}\) koşulunu sağladığı durumlar mümkündür.
Sabit kalan-terim sayıları için
\[ T_{a,a',b,b'}(d)=\sum_{s-t=d} c_{a,a'}(s)\,c_{b,b'}(t) \]
tanımını yapmak kullanışlıdır. Bu nicelik, ilgili sütunda farkı tam olarak \(d\) yapan rakam atamalarının sayısını verir. Çözümlerin gerçekten önceden hazırladığı tablolar tam olarak bunlardır.
\(D(u,a,b,\delta)\), alt sütunları çoktan sabitlenmiş, toplam sabitlenmiş uzunluğu \(u\) olan, solda \(a\) ve sağda \(b\) aktif terim barındıran ve mevcut sütuna \(\delta\) eldesiyle giren kısmi denklemlerin sayısı olsun.
Başlangıç durumları
\[ D(\ell+r-1,\ell,r,0)=1 \]
şeklindedir; burada \(\ell\ge 1\), \(r\ge 1\), \(\ell+r\le 25\). Yeni bir sütun işlendiğinde her aktif terim tam bir rakam eklediği için uzunluk
\[ u'=u+a+b \]
olur. Bir sonraki sütunda solda \(a'\le a\), sağda \(b'\le b\) terim kalıyorsa geçiş
\[ D(u+a+b,a',b',\delta') \;+\!=\; D(u,a,b,\delta)\binom{a}{a'}\binom{b}{b'}T_{a,a',b,b'}(d) \]
biçimindedir; yeter ki \(d+\delta=10\delta'\) olsun. Bir denklem ancak
\[ a=b=0,\qquad \delta=0 \]
durumunda tamamlanır. Dolayısıyla
\[ F(n)=\sum_{u=0}^{n} D(u,0,0,0) \]
elde edilir.
Her anda toplam en fazla 25 aktif terim bulunduğundan sütun farkı için
\[ |L-R|\le 9\cdot 25=225 \]
geçerlidir. Eğer \(|\delta|\le 25\) ise
\[ |\delta'|=\left|\frac{L-R+\delta}{10}\right|\le \frac{225+25}{10}=25 \]
olur. Süreç \(\delta=0\) ile başladığı için erişilebilir bütün elde değerleri bu sabit pencerenin içinde kalır.
Uzunluğu 5 olan kontrol değeri aynı mekanizmanın küçük bir örneğidir. Bütün sayıları tek basamaklı olan \(a+b=c\) biçimindeki eşitlikleri düşünelim. Ayırıcılar uzunluğa 2 katkı yapar; tek sütun işlendiğinde toplam uzunluk 5 olur. Başlangıç durumu \(D(2,2,1,0)=1\)'dir ve mümkün olan tek kalan sayıları \(a'=0\), \(b'=0\)'dır.
Gerekli polinomlar
\[ P_{2,0}(x)=\bigl(x+\cdots+x^9\bigr)^2,\qquad P_{1,0}(x)=x+\cdots+x^9 \]
şeklindedir. Son eldenin sıfır olması gerektiğinden \(d=0\) farkını isteriz. Sağ taraftaki rakam \(c\in\{1,\dots,9\}\) için \(a+b=c\) eşitliğini sağlayan sıralı \((a,b)\) çiftlerinin sayısı tam \(c-1\)'dir. Bu yüzden
\[ T_{2,0,1,0}(0)=\sum_{c=2}^{9}(c-1)=36 \]
olur. Ayna görüntüsü olan \(c=a+b\) biçimi de 36 katkı verir. Buna 9 adet \(d=d\) eşitliği ve 90 adet iki basamaklı \(m=m\) özdeşliği eklenince
\[ F(5)=9+90+36+36=171 \]
elde edilir; bu da kontrol değeriyle tam uyuşur.
C++, Python ve Java uygulamaları önce 25'e kadar bütün binom katsayılarını üretir. Ardından her \((a,a')\) çifti için tek taraflı sütun-toplam katsayılarını, yani \(c_{a,a'}(s)\) dizilerini hesaplar.
Her \((a,a',b,b')\) dörtlüsü için iki tarafın tabloları birleştirilip \(T_{a,a',b,b'}(d)\) fark sayıları çıkarılır. Bu sayılar \(d\bmod 10\) değerine göre gruplanır. Böylece elde değeri \(\delta\) olan bir durum, yalnızca \(d\equiv -\delta \pmod{10}\) sınıfındaki farklara bakar; imkansız farklar hiç dolaşılmaz.
Dinamik programlama, toplam terim sayısının iki tarafa bütün geçerli dağılımlarıyla başlatılır. Sonra durumlar sabitlenmiş uzunluğa göre artan sırada işlenir. Her güncellemede kalan terim sayıları seçilir, binom çarpanları uygulanır, hazır fark tablosundan uygun değer okunur, yeni elde \((d+\delta)/10\) hesaplanır ve katkı uzunluğu \(u+a+b\) olan yeni duruma eklenir. En sonda uzunluğu \(n\)'i aşmayan bütün tamamlanmış durumlar toplanır. Üç dildeki uygulamalar aynı reküransı uygular; C++ sürümü isterse ön işlemenin bir kısmını birden fazla iş parçacığına paylaştırabilir.
Belirleyici sınır \(T\le 25\) olmasıdır. Bu yüzden DP depolaması \((n+1)\cdot 26\cdot 26\cdot 51\) hücre içerir; \(n=50\) için bu yaklaşık \(1.76\times 10^6\) giriş eder. Ayrıca \(a+b\le 25\) koşulu yüzünden bu hücrelerin önemli bir kısmı hiç dolmaz.
Asıl maliyet, erişilebilir durumlar üzerinden geçmek, bütün \(a',b'\) seçimlerini denemek ve uygun artık sınıfındaki kısa fark listelerini dolaşmaktır. Bellek kullanımı durum sayısı artı sonlu sayıdaki fark tablosuyla doğrusal kalır. Pratikte yöntem hızlıdır; çünkü gerçek denklem dizgilerini tek tek üretmek yerine, sütun toplamlarını ve elde geçişlerini sayar.
Sea \(F(n)\) el número de identidades decimales verdaderas de la forma
\[ A_1+\cdots+A_\ell = B_1+\cdots+B_r, \]
donde cada término es un entero positivo escrito sin ceros iniciales. La longitud total cuenta todos los dígitos, todos los signos de suma y el signo de igualdad:
\[ |E|=\sum_{i=1}^{\ell}\operatorname{len}(A_i)+\sum_{j=1}^{r}\operatorname{len}(B_j)+(\ell-1)+(r-1)+1. \]
La tarea es calcular \(F(50)\bmod 10^9+7\). Las implementaciones se comprueban con
\[ F(3)=9,\qquad F(5)=171,\qquad F(7)=4878. \]
Probar todas las cadenas posibles sería inviable. La idea correcta es construir la igualdad columna por columna, de derecha a izquierda, y conservar solo la información que todavía puede influir en las columnas superiores.
La simplificación decisiva es que la suma decimal es local. Una vez fijadas las columnas bajas, el resto de la ecuación queda resumido por cuántos términos siguen activos en cada lado y por el acarreo que llega desde abajo.
Un término es activo en una columna si todavía aporta un dígito en esa columna. Si la igualdad tiene \(T=\ell+r\) términos en total, incluso la forma más corta posible contiene \(T\) dígitos y \(T-1\) separadores. Por tanto,
\[ |E|\ge 2T-1. \]
De \(|E|\le 50\) se obtiene \(T\le 25\). Esa es exactamente la cota que usan las implementaciones: nunca puede haber más de 25 términos activos entre ambos lados.
Antes de procesar ninguna columna de dígitos, solo están fijados los separadores. Si hay \(\ell\) términos a la izquierda y \(r\) a la derecha, la longitud comprometida al inicio es
\[ (\ell-1)+(r-1)+1=\ell+r-1. \]
Supongamos que una columna empieza con \(a\) términos activos en un lado y que exactamente \(a'\le a\) de ellos sobreviven a la siguiente columna más significativa. Entonces \(a-a'\) términos terminan aquí, así que su dígito actual es el primer dígito de su número y debe pertenecer a \(\{1,\dots,9\}\). Los \(a'\) que continúan pueden aportar cualquier dígito de \(\{0,\dots,9\}\).
Eso produce el polinomio generador
\[ P_{a,a'}(x)=\bigl(x+x^2+\cdots+x^9\bigr)^{a-a'}\bigl(1+x+x^2+\cdots+x^9\bigr)^{a'}. \]
Si definimos
\[ c_{a,a'}(s)=[x^s]\,P_{a,a'}(x), \]
entonces \(c_{a,a'}(s)\) cuenta las asignaciones admisibles de dígitos con suma de columna \(s\). Como los términos se distinguen por su posición escrita en la ecuación, elegir qué \(a'\) términos continúan aporta el factor \(\binom{a}{a'}\).
Sean \(L\) y \(R\) las sumas de dígitos de la columna en los lados izquierdo y derecho, y sea \(\delta\) el acarreo que entra desde las columnas ya procesadas. La condición exacta de la aritmética decimal es
\[ L-R+\delta=10\delta', \]
donde \(\delta'\) es el acarreo que pasa a la columna siguiente. Así, solo son posibles las diferencias
\[ d=L-R \]
que satisfacen \(d\equiv -\delta \pmod{10}\).
Para números de supervivientes fijados en ambos lados, resulta útil definir
\[ T_{a,a',b,b'}(d)=\sum_{s-t=d} c_{a,a'}(s)\,c_{b,b'}(t), \]
que cuenta cuántas asignaciones de dígitos producen diferencia \(d\). Este es el objeto combinatorio que realmente precalcula la implementación.
Sea \(D(u,a,b,\delta)\) el número de ecuaciones parcialmente construidas cuyas columnas bajas ya están fijadas, cuya longitud comprometida es \(u\), con \(a\) términos activos a la izquierda, \(b\) a la derecha y acarreo entrante \(\delta\) para la columna actual.
Los estados iniciales son
\[ D(\ell+r-1,\ell,r,0)=1 \]
para todos \(\ell\ge 1\), \(r\ge 1\), \(\ell+r\le 25\). Al procesar una columna nueva se añade un dígito por cada término activo, así que
\[ u'=u+a+b. \]
Si la siguiente columna deja \(a'\le a\) términos activos a la izquierda y \(b'\le b\) a la derecha, la transición es
\[ D(u+a+b,a',b',\delta') \;+\!=\; D(u,a,b,\delta)\binom{a}{a'}\binom{b}{b'}T_{a,a',b,b'}(d), \]
siempre que \(d+\delta=10\delta'\). Una ecuación termina exactamente cuando
\[ a=b=0,\qquad \delta=0, \]
de modo que
\[ F(n)=\sum_{u=0}^{n} D(u,0,0,0). \]
En cualquier columna hay como máximo 25 términos activos en total, luego
\[ |L-R|\le 9\cdot 25=225. \]
Si \(|\delta|\le 25\), entonces
\[ |\delta'|=\left|\frac{L-R+\delta}{10}\right|\le \frac{225+25}{10}=25. \]
Como el proceso empieza con \(\delta=0\), todos los acarreos alcanzables quedan dentro de esa ventana fija.
La verificación de longitud 5 ya muestra toda la idea. Consideremos igualdades del tipo \(a+b=c\) en las que los tres números tienen una sola cifra. Los separadores aportan longitud 2, así que una sola columna procesada lleva a longitud total 5. El estado inicial es \(D(2,2,1,0)=1\), y necesariamente \(a'=0\), \(b'=0\).
Los polinomios relevantes son
\[ P_{2,0}(x)=\bigl(x+\cdots+x^9\bigr)^2,\qquad P_{1,0}(x)=x+\cdots+x^9. \]
Como el acarreo final debe ser cero, necesitamos diferencia \(d=0\). Para cada dígito derecho \(c\in\{1,\dots,9\}\), hay exactamente \(c-1\) pares ordenados \((a,b)\) con \(a+b=c\). Por tanto,
\[ T_{2,0,1,0}(0)=\sum_{c=2}^{9}(c-1)=36. \]
La forma simétrica \(c=a+b\) aporta otros 36. Sumando además las 9 identidades de una cifra \(d=d\) y las 90 identidades de dos cifras \(m=m\), obtenemos
\[ F(5)=9+90+36+36=171, \]
exactamente el valor de control.
Las implementaciones en C++, Python y Java construyen primero todos los coeficientes binomiales hasta 25. Después generan, para cada par \((a,a')\), las listas de coeficientes \(c_{a,a'}(s)\) que describen las sumas posibles de una sola cara de la columna.
Para cada cuádrupla \((a,a',b,b')\), la implementación combina las dos tablas de un solo lado y obtiene los conteos \(T_{a,a',b,b'}(d)\). Esos conteos se agrupan por \(d\bmod 10\), de modo que un estado con acarreo \(\delta\) solo consulta la clase compatible \(d\equiv -\delta \pmod{10}\).
El DP se inicializa con todas las distribuciones válidas del número total de términos entre ambos lados. Luego procesa los estados por longitud comprometida creciente. Cada actualización elige cuántos términos sobreviven, aplica los factores binomiales, lee el conteo precalculado de diferencias, calcula el siguiente acarreo \((d+\delta)/10\) y suma la contribución al estado de longitud \(u+a+b\). Al final se suman todos los estados completos con longitud a lo sumo \(n\). Las tres versiones implementan la misma recurrencia; la versión en C++ también puede repartir parte del precálculo entre varios trabajadores.
La cota decisiva es \(T\le 25\). Por eso el almacenamiento del DP tiene \((n+1)\cdot 26\cdot 26\cdot 51\) posiciones; para \(n=50\) eso es aproximadamente \(1.76\times 10^6\) entradas, y muchas de ellas permanecen en cero porque siempre se cumple \(a+b\le 25\).
El trabajo principal está en recorrer los estados alcanzables, considerar todas las elecciones de supervivientes \((a',b')\) y usar las listas precalculadas de diferencias viables en la clase residual adecuada. La memoria es lineal en el número de estados almacenados más la familia finita de tablas de diferencias. En la práctica el método es rápido porque nunca enumera ecuaciones como cadenas completas; cuenta distribuciones de sumas por columna y acarreos.
设 \(F(n)\) 表示所有正确十进制等式
\[ A_1+\cdots+A_\ell = B_1+\cdots+B_r \]
的个数，其中每一项都是没有前导零的正整数。总长度要把所有数字、所有加号以及等号一起算进去：
\[ |E|=\sum_{i=1}^{\ell}\operatorname{len}(A_i)+\sum_{j=1}^{r}\operatorname{len}(B_j)+(\ell-1)+(r-1)+1. \]
题目要求计算 \(F(50)\bmod 10^9+7\)。实现中用以下小规模结果做校验：
\[ F(3)=9,\qquad F(5)=171,\qquad F(7)=4878. \]
直接枚举所有可能的字符串完全不可行，因为项数、每一项的位数以及具体数字都会带来巨大的组合爆炸。真正有效的方法是像手算加法那样，从最低位开始逐列处理，只保留会影响更高位的信息。
核心简化在于：十进制加法是局部的。当低位已经确定以后，尚未完成的部分只由两类信息决定：左右两边还有多少项在当前列仍然“活着”，以及从更低列传上来的进位是多少。
如果某一项在当前列还有一个未处理的数字，那么它在这一列就是活跃的。设等式总共有 \(T=\ell+r\) 项。即使取最短情况，每一项至少贡献 1 个数字，同时还需要 \(T-1\) 个分隔符，因此有
\[ |E|\ge 2T-1. \]
于是由 \(|E|\le 50\) 可知 \(T\le 25\)。这正是实现里使用的关键上界：任意时刻左右两边活跃项总数都不会超过 25。
在尚未处理任何数字列之前，已经固定的只有分隔符。如果左边有 \(\ell\) 项，右边有 \(r\) 项，那么初始时已经计入的长度是
\[ (\ell-1)+(r-1)+1=\ell+r-1. \]
设某一侧当前列开始时有 \(a\) 个活跃项，其中恰好有 \(a'\le a\) 个会延续到更高一列。这样就有 \(a-a'\) 个项在当前列结束；它们这一位就是该数的最高位，因此必须属于 \(\{1,\dots,9\}\)。另外 \(a'\) 个继续存在的项这一位可以是 \(\{0,\dots,9\}\) 中的任意数字。
因此得到生成多项式
\[ P_{a,a'}(x)=\bigl(x+x^2+\cdots+x^9\bigr)^{a-a'}\bigl(1+x+x^2+\cdots+x^9\bigr)^{a'}. \]
记
\[ c_{a,a'}(s)=[x^s]\,P_{a,a'}(x), \]
则 \(c_{a,a'}(s)\) 就是这一侧当前列数字和为 \(s\) 的合法赋值个数。由于各项在书写顺序上是可区分的，所以从 \(a\) 个活跃项中选出哪 \(a'\) 个继续存在，还要乘上组合因子 \(\binom{a}{a'}\)。
设当前列左边数字和为 \(L\)，右边数字和为 \(R\)，从更低位传来的进位为 \(\delta\)。十进制运算正确当且仅当
\[ L-R+\delta=10\delta', \]
其中 \(\delta'\) 是传向更高一列的进位。于是只有差值
\[ d=L-R \]
满足 \(d\equiv -\delta \pmod{10}\) 时才可能出现。
对固定的左右存活数，定义
\[ T_{a,a',b,b'}(d)=\sum_{s-t=d} c_{a,a'}(s)\,c_{b,b'}(t), \]
它表示在这一列里产生差值 \(d\) 的数字赋值数量。实现真正预处理的正是这些差值表：有了它们之后，DP 中就不需要再逐个枚举左右列和。
令 \(D(u,a,b,\delta)\) 表示部分构造完成的等式个数，其中低位列已经全部确定，当前已计入的总长度为 \(u\)，左边还有 \(a\) 个活跃项，右边还有 \(b\) 个活跃项，并且当前列接收到的进位为 \(\delta\)。
初始状态为
\[ D(\ell+r-1,\ell,r,0)=1 \]
其中 \(\ell\ge 1\)、\(r\ge 1\)、\(\ell+r\le 25\)。处理一列时，每个活跃项都会再贡献 1 个数字，因此长度更新为
\[ u'=u+a+b. \]
如果下一列左边剩下 \(a'\le a\) 个活跃项，右边剩下 \(b'\le b\) 个，那么转移就是
\[ D(u+a+b,a',b',\delta') \;+\!=\; D(u,a,b,\delta)\binom{a}{a'}\binom{b}{b'}T_{a,a',b,b'}(d), \]
前提是 \(d+\delta=10\delta'\)。一个等式恰好在
\[ a=b=0,\qquad \delta=0 \]
时完成，因此答案为
\[ F(n)=\sum_{u=0}^{n} D(u,0,0,0). \]
任意时刻活跃项总数最多为 25，所以列差值总满足
\[ |L-R|\le 9\cdot 25=225. \]
如果 \(|\delta|\le 25\)，那么
\[ |\delta'|=\left|\frac{L-R+\delta}{10}\right|\le \frac{225+25}{10}=25. \]
又因为过程从 \(\delta=0\) 开始，所以所有可达的进位都会始终落在这个固定区间内。这就是实现能够使用固定进位维度的原因。
长度为 5 的校验值已经能完整展示这套方法。考虑所有形如 \(a+b=c\) 的等式，其中三个数都只有一位。分隔符本身占去长度 2，处理一列数字后总长度正好变成 5。初始状态是 \(D(2,2,1,0)=1\)，而且只能取 \(a'=0\)、\(b'=0\)。
对应的多项式是
\[ P_{2,0}(x)=\bigl(x+\cdots+x^9\bigr)^2,\qquad P_{1,0}(x)=x+\cdots+x^9. \]
因为最终进位必须是 0，所以需要差值 \(d=0\)。对右侧数字 \(c\in\{1,\dots,9\}\)，满足 \(a+b=c\) 的有序数对 \((a,b)\) 恰好有 \(c-1\) 个，因此
\[ T_{2,0,1,0}(0)=\sum_{c=2}^{9}(c-1)=36. \]
镜像形式 \(c=a+b\) 再贡献 36。再加上 9 个一位恒等式 \(d=d\) 和 90 个两位恒等式 \(m=m\)，就得到
\[ F(5)=9+90+36+36=171, \]
与校验值完全一致。
C++、Python 和 Java 三个实现都会先预计算到 25 为止的二项式系数。接着，它们为每个 \((a,a')\) 生成单侧列和系数表 \(c_{a,a'}(s)\)，把“哪些项结束、哪些项继续”和“这一列数字之和是多少”分开处理。
对于每个四元组 \((a,a',b,b')\)，实现把左右两侧的列和表合并成差值计数 \(T_{a,a',b,b'}(d)\)。这些计数再按 \(d\bmod 10\) 分组。这样，当某个 DP 状态的当前进位是 \(\delta\) 时，只需要查看满足 \(d\equiv -\delta \pmod{10}\) 的那一组即可。
DP 从所有合法的左右项数分配出发，初始长度等于分隔符数量。随后按已确定长度递增的顺序处理状态。每一步都会选择下一列要保留下来的活跃项数，乘上对应的组合因子，读取预处理好的差值计数，计算新的进位 \((d+\delta)/10\)，并把贡献加入长度为 \(u+a+b\) 的下一状态。遍历结束后，把所有长度不超过 \(n\) 且已经完成的状态加总，就是最终结果。三个实现使用同一条递推；C++ 版本还可以把部分预处理分配到多个工作线程上。
最关键的约束是 \(T\le 25\)。因此 DP 存储规模为 \((n+1)\cdot 26\cdot 26\cdot 51\)；在 \(n=50\) 时大约是 \(1.76\times 10^6\) 个槽位，而且由于始终满足 \(a+b\le 25\)，其中很多槽位根本不会被访问到。
主要时间开销来自遍历所有可达状态、枚举存活数 \((a',b')\)，以及扫描匹配余数类中的短差值列表。内存开销与状态数和有限个差值表线性相关。实际运行速度很舒服，因为算法从不枚举完整等式字符串，而是通过列和分布与进位来间接计数。
Пусть \(F(n)\) обозначает число верных десятичных тождеств вида
\[ A_1+\cdots+A_\ell = B_1+\cdots+B_r, \]
где каждый член является положительным целым числом без ведущих нулей. В полную длину входят все цифры, все знаки плюса и знак равенства:
\[ |E|=\sum_{i=1}^{\ell}\operatorname{len}(A_i)+\sum_{j=1}^{r}\operatorname{len}(B_j)+(\ell-1)+(r-1)+1. \]
Нужно вычислить \(F(50)\bmod 10^9+7\). Реализации проверяют себя на значениях
\[ F(3)=9,\qquad F(5)=171,\qquad F(7)=4878. \]
Полный перебор невозможен: слишком быстро растёт число вариантов числа слагаемых, их длин и самих цифр. Рабочая идея состоит в том, чтобы читать равенство справа налево, по одному десятичному разряду, и запоминать только ту информацию, которая ещё влияет на старшие разряды.
Главное упрощение такое: десятичное сложение локально. После того как младшие разряды уже зафиксированы, всё, что важно для продолжения, это количество ещё активных членов слева и справа и перенос, пришедший снизу.
Слагаемое называется активным в данном столбце, если оно ещё содержит цифру в этом разряде. Если всего в равенстве \(T=\ell+r\) членов, то даже самое короткое возможное равенство имеет \(T\) цифр и \(T-1\) разделителей. Поэтому
\[ |E|\ge 2T-1. \]
Из условия \(|E|\le 50\) сразу следует \(T\le 25\). Именно эта граница и используется в программах: суммарное число активных членов никогда не превосходит 25.
До обработки первой цифровой колонки уже известны только разделители. Если слева \(\ell\) членов, а справа \(r\), то начальная зафиксированная длина равна
\[ (\ell-1)+(r-1)+1=\ell+r-1. \]
Пусть в некотором столбце на одной стороне активно \(a\) членов, и ровно \(a'\le a\) из них переходят в следующий, более старший разряд. Тогда \(a-a'\) членов заканчиваются в текущем столбце, а их текущая цифра является старшей цифрой соответствующего числа и обязана лежать в \(\{1,\dots,9\}\). У продолжающихся \(a'\) членов цифра может быть любой из \(\{0,\dots,9\}\).
Отсюда получается производящий полином
\[ P_{a,a'}(x)=\bigl(x+x^2+\cdots+x^9\bigr)^{a-a'}\bigl(1+x+x^2+\cdots+x^9\bigr)^{a'}. \]
Если обозначить
\[ c_{a,a'}(s)=[x^s]\,P_{a,a'}(x), \]
то \(c_{a,a'}(s)\) считает допустимые назначения цифр с суммой столбца \(s\). Поскольку члены различаются своим положением в записи равенства, выбор того, какие именно \(a'\) членов продолжаются, даёт множитель \(\binom{a}{a'}\).
Пусть \(L\) и \(R\) обозначают суммы цифр в текущем столбце слева и справа, а \(\delta\) есть перенос, пришедший из уже обработанных младших разрядов. Тогда корректность десятичной арифметики равносильна условию
\[ L-R+\delta=10\delta', \]
где \(\delta'\) есть перенос в следующий старший разряд. Значит, возможны только такие разности
\[ d=L-R \]
что \(d\equiv -\delta \pmod{10}\).
Для фиксированных чисел выживших членов удобно заранее определить
\[ T_{a,a',b,b'}(d)=\sum_{s-t=d} c_{a,a'}(s)\,c_{b,b'}(t), \]
то есть число присваиваний цифр, дающих разность \(d\). Именно эти таблицы и предвычисляют реализации.
Пусть \(D(u,a,b,\delta)\) означает количество частично построенных равенств, у которых младшие разряды уже зафиксированы, суммарная зафиксированная длина равна \(u\), слева остаётся \(a\) активных членов, справа \(b\), а в текущий столбец входит перенос \(\delta\).
Начальные состояния имеют вид
\[ D(\ell+r-1,\ell,r,0)=1 \]
для всех \(\ell\ge 1\), \(r\ge 1\), \(\ell+r\le 25\). Обработка ещё одного столбца добавляет по одной цифре от каждого активного члена, поэтому
\[ u'=u+a+b. \]
Если в следующем столбце остаётся \(a'\le a\) активных членов слева и \(b'\le b\) справа, то переход записывается как
\[ D(u+a+b,a',b',\delta') \;+\!=\; D(u,a,b,\delta)\binom{a}{a'}\binom{b}{b'}T_{a,a',b,b'}(d), \]
при условии \(d+\delta=10\delta'\). Равенство завершено тогда и только тогда, когда
\[ a=b=0,\qquad \delta=0, \]
и потому
\[ F(n)=\sum_{u=0}^{n} D(u,0,0,0). \]
В любой момент активных членов не больше 25, поэтому всегда
\[ |L-R|\le 9\cdot 25=225. \]
Если \(|\delta|\le 25\), то
\[ |\delta'|=\left|\frac{L-R+\delta}{10}\right|\le \frac{225+25}{10}=25. \]
Так как процесс стартует с \(\delta=0\), все достижимые переносы навсегда остаются внутри этого фиксированного окна.
Проверка для длины 5 уже содержит всю ту же механику. Рассмотрим равенства вида \(a+b=c\), где все три числа однозначные. Разделители дают длину 2, а одна обработанная цифровая колонка доводит общую длину до 5. Начальное состояние равно \(D(2,2,1,0)=1\), и единственный вариант числа выживших членов: \(a'=0\), \(b'=0\).
Нужные полиномы равны
\[ P_{2,0}(x)=\bigl(x+\cdots+x^9\bigr)^2,\qquad P_{1,0}(x)=x+\cdots+x^9. \]
Так как конечный перенос должен исчезнуть, требуется разность \(d=0\). Для каждой правой цифры \(c\in\{1,\dots,9\}\) существует ровно \(c-1\) упорядоченных пар \((a,b)\) с \(a+b=c\). Следовательно,
\[ T_{2,0,1,0}(0)=\sum_{c=2}^{9}(c-1)=36. \]
Зеркальный тип \(c=a+b\) добавляет ещё 36. Если прибавить 9 однозначных тождеств \(d=d\) и 90 двузначных тождеств \(m=m\), получаем
\[ F(5)=9+90+36+36=171, \]
точно как в контрольных значениях.
Реализации на C++, Python и Java сначала строят все биномиальные коэффициенты до 25. Затем для каждой пары \((a,a')\) они вычисляют коэффициенты \(c_{a,a'}(s)\), то есть распределение возможных сумм цифр для одной стороны столбца.
Для каждого набора \((a,a',b,b')\) код объединяет две односторонние таблицы и получает значения \(T_{a,a',b,b'}(d)\). Эти значения группируются по \(d\bmod 10\), поэтому состояние с переносом \(\delta\) рассматривает только совместимый класс \(d\equiv -\delta \pmod{10}\).
Динамика стартует со всех допустимых распределений общего числа членов между левой и правой частью. Далее состояния обрабатываются по возрастанию уже зафиксированной длины. Каждый переход выбирает числа выживших членов, умножает на биномиальные множители, читает предвычисленную таблицу разностей, вычисляет новый перенос \((d+\delta)/10\) и добавляет вклад в состояние длины \(u+a+b\). После завершения прохода суммируются все завершённые состояния длины не больше \(n\). Во всех трёх языках используется одна и та же рекурсия; версия на C++ дополнительно умеет распараллеливать часть предвычислений.
Определяющая граница состоит в том, что \(T\le 25\). Поэтому память DP имеет \((n+1)\cdot 26\cdot 26\cdot 51\) ячеек; для \(n=50\) это примерно \(1.76\times 10^6\) записей, причём многие из них никогда не используются, потому что всегда выполнено \(a+b\le 25\).
Основная работа приходится на проход по достижимым состояниям, перебор возможных \((a',b')\) и просмотр коротких предвычисленных списков допустимых разностей в нужном классе вычетов. Память линейна по числу состояний плюс конечное семейство таблиц разностей. На практике метод быстр, потому что он не перебирает сами строковые записи равенств, а считает их через распределения сумм по столбцам и переносы.
لتكن \(F(n)\) هي عدد الهويات العشرية الصحيحة من الشكل
\[ A_1+\cdots+A_\ell = B_1+\cdots+B_r, \]
حيث إن كل حد عدد صحيح موجب من دون أصفار بادئة. ويحسب الطول الكلي جميع الأرقام وجميع إشارات الجمع وعلامة المساواة:
\[ |E|=\sum_{i=1}^{\ell}\operatorname{len}(A_i)+\sum_{j=1}^{r}\operatorname{len}(B_j)+(\ell-1)+(r-1)+1. \]
المطلوب هو حساب \(F(50)\bmod 10^9+7\). وتتحقق التطبيقات من نفسها بواسطة القيم الصغيرة
\[ F(3)=9,\qquad F(5)=171,\qquad F(7)=4878. \]
العد المباشر لكل السلاسل الممكنة غير عملي إطلاقاً، لأن عدد الحدود وأطوالها واختيارات الأرقام ينفجر بسرعة. الفكرة الصحيحة هي قراءة المعادلة من اليمين إلى اليسار، عموداً عشرياً بعد عمود، مع الاحتفاظ فقط بالمعلومات التي ما زالت تؤثر في الأعمدة الأعلى.
التبسيط الحاسم هو أن الجمع العشري محلي. بعد تثبيت الأعمدة الدنيا، لا يبقى مهماً إلا عدد الحدود التي ما زالت نشطة في كل طرف، وقيمة الحمل القادم من الأسفل.
نقول إن الحد نشط في عمود ما إذا كان ما يزال يساهم برقماً في ذلك العمود. إذا كان في المعادلة \(T=\ell+r\) حدود بالمجموع، فإن أقصر معادلة ممكنة تحتوي على \(T\) أرقام و\(T-1\) فواصل. لذلك
\[ |E|\ge 2T-1. \]
ومن ثم فإن \(|E|\le 50\) يفرض \(T\le 25\). وهذا هو بالضبط الحد الذي تستخدمه التطبيقات: لا يمكن أن يتجاوز عدد الحدود النشطة في الطرفين معاً 25.
قبل معالجة أي عمود من الأرقام لا تكون الأجزاء المثبتة سوى الفواصل. فإذا كان في الطرف الأيسر \(\ell\) حدود وفي الطرف الأيمن \(r\) حدود، فإن الطول المثبت في البداية يساوي
\[ (\ell-1)+(r-1)+1=\ell+r-1. \]
لنفترض أن عموداً ما يبدأ وفي أحد الطرفين \(a\) حدود نشطة، وأن \(a'\le a\) منها فقط تستمر إلى العمود الأعلى. عندئذٍ تنتهي \(a-a'\) حدود في هذا العمود، ولذلك تكون هذه الخانة هي الخانة الأولى في أعدادها ويجب أن تقع في \(\{1,\dots,9\}\). أما الحدود \(a'\) التي تستمر فيجوز أن تسهم بأي رقم من \(\{0,\dots,9\}\).
ومن هنا نحصل على كثير الحدود المولد
\[ P_{a,a'}(x)=\bigl(x+x^2+\cdots+x^9\bigr)^{a-a'}\bigl(1+x+x^2+\cdots+x^9\bigr)^{a'}. \]
وإذا كتبنا
\[ c_{a,a'}(s)=[x^s]\,P_{a,a'}(x), \]
فإن \(c_{a,a'}(s)\) يعدّ التعيينات المسموح بها للأرقام التي تعطي مجموعاً عمودياً مقداره \(s\). وبما أن الحدود مميزة بترتيبها في كتابة المعادلة، فإن اختيار أي \(a'\) من أصل \(a\) للاستمرار يضيف العامل \(\binom{a}{a'}\).
لتكن \(L\) و\(R\) مجموعي الأرقام في العمود الحالي في الطرفين الأيسر والأيمن، ولتكن \(\delta\) قيمة الحمل الداخل من الأعمدة الدنيا. تكون صحة الحساب العشري مكافئة تماماً للمعادلة
\[ L-R+\delta=10\delta'. \]
وهنا \(\delta'\) هو الحمل الذي ينتقل إلى العمود الأعلى. لذلك لا يمكن أن تظهر إلا الفروق
\[ d=L-R \]
التي تحقق \(d\equiv -\delta \pmod{10}\).
ومن المفيد، مع تثبيت أعداد الحدود التي تبقى نشطة في الطرفين، تعريف
\[ T_{a,a',b,b'}(d)=\sum_{s-t=d} c_{a,a'}(s)\,c_{b,b'}(t), \]
وهو عدد تعيينات الأرقام التي تولد الفرق \(d\). هذه هي الجداول التوافقية الأساسية التي تسبقها التطبيقات بالحساب.
لنعرّف \(D(u,a,b,\delta)\) بأنه عدد المعادلات المبنية جزئياً التي ثُبتت أعمدتها الدنيا، وصار طولها المثبت \(u\)، وما زال فيها \(a\) حدود نشطة يساراً و\(b\) حدود نشطة يميناً، مع حمل داخل إلى العمود الحالي قيمته \(\delta\).
الحالات الابتدائية هي
\[ D(\ell+r-1,\ell,r,0)=1 \]
لكل \(\ell\ge 1\)، \(r\ge 1\)، \(\ell+r\le 25\). وعند معالجة عمود جديد يضاف رقم واحد لكل حد نشط، لذلك يصبح الطول
\[ u'=u+a+b. \]
إذا بقي في العمود التالي \(a'\le a\) حدود نشطة في اليسار و\(b'\le b\) في اليمين، فإن الانتقال يكتب على الصورة
\[ D(u+a+b,a',b',\delta') \;+\!=\; D(u,a,b,\delta)\binom{a}{a'}\binom{b}{b'}T_{a,a',b,b'}(d), \]
متى كان \(d+\delta=10\delta'\). وتكون المعادلة مكتملة بالضبط عندما
\[ a=b=0,\qquad \delta=0, \]
ومن ثم
\[ F(n)=\sum_{u=0}^{n} D(u,0,0,0). \]
في كل لحظة يوجد على الأكثر 25 حداً نشطاً، ومن ثم فإن فرق المجاميع العمودية يحقق دائماً
\[ |L-R|\le 9\cdot 25=225. \]
وإذا كان \(|\delta|\le 25\) فإن
\[ |\delta'|=\left|\frac{L-R+\delta}{10}\right|\le \frac{225+25}{10}=25. \]
وبما أن العملية تبدأ من حمل يساوي الصفر، فإن جميع القيم الممكنة للحمل تبقى داخل هذه النافذة الثابتة طوال الوقت.
قيمة التحقق عند الطول 5 تكشف الآلية نفسها بصورة صغيرة. خذ المعادلات من الشكل \(a+b=c\) حيث تكون الأعداد الثلاثة جميعها من رقم واحد. تسهم الفواصل بطول مقداره 2، ومع معالجة عمود رقمي واحد يصبح الطول الكلي 5. الحالة الابتدائية هي \(D(2,2,1,0)=1\)، والاختيار الوحيد هو \(a'=0\) و\(b'=0\).
كثيرا الحدود المطلوبان هما
\[ P_{2,0}(x)=\bigl(x+\cdots+x^9\bigr)^2,\qquad P_{1,0}(x)=x+\cdots+x^9. \]
ولأن الحمل النهائي يجب أن يختفي، فنحن بحاجة إلى الفرق \(d=0\). ولكل رقم في الطرف الأيمن \(c\in\{1,\dots,9\}\) يوجد بالضبط \(c-1\) زوج مرتب \((a,b)\) يحقق \(a+b=c\). لذلك
\[ T_{2,0,1,0}(0)=\sum_{c=2}^{9}(c-1)=36. \]
والصيغة المعكوسة \(c=a+b\) تعطي 36 أخرى. وإذا أضفنا 9 هويات أحادية الرقم من الشكل \(d=d\) و90 هوية ثنائية الرقم من الشكل \(m=m\)، نحصل على
\[ F(5)=9+90+36+36=171, \]
وهو بالضبط مقدار التحقق.
تبدأ تطبيقات C++ وPython وJava ببناء جميع معاملات ثنائية الحد حتى 25. بعد ذلك تحسب، لكل زوج \((a,a')\)، الجداول \(c_{a,a'}(s)\) التي تصف توزيعات مجاميع الأرقام في جهة واحدة من العمود.
لكل رباعية \((a,a',b,b')\)، تجمع الشيفرة جدولي الطرفين لتكوين الأعداد \(T_{a,a',b,b'}(d)\). ثم تنظَّم هذه القيم بحسب \(d\bmod 10\)، ولذلك فإن حالة ذات حمل \(\delta\) لا تحتاج إلا إلى فحص الفروق الموافقة للشرط \(d\equiv -\delta \pmod{10}\).
تبدأ البرمجة الديناميكية من جميع التوزيعات المسموح بها لعدد الحدود بين الطرفين، مع طول ابتدائي يساوي عدد الفواصل. ثم تعالج الحالات بترتيب تصاعدي في الطول المثبت. في كل انتقال تختار أعداد الحدود التي ستبقى نشطة، وتطبّق عوامل ثنائية الحد المناسبة، وتقرأ عدد الفروق المحسوب مسبقاً، وتحسب الحمل التالي \((d+\delta)/10\)، ثم تضيف المساهمة إلى الحالة ذات الطول \(u+a+b\). بعد انتهاء المرور، يجمع الناتج من كل الحالات المكتملة ذات الطول الذي لا يتجاوز \(n\). تعتمد اللغات الثلاث العلاقة العودية نفسها؛ كما يمكن لنسخة C++ توزيع جزء من مرحلة التمهيد على عدة عمال.
القيد الحاسم هو \(T\le 25\). ولذلك فإن مساحة التخزين الخاصة بالـ DP تساوي \((n+1)\cdot 26\cdot 26\cdot 51\) خانة؛ وعندما يكون \(n=50\) يكون ذلك نحو \(1.76\times 10^6\) موضع، مع بقاء عدد كبير منها صفراً لأن الشرط \(a+b\le 25\) يمنع الوصول إليها.
العمل الرئيسي يقع في المرور على الحالات الممكنة، وتجربة اختيارات البقاء \((a',b')\)، وفحص القوائم القصيرة للفروق المسموح بها في فئة البواقي المناسبة. يظل استهلاك الذاكرة خطياً في عدد الحالات المخزنة مضافاً إليه عدد محدود من جداول الفروق. عملياً تكون الطريقة سريعة لأنها لا تعدّد السلاسل الكاملة للمعادلات، بل تعدّها بصورة غير مباشرة عبر مجاميع الأعمدة والحمل.