For a positive integer \(n\), define
$$f(n)=\sum_{d\in\mathrm{digits}(n)} d!,$$
and then define
$$sf(n)=s\bigl(f(n)\bigr),$$
where \(s(x)\) is the ordinary decimal digit sum.
For each \(i\ge 1\), the problem introduces
$$g(i)=\min\{n\ge 1: sf(n)=i\},\qquad sg(i)=s\bigl(g(i)\bigr).$$
The goal is to compute
$$\sum_{i=1}^{150} sg(i).$$
A direct search over \(n\) is completely impractical. The code therefore changes viewpoint: it searches over the value
$$y=f(n),$$
derives the smallest decimal \(n\) compatible with that \(y\), and uses a bitset dynamic program to find all relevant \(y\) grouped by decimal digit sum and residue modulo \(9!\).
If the digit \(d\) appears \(c_d\) times in \(n\), then
$$f(n)=\sum_{d=0}^{9} c_d\,d!.$$
So a number \(n\) is completely described, for the purposes of \(f\), by the multiplicities of its digits. Once a target value \(y\) is fixed, the question becomes:
Among all digit multisets whose factorial sum is \(y\), which multiset yields the smallest decimal integer?
For any fixed multiset of digits, the smallest corresponding integer is obtained by arranging the digits in nondecreasing order. So for each \(y\), we only need the lexicographically smallest valid multiset.
This is one of the key structural facts behind the code.
First, note that
$$0!=1!=1.$$
If a candidate multiset contains both a 0 and a 1, then we may replace that pair by a single digit 2, because
$$0!+1!=1+1=2=2!.$$
This preserves \(f(n)\) while shortening the decimal length, so the original number cannot have been minimal.
If a candidate contains a 0 but no 1, then its smallest nonzero digit is at least 2. Replacing one 0 by a 1 keeps \(f(n)\) unchanged, and after sorting the digits the resulting positive integer is smaller, because a leading 1 is better than a leading digit \(\ge 2\) followed by an internal 0.
Therefore, in a truly minimal \(g(i)\), zeros never appear. That is why the implementation only stores counts for digits \(1,\dots,9\).
The next crucial identity is
$$(d+1)!=(d+1)\,d!.$$
So whenever a digit multiset contains at least \(d+1\) copies of the digit \(d\), we may replace those \(d+1\) copies by a single digit \(d+1\). This keeps the factorial sum unchanged and strictly shortens the decimal length.
Consequently, in any minimal solution we must have
$$0\le c_d\le d\qquad(1\le d\le 8).$$
Repeatedly applying these carries produces a unique normalized expansion
$$y=c_9\cdot 9!+c_8\cdot 8!+\cdots+c_2\cdot 2!+c_1\cdot 1!,$$
where
$$0\le c_d\le d\qquad(1\le d\le 8),$$
and \(c_9\) is unrestricted.
This is exactly the factorial number system, truncated at \(9!\). The tuple \((c_1,\dots,c_9)\) is the canonical multiset of digits attached to \(y\).
There are three reasons:
1. Sorting a fixed multiset in nondecreasing order gives the smallest decimal number for that multiset.
2. Any zero can be eliminated, so minimal candidates use only digits \(1,\dots,9\).
3. Any violation of \(c_d\le d\) can be repaired by a carry, which strictly shortens the decimal number.
Therefore the normalized factorial digits are not just a convenient encoding of \(y\): they are precisely the digit counts of the smallest decimal \(n\) with \(f(n)=y\).
If the normalized counts are \(c_1,\dots,c_9\), then the corresponding minimal decimal number is
$$\underbrace{11\cdots1}_{c_1}\underbrace{22\cdots2}_{c_2}\cdots\underbrace{99\cdots9}_{c_9}.$$
Its decimal digit sum is
$$sg=\sum_{d=1}^{9} d\,c_d,$$
and its length is \(c_1+\cdots+c_9\).
The C++ code checks that
$$g(5)=25.$$
Indeed,
$$f(25)=2!+5!=2+120=122,$$
so
$$sf(25)=s(122)=1+2+2=5.$$
The canonical factorial representation of \(122\) is simply
$$122=1\cdot 5!+1\cdot 2!,$$
which corresponds to the multiset \(\{2,5\}\), hence to the decimal integer \(25\).
The second checkpoint is
$$g(20)=267.$$
This comes from
$$f(267)=2!+6!+7!=2+720+5040=5762,$$
and therefore
$$sf(267)=s(5762)=5+7+6+2=20.$$
This example is important because it shows the real target of the search: for fixed \(i\), we are not looking for numbers \(n\) whose own digit sum is \(i\); we are looking for numbers whose factorial-digit-sum value \(y=f(n)\) has decimal digit sum \(i\).
Write
$$y=q\cdot 9!+r,\qquad 0\le r<9!.$$
Then \(q=c_9\), while the remainder \(r\) determines the lower coefficients \(c_1,\dots,c_8\) uniquely via the factorial system.
So inside one residue class modulo \(9!\), the only thing that changes is the number of 9s.
If we replace \(y\) by \(y+9!\), then the normalized digit multiset simply gains one extra digit 9. That makes the resulting decimal \(n\) longer, hence larger. Therefore, for each residue class, only the smallest compatible \(y\) can ever matter.
This is the reason the whole search is organized by the modulus
$$9!=362880.$$
Because
$$sf(n)=s\bigl(f(n)\bigr)=s(y),$$
the condition \(sf(n)=i\) is equivalent to asking for a decimal integer \(y\) whose digit sum is \(i\).
The solver builds a DP state
$$DP[\ell][s][r],$$
meaning: there exists a decimal number of length \(\ell\), decimal digit sum \(s\), and residue \(r\bmod 9!\).
If a new digit \(d\) is placed in the next decimal position, the residue changes by
$$r' \equiv r + d\cdot 10^{\ell}\pmod{9!},$$
and the digit sum changes to \(s+d\). So the transition is
$$DP[\ell+1][s+d][r'] \leftarrow DP[\ell][s][r].$$
The implementation stores the whole residue layer for each pair \((\ell,s)\) as a bitset. Then “add digit \(d\)” becomes a cyclic rotation by
$$d\cdot 10^{\ell}\bmod 9!$$
followed by bitwise OR. That is exactly what rotate_or does.
The DP starts at length \(0\) and allows transitions with digit \(0\), so formally it also represents numbers with leading zeros. This is harmless, because for each target digit sum \(i\) and each residue \(r\), the solver scans lengths in increasing order and picks the first reachable one.
Therefore the chosen \(\ell\) is the true shortest decimal length of \(y\), and within that length the backtracking step reconstructs the lexicographically smallest decimal representation.
For a fixed target \(i\) and residue \(r\), once the smallest reachable length \(\ell\) is known, the code reconstructs the smallest \(y\) greedily. At each position it tries digits
$$0,1,2,\dots,9$$
in that order, and checks whether the predecessor state remains feasible. The first successful digit is taken.
This produces the smallest decimal \(y\) among all numbers with the chosen length, digit sum, and residue.
Each reconstructed \(y\) is decoded to its canonical factorial coefficients \(c_d\). That yields one candidate for \(g(i)\).
To compare two candidates, the code first compares their lengths. The shorter decimal number is always smaller. If lengths tie, then the lexicographically smaller sorted digit string wins, which is equivalent to saying that more copies of smaller digits are better. This is exactly what node_less implements.
Finally, once the best candidate for \(g(i)\) is known, the contribution to the global answer is
$$sg(i)=\sum_{d=1}^{9} d\,c_d.$$
The implementation includes three useful checks:
$$g(5)=25,$$
$$g(20)=267,$$
and
$$\sum_{i=1}^{20} sg(i)=156.$$
These validate the normalization logic, the residue search, and the final candidate ordering.
The constructor precomputes \(10^\ell \bmod 9!\) for all \(\ell\le 18\), then calls build_dp() to fill the bitset table for every length up to 18 and every digit sum up to 150. For a target value \(i\), the routine best_node_for_sf(i) scans all residues modulo \(9!\), finds the smallest length where that residue is reachable, reconstructs the minimal decimal \(y\) with backtrace_min_number(), decodes it with node_from_y(), and keeps the smallest candidate according to node_less(). The outer function simply sums the digit sums \(sg(i)\).
The implementation chooses a maximum decimal length of 18 for \(y\); this is sufficient for the target range \(i\le 150\) used here and is supported by the built-in checkpoints.
Let
$$L=18,\qquad S=150,\qquad M=9!=362880.$$
For each pair \((\ell,s)\), the DP stores a bitset over all \(M\) residues. So the memory usage is
$$O\!\left(\frac{L\cdot S\cdot M}{64}\right)$$
machine words.
The main time cost is building this table and then scanning residues for each \(i\). Because residue transitions are done by bitset rotation and OR, the algorithm is massively word-parallel and far faster than any direct search over \(n\), or even over all decimal \(y\) with a given digit sum.
Für eine positive ganze Zahl \(n\) definieren wir
$$f(n)=\sum_{d\in\mathrm{Ziffern}(n)} d!,$$
sowie
$$sf(n)=s\bigl(f(n)\bigr),$$
wobei \(s(x)\) die gewöhnliche Dezimal-Quersumme bezeichnet.
Weiter sei
$$g(i)=\min\{n\ge 1: sf(n)=i\},\qquad sg(i)=s\bigl(g(i)\bigr).$$
Gesucht ist
$$\sum_{i=1}^{150} sg(i).$$
Eine direkte Suche über \(n\) ist aussichtslos. Der Code wechselt deshalb zum Wert \(y=f(n)\), konstruiert daraus die kleinste zugehörige Dezimalzahl \(n\) und organisiert die Suche dann über Dezimal-Quersummen und Restklassen modulo \(9!\).
Wenn die Ziffer \(d\) in \(n\) genau \(c_d\)-mal vorkommt, dann gilt
$$f(n)=\sum_{d=0}^{9} c_d\,d!.$$
Für festes \(y=f(n)\) bleibt also die Frage: Welche Ziffernmultimenge mit dieser Fakultätssumme erzeugt die kleinste Dezimalzahl?
Für eine feste Multimenge ist die kleinste Dezimalzahl einfach die sortierte Folge in nichtabsteigender Reihenfolge. Daher genügt es, für jedes \(y\) die kleinste zulässige Ziffernmultimenge zu finden.
Hier steckt ein wichtiger struktureller Trick. Es gilt nämlich
$$0!=1!=1.$$
Wenn eine Kandidatenmenge sowohl eine 0 als auch eine 1 enthält, können wir dieses Paar durch eine einzelne 2 ersetzen, denn
$$0!+1!=1+1=2=2!.$$
Dadurch bleibt \(f(n)\) erhalten, aber die Dezimallänge wird kürzer. Also kann die ursprüngliche Zahl nicht minimal gewesen sein.
Enthält eine Kandidatenmenge eine 0, aber keine 1, dann ist ihre kleinste von null verschiedene Ziffer mindestens 2. Ersetzt man eine 0 durch eine 1, bleibt \(f(n)\) unverändert, und nach dem Sortieren erhält man eine kleinere positive Dezimalzahl.
Folglich kommen in echten Minimaldarstellungen keine Nullen vor. Deshalb speichert der Code nur Ziffernzahlen für \(1,\dots,9\).
Die zentrale Identität lautet
$$(d+1)!=(d+1)\,d!.$$
Wenn also eine Ziffernmultimenge mindestens \(d+1\) Kopien der Ziffer \(d\) enthält, dürfen diese \(d+1\) Kopien durch eine einzige Ziffer \(d+1\) ersetzt werden. Die Fakultätssumme bleibt gleich, die Dezimallänge wird aber strikt kürzer.
Daher muss in jeder Minimaldarstellung gelten
$$0\le c_d\le d\qquad(1\le d\le 8).$$
Nach vollständigem Übertragen entsteht die eindeutige Normalform
$$y=c_9\cdot 9!+c_8\cdot 8!+\cdots+c_2\cdot 2!+c_1\cdot 1!,$$
mit
$$0\le c_d\le d\qquad(1\le d\le 8),$$
während \(c_9\) unbeschränkt bleibt. Das ist genau das Fakultätszahlensystem, abgeschnitten bei \(9!\).
Der Beweis besteht aus drei Beobachtungen:
1. Für eine feste Multimenge ist die sortierte Dezimaldarstellung die kleinste.
2. Nullen lassen sich immer eliminieren.
3. Jede Verletzung von \(c_d\le d\) kann per Carry beseitigt werden, was die Länge verkürzt.
Damit sind die normalisierten Faktoradizit-Ziffern nicht nur eine Kodierung von \(y\), sondern genau die Ziffernanzahlen der kleinsten Dezimalzahl \(n\) mit \(f(n)=y\).
Kennt man also \(c_1,\dots,c_9\), dann ist die kleinste zugehörige Dezimalzahl
$$\underbrace{11\cdots1}_{c_1}\underbrace{22\cdots2}_{c_2}\cdots\underbrace{99\cdots9}_{c_9}.$$
Ihre Quersumme ist
$$sg=\sum_{d=1}^{9} d\,c_d.$$
Ein Checkpoint des Programms lautet
$$g(5)=25.$$
Denn
$$f(25)=2!+5!=2+120=122,$$
also
$$sf(25)=s(122)=1+2+2=5.$$
Die kanonische Fakultätsdarstellung von \(122\) ist
$$122=1\cdot 5!+1\cdot 2!,$$
also die Ziffernmultimenge \(\{2,5\}\), und damit ist \(25\) die kleinste Zahl.
Ein weiterer Test ist
$$g(20)=267.$$
Dies folgt aus
$$f(267)=2!+6!+7!=2+720+5040=5762,$$
und damit
$$sf(267)=s(5762)=5+7+6+2=20.$$
Hier sieht man deutlich: Die Zielgröße \(i\) ist die Dezimal-Quersumme von \(y=f(n)\), nicht die Quersumme von \(n\).
Schreibe
$$y=q\cdot 9!+r,\qquad 0\le r<9!.$$
Dann ist \(q=c_9\), während der Rest \(r\) die unteren Koeffizienten \(c_1,\dots,c_8\) eindeutig festlegt.
Innerhalb einer festen Restklasse modulo \(9!\) ändert sich also nur die Anzahl der Neunen. Erhöht man \(y\) um \(9!\), dann kommt in der kanonischen Darstellung genau eine weitere 9 hinzu. Dadurch wird die Dezimalzahl länger und somit größer.
Also ist in jeder Restklasse immer nur das kleinste zulässige \(y\) relevant. Genau deshalb arbeitet der Solver modulo
$$9!=362880.$$
Weil
$$sf(n)=s\bigl(f(n)\bigr)=s(y),$$
ist die Bedingung \(sf(n)=i\) gleichbedeutend mit: \(y\) ist eine Dezimalzahl mit Quersumme \(i\).
Der DP-Zustand lautet
$$DP[\ell][s][r],$$
und bedeutet: Es existiert eine Dezimalzahl der Länge \(\ell\), mit Quersumme \(s\) und Rest \(r\bmod 9!\).
Wird eine weitere Dezimalziffer \(d\) an der nächsten Stelle hinzugefügt, so gilt
$$r' \equiv r + d\cdot 10^{\ell}\pmod{9!},$$
und die Quersumme wird zu \(s+d\). Also:
$$DP[\ell+1][s+d][r'] \leftarrow DP[\ell][s][r].$$
Der Code speichert für jedes Paar \((\ell,s)\) die gesamte Restmenge als Bitset. Damit wird „Ziffer \(d\) hinzufügen“ zu einer zyklischen Bitset-Verschiebung um
$$d\cdot 10^{\ell}\bmod 9!$$
gefolgt von OR.
Das DP startet bei Länge \(0\) und erlaubt auch Übergänge mit Ziffer \(0\). Formal entstehen dadurch Darstellungen mit führenden Nullen. Das ist aber unproblematisch, weil der Solver für jedes Ziel \(i\) und jeden Rest \(r\) die Länge \(\ell\) von klein nach groß durchsucht und die erste erfolgreiche nimmt.
Damit ist die gewählte \(\ell\) automatisch die echte minimale Dezimallänge von \(y\).
Ist für gegebenes \(i\) und \(r\) die kleinste Länge \(\ell\) bekannt, dann rekonstruiert der Code die kleinste zugehörige Dezimalzahl \(y\) greedily. Er probiert die Ziffern
$$0,1,2,\dots,9$$
der Reihe nach und nimmt die erste, deren Vorgängerzustand im DP existiert.
So entsteht die kleinste Dezimalzahl \(y\) mit der gewählten Länge, Quersumme und Restklasse.
Jedes rekonstruierte \(y\) wird in die kanonischen Fakultätskoeffizienten \(c_d\) dekodiert. Das erzeugt einen Kandidaten für \(g(i)\).
Beim Vergleich zweier Kandidaten gewinnt zuerst die kürzere Länge. Bei gleicher Länge gewinnt die lexikographisch kleinere sortierte Ziffernfolge, also diejenige mit mehr kleinen Ziffern vorne. Genau das implementiert node_less.
Ist der beste Kandidat gefunden, so trägt er
$$sg(i)=\sum_{d=1}^{9} d\,c_d$$
zur Gesamtsumme bei.
Die Implementierung prüft drei Dinge:
$$g(5)=25,$$
$$g(20)=267,$$
und
$$\sum_{i=1}^{20} sg(i)=156.$$
Damit werden Normalisierung, Rekonstruktion und Kandidatenvergleich gleichzeitig getestet.
Der Konstruktor berechnet zunächst \(10^\ell \bmod 9!\) für alle \(\ell\le 18\) und füllt dann per build_dp() die Bitset-Tabelle für alle Längen bis 18 und alle Quersummen bis 150. Für eine Anfrage \(i\) durchsucht best_node_for_sf(i) alle Restklassen modulo \(9!\), bestimmt die kleinste erreichbare Länge, rekonstruiert mit backtrace_min_number() das kleinste passende \(y\), dekodiert es mit node_from_y() und behält per node_less() den besten Kandidaten. Schließlich werden die Quersummen \(sg(i)\) aufsummiert.
Die Schranke 18 für die Dezimallänge von \(y\) ist Teil der Implementierung und für den Zielbereich \(i\le 150\) ausreichend; die eingebauten Checkpoints stützen diese Wahl.
Mit
$$L=18,\qquad S=150,\qquad M=9!=362880$$
speichert das DP für jedes Paar \((\ell,s)\) ein Bitset über alle \(M\) Restklassen. Der Speicherbedarf beträgt also
$$O\!\left(\frac{L\cdot S\cdot M}{64}\right)$$
Maschinenwörter.
Die Laufzeit wird durch den Aufbau dieser Tabelle und durch das spätere Durchlaufen der Restklassen dominiert. Wegen der Bitparallelität ist dies aber dramatisch schneller als jede direkte Suche über \(n\) oder sogar über alle Dezimalzahlen \(y\) mit gegebener Quersumme.
Pozitif bir \(n\) sayısı için
$$f(n)=\sum_{d\in\mathrm{digits}(n)} d!$$
tanımlansın. Ayrıca
$$sf(n)=s\bigl(f(n)\bigr)$$
olsun; burada \(s(x)\), \(x\)'in onluk rakam toplamıdır.
Her \(i\ge 1\) için
$$g(i)=\min\{n\ge 1: sf(n)=i\},\qquad sg(i)=s\bigl(g(i)\bigr)$$
tanımlanır. Problem
$$\sum_{i=1}^{150} sg(i)$$
toplamını ister. Doğrudan \(n\) üzerinde arama yapmak mümkün değildir; bu yüzden çözüm önce
$$y=f(n)$$
değerine geçer, bu \(y\) için en küçük olası \(n\)'yi kanonik olarak üretir ve ardından onluk rakam toplamı ile \(9!\) modundaki kalıntı üzerinden bir bitset-DP kurar.
Eğer \(n\) içinde rakam \(d\), \(c_d\) kez geçiyorsa
$$f(n)=\sum_{d=0}^{9} c_d\,d!$$
olur. O halde sabit bir \(y\) için asıl problem şudur:
Factorial toplamı \(y\) olan tüm rakam çoklukları arasında en küçük onluk tamsayıyı hangisi verir?
Sabit bir rakam multiseti için en küçük sayı, rakamları artan sırada yazarak elde edilir. Dolayısıyla her \(y\) için yalnızca en küçük geçerli rakam multiseti aranmalıdır.
Bu, çözümün en önemli yapısal gözlemlerinden biridir. Çünkü
$$0!=1!=1.$$
Eğer bir aday hem 0 hem 1 içeriyorsa, bu ikili yerine tek bir 2 yazabiliriz; zira
$$0!+1!=1+1=2=2!.$$
Böylece \(f(n)\) değişmez ama sayı bir basamak kısalır. O halde orijinal sayı minimal olamaz.
Eğer adayda 0 var ama 1 yoksa, en küçük sıfır olmayan rakam en az 2'dir. Bu durumda bir 0'ı 1 ile değiştirmek factorial toplamı korur ve sıralı yazımda daha küçük bir pozitif sayı verir.
Sonuç: Gerçek minimal \(g(i)\) adaylarında 0 hiç gerekmez. Bu yüzden kod yalnızca \(1,\dots,9\) rakamlarının sayısını tutar.
Temel özdeşlik
$$(d+1)!=(d+1)\,d!$$
şeklindedir. Dolayısıyla bir adayda \(d\) rakamı en az \(d+1\) kez varsa, bu \(d+1\) adet \(d\) rakamı tek bir \(d+1\) rakamına dönüştürülebilir. Factorial toplam değişmez ama onluk uzunluk kısalır.
Bu nedenle minimal bir adayda mutlaka
$$0\le c_d\le d\qquad(1\le d\le 8)$$
olmalıdır.
Bu carry işlemi tekrar tekrar uygulanınca tek bir normal forma ulaşılır:
$$y=c_9\cdot 9!+c_8\cdot 8!+\cdots+c_2\cdot 2!+c_1\cdot 1!,$$
burada
$$0\le c_d\le d\qquad(1\le d\le 8),$$
ve \(c_9\) serbesttir. Bu, \(9!\)'de kesilmiş factorial sayı sistemidir.
Üç neden vardır:
1. Sabit bir rakam multiseti için sıralı yazım en küçük sayıdır.
2. Sıfırlar her zaman elimine edilebilir.
3. \(c_d\le d\) ihlali varsa carry yapılarak sayı kesin olarak kısaltılır.
Dolayısıyla normalleştirilmiş factoradic katsayıları yalnızca \(y\)'nin bir kodu değil, aynı zamanda \(f(n)=y\) koşulunu sağlayan en küçük onluk sayının rakam sayılarıdır.
Kanonik katsayılar \(c_1,\dots,c_9\) biliniyorsa en küçük aday
$$\underbrace{11\cdots1}_{c_1}\underbrace{22\cdots2}_{c_2}\cdots\underbrace{99\cdots9}_{c_9}$$
olur. Bunun rakam toplamı
$$sg=\sum_{d=1}^{9} d\,c_d$$
şeklindedir.
Koddaki kontrol noktalarından biri
$$g(5)=25$$
eşitliğidir. Gerçekten
$$f(25)=2!+5!=2+120=122,$$
dolayısıyla
$$sf(25)=s(122)=1+2+2=5.$$
\(122\)'nin kanonik factoradic ayrışımı
$$122=1\cdot 5!+1\cdot 2!$$
olduğundan buna karşılık gelen minimal rakam multiseti \(\{2,5\}\), yani minimal sayı \(25\)'tir.
Bir diğer test
$$g(20)=267$$
sonucudur. Çünkü
$$f(267)=2!+6!+7!=2+720+5040=5762,$$
ve
$$sf(267)=s(5762)=5+7+6+2=20.$$
Bu örnek şunu açık eder: Hedef \(i\), \(n\)'nin rakam toplamı değil, \(y=f(n)\)'nin rakam toplamıdır.
\(y\)'yi
$$y=q\cdot 9!+r,\qquad 0\le r<9!$$
şeklinde yazalım. Burada \(q=c_9\) olur; alt katsayılar \(c_1,\dots,c_8\) ise yalnızca kalan \(r\)'ye bağlıdır.
Demek ki aynı kalıntı sınıfı içinde değişen tek şey 9 rakamlarının sayısıdır. \(y\)'ye bir tane \(9!\) eklemek, kanonik adayda yalnızca bir tane daha 9 rakamı üretir. Bu da sayıyı uzatır ve büyütür.
O halde her kalıntı sınıfında yalnızca en küçük uygun \(y\) önemlidir. Bu yüzden çözüm
$$9!=362880$$
modülüne göre çalışır.
Çünkü
$$sf(n)=s\bigl(f(n)\bigr)=s(y),$$
\(sf(n)=i\) koşulu, \(y\)'nin onluk rakam toplamının \(i\) olmasıyla aynıdır.
DP durumu
$$DP[\ell][s][r]$$
şudur: uzunluğu \(\ell\), rakam toplamı \(s\), kalanı \(r\bmod 9!\) olan bir onluk sayı vardır.
Yeni bir basamak \(d\) daha eklendiğinde kalan
$$r' \equiv r + d\cdot 10^{\ell}\pmod{9!}$$
olur, rakam toplamı da \(s+d\)'ye çıkar. Dolayısıyla geçiş
$$DP[\ell+1][s+d][r'] \leftarrow DP[\ell][s][r]$$
şeklindedir.
Kod her \((\ell,s)\) çifti için tüm residue katmanını bir bitset olarak saklar. Böylece “\(d\) basamağını ekle” işlemi,
$$d\cdot 10^{\ell}\bmod 9!$$
kadar döndür ve OR yap problemine dönüşür. rotate_or tam olarak bunu uygular.
DP uzunluk 0'dan başlar ve 0 rakamı da geçişlerde kullanılabilir; yani biçimsel olarak baştaki sıfırlı yazımlar da temsil edilir. Bu bir sorun değildir, çünkü çözüm her hedef \(i\) ve her residue \(r\) için uzunlukları küçükten büyüğe tarar ve ilk başarılı uzunluğu seçer.
Bu yüzden seçilen \(\ell\), \(y\)'nin gerçek en kısa onluk uzunluğudur.
Hedef \(i\) ve residue \(r\) için en küçük uygun uzunluk \(\ell\) bulunduğunda, kod en küçük \(y\)'yi greedy biçimde geri kurar. Her pozisyonda
$$0,1,2,\dots,9$$
rakamlarını sırayla dener ve önceki durum DP'de hâlâ mümkün kalıyorsa ilk başarılı rakamı seçer.
Böylece seçilen uzunluk, rakam toplamı ve residue için mümkün olan en küçük onluk \(y\) elde edilir.
Geri üretilen her \(y\), kanonik factoradic katsayılara çevrilir ve bu bir \(g(i)\) adayı üretir.
İki aday karşılaştırılırken önce uzunluk kıyaslanır; kısa olan küçüktür. Uzunluk eşitse, sıralı rakam dizisi lexicographic olarak küçük olan kazanır. Bu da daha çok küçük rakam içeren adayın tercih edilmesi demektir. Koddaki node_less mantığı budur.
Sonunda cevap katkısı
$$sg(i)=\sum_{d=1}^{9} d\,c_d$$
olarak alınır.
Uygulama şu üç kontrolü yapar:
$$g(5)=25,$$
$$g(20)=267,$$
ve
$$\sum_{i=1}^{20} sg(i)=156.$$
Bunlar hem normalizasyonu hem geri izlemeyi hem de aday sıralamayı test eder.
Kurucu fonksiyon önce \(10^\ell \bmod 9!\) değerlerini \(\ell\le 18\) için hesaplar, sonra build_dp() ile uzunluğu 18'e, rakam toplamı 150'ye kadar tüm durumlar için bitset tablosunu kurar. Bir hedef \(i\) verildiğinde best_node_for_sf(i) tüm residue sınıflarını tarar, en küçük uzunluğu bulur, backtrace_min_number() ile minimum \(y\)'yi geri üretir, node_from_y() ile kanonik rakam sayımlarını çıkarır ve node_less() ile en iyi adayı korur. Dış fonksiyon da bütün \(sg(i)\) değerlerini toplar.
Uygulamadaki 18 basamak sınırı, bu problemdeki \(i\le 150\) hedef aralığı için yeterlidir; gömülü kontrol noktaları da bunu destekler.
$$L=18,\qquad S=150,\qquad M=9!=362880$$
olsun. DP her \((\ell,s)\) çifti için tüm \(M\) residue'leri içeren bir bitset tuttuğundan bellek kullanımı
$$O\!\left(\frac{L\cdot S\cdot M}{64}\right)$$
makine kelimesi mertebesindedir.
Zaman maliyetinin ana kısmı bu tabloyu kurmak ve ardından her \(i\) için residue'leri taramaktır. Ama residue geçişleri bitset döndürme ve OR ile word-parallel yapıldığı için, yöntem doğrudan \(n\) üzerinde ya da sabit rakam toplamlı tüm \(y\)'ler üzerinde arama yapmaktan çok daha hızlıdır.
Para un entero positivo \(n\), definimos
$$f(n)=\sum_{d\in\mathrm{digits}(n)} d!,$$
y luego
$$sf(n)=s\bigl(f(n)\bigr),$$
donde \(s(x)\) es la suma decimal de cifras.
Además, para cada \(i\ge 1\),
$$g(i)=\min\{n\ge 1: sf(n)=i\},\qquad sg(i)=s\bigl(g(i)\bigr).$$
El objetivo es calcular
$$\sum_{i=1}^{150} sg(i).$$
Buscar directamente sobre \(n\) es imposible en la práctica. Por eso el código trabaja con
$$y=f(n),$$
reconstruye el menor \(n\) compatible con ese \(y\), y organiza la búsqueda mediante una DP de bitsets sobre suma decimal de cifras y residuos módulo \(9!\).
Si la cifra \(d\) aparece \(c_d\) veces en \(n\), entonces
$$f(n)=\sum_{d=0}^{9} c_d\,d!.$$
Así, para un \(y\) fijo, la cuestión pasa a ser: entre todos los multiconjuntos de cifras cuya suma factorial es \(y\), ¿cuál produce el menor entero decimal?
Para un multiconjunto fijo, el menor entero se obtiene ordenando las cifras de menor a mayor.
Se usa el hecho de que
$$0!=1!=1.$$
Si un candidato contiene simultáneamente 0 y 1, podemos reemplazar ese par por un 2, porque
$$0!+1!=1+1=2=2!.$$
Eso conserva \(f(n)\) y acorta el número decimal.
Si contiene un 0 pero no contiene ningún 1, entonces su cifra no nula más pequeña es al menos 2. Reemplazar un 0 por un 1 conserva \(f(n)\) y produce un entero decimal menor.
Por lo tanto, en un verdadero \(g(i)\) mínimo nunca hace falta el dígito 0. De ahí que la implementación almacene solo las cuentas de \(1,\dots,9\).
La identidad central es
$$(d+1)!=(d+1)\,d!.$$
Así, si aparecen al menos \(d+1\) copias de la cifra \(d\), esas \(d+1\) copias pueden sustituirse por una sola cifra \(d+1\). La suma factorial no cambia y el número decimal se hace más corto.
Por eso, en un candidato mínimo debe cumplirse
$$0\le c_d\le d\qquad(1\le d\le 8).$$
Repitiendo el acarreo se llega a la forma normal
$$y=c_9\cdot 9!+c_8\cdot 8!+\cdots+c_2\cdot 2!+c_1\cdot 1!,$$
con
$$0\le c_d\le d\qquad(1\le d\le 8),$$
mientras \(c_9\) queda libre. Esta es la versión truncada del sistema factorial.
La razón es:
1. ordenando un multiconjunto fijo se obtiene el menor número;
2. los ceros siempre se pueden eliminar;
3. cualquier violación de \(c_d\le d\) puede corregirse con un acarreo que reduce la longitud.
Por tanto, las cifras factoriales normalizadas son exactamente las cuentas de los dígitos del menor entero decimal \(n\) con \(f(n)=y\).
Si las cuentas son \(c_1,\dots,c_9\), el candidato mínimo es
$$\underbrace{11\cdots1}_{c_1}\underbrace{22\cdots2}_{c_2}\cdots\underbrace{99\cdots9}_{c_9},$$
y su suma de cifras es
$$sg=\sum_{d=1}^{9} d\,c_d.$$
Uno de los checkpoints del programa es
$$g(5)=25.$$
En efecto,
$$f(25)=2!+5!=2+120=122,$$
y por tanto
$$sf(25)=s(122)=1+2+2=5.$$
La forma factorial canónica de \(122\) es
$$122=1\cdot 5!+1\cdot 2!,$$
que corresponde al multiconjunto \(\{2,5\}\), así que el menor entero es \(25\).
Otro control interno es
$$g(20)=267.$$
Esto viene de
$$f(267)=2!+6!+7!=2+720+5040=5762,$$
y entonces
$$sf(267)=s(5762)=5+7+6+2=20.$$
Así se ve con claridad que el valor objetivo \(i\) es la suma decimal de cifras de \(y=f(n)\), no la de \(n\) mismo.
Escribimos
$$y=q\cdot 9!+r,\qquad 0\le r<9!.$$
Entonces \(q=c_9\), mientras que el residuo \(r\) determina de manera única \(c_1,\dots,c_8\).
Dentro de una misma clase residual módulo \(9!\), lo único que cambia es el número de nueves. Sumar \(9!\) añade exactamente un 9 a la representación canónica, por lo que el entero decimal resultante es más largo y, por tanto, mayor.
Por eso, para cada residuo, solo interesa el menor \(y\) posible.
Como
$$sf(n)=s\bigl(f(n)\bigr)=s(y),$$
la condición \(sf(n)=i\) equivale a pedir que \(y\) tenga suma decimal de cifras igual a \(i\).
El estado DP es
$$DP[\ell][s][r],$$
que significa: existe un número decimal de longitud \(\ell\), suma de cifras \(s\) y residuo \(r\bmod 9!\).
Al añadir una cifra \(d\), el residuo cambia según
$$r' \equiv r + d\cdot 10^{\ell}\pmod{9!},$$
y la suma pasa a \(s+d\). Así,
$$DP[\ell+1][s+d][r'] \leftarrow DP[\ell][s][r].$$
La implementación guarda, para cada par \((\ell,s)\), el conjunto completo de residuos como un bitset. Añadir una cifra se convierte entonces en una rotación cíclica seguida de OR.
La DP parte de longitud 0 y permite transiciones con el dígito 0, así que formalmente también representa cadenas con ceros iniciales. Eso no es un problema porque, para cada objetivo \(i\) y residuo \(r\), el solver busca la longitud \(\ell\) de menor a mayor y se queda con la primera alcanzable.
Por tanto, la \(\ell\) elegida es la verdadera longitud decimal mínima de \(y\).
Conocidos \(i\), \(r\) y la mínima longitud \(\ell\), el código reconstruye el menor \(y\) de forma voraz: prueba las cifras
$$0,1,2,\dots,9$$
en ese orden y toma la primera cuyo estado predecesor siga siendo alcanzable.
Así se obtiene el menor \(y\) compatible con esa longitud, suma de cifras y residuo.
Cada \(y\) reconstruido se convierte en sus coeficientes factoriales canónicos \(c_d\), y eso produce un candidato para \(g(i)\).
Al comparar candidatos, primero gana la menor longitud. Si hay empate, gana la cadena ordenada lexicográficamente menor, es decir, la que tiene más cifras pequeñas al principio. Eso es exactamente lo que implementa node_less.
Finalmente, la contribución al resultado es
$$sg(i)=\sum_{d=1}^{9} d\,c_d.$$
La implementación verifica
$$g(5)=25,\qquad g(20)=267,\qquad \sum_{i=1}^{20} sg(i)=156.$$
Estos controles validan la normalización, la reconstrucción y el criterio de comparación.
El constructor precalcula \(10^\ell \bmod 9!\) para \(\ell\le 18\) y luego rellena con build_dp() la tabla de bitsets para todas las longitudes hasta 18 y todas las sumas de cifras hasta 150. Para un objetivo \(i\), best_node_for_sf(i) recorre todos los residuos, encuentra la menor longitud alcanzable, reconstruye el menor \(y\) con backtrace_min_number(), lo decodifica con node_from_y() y conserva el mejor candidato mediante node_less(). Después se suman todos los \(sg(i)\).
El límite de 18 cifras para \(y\) forma parte de la implementación y basta para el rango \(i\le 150\) tratado aquí.
Tomando
$$L=18,\qquad S=150,\qquad M=9!=362880,$$
la memoria viene dominada por un bitset de tamaño \(M\) para cada par \((\ell,s)\), es decir
$$O\!\left(\frac{L\cdot S\cdot M}{64}\right)$$
palabras de máquina.
El tiempo está dominado por la construcción de esta tabla y por el recorrido posterior de residuos. Gracias al paralelismo a nivel de palabra, este método es muchísimo más rápido que una búsqueda directa sobre \(n\) o incluso sobre todos los valores decimales \(y\) con suma de cifras dada.
对一个正整数 \(n\)，定义
$$f(n)=\sum_{d\in\mathrm{digits}(n)} d!,$$
再定义
$$sf(n)=s\bigl(f(n)\bigr),$$
其中 \(s(x)\) 表示十进制数位和。
对每个 \(i\ge 1\)，再定义
$$g(i)=\min\{n\ge 1: sf(n)=i\},\qquad sg(i)=s\bigl(g(i)\bigr).$$
题目要求计算
$$\sum_{i=1}^{150} sg(i).$$
直接在 \(n\) 上暴力搜索几乎不可能，因此代码先转向
$$y=f(n),$$
再从 \(y\) 的规范阶乘表示中恢复最小的 \(n\)，最后用一个关于十进制数位和与模 \(9!\) 余数的 bitset 动态规划完成搜索。
如果数字 \(d\) 在 \(n\) 中出现了 \(c_d\) 次，那么
$$f(n)=\sum_{d=0}^{9} c_d\,d!.$$
因此，对固定的 \(y=f(n)\)，真正的问题变成：在所有阶乘和等于 \(y\) 的数字多重集中，哪一个能组成最小的十进制整数？
对于固定的多重集，把数字按从小到大排序就是最小的十进制写法。
关键事实是
$$0!=1!=1.$$
如果一个候选同时含有 0 和 1，那么可以把这一对替换成一个 2，因为
$$0!+1!=1+1=2=2!.$$
这样 \(f(n)\) 不变，但十进制长度变短，所以原来的数不可能是最小的。
如果候选含有 0 但不含 1，那么它最小的非零数字至少是 2。把一个 0 改成 1 后，\(f(n)\) 不变，而排序后的十进制整数会更小。
所以真正的最小 \(g(i)\) 从来不需要数字 0。这就是为什么代码只存储 \(1,\dots,9\) 的计数。
核心恒等式是
$$(d+1)!=(d+1)\,d!.$$
因此，只要某个数字 \(d\) 出现了至少 \(d+1\) 次，就可以把这 \(d+1\) 个 \(d\) 替换成一个 \(d+1\)。阶乘和保持不变，但十进制长度严格减少。
于是，在最小表示中一定有
$$0\le c_d\le d\qquad(1\le d\le 8).$$
不断应用这种“进位”后，会得到唯一的规范形式
$$y=c_9\cdot 9!+c_8\cdot 8!+\cdots+c_2\cdot 2!+c_1\cdot 1!,$$
其中
$$0\le c_d\le d\qquad(1\le d\le 8),$$
而 \(c_9\) 不受限制。这正是截断到 \(9!\) 的阶乘数制。
理由有三点：
1. 固定数字多重集时，排序写法最小；
2. 0 总能被消去；
3. 如果某个 \(c_d\) 超过上界，就能继续进位，从而缩短长度。
因此，规范化后的阶乘数字不只是 \(y\) 的一种编码，它恰好就是满足 \(f(n)=y\) 的最小十进制整数的数字计数。
若规范计数为 \(c_1,\dots,c_9\)，那么对应最小整数就是
$$\underbrace{11\cdots1}_{c_1}\underbrace{22\cdots2}_{c_2}\cdots\underbrace{99\cdots9}_{c_9}.$$
它的数位和为
$$sg=\sum_{d=1}^{9} d\,c_d.$$
程序中的一个检查点是
$$g(5)=25.$$
因为
$$f(25)=2!+5!=2+120=122,$$
所以
$$sf(25)=s(122)=1+2+2=5.$$
而 \(122\) 的规范阶乘分解是
$$122=1\cdot 5!+1\cdot 2!,$$
对应的数字多重集就是 \(\{2,5\}\)，因此最小整数是 \(25\)。
第二个检查点是
$$g(20)=267.$$
因为
$$f(267)=2!+6!+7!=2+720+5040=5762,$$
从而
$$sf(267)=s(5762)=5+7+6+2=20.$$
这个例子说明，目标 \(i\) 来自 \(y=f(n)\) 的十进制数位和，而不是 \(n\) 本身的数位和。
把 \(y\) 写成
$$y=q\cdot 9!+r,\qquad 0\le r<9!.$$
那么 \(q=c_9\)，而余数 \(r\) 唯一决定 \(c_1,\dots,c_8\)。
也就是说，在同一个模 \(9!\) 余数类中，唯一会变化的是数字 9 的个数。把 \(y\) 增加一个 \(9!\)，规范表示里只会多出一个 9，而这会让对应的十进制整数更长、更大。
因此，在每个余数类里，只有最小的可行 \(y\) 才有意义。
由于
$$sf(n)=s\bigl(f(n)\bigr)=s(y),$$
条件 \(sf(n)=i\) 等价于“\(y\) 的十进制数位和等于 \(i\)”。
动态规划状态写作
$$DP[\ell][s][r],$$
表示：存在一个长度为 \(\ell\)、数位和为 \(s\)、模 \(9!\) 余数为 \(r\) 的十进制数。
加入一个新数字 \(d\) 后，余数变成
$$r' \equiv r + d\cdot 10^{\ell}\pmod{9!},$$
数位和变成 \(s+d\)。因此转移是
$$DP[\ell+1][s+d][r'] \leftarrow DP[\ell][s][r].$$
代码对每个 \((\ell,s)\) 都把全部余数层存成 bitset，因此“加入一个数字”就变成循环平移再做 OR。
DP 从长度 0 开始，也允许加入数字 0，所以形式上会包含带前导零的写法。这没有问题，因为对固定的目标 \(i\) 和余数 \(r\)，程序总是按长度从小到大扫描，取第一个可达的长度。
因此最后选中的 \(\ell\) 就是 \(y\) 的真实最短十进制长度。
一旦知道了 \(i\)、\(r\) 和最小长度 \(\ell\)，代码就贪心回溯最小的 \(y\)。它按顺序尝试
$$0,1,2,\dots,9$$
这些数字，只要前驱状态仍然可达，就立即选取当前最小可行数字。
这样得到的就是该长度、该数位和、该余数下最小的十进制 \(y\)。
每个回溯得到的 \(y\) 都会被解码成规范阶乘系数 \(c_d\)，从而得到一个候选 \(g(i)\)。
比较候选时，先比较长度；更短的整数一定更小。若长度相同，则比较排序后的数字串，谁在前面有更多小数字谁更优。这就是 node_less 的作用。
最终该 \(i\) 对答案的贡献为
$$sg(i)=\sum_{d=1}^{9} d\,c_d.$$
程序验证了三个关键结果：
$$g(5)=25,\qquad g(20)=267,\qquad \sum_{i=1}^{20} sg(i)=156.$$
这三个检查一起验证了规范化、回溯和候选比较逻辑。
构造函数先预计算 \(10^\ell \bmod 9!\)，再调用 build_dp() 填满所有 \(\ell\le 18\)、\(s\le 150\) 的 bitset 动态规划表。对某个目标 \(i\)，函数 best_node_for_sf(i) 遍历全部余数，找到最短可达长度，用 backtrace_min_number() 回溯出最小的十进制 \(y\)，再用 node_from_y() 把它转成规范计数向量，并用 node_less() 保留最优候选。最后把所有 \(sg(i)\) 累加。
实现里把 \(y\) 的十进制长度上限设为 18；对于本题 \(i\le 150\) 的目标范围，这个上限是足够的。
记
$$L=18,\qquad S=150,\qquad M=9!=362880.$$
那么 DP 为每个 \((\ell,s)\) 存一个大小为 \(M\) 的余数 bitset，因此空间复杂度为
$$O\!\left(\frac{L\cdot S\cdot M}{64}\right).$$
时间主要花在构建这张表以及随后按余数扫描上。由于所有余数转移都是 bitset 旋转与 OR，具有很强的字级并行性，所以远比直接枚举 \(n\) 或枚举所有满足数位和条件的 \(y\) 更快。
Для положительного целого \(n\) определим
$$f(n)=\sum_{d\in\mathrm{digits}(n)} d!,$$
а затем
$$sf(n)=s\bigl(f(n)\bigr),$$
где \(s(x)\) — обычная сумма десятичных цифр.
Для каждого \(i\ge 1\) задаются
$$g(i)=\min\{n\ge 1: sf(n)=i\},\qquad sg(i)=s\bigl(g(i)\bigr).$$
Нужно вычислить
$$\sum_{i=1}^{150} sg(i).$$
Прямой поиск по \(n\) слишком дорог, поэтому код переходит к величине
$$y=f(n),$$
восстанавливает из неё минимальное возможное \(n\), а затем использует bitset-DP по десятичной сумме цифр и остаткам modulo \(9!\).
Если цифра \(d\) встречается в \(n\) ровно \(c_d\) раз, то
$$f(n)=\sum_{d=0}^{9} c_d\,d!.$$
Значит, при фиксированном \(y\) задача сводится к вопросу: какой мультимножество цифр с такой суммой факториалов даёт минимальное десятичное число?
Для фиксированного мультимножества минимальное число получается простой сортировкой цифр по неубыванию.
Здесь важно, что
$$0!=1!=1.$$
Если кандидат содержит и 0, и 1, то эту пару можно заменить одной цифрой 2, потому что
$$0!+1!=1+1=2=2!.$$
Это сохраняет \(f(n)\), но уменьшает длину числа, значит исходный кандидат не был минимальным.
Если кандидат содержит 0, но не содержит 1, то его минимальная ненулевая цифра не меньше 2. Замена одного нуля на единицу сохраняет \(f(n)\) и даёт меньшее положительное десятичное число.
Следовательно, настоящие минимальные кандидаты никогда не используют цифру 0. Поэтому реализация хранит только счётчики цифр \(1,\dots,9\).
Ключевая формула:
$$(d+1)!=(d+1)\,d!.$$
Если цифра \(d\) встречается хотя бы \(d+1\) раз, эти \(d+1\) копий можно заменить одной цифрой \(d+1\). Сумма факториалов не меняется, а длина десятичной записи уменьшается.
Поэтому в минимальном кандидате обязательно
$$0\le c_d\le d\qquad(1\le d\le 8).$$
После всех переносов получается единственная нормальная форма
$$y=c_9\cdot 9!+c_8\cdot 8!+\cdots+c_2\cdot 2!+c_1\cdot 1!,$$
где
$$0\le c_d\le d\qquad(1\le d\le 8),$$
а \(c_9\) не ограничен. Это и есть факториальная система счисления, обрезанная на \(9!\).
Причина состоит из трёх шагов:
1. для фиксированного мультимножества отсортированная запись даёт минимальное число;
2. нули всегда можно удалить;
3. любое нарушение условия \(c_d\le d\) исправляется переносом, который уменьшает длину.
Значит, нормализованные факториальные коэффициенты — это не просто код числа \(y\), а именно счётчики цифр минимального десятичного \(n\) с \(f(n)=y\).
Если известны \(c_1,\dots,c_9\), то минимальный кандидат имеет вид
$$\underbrace{11\cdots1}_{c_1}\underbrace{22\cdots2}_{c_2}\cdots\underbrace{99\cdots9}_{c_9},$$
а его сумма цифр равна
$$sg=\sum_{d=1}^{9} d\,c_d.$$
Один из checkpoint'ов программы:
$$g(5)=25.$$
Действительно,
$$f(25)=2!+5!=2+120=122,$$
поэтому
$$sf(25)=s(122)=1+2+2=5.$$
Каноническая факториальная запись числа \(122\) равна
$$122=1\cdot 5!+1\cdot 2!,$$
что соответствует мультимножеству \(\{2,5\}\), а значит минимальному числу \(25\).
Второй встроенный тест:
$$g(20)=267.$$
Он следует из
$$f(267)=2!+6!+7!=2+720+5040=5762,$$
и, следовательно,
$$sf(267)=s(5762)=5+7+6+2=20.$$
Этот пример показывает, что целевое значение \(i\) — это сумма цифр числа \(y=f(n)\), а не самого \(n\).
Пусть
$$y=q\cdot 9!+r,\qquad 0\le r<9!.$$
Тогда \(q=c_9\), а остаток \(r\) однозначно определяет нижние коэффициенты \(c_1,\dots,c_8\).
Внутри одного класса вычетов modulo \(9!\) меняется только число девяток. Добавление одного \(9!\) даёт в каноническом кандидате ещё одну цифру 9, то есть увеличивает длину и делает число больше.
Следовательно, в каждом классе вычетов нас интересует только минимальное подходящее \(y\).
Так как
$$sf(n)=s\bigl(f(n)\bigr)=s(y),$$
условие \(sf(n)=i\) эквивалентно тому, что десятичная сумма цифр числа \(y\) равна \(i\).
Состояние динамики:
$$DP[\ell][s][r],$$
где это означает существование десятичного числа длины \(\ell\), с суммой цифр \(s\) и остатком \(r\bmod 9!\).
При добавлении цифры \(d\) остаток становится
$$r' \equiv r + d\cdot 10^{\ell}\pmod{9!},$$
а сумма цифр — \(s+d\). То есть
$$DP[\ell+1][s+d][r'] \leftarrow DP[\ell][s][r].$$
Код хранит для каждой пары \((\ell,s)\) весь слой остатков в виде bitset. Поэтому добавление цифры превращается в циклический сдвиг bitset и OR.
DP стартует с длины 0 и допускает добавление цифры 0, так что формально она описывает и записи с ведущими нулями. Это не проблема, потому что для каждого \(i\) и \(r\) алгоритм просматривает длины по возрастанию и берёт первую достижимую.
Значит, выбранная длина \(\ell\) и есть настоящая минимальная десятичная длина числа \(y\).
Зная \(i\), \(r\) и минимальную длину \(\ell\), код восстанавливает минимальное \(y\) жадно. На каждом шаге он пробует цифры
$$0,1,2,\dots,9$$
в этом порядке и берёт первую, для которой допустимо предыдущее состояние DP.
Так строится минимальное десятичное число с нужной длиной, суммой цифр и остатком.
Каждое восстановленное \(y\) декодируется в канонические коэффициенты \(c_d\), откуда получается один кандидат для \(g(i)\).
При сравнении кандидатов сначала выигрывает меньшая длина. При равной длине выигрывает лексикографически меньшая отсортированная запись, то есть та, где впереди больше маленьких цифр. Это и реализует node_less.
После этого вклад в ответ равен
$$sg(i)=\sum_{d=1}^{9} d\,c_d.$$
Код проверяет три равенства:
$$g(5)=25,\qquad g(20)=267,\qquad \sum_{i=1}^{20} sg(i)=156.$$
Они проверяют нормализацию, восстановление и порядок сравнения кандидатов.
Конструктор заранее вычисляет \(10^\ell \bmod 9!\) для \(\ell\le 18\), затем через build_dp() строит bitset-таблицу для всех длин до 18 и всех сумм цифр до 150. Для запроса \(i\) функция best_node_for_sf(i) перебирает все остатки, находит минимальную достижимую длину, восстанавливает минимальное \(y\) через backtrace_min_number(), декодирует его с помощью node_from_y() и оставляет лучший кандидат при помощи node_less(). После этого значения \(sg(i)\) суммируются.
Ограничение длины \(y\) числом 18 является частью реализации и достаточно для диапазона \(i\le 150\), рассматриваемого в задаче.
Положим
$$L=18,\qquad S=150,\qquad M=9!=362880.$$
Тогда память определяется bitset-слоем размера \(M\) для каждой пары \((\ell,s)\), то есть
$$O\!\left(\frac{L\cdot S\cdot M}{64}\right)$$
машинных слов.
Время в основном тратится на построение этой таблицы и на последующий просмотр остатков. Благодаря сильной битовой параллельности этот подход намного быстрее любого прямого перебора по \(n\) или по всем десятичным \(y\) с заданной суммой цифр.
لعدد صحيح موجب \(n\)، نعرّف
$$f(n)=\sum_{d\in\mathrm{digits}(n)} d!,$$
ثم نعرّف
$$sf(n)=s\bigl(f(n)\bigr),$$
حيث \(s(x)\) هو مجموع الأرقام العشري المعتاد.
ولكل \(i\ge 1\) نضع
$$g(i)=\min\{n\ge 1: sf(n)=i\},\qquad sg(i)=s\bigl(g(i)\bigr).$$
والمطلوب هو حساب
$$\sum_{i=1}^{150} sg(i).$$
البحث المباشر في \(n\) غير عملي تمامًا، لذلك يحول الحل المسألة إلى البحث في
$$y=f(n),$$
ثم يستخرج أصغر \(n\) ممكن لهذا \(y\)، وبعد ذلك يستخدم برمجة ديناميكية مبنية على bitset وفق مجموع الأرقام العشري وبواقي modulo \(9!\).
إذا ظهر الرقم \(d\) عدد \(c_d\) من المرات داخل \(n\)، فإن
$$f(n)=\sum_{d=0}^{9} c_d\,d!.$$
إذًا إذا ثبتت قيمة \(y\)، يصبح السؤال الحقيقي: أي متعدد أرقام يحقق هذه القيمة ويعطي أصغر عدد عشري؟
ولأي متعدد أرقام ثابت، فإن أصغر ترتيب عشري ينتج من ترتيب الأرقام تصاعديًا.
الحقيقة الأساسية هنا هي
$$0!=1!=1.$$
فإذا احتوى المرشح على 0 و1 معًا، فيمكن استبدال هذا الزوج برقم واحد هو 2، لأن
$$0!+1!=1+1=2=2!.$$
بهذا تبقى قيمة \(f(n)\) نفسها، لكن طول العدد العشري ينقص، ولذلك لا يمكن أن يكون المرشح الأصلي هو الأصغر.
أما إذا احتوى المرشح على 0 من دون 1، فإن أصغر رقم غير صفري فيه لا بد أن يكون على الأقل 2. وعند استبدال صفر واحد بالرقم 1 تبقى قيمة \(f(n)\) كما هي، لكن العدد العشري الناتج بعد الترتيب يصبح أصغر.
إذن المرشح الأدنى الحقيقي لا يحتاج أبدًا إلى الرقم 0. ولهذا يخزن الكود فقط أعداد الأرقام \(1,\dots,9\).
الهوية المحورية هي
$$(d+1)!=(d+1)\,d!.$$
ولذلك إذا ظهر الرقم \(d\) على الأقل \(d+1\) مرة، يمكن استبدال هذه النسخ \(d+1\) بنسخة واحدة من الرقم \(d+1\). مجموع العاملات يبقى نفسه، لكن طول العدد العشري يقصر.
ومن ثم في أي تمثيل أدنى يجب أن يتحقق
$$0\le c_d\le d\qquad(1\le d\le 8).$$
وبتكرار عمليات النقل نصل إلى الصورة القياسية الوحيدة
$$y=c_9\cdot 9!+c_8\cdot 8!+\cdots+c_2\cdot 2!+c_1\cdot 1!,$$
مع
$$0\le c_d\le d\qquad(1\le d\le 8),$$
بينما يبقى \(c_9\) غير محدود. وهذا هو نظام العد العاملي بعد قطعه عند \(9!\).
السبب يتكون من ثلاث ملاحظات:
1. إذا ثبت متعدد الأرقام، فإن ترتيبه تصاعديًا يعطي أصغر عدد عشري.
2. يمكن دائمًا حذف الأصفار كما رأينا.
3. إذا خالف أحد المعاملات الشرط \(c_d\le d\)، فإن النقل يقلل طول العدد مباشرة.
إذن المعاملات العاملية بعد التطبيع ليست مجرد ترميز للقيمة \(y\)، بل هي بالضبط أعداد الأرقام في أصغر عدد عشري \(n\) يحقق \(f(n)=y\).
فإذا كانت المعاملات \(c_1,\dots,c_9\)، فالمرشح الأدنى هو
$$\underbrace{11\cdots1}_{c_1}\underbrace{22\cdots2}_{c_2}\cdots\underbrace{99\cdots9}_{c_9},$$
ويكون مجموع أرقامه
$$sg=\sum_{d=1}^{9} d\,c_d.$$
من نقاط التحقق في البرنامج أن
$$g(5)=25.$$
وذلك لأن
$$f(25)=2!+5!=2+120=122,$$
ومن ثم
$$sf(25)=s(122)=1+2+2=5.$$
والتفكيك العاملي القياسي للعدد \(122\) هو
$$122=1\cdot 5!+1\cdot 2!,$$
أي أن متعدد الأرقام الأدنى هو \(\{2,5\}\)، وبالتالي أصغر عدد هو \(25\).
هناك أيضًا نقطة التحقق
$$g(20)=267.$$
وذلك لأن
$$f(267)=2!+6!+7!=2+720+5040=5762,$$
ومن ثم
$$sf(267)=s(5762)=5+7+6+2=20.$$
هذا المثال يوضح أن القيمة الهدف \(i\) تأتي من مجموع أرقام \(y=f(n)\)، لا من مجموع أرقام \(n\) نفسه.
لنكتب
$$y=q\cdot 9!+r,\qquad 0\le r<9!.$$
عندها يكون \(q=c_9\)، بينما يحدد الباقي \(r\) المعاملات \(c_1,\dots,c_8\) بشكل وحيد.
إذن داخل فئة الباقي الواحدة modulo \(9!\)، الشيء الوحيد الذي يتغير هو عدد التسعات. وإذا زدنا \(y\) بمقدار \(9!\)، فإن الصورة القياسية تضيف رقم 9 واحدًا، فيزداد طول العدد العشري ويصبح أكبر.
لذلك لا يهم في كل فئة بواقي إلا أصغر \(y\) ممكن.
بما أن
$$sf(n)=s\bigl(f(n)\bigr)=s(y),$$
فإن الشرط \(sf(n)=i\) يكافئ أن يكون مجموع أرقام \(y\) العشري مساويًا لـ \(i\).
تكون حالة البرمجة الديناميكية
$$DP[\ell][s][r],$$
ومعناها: يوجد عدد عشري طوله \(\ell\)، ومجموع أرقامه \(s\)، وباقيه \(r\bmod 9!\).
عند إضافة رقم جديد \(d\)، يتغير الباقي وفق
$$r' \equiv r + d\cdot 10^{\ell}\pmod{9!},$$
ويصبح مجموع الأرقام \(s+d\). أي أن الانتقال هو
$$DP[\ell+1][s+d][r'] \leftarrow DP[\ell][s][r].$$
يخزن الكود كل طبقة بواقي خاصة بالزوج \((\ell,s)\) على شكل bitset. ومن ثم فإن إضافة رقم جديد تتحول إلى تدوير دائري ثم OR.
تبدأ الـ DP بطول 0 وتسمح أيضًا بالرقم 0، ولذلك فهي تمثل صوريًا سلاسل ذات أصفار بادئة. هذا لا يسبب مشكلة، لأن الخوارزمية تمسح الأطوال من الأصغر إلى الأكبر لكل هدف \(i\) ولكل باقي \(r\)، وتختار أول طول ممكن.
وبذلك يكون الطول المختار هو بالفعل أقصر طول عشري حقيقي للقيمة \(y\).
بعد معرفة \(i\) و\(r\) وأصغر طول \(\ell\)، يعيد الكود بناء أصغر \(y\) بطريقة جشعة. فهو يجرب الأرقام
$$0,1,2,\dots,9$$
بهذا الترتيب، ويختار أول رقم يبقي الحالة السابقة ممكنة داخل الـ DP.
وبذلك نحصل على أصغر \(y\) يحقق الطول ومجموع الأرقام والباقي المحدد.
كل قيمة \(y\) معاد بناؤها تُفكك إلى معاملاتها العاملية القياسية \(c_d\)، ومن ثم تعطينا مرشحًا واحدًا لـ \(g(i)\).
عند المقارنة بين المرشحين، يفوز الأقصر أولًا. وإذا تساوى الطول، يفوز المرشح الذي يملك أرقامًا أصغر في البداية أكثر، أي الأصغر ترتيبًا بعد الفرز. وهذا بالضبط ما تطبقه الدالة node_less.
بعد اختيار المرشح الأفضل، تكون مساهمته في الجواب
$$sg(i)=\sum_{d=1}^{9} d\,c_d.$$
يتحقق البرنامج من العلاقات
$$g(5)=25,\qquad g(20)=267,\qquad \sum_{i=1}^{20} sg(i)=156.$$
وهذه تختبر منطق التطبيع، وإعادة البناء، وترتيب المرشحين.
يقوم الباني أولًا بحساب \(10^\ell \bmod 9!\) لكل \(\ell\le 18\)، ثم يبني عبر build_dp() جدول bitset لكل الأطوال حتى 18 ولكل مجاميع الأرقام حتى 150. وعند الاستعلام عن قيمة \(i\)، تقوم الدالة best_node_for_sf(i) بمسح جميع البواقي، ثم إيجاد أصغر طول ممكن، ثم إعادة بناء أصغر \(y\) عبر backtrace_min_number()، ثم فك هذا \(y\) بواسطة node_from_y()، وأخيرًا اختيار أفضل مرشح باستخدام node_less(). وفي النهاية تُجمع كل قيم \(sg(i)\).
كما أن الحد الأقصى لطول \(y\) في التطبيق هو 18 خانة، وهذا كافٍ لنطاق الهدف \(i\le 150\) المستخدم هنا.
لنأخذ
$$L=18,\qquad S=150,\qquad M=9!=362880.$$
عندها تتحدد الذاكرة بطبقة bitset واحدة بحجم \(M\) لكل زوج \((\ell,s)\)، أي
$$O\!\left(\frac{L\cdot S\cdot M}{64}\right)$$
كلمات آلية.
أما الزمن فيهيمن عليه بناء هذه الطبقة الكبيرة ثم مسح البواقي لاحقًا. وبفضل المعالجة المتوازية على مستوى البتات، فإن هذه الطريقة أسرع بكثير من البحث المباشر في \(n\) أو حتى في جميع قيم \(y\) ذات مجموع الأرقام المعطى.