For each integer \(k \ge 2\), define the sequence
$$f_k(0)=1,\qquad f_k(n)=f_k(n-1)+f_k\left(\left\lfloor\frac{n}{k}\right\rfloor\right)\qquad (n\ge 1).$$
The required value is
$$\sum_{k=2}^{10} f_k(N)\pmod{10^9+7},$$
with \(N=10^{14}\) in the standard instance. A direct dynamic program up to \(N\) is impossible, so the solution converts the recurrence into a digit-by-digit polynomial computation.
Fix one base \(k\), and write \(f(n)=f_k(n)\). Let the base-\(k\) expansion of \(n\) be
$$n=d_0+d_1k+\cdots+d_Lk^L,\qquad 0\le d_i\le k-1.$$
The aim is to evaluate \(f(n)\) without iterating through every integer from \(1\) to \(n\).
Since \(f(0)=1\), the recurrence telescopes into
$$f(n)=\sum_{m=0}^{n} f\left(\left\lfloor\frac{m}{k}\right\rfloor\right).$$
Now write \(n=kx+s\) with \(0\le s\le k-1\). Grouping the integers \(m\) by the quotient \(q=\lfloor m/k\rfloor\) gives
$$f(kx+s)=k\sum_{q=0}^{x-1} f(q)+(s+1)f(x).$$
So one base-\(k\) digit tells us how a prefix sum of previous values is sampled.
Apply the same identity again to \(f(x)\), then to the next quotient, and continue until the quotient becomes \(0\). The result is an exact nested-sum formula:
$$f(n)=\sum_{x_L=0}^{d_L}\sum_{x_{L-1}=0}^{kx_L+d_{L-1}}\cdots\sum_{x_1=0}^{kx_2+d_1}\sum_{x_0=0}^{kx_1+d_0}1.$$
Each level introduces one variable whose upper bound is \(k\) times the next variable plus the corresponding digit of \(n\). The depth is only the number of base-\(k\) digits, which is \(O(\log_k n)\).
For any function \(P(x)\), define
$$T_s[P](x)=\sum_{t=0}^{kx+s} P(t),\qquad 0\le s\le k-1.$$
Then the nested sum can be written compactly as
$$f(n)=\left(T_{d_L}\circ T_{d_{L-1}}\circ\cdots\circ T_{d_0}\right)[1](0).$$
Thus the problem becomes: start from the constant polynomial \(1\), and repeatedly apply the operator “take a prefix sum and evaluate it at \(kx+s\)” according to the digits of \(n\).
If \(P(x)\) is a polynomial of degree \(r\), then its prefix sum
$$S[P](x)=\sum_{t=0}^{x}P(t)$$
is a polynomial of degree \(r+1\), and the substitution \(x\mapsto kx+s\) preserves polynomial form. Therefore repeated applications of \(T_s[P](x)=S[P](kx+s)\) never leave the polynomial world.
For a monomial \(x^p\), the required prefix sum is
$$\sum_{t=0}^{x} t^p=\sum_{j=0}^{p} S(p,j)\,j!\binom{x+1}{j+1},$$
where \(S(p,j)\) denotes a Stirling number of the second kind. This Faulhaber-type identity is exactly what lets the implementation precompute every power-sum polynomial once and reuse it.
The implementation does not compose a single operator chain literally. Instead it scans the base-\(k\) digits of \(n\) from least significant to most significant and keeps two polynomial states:
one state for choices that still match the already processed part of \(n\), and one state for choices that are already strictly smaller.
If the next digit is \(d_j\), and \(E_{j-1}\) and \(B_{j-1}\) are the exact and below states from the previous step, then with \(S[P](x)=\sum_{t=0}^{x}P(t)\) we have
$$B_j(x)=\sum_{s=0}^{k-1} S[B_{j-1}](kx+s),$$
$$E_j(x)=\sum_{s=0}^{d_j-1} S[B_{j-1}](kx+s)+S[E_{j-1}](kx+d_j).$$
The initial one-digit states are
$$B_0(x)=k,\qquad E_0(x)=d_0+1,$$
because a full last-digit block contributes \(k\) choices, while the truncated block allowed by \(d_0\) contributes \(d_0+1\). After the final digit, the desired value is simply
$$f(n)=E_L(0).$$
Since \(10=(20)_5\), the digits are \(d_0=0\) and \(d_1=2\). The nested-sum formula gives
$$f_5(10)=\sum_{x_1=0}^{2}\sum_{x_0=0}^{5x_1}1=1+6+11=18,$$
which matches the sample checkpoint used by the implementation.
The polynomial-state update gives the same answer. Initially, \(B_0(x)=5\) and \(E_0(x)=1\). Their prefix sums are \(5x+5\) and \(x+1\). Therefore
$$E_1(x)=\sum_{s=0}^{1}(25x+5s+5)+(5x+3)=55x+18,$$
so
$$f_5(10)=E_1(0)=18.$$
The C++, Python, and Java implementations follow the same plan. They first determine a safe maximum polynomial degree from the binary length of \(N\), because base \(2\) yields the largest number of digits. Then they precompute binomial coefficients, Stirling numbers of the second kind, factorials, and the explicit polynomials for \(\sum_{t=0}^{x} t^p\) for every degree that can appear.
For each \(k=2,3,\dots,10\), the implementation converts \(N\) to base \(k\), initializes the exact and below states for the least significant digit, and processes the remaining digits one by one. Each digit step performs two generic algebraic operations:
$$P(x)\longmapsto \sum_{t=0}^{x}P(t),\qquad P(x)\longmapsto P(kx+s).$$
Because the states are stored by coefficients, both operations are done symbolically modulo \(10^9+7\), never by iterating up to \(N\). After the highest digit is processed, the exact-state polynomial is evaluated at \(x=0\), giving \(f_k(N)\). The final answer is the sum of these nine values modulo \(10^9+7\).
Let \(D=\lfloor\log_2 N\rfloor+2\). This bounds the number of digits in every base from \(2\) to \(10\), so every polynomial degree is \(O(D)\). The precomputation of binomial and power-sum data costs \(O(D^3)\) time and \(O(D^2)\) memory. For a fixed base \(k\), processing all digits costs \(O(kD^3)\) time in the worst case, because the degree grows linearly with the number of processed digits and each digit step performs a bounded number of \(O(D^2)\) polynomial transforms. Here \(k\le 10\) and \(D\) is only about the number of binary digits of \(10^{14}\), so the method is easily fast enough.
Für jede ganze Zahl \(k \ge 2\) sei die Folge
$$f_k(0)=1,\qquad f_k(n)=f_k(n-1)+f_k\left(\left\lfloor\frac{n}{k}\right\rfloor\right)\qquad (n\ge 1)$$
gegeben. Gesucht ist
$$\sum_{k=2}^{10} f_k(N)\pmod{10^9+7},$$
wobei im Standardfall \(N=10^{14}\) ist. Ein direktes dynamisches Programm bis \(N\) ist unmöglich, daher wandelt die Lösung die Rekurrenz in eine ziffernweise Polynomrechnung um.
Fixiere eine Basis \(k\) und schreibe \(f(n)=f_k(n)\). Die Darstellung von \(n\) in Basis \(k\) sei
$$n=d_0+d_1k+\cdots+d_Lk^L,\qquad 0\le d_i\le k-1.$$
Wir wollen \(f(n)\) berechnen, ohne alle Zahlen von \(1\) bis \(n\) durchzulaufen.
Aus \(f(0)=1\) folgt durch Teleskopieren
$$f(n)=\sum_{m=0}^{n} f\left(\left\lfloor\frac{m}{k}\right\rfloor\right).$$
Setze nun \(n=kx+s\) mit \(0\le s\le k-1\). Gruppiert man die Werte \(m\) nach dem Quotienten \(q=\lfloor m/k\rfloor\), so erhält man
$$f(kx+s)=k\sum_{q=0}^{x-1} f(q)+(s+1)f(x).$$
Eine einzelne Ziffer in Basis \(k\) steuert also, wie eine Präfixsumme früherer Werte abgetastet wird.
Wendet man dieselbe Identität erneut auf \(f(x)\), dann auf den nächsten Quotienten usw. an, entsteht eine exakte verschachtelte Summe:
$$f(n)=\sum_{x_L=0}^{d_L}\sum_{x_{L-1}=0}^{kx_L+d_{L-1}}\cdots\sum_{x_1=0}^{kx_2+d_1}\sum_{x_0=0}^{kx_1+d_0}1.$$
Jede Ebene führt eine Variable ein, deren obere Grenze aus \(k\) mal der nächsten Variable plus der zugehörigen Ziffer von \(n\) besteht. Die Tiefe ist nur die Anzahl der Ziffern von \(n\) in Basis \(k\), also \(O(\log_k n)\).
Für jede Funktion \(P(x)\) definieren wir
$$T_s[P](x)=\sum_{t=0}^{kx+s} P(t),\qquad 0\le s\le k-1.$$
Dann lässt sich die verschachtelte Summe kompakt als
$$f(n)=\left(T_{d_L}\circ T_{d_{L-1}}\circ\cdots\circ T_{d_0}\right)[1](0)$$
schreiben. Das Problem reduziert sich damit auf folgendes: Starte mit dem konstanten Polynom \(1\) und wende entsprechend den Ziffern von \(n\) wiederholt den Operator „Präfixsumme bilden und bei \(kx+s\) auswerten“ an.
Ist \(P(x)\) ein Polynom vom Grad \(r\), dann ist seine Präfixsumme
$$S[P](x)=\sum_{t=0}^{x}P(t)$$
ein Polynom vom Grad \(r+1\), und die Substitution \(x\mapsto kx+s\) erhält die Polynomform. Wiederholte Anwendungen von \(T_s[P](x)=S[P](kx+s)\) verlassen also nie die Welt der Polynome.
Für ein Monom \(x^p\) gilt
$$\sum_{t=0}^{x} t^p=\sum_{j=0}^{p} S(p,j)\,j!\binom{x+1}{j+1},$$
wobei \(S(p,j)\) die Stirling-Zahl zweiter Art bezeichnet. Genau diese Faulhaber-artige Identität erlaubt es der Implementierung, alle Potenzsummen-Polynome einmal vorzuberechnen und danach wiederzuverwenden.
Die Implementierung komponiert die Operatoren nicht wörtlich als eine einzige Kette. Stattdessen liest sie die Ziffern von \(n\) in Basis \(k\) von der niederwertigsten zur höchstwertigen und hält zwei Polynomzustände:
einen Zustand für Entscheidungen, die noch exakt mit dem bereits verarbeiteten Teil von \(n\) übereinstimmen, und einen Zustand für Entscheidungen, die bereits strikt kleiner sind.
Ist die nächste Ziffer \(d_j\), und seien \(E_{j-1}\) und \(B_{j-1}\) die exakten bzw. kleineren Zustände aus dem vorigen Schritt, dann gilt mit \(S[P](x)=\sum_{t=0}^{x}P(t)\)
$$B_j(x)=\sum_{s=0}^{k-1} S[B_{j-1}](kx+s),$$
$$E_j(x)=\sum_{s=0}^{d_j-1} S[B_{j-1}](kx+s)+S[E_{j-1}](kx+d_j).$$
Die Anfangszustände für eine einzelne Ziffer sind
$$B_0(x)=k,\qquad E_0(x)=d_0+1,$$
denn ein vollständiger letzter Ziffernblock liefert \(k\) Möglichkeiten, während der abgeschnittene Block durch \(d_0\) genau \(d_0+1\) Möglichkeiten besitzt. Nach der letzten Ziffer ist der gesuchte Wert einfach
$$f(n)=E_L(0).$$
Da \(10=(20)_5\), sind die Ziffern \(d_0=0\) und \(d_1=2\). Die verschachtelte Summenformel liefert
$$f_5(10)=\sum_{x_1=0}^{2}\sum_{x_0=0}^{5x_1}1=1+6+11=18,$$
genau den Kontrollwert der Implementierung.
Auch die Polynomzustände geben dasselbe Resultat. Anfangs ist \(B_0(x)=5\) und \(E_0(x)=1\). Die Präfixsummen sind \(5x+5\) bzw. \(x+1\). Daher
$$E_1(x)=\sum_{s=0}^{1}(25x+5s+5)+(5x+3)=55x+18,$$
und somit
$$f_5(10)=E_1(0)=18.$$
Die C++-, Python- und Java-Implementierungen folgen demselben Plan. Zunächst bestimmen sie einen sicheren maximalen Polynomgrad aus der Binärlänge von \(N\), denn Basis \(2\) erzeugt die größte Ziffernzahl. Danach werden Binomialkoeffizienten, Stirling-Zahlen zweiter Art, Fakultäten und die expliziten Polynome für \(\sum_{t=0}^{x} t^p\) für alle relevanten Grade vorab berechnet.
Für jedes \(k=2,3,\dots,10\) wird \(N\) in Basis \(k\) zerlegt, der exakte und der kleinere Zustand für die niederwertigste Ziffer initialisiert und dann die restlichen Ziffern nacheinander verarbeitet. Jeder Ziffernschritt verwendet zwei algebraische Standardoperationen:
$$P(x)\longmapsto \sum_{t=0}^{x}P(t),\qquad P(x)\longmapsto P(kx+s).$$
Da die Zustände über ihre Koeffizienten gespeichert werden, erfolgen beide Operationen symbolisch modulo \(10^9+7\), nie durch Iteration bis \(N\). Nach der höchstwertigen Ziffer wird das exakte Zustandspolynom bei \(x=0\) ausgewertet und liefert \(f_k(N)\). Die endgültige Antwort ist die Summe dieser neun Werte modulo \(10^9+7\).
Sei \(D=\lfloor\log_2 N\rfloor+2\). Das begrenzt die Ziffernzahl in allen Basen von \(2\) bis \(10\), also auch jeden auftretenden Polynomgrad durch \(O(D)\). Die Vorberechnung der Binomial- und Potenzsummendaten kostet \(O(D^3)\) Zeit und \(O(D^2)\) Speicher. Für eine feste Basis \(k\) kostet die Verarbeitung aller Ziffern im schlechtesten Fall \(O(kD^3)\) Zeit, weil der Grad linear mit der Anzahl verarbeiteter Ziffern wächst und jeder Ziffernschritt nur eine beschränkte Zahl von \(O(D^2)\)-Transformationen ausführt. Hier gilt \(k\le 10\), und \(D\) ist nur ungefähr die Anzahl der Binärziffern von \(10^{14}\), daher ist das Verfahren problemlos schnell genug.
Her \(k \ge 2\) tamsayısı için dizi
$$f_k(0)=1,\qquad f_k(n)=f_k(n-1)+f_k\left(\left\lfloor\frac{n}{k}\right\rfloor\right)\qquad (n\ge 1)$$
şeklinde tanımlanır. İstenen değer
$$\sum_{k=2}^{10} f_k(N)\pmod{10^9+7}$$
olup standart durumda \(N=10^{14}\) alınır. \(N\)'ye kadar doğrusal bir dinamik program mümkün olmadığından çözüm, özyinelemeyi taban-\(k\) basamakları üzerinde çalışan polinom tabanlı bir hesaba dönüştürür.
Tek bir taban \(k\) sabitleyelim ve \(f(n)=f_k(n)\) yazalım. \(n\)'nin taban-\(k\) açılımı
$$n=d_0+d_1k+\cdots+d_Lk^L,\qquad 0\le d_i\le k-1$$
olsun. Amacımız \(1\)'den \(n\)'ye kadar bütün sayıları dolaşmadan \(f(n)\)'yi bulmaktır.
\(f(0)=1\) olduğundan özyineleme şu biçime gelir:
$$f(n)=\sum_{m=0}^{n} f\left(\left\lfloor\frac{m}{k}\right\rfloor\right).$$
Şimdi \(n=kx+s\) ve \(0\le s\le k-1\) olsun. \(m\) değerlerini \(q=\lfloor m/k\rfloor\) bölümüne göre gruplayınca
$$f(kx+s)=k\sum_{q=0}^{x-1} f(q)+(s+1)f(x)$$
elde edilir. Yani tek bir taban-\(k\) basamağı, daha önceki değerlerin bir önek toplamının nasıl örnekleneceğini belirler.
Aynı özdeşliği önce \(f(x)\)'e, sonra sonraki bölüme ve bu şekilde bölüm \(0\) olana kadar uygularsak tam bir iç içe toplam formülü çıkar:
$$f(n)=\sum_{x_L=0}^{d_L}\sum_{x_{L-1}=0}^{kx_L+d_{L-1}}\cdots\sum_{x_1=0}^{kx_2+d_1}\sum_{x_0=0}^{kx_1+d_0}1.$$
Her katman, üst sınırı “bir sonraki değişkenin \(k\) katı artı \(n\)'nin ilgili basamağı” olan yeni bir değişken getirir. Derinlik sadece taban-\(k\) basamak sayısıdır; bu da \(O(\log_k n)\) demektir.
Herhangi bir \(P(x)\) fonksiyonu için
$$T_s[P](x)=\sum_{t=0}^{kx+s} P(t),\qquad 0\le s\le k-1$$
tanımını yapalım. O zaman iç içe toplamı kısa biçimde
$$f(n)=\left(T_{d_L}\circ T_{d_{L-1}}\circ\cdots\circ T_{d_0}\right)[1](0)$$
olarak yazabiliriz. Böylece problem şu hale gelir: sabit \(1\) polinomuyla başla ve \(n\)'nin basamaklarına göre tekrar tekrar “önek toplam al, sonra \(kx+s\)'de değerlendir” operatörünü uygula.
\(P(x)\) derecesi \(r\) olan bir polinomsa onun önek toplamı
$$S[P](x)=\sum_{t=0}^{x}P(t)$$
derecesi \(r+1\) olan bir polinomdur; ayrıca \(x\mapsto kx+s\) yerine koyması da polinom yapısını korur. Bu nedenle \(T_s[P](x)=S[P](kx+s)\) işlemini tekrar tekrar uygulamak bizi polinomlar dünyasının dışına çıkarmaz.
Bir \(x^p\) monomu için gereken önek toplam
$$\sum_{t=0}^{x} t^p=\sum_{j=0}^{p} S(p,j)\,j!\binom{x+1}{j+1}$$
şeklindedir; burada \(S(p,j)\) ikinci tür Stirling sayısını gösterir. Uygulamanın tüm kuvvet-toplamı polinomlarını bir kez önceden hesaplayabilmesini sağlayan Faulhaber tipi özdeşlik tam olarak budur.
Uygulama operatörleri tek bir zincir halinde doğrudan bileştirmez. Bunun yerine \(n\)'nin taban-\(k\) basamaklarını en düşük anlamlı basamaktan başlayarak işler ve iki polinom durumu tutar:
biri şimdiye kadar işlenen kısmı hâlâ \(n\) ile tam eşleşen seçimler için, diğeri ise artık kesin olarak daha küçük olan seçimler için.
Sıradaki basamak \(d_j\) olsun. Bir önceki adımdaki tam-eşleşme ve daha-küçük durumları \(E_{j-1}\) ve \(B_{j-1}\) ile gösterilirse, \(S[P](x)=\sum_{t=0}^{x}P(t)\) olmak üzere
$$B_j(x)=\sum_{s=0}^{k-1} S[B_{j-1}](kx+s),$$
$$E_j(x)=\sum_{s=0}^{d_j-1} S[B_{j-1}](kx+s)+S[E_{j-1}](kx+d_j)$$
olur. Tek basamaklı başlangıç durumları
$$B_0(x)=k,\qquad E_0(x)=d_0+1$$
şeklindedir; çünkü tam bir son basamak bloğu \(k\) seçenek verir, \(d_0\) ile kesilmiş blok ise \(d_0+1\) seçenek verir. Son basamak işlendiğinde aradığımız değer doğrudan
$$f(n)=E_L(0)$$
olur.
\(10=(20)_5\) olduğundan basamaklar \(d_0=0\) ve \(d_1=2\)'dir. İç içe toplam formülü
$$f_5(10)=\sum_{x_1=0}^{2}\sum_{x_0=0}^{5x_1}1=1+6+11=18$$
sonucunu verir; bu da uygulamanın kullandığı kontrol değeriyle aynıdır.
Polinom durumu güncellemesi de aynı sonucu üretir. Başlangıçta \(B_0(x)=5\) ve \(E_0(x)=1\) olur. Önek toplamlar sırasıyla \(5x+5\) ve \(x+1\)'dir. Bu yüzden
$$E_1(x)=\sum_{s=0}^{1}(25x+5s+5)+(5x+3)=55x+18$$
ve dolayısıyla
$$f_5(10)=E_1(0)=18.$$
C++, Python ve Java uygulamaları aynı planı izler. Önce, en çok basamağı taban \(2\) verdiği için \(N\)'nin ikilik uzunluğundan güvenli bir azami polinom derecesi belirlenir. Ardından binom katsayıları, ikinci tür Stirling sayıları, faktöriyeller ve oluşabilecek her derece için \(\sum_{t=0}^{x} t^p\) polinomları önceden hesaplanır.
Her \(k=2,3,\dots,10\) için uygulama \(N\)'yi taban \(k\)'ya çevirir, en düşük anlamlı basamak için tam-eşleşme ve daha-küçük durumlarını başlatır ve kalan basamakları tek tek işler. Her basamak adımı iki genel cebirsel işlem kullanır:
$$P(x)\longmapsto \sum_{t=0}^{x}P(t),\qquad P(x)\longmapsto P(kx+s).$$
Durumlar katsayılar halinde tutulduğu için bu işlemler \(N\)'ye kadar sayıları dolaşmadan, doğrudan \(10^9+7\) modunda sembolik olarak yapılır. En yüksek basamak işlendiğinde tam-eşleşme durumu \(x=0\)'da değerlendirilir ve \(f_k(N)\) elde edilir. Son cevap bu dokuz değerin \(10^9+7\) modundaki toplamıdır.
\(D=\lfloor\log_2 N\rfloor+2\) olsun. Bu, \(2\) ile \(10\) arasındaki tüm tabanlardaki basamak sayısını ve dolayısıyla tüm polinom derecelerini \(O(D)\) ile sınırlar. Binom ve kuvvet-toplamı verilerinin ön hesabı \(O(D^3)\) zaman ve \(O(D^2)\) bellek gerektirir. Sabit bir \(k\) için bütün basamakların işlenmesi en kötü durumda \(O(kD^3)\) zaman alır; çünkü derece işlenen basamak sayısıyla doğrusal büyür ve her basamak adımı sınırlı sayıda \(O(D^2)\) polinom dönüşümü yapar. Burada \(k\le 10\) ve \(D\), \(10^{14}\)'ün ikilik basamak sayısı civarında olduğundan yöntem fazlasıyla pratiktir.
Para cada entero \(k \ge 2\), se define la sucesión
$$f_k(0)=1,\qquad f_k(n)=f_k(n-1)+f_k\left(\left\lfloor\frac{n}{k}\right\rfloor\right)\qquad (n\ge 1).$$
Se pide calcular
$$\sum_{k=2}^{10} f_k(N)\pmod{10^9+7},$$
donde en la instancia estándar \(N=10^{14}\). Un DP lineal hasta \(N\) es inviable, así que la solución transforma la recurrencia en un cálculo polinómico dígito por dígito.
Fijemos una base \(k\) y escribamos \(f(n)=f_k(n)\). La expansión de \(n\) en base \(k\) es
$$n=d_0+d_1k+\cdots+d_Lk^L,\qquad 0\le d_i\le k-1.$$
La meta es evaluar \(f(n)\) sin recorrer todos los enteros entre \(1\) y \(n\).
Como \(f(0)=1\), la recurrencia se telescopa en
$$f(n)=\sum_{m=0}^{n} f\left(\left\lfloor\frac{m}{k}\right\rfloor\right).$$
Ahora escribimos \(n=kx+s\) con \(0\le s\le k-1\). Si agrupamos los valores de \(m\) por el cociente \(q=\lfloor m/k\rfloor\), obtenemos
$$f(kx+s)=k\sum_{q=0}^{x-1} f(q)+(s+1)f(x).$$
Así, un solo dígito en base \(k\) determina cómo se toma una suma prefijo de valores anteriores.
Si aplicamos la misma identidad a \(f(x)\), luego al siguiente cociente, y continuamos hasta que el cociente se vuelva \(0\), obtenemos una fórmula exacta de sumas anidadas:
$$f(n)=\sum_{x_L=0}^{d_L}\sum_{x_{L-1}=0}^{kx_L+d_{L-1}}\cdots\sum_{x_1=0}^{kx_2+d_1}\sum_{x_0=0}^{kx_1+d_0}1.$$
Cada nivel introduce una variable cuyo límite superior es \(k\) veces la variable siguiente más el dígito correspondiente de \(n\). La profundidad es solo el número de dígitos de \(n\) en base \(k\), es decir, \(O(\log_k n)\).
Para cualquier función \(P(x)\), definimos
$$T_s[P](x)=\sum_{t=0}^{kx+s} P(t),\qquad 0\le s\le k-1.$$
Entonces la suma anidada puede escribirse de manera compacta como
$$f(n)=\left(T_{d_L}\circ T_{d_{L-1}}\circ\cdots\circ T_{d_0}\right)[1](0).$$
El problema pasa a ser: empezar con el polinomio constante \(1\) y aplicar repetidamente el operador “tomar suma prefijo y evaluar en \(kx+s\)” siguiendo los dígitos de \(n\).
Si \(P(x)\) es un polinomio de grado \(r\), entonces su suma prefijo
$$S[P](x)=\sum_{t=0}^{x}P(t)$$
es un polinomio de grado \(r+1\), y la sustitución \(x\mapsto kx+s\) preserva la forma polinómica. Por tanto, las aplicaciones repetidas de \(T_s[P](x)=S[P](kx+s)\) nunca salen del mundo de los polinomios.
Para un monomio \(x^p\), la suma prefijo necesaria es
$$\sum_{t=0}^{x} t^p=\sum_{j=0}^{p} S(p,j)\,j!\binom{x+1}{j+1},$$
donde \(S(p,j)\) denota un número de Stirling de segunda especie. Esta identidad de tipo Faulhaber es exactamente la que permite precalcular una vez todos los polinomios de sumas de potencias y reutilizarlos.
La implementación no compone una sola cadena de operadores de forma literal. En su lugar, recorre los dígitos de \(n\) en base \(k\) desde el menos significativo hasta el más significativo y mantiene dos estados polinómicos:
uno para las elecciones que todavía coinciden exactamente con la parte ya procesada de \(n\), y otro para las elecciones que ya son estrictamente menores.
Si el siguiente dígito es \(d_j\), y \(E_{j-1}\) y \(B_{j-1}\) son los estados exacto y menor del paso anterior, entonces con \(S[P](x)=\sum_{t=0}^{x}P(t)\) se cumple
$$B_j(x)=\sum_{s=0}^{k-1} S[B_{j-1}](kx+s),$$
$$E_j(x)=\sum_{s=0}^{d_j-1} S[B_{j-1}](kx+s)+S[E_{j-1}](kx+d_j).$$
Los estados iniciales para un solo dígito son
$$B_0(x)=k,\qquad E_0(x)=d_0+1,$$
porque un bloque completo del último dígito aporta \(k\) posibilidades, mientras que el bloque truncado permitido por \(d_0\) aporta \(d_0+1\). Tras procesar el último dígito, el valor buscado es
$$f(n)=E_L(0).$$
Como \(10=(20)_5\), los dígitos son \(d_0=0\) y \(d_1=2\). La fórmula anidada da
$$f_5(10)=\sum_{x_1=0}^{2}\sum_{x_0=0}^{5x_1}1=1+6+11=18,$$
que coincide con el valor de comprobación utilizado por la implementación.
La actualización por estados polinómicos produce lo mismo. Al inicio, \(B_0(x)=5\) y \(E_0(x)=1\). Sus sumas prefijo son \(5x+5\) y \(x+1\). Por tanto,
$$E_1(x)=\sum_{s=0}^{1}(25x+5s+5)+(5x+3)=55x+18,$$
y entonces
$$f_5(10)=E_1(0)=18.$$
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero fijan un grado máximo seguro para los polinomios a partir de la longitud binaria de \(N\), porque la base \(2\) produce el mayor número de dígitos. Después precalculan coeficientes binomiales, números de Stirling de segunda especie, factoriales y los polinomios explícitos para \(\sum_{t=0}^{x} t^p\) para todos los grados que pueden aparecer.
Para cada \(k=2,3,\dots,10\), la implementación convierte \(N\) a base \(k\), inicializa los estados exacto y menor para el dígito menos significativo y procesa los dígitos restantes uno por uno. Cada paso de dígito usa dos operaciones algebraicas genéricas:
$$P(x)\longmapsto \sum_{t=0}^{x}P(t),\qquad P(x)\longmapsto P(kx+s).$$
Como los estados se almacenan por coeficientes, ambas operaciones se realizan simbólicamente módulo \(10^9+7\), sin iterar nunca hasta \(N\). Tras procesar el dígito más significativo, el polinomio del estado exacto se evalúa en \(x=0\), obteniendo \(f_k(N)\). La respuesta final es la suma de esos nueve valores módulo \(10^9+7\).
Sea \(D=\lfloor\log_2 N\rfloor+2\). Esto acota el número de dígitos en todas las bases de \(2\) a \(10\), y por tanto todos los grados polinómicos por \(O(D)\). El precálculo de datos binomiales y de sumas de potencias cuesta \(O(D^3)\) tiempo y \(O(D^2)\) memoria. Para una base fija \(k\), procesar todos los dígitos cuesta \(O(kD^3)\) tiempo en el peor caso, ya que el grado crece linealmente con el número de dígitos procesados y cada paso realiza un número acotado de transformaciones polinómicas de coste \(O(D^2)\). Aquí \(k\le 10\) y \(D\) es solo del orden del número de bits de \(10^{14}\), así que el método es plenamente práctico.
对每个整数 \(k \ge 2\)，定义数列
$$f_k(0)=1,\qquad f_k(n)=f_k(n-1)+f_k\left(\left\lfloor\frac{n}{k}\right\rfloor\right)\qquad (n\ge 1).$$
题目要求计算
$$\sum_{k=2}^{10} f_k(N)\pmod{10^9+7},$$
标准参数中 \(N=10^{14}\)。如果直接从 \(1\) 递推到 \(N\)，复杂度完全不可接受，因此必须把这个递推式改写成只依赖于 \(N\) 的 base-\(k\) 数位结构的算法。
固定一个底数 \(k\)，记 \(f(n)=f_k(n)\)。把 \(n\) 写成 \(k\) 进制：
$$n=d_0+d_1k+\cdots+d_Lk^L,\qquad 0\le d_i\le k-1.$$
我们的目标是在不显式枚举 \(1,2,\dots,n\) 的前提下求出 \(f(n)\)。
由于 \(f(0)=1\)，原递推式可以整理为
$$f(n)=\sum_{m=0}^{n} f\left(\left\lfloor\frac{m}{k}\right\rfloor\right).$$
现在令 \(n=kx+s\)，其中 \(0\le s\le k-1\)。按商 \(q=\lfloor m/k\rfloor\) 对所有 \(m\) 分组，就得到
$$f(kx+s)=k\sum_{q=0}^{x-1} f(q)+(s+1)f(x).$$
这说明：最低一位的数字，决定了“前缀和”要如何在当前层被取样。换句话说，问题的本质不是逐个 \(n\) 推进，而是不断对较小规模的函数做前缀求和。
接下来把同样的等式继续应用到 \(f(x)\)、再应用到下一层商、一直做到商变成 \(0\)。这样就能得到一个完全精确的嵌套求和公式：
$$f(n)=\sum_{x_L=0}^{d_L}\sum_{x_{L-1}=0}^{kx_L+d_{L-1}}\cdots\sum_{x_1=0}^{kx_2+d_1}\sum_{x_0=0}^{kx_1+d_0}1.$$
这个公式的含义非常直接：每一层变量的上界都等于“下一层变量乘以 \(k\)，再加上 \(n\) 的对应数位”。求和深度只等于 \(n\) 的 \(k\) 进制位数，因此是 \(O(\log_k n)\)，而不是 \(O(n)\)。
对任意函数 \(P(x)\)，定义算子
$$T_s[P](x)=\sum_{t=0}^{kx+s} P(t),\qquad 0\le s\le k-1.$$
那么上面的嵌套和可以紧凑地写成
$$f(n)=\left(T_{d_L}\circ T_{d_{L-1}}\circ\cdots\circ T_{d_0}\right)[1](0).$$
也就是说，我们从常数函数 \(1\) 出发，按照 \(n\) 的各位数字，重复执行“先做前缀求和，再在 \(kx+s\) 处代入”的操作，最后在 \(x=0\) 处取值即可。
如果 \(P(x)\) 是一个 \(r\) 次多项式，那么它的前缀和
$$S[P](x)=\sum_{t=0}^{x}P(t)$$
就是一个 \(r+1\) 次多项式；而把 \(x\) 替换成 \(kx+s\) 仍然是多项式。因此，反复应用 \(T_s[P](x)=S[P](kx+s)\) 时，状态始终停留在“多项式”这个有限维空间里。
对单项式 \(x^p\)，所需的前缀和可以写成
$$\sum_{t=0}^{x} t^p=\sum_{j=0}^{p} S(p,j)\,j!\binom{x+1}{j+1},$$
这里的 \(S(p,j)\) 是第二类 Stirling 数。这个 Faulhaber 型恒等式正是实现中预处理“所有幂和多项式”的关键，因为一旦这些基础多项式准备好，任意多项式的前缀和都能由线性组合得到。
实现并不是生硬地把所有 \(T_{d_i}\) 串成一条链，而是从最低位到最高位扫描 \(n\) 的 \(k\) 进制数字，同时维护两个多项式状态：
一个状态表示“到目前为止仍然与 \(n\) 的已处理部分完全相等”，另一个状态表示“已经严格小于 \(n\) 的已处理部分”。
设下一位数字是 \(d_j\)，上一轮的两个状态分别记为 \(E_{j-1}\) 和 \(B_{j-1}\)。令 \(S[P](x)=\sum_{t=0}^{x}P(t)\)，则更新公式为
$$B_j(x)=\sum_{s=0}^{k-1} S[B_{j-1}](kx+s),$$
$$E_j(x)=\sum_{s=0}^{d_j-1} S[B_{j-1}](kx+s)+S[E_{j-1}](kx+d_j).$$
初始的一位状态非常简单：
$$B_0(x)=k,\qquad E_0(x)=d_0+1.$$
原因是：如果最低位已经不受上界限制，那么一整块最后一位共有 \(k\) 种选择；如果仍然必须和 \(d_0\) 对齐，那么最后一位只能取 \(0\) 到 \(d_0\)，共有 \(d_0+1\) 种。等所有数位都处理完之后，答案就是
$$f(n)=E_L(0).$$
因为 \(10=(20)_5\)，所以 \(d_0=0\)、\(d_1=2\)。用嵌套求和公式直接计算：
$$f_5(10)=\sum_{x_1=0}^{2}\sum_{x_0=0}^{5x_1}1=1+6+11=18.$$
这正好对应实现里用于校验的小样例结果。
如果改用多项式状态来看，初始有 \(B_0(x)=5\)、\(E_0(x)=1\)。它们的前缀和分别是 \(5x+5\) 和 \(x+1\)。于是
$$E_1(x)=\sum_{s=0}^{1}(25x+5s+5)+(5x+3)=55x+18,$$
从而
$$f_5(10)=E_1(0)=18.$$
C++、Python 和 Java 三个实现采用的是同一套思路。首先，它们根据 \(N\) 的二进制位数确定一个安全的最大多项式次数，因为在所有底数中，base \(2\) 会产生最多的数位。然后统一预处理二项式系数、第二类 Stirling 数、阶乘，以及所有可能用到的幂和多项式 \(\sum_{t=0}^{x} t^p\)。
对于每个 \(k=2,3,\dots,10\)，实现会先把 \(N\) 转成 \(k\) 进制，针对最低位初始化“相等状态”和“已小于状态”，然后逐位向高位推进。每一位的更新都只依赖两种通用的代数操作：
$$P(x)\longmapsto \sum_{t=0}^{x}P(t),\qquad P(x)\longmapsto P(kx+s).$$
由于状态以系数数组的形式保存，所以这些变换都是在模 \(10^9+7\) 下进行的符号计算，而不是对 \(0\) 到 \(N\) 做任何显式循环。处理完最高位后，把“相等状态”在 \(x=0\) 处取值，就得到 \(f_k(N)\)。最后再把 \(k=2\) 到 \(10\) 的九个结果相加并取模。
设 \(D=\lfloor\log_2 N\rfloor+2\)。这同时控制了底数 \(2\) 到 \(10\) 下的最大位数，因此所有出现的多项式次数都是 \(O(D)\)。预处理二项式数据和幂和多项式需要 \(O(D^3)\) 时间与 \(O(D^2)\) 空间。对固定的底数 \(k\)，逐位处理的最坏时间复杂度是 \(O(kD^3)\)，因为次数会随着已处理位数线性增长，而每一位只进行常数次 \(O(D^2)\) 的多项式变换。这里 \(k\le 10\)，而 \(D\) 大约只是 \(10^{14}\) 的二进制位数规模，所以整体计算非常轻量。
Для каждого целого \(k \ge 2\) задается последовательность
$$f_k(0)=1,\qquad f_k(n)=f_k(n-1)+f_k\left(\left\lfloor\frac{n}{k}\right\rfloor\right)\qquad (n\ge 1).$$
Нужно вычислить
$$\sum_{k=2}^{10} f_k(N)\pmod{10^9+7},$$
где в стандартной постановке \(N=10^{14}\). Линейный DP до \(N\) здесь невозможен, поэтому решение переводит рекурсию в вычисление по цифрам с полиномиальными состояниями.
Зафиксируем основание \(k\) и запишем \(f(n)=f_k(n)\). Пусть запись числа \(n\) в системе счисления по основанию \(k\) имеет вид
$$n=d_0+d_1k+\cdots+d_Lk^L,\qquad 0\le d_i\le k-1.$$
Нужно найти \(f(n)\), не перебирая все числа от \(1\) до \(n\).
Из условия \(f(0)=1\) следует тождество
$$f(n)=\sum_{m=0}^{n} f\left(\left\lfloor\frac{m}{k}\right\rfloor\right).$$
Теперь представим \(n\) в виде \(n=kx+s\), где \(0\le s\le k-1\). Если сгруппировать значения \(m\) по частному \(q=\lfloor m/k\rfloor\), получится
$$f(kx+s)=k\sum_{q=0}^{x-1} f(q)+(s+1)f(x).$$
То есть одна цифра числа в базе \(k\) определяет, каким образом берется префиксная сумма от предыдущих значений.
Применяя то же самое равенство к \(f(x)\), затем к следующему частному и так далее, пока частное не станет равным нулю, получаем точную вложенную сумму:
$$f(n)=\sum_{x_L=0}^{d_L}\sum_{x_{L-1}=0}^{kx_L+d_{L-1}}\cdots\sum_{x_1=0}^{kx_2+d_1}\sum_{x_0=0}^{kx_1+d_0}1.$$
На каждом уровне появляется новая переменная, верхняя граница которой равна \(k\), умноженному на следующую переменную, плюс соответствующая цифра числа \(n\). Глубина равна всего лишь числу цифр в записи \(n\) по основанию \(k\), то есть \(O(\log_k n)\).
Для произвольной функции \(P(x)\) введем оператор
$$T_s[P](x)=\sum_{t=0}^{kx+s} P(t),\qquad 0\le s\le k-1.$$
Тогда вложенная сумма компактно записывается как
$$f(n)=\left(T_{d_L}\circ T_{d_{L-1}}\circ\cdots\circ T_{d_0}\right)[1](0).$$
Значит, задача сводится к следующему: начать с постоянного полинома \(1\) и затем последовательно применять оператор «взять префиксную сумму и подставить \(kx+s\)» в соответствии с цифрами числа \(n\).
Если \(P(x)\) является полиномом степени \(r\), то его префиксная сумма
$$S[P](x)=\sum_{t=0}^{x}P(t)$$
является полиномом степени \(r+1\), а подстановка \(x\mapsto kx+s\) сохраняет полиномиальную форму. Поэтому повторные применения \(T_s[P](x)=S[P](kx+s)\) никогда не выводят нас за пределы пространства полиномов.
Для монома \(x^p\) нужная префиксная сумма имеет вид
$$\sum_{t=0}^{x} t^p=\sum_{j=0}^{p} S(p,j)\,j!\binom{x+1}{j+1},$$
где \(S(p,j)\) обозначает число Стирлинга второго рода. Именно эта формула типа Фаульхабера позволяет один раз предвычислить все полиномы сумм степеней и затем использовать их при каждом переходе.
Реализация не строит одну длинную цепочку операторов буквально. Вместо этого цифры числа \(n\) в базе \(k\) обрабатываются от младшей к старшей, а в каждый момент поддерживаются два полиномиальных состояния:
одно состояние отвечает за выборы, которые все еще точно совпадают с уже обработанной частью \(n\), а второе — за выборы, которые уже стали строго меньше.
Пусть следующая цифра равна \(d_j\), а \(E_{j-1}\) и \(B_{j-1}\) — точное и меньшее состояния после предыдущего шага. Обозначим \(S[P](x)=\sum_{t=0}^{x}P(t)\). Тогда
$$B_j(x)=\sum_{s=0}^{k-1} S[B_{j-1}](kx+s),$$
$$E_j(x)=\sum_{s=0}^{d_j-1} S[B_{j-1}](kx+s)+S[E_{j-1}](kx+d_j).$$
Начальные одноразрядные состояния равны
$$B_0(x)=k,\qquad E_0(x)=d_0+1,$$
потому что полный блок по последней цифре дает \(k\) вариантов, а усеченный блок, разрешенный цифрой \(d_0\), дает \(d_0+1\) вариант. После обработки последней цифры искомое значение равно
$$f(n)=E_L(0).$$
Так как \(10=(20)_5\), имеем \(d_0=0\) и \(d_1=2\). По вложенной формуле
$$f_5(10)=\sum_{x_1=0}^{2}\sum_{x_0=0}^{5x_1}1=1+6+11=18,$$
что совпадает с контрольным примером, используемым в реализации.
Полиномиальные состояния дают тот же результат. Сначала \(B_0(x)=5\) и \(E_0(x)=1\). Их префиксные суммы равны \(5x+5\) и \(x+1\). Следовательно,
$$E_1(x)=\sum_{s=0}^{1}(25x+5s+5)+(5x+3)=55x+18,$$
поэтому
$$f_5(10)=E_1(0)=18.$$
Реализации на C++, Python и Java используют один и тот же план. Сначала они определяют безопасную максимальную степень полинома по двоичной длине числа \(N\), потому что основание \(2\) дает наибольшее число цифр. Затем заранее вычисляются биномиальные коэффициенты, числа Стирлинга второго рода, факториалы и явные полиномы для \(\sum_{t=0}^{x} t^p\) для всех степеней, которые могут понадобиться.
Для каждого \(k=2,3,\dots,10\) реализация переводит \(N\) в систему счисления по основанию \(k\), инициализирует точное и меньшее состояния для младшей цифры и затем последовательно обрабатывает остальные цифры. На каждом шаге используются две стандартные алгебраические операции:
$$P(x)\longmapsto \sum_{t=0}^{x}P(t),\qquad P(x)\longmapsto P(kx+s).$$
Поскольку состояния хранятся в виде массивов коэффициентов, обе операции выполняются символически по модулю \(10^9+7\), без какого-либо прохода по всем значениям до \(N\). После обработки старшей цифры точное состояние вычисляется в точке \(x=0\), что и дает \(f_k(N)\). Итоговый ответ — сумма девяти таких значений по модулю \(10^9+7\).
Пусть \(D=\lfloor\log_2 N\rfloor+2\). Эта величина ограничивает число цифр во всех основаниях от \(2\) до \(10\), а значит и все возникающие степени полиномов величиной \(O(D)\). Предвычисление биномиальных данных и полиномов сумм степеней требует \(O(D^3)\) времени и \(O(D^2)\) памяти. Для фиксированного основания \(k\) обработка всех цифр стоит \(O(kD^3)\) времени в худшем случае, потому что степень растет линейно с числом обработанных цифр, а на каждом шаге выполняется ограниченное число полиномиальных преобразований по \(O(D^2)\). Здесь \(k\le 10\), а \(D\) — это всего лишь порядок количества двоичных цифр у числа \(10^{14}\), так что метод остается очень быстрым.
لكل عدد صحيح \(k \ge 2\)، تُعرَّف المتتالية
$$f_k(0)=1,\qquad f_k(n)=f_k(n-1)+f_k\left(\left\lfloor\frac{n}{k}\right\rfloor\right)\qquad (n\ge 1).$$
والمطلوب حساب
$$\sum_{k=2}^{10} f_k(N)\pmod{10^9+7},$$
حيث تكون \(N=10^{14}\) في النسخة القياسية من المسألة. التنفيذ الخطي حتى \(N\) غير ممكن، لذلك تُعاد صياغة العلاقة العودية في صورة حساب كثيرات حدود يعتمد فقط على خانات العدد في الأساس \(k\).
نثبّت أساسًا واحدًا \(k\)، ونكتب \(f(n)=f_k(n)\). لنفرض أن تمثيل \(n\) في الأساس \(k\) هو
$$n=d_0+d_1k+\cdots+d_Lk^L,\qquad 0\le d_i\le k-1.$$
الهدف هو إيجاد \(f(n)\) من غير المرور على كل الأعداد من \(1\) إلى \(n\).
بما أن \(f(0)=1\)، يمكن جمع العلاقة على نحو يؤدي إلى
$$f(n)=\sum_{m=0}^{n} f\left(\left\lfloor\frac{m}{k}\right\rfloor\right).$$
الآن اكتب \(n=kx+s\) حيث \(0\le s\le k-1\). وإذا جمعنا الحدود بحسب خارج القسمة \(q=\lfloor m/k\rfloor\)، نحصل على
$$f(kx+s)=k\sum_{q=0}^{x-1} f(q)+(s+1)f(x).$$
إذًا كل خانة في التمثيل بالأساس \(k\) تتحكم في كيفية أخذ مجموع بادئة من القيم السابقة.
إذا طبقنا الهوية نفسها على \(f(x)\)، ثم على خارج القسمة التالي، واستمررنا حتى يصل الخارج إلى \(0\)، فإننا نحصل على صيغة دقيقة من المجاميع المتداخلة:
$$f(n)=\sum_{x_L=0}^{d_L}\sum_{x_{L-1}=0}^{kx_L+d_{L-1}}\cdots\sum_{x_1=0}^{kx_2+d_1}\sum_{x_0=0}^{kx_1+d_0}1.$$
كل طبقة تضيف متغيرًا جديدًا، وحده الأعلى يساوي \(k\) مضروبًا في المتغير التالي ثم مضافًا إليه الرقم الموافق من خانات \(n\). وعمق هذا التركيب لا يزيد على عدد خانات \(n\) في الأساس \(k\)، أي \(O(\log_k n)\).
لكل دالة \(P(x)\) نعرّف
$$T_s[P](x)=\sum_{t=0}^{kx+s} P(t),\qquad 0\le s\le k-1.$$
وعندئذ يمكن كتابة المجموع المتداخل على الصورة الموجزة
$$f(n)=\left(T_{d_L}\circ T_{d_{L-1}}\circ\cdots\circ T_{d_0}\right)[1](0).$$
وهكذا تتحول المسألة إلى الآتي: نبدأ من كثير الحدود الثابت \(1\)، ثم نطبق مرارًا مؤثرًا من نوع "خذ مجموع البادئة ثم قيّم عند \(kx+s\)" وفقًا لخانات العدد \(n\).
إذا كان \(P(x)\) كثير حدود درجته \(r\)، فإن مجموع بادئته
$$S[P](x)=\sum_{t=0}^{x}P(t)$$
يكون كثير حدود درجته \(r+1\)، كما أن التعويض \(x\mapsto kx+s\) يحافظ على كونه كثير حدود. لذلك فإن التكرار المستمر للعملية \(T_s[P](x)=S[P](kx+s)\) لا يخرجنا أبدًا من فضاء كثيرات الحدود.
وبالنسبة إلى الحد الأحادي \(x^p\)، فإن مجموع البادئة المطلوب يكتب على الصورة
$$\sum_{t=0}^{x} t^p=\sum_{j=0}^{p} S(p,j)\,j!\binom{x+1}{j+1},$$
حيث يرمز \(S(p,j)\) إلى عدد Stirling من النوع الثاني. وهذه الهوية من نمط صيغة Faulhaber هي التي تسمح للتنفيذ بأن يسبق حساب جميع كثيرات حدود مجاميع القوى مرة واحدة فقط ثم يعيد استخدامها.
لا ينفذ البرنامج سلسلة المؤثرات السابقة حرفيًا كمؤثر واحد طويل. بدلًا من ذلك، يمر على خانات \(n\) في الأساس \(k\) من الأقل أهمية إلى الأعلى أهمية، ويحفظ حالتين كثيرتي حدود:
حالة للاختيارات التي ما زالت مطابقة تمامًا للجزء المعالج من \(n\)، وحالة للاختيارات التي أصبحت أصغر من ذلك الجزء بالفعل.
إذا كانت الخانة التالية هي \(d_j\)، وسمينا الحالتين السابقتين \(E_{j-1}\) و\(B_{j-1}\)، ومع تعريف \(S[P](x)=\sum_{t=0}^{x}P(t)\)، فإن التحديث يكون
$$B_j(x)=\sum_{s=0}^{k-1} S[B_{j-1}](kx+s),$$
$$E_j(x)=\sum_{s=0}^{d_j-1} S[B_{j-1}](kx+s)+S[E_{j-1}](kx+d_j).$$
أما حالتا البداية لخانة واحدة فهما
$$B_0(x)=k,\qquad E_0(x)=d_0+1,$$
لأن كتلة الخانة الأخيرة الكاملة تعطي \(k\) اختيارات، بينما الكتلة المقتطعة المسموح بها بواسطة \(d_0\) تعطي \(d_0+1\) اختيارًا. وبعد إنهاء آخر خانة يصبح الجواب المطلوب ببساطة
$$f(n)=E_L(0).$$
بما أن \(10=(20)_5\)، فإن \(d_0=0\) و\(d_1=2\). ومن صيغة المجاميع المتداخلة نحصل على
$$f_5(10)=\sum_{x_1=0}^{2}\sum_{x_0=0}^{5x_1}1=1+6+11=18,$$
وهو نفس مقدار التحقق المستخدم في التنفيذ.
ومن زاوية الحالات كثيرة الحدود نحصل على النتيجة نفسها. في البداية \(B_0(x)=5\) و\(E_0(x)=1\). مجموعا البادئة لهما هما \(5x+5\) و\(x+1\). ومن ثم
$$E_1(x)=\sum_{s=0}^{1}(25x+5s+5)+(5x+3)=55x+18,$$
وبالتالي
$$f_5(10)=E_1(0)=18.$$
التنفيذات المكتوبة بلغة C++ وPython وJava تتبع الخطة نفسها. أولًا يجري تحديد درجة عظمى آمنة لكثيرات الحدود انطلاقًا من طول \(N\) بالثنائي، لأن الأساس \(2\) يعطي أكبر عدد من الخانات. بعد ذلك تُحسب مسبقًا معاملات ذات الحدين، وأعداد Stirling من النوع الثاني، والمضاريب، والصيغ الصريحة لكثيرات الحدود التي تمثل \(\sum_{t=0}^{x} t^p\) لكل درجة قد تظهر أثناء التنفيذ.
لكل \(k=2,3,\dots,10\)، يحوّل التنفيذ العدد \(N\) إلى الأساس \(k\)، ثم يهيئ حالتي المطابقة والأصغر للخانة الأقل أهمية، وبعدها يعالج بقية الخانات واحدة تلو الأخرى. كل خطوة تستخدم عمليتين جبريتين عامتين:
$$P(x)\longmapsto \sum_{t=0}^{x}P(t),\qquad P(x)\longmapsto P(kx+s).$$
وبما أن الحالات ممثلة بمصفوفات معاملات، فإن العمليتين تنفذان رمزيًا بترديد \(10^9+7\)، من غير أي حلقة تمتد حتى \(N\). وبعد معالجة الخانة الأعلى أهمية، تُقيَّم حالة المطابقة عند \(x=0\) فنحصل على \(f_k(N)\). وأخيرًا تُجمع القيم التسع الخاصة بـ \(k=2\) حتى \(10\) ويؤخذ الناتج بترديد \(10^9+7\).
لنضع \(D=\lfloor\log_2 N\rfloor+2\). هذا يحدّ عدد الخانات في كل أساس من \(2\) إلى \(10\)، وبالتالي يحد أيضًا درجات جميع كثيرات الحدود الظاهرة بمقدار \(O(D)\). أما الحسابات المسبقة الخاصة بمعاملات ذات الحدين ومجاميع القوى فتأخذ \(O(D^3)\) زمنًا و\(O(D^2)\) ذاكرة. وبالنسبة إلى أساس ثابت \(k\)، فإن معالجة جميع الخانات تستغرق \(O(kD^3)\) زمنًا في أسوأ الأحوال، لأن الدرجة تنمو خطيًا مع عدد الخانات المعالجة، ولأن كل خطوة تنفذ عددًا محدودًا من تحويلات كثيرة الحدود ذات الكلفة \(O(D^2)\). وهنا \(k\le 10\)، بينما \(D\) لا يتجاوز تقريبًا عدد الخانات الثنائية للعدد \(10^{14}\)، لذا فالطريقة عملية جدًا.