Write every nonnegative integer in decimal, padding with leading zeros when necessary so that all positions line up. The freshman's product multiplies matching digits and keeps only the last digit at each position, with no carries between positions. If
$$d_j(n)=\left\lfloor\frac{n}{10^j}\right\rfloor \bmod 10,$$
then for two numbers
$$a\odot b=\sum_{j\ge 0}\left(d_j(a)d_j(b)\bmod 10\right)10^j.$$
Because multiplication modulo \(10\) is associative at each digit, the same definition extends to \(R\) factors:
$$n_1\odot n_2\odot \cdots \odot n_R=\sum_{j\ge 0}\left(\prod_{t=1}^R d_j(n_t)\bmod 10\right)10^j.$$
The quantity to compute is
$$F(R,M)=\sum_{0\le n_1,\dots,n_R\le M} n_1\odot n_2\odot \cdots \odot n_R \pmod{10^9+9}.$$
A direct enumeration would require \((M+1)^R\) ordered tuples, so the solution instead counts the contribution of each decimal position separately and compresses the repeated digit multiplication into a fixed \(10\times 10\) transition matrix.
The crucial observation is that the freshman's product never creates carries. Each decimal place can therefore be analyzed independently and then recombined with its place value.
Fix one place \(p=10^j\). For an ordered \(R\)-tuple \((n_1,\dots,n_R)\), the digit contributed at that place is
$$g_p(n_1,\dots,n_R)=\left(\prod_{t=1}^R d_j(n_t)\right)\bmod 10.$$
So the whole sum splits as
$$F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j S_j \pmod{10^9+9},$$
where
$$S_j=\sum_{0\le n_1,\dots,n_R\le M} g_{10^j}(n_1,\dots,n_R).$$
All higher positions vanish automatically, because every number in \([0,M]\) has digit \(0\) there.
For a fixed place \(p=10^j\), let \(c_d(p)\) be the number of integers in \([0,M]\) whose digit at that place equals \(d\). Set
$$N=M+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad u=N\bmod(10p).$$
Each complete block of length \(10p\) contributes exactly \(p\) copies of every digit, so the \(q\) full blocks contribute \(qp\). The remaining tail contributes a partial block, giving
$$c_d(p)=qp+\min\bigl(\max(u-dp,0),\,p\bigr),\qquad 0\le d\le 9.$$
This formula automatically handles leading zeros. For example, if \(M=27\) and \(p=10\), then the tens digit counts are
$$c_0(10)=10,\qquad c_1(10)=10,\qquad c_2(10)=8,\qquad c_d(10)=0\ \text{for }d\ge 3,$$
because the numbers \(0\) to \(9\) contribute a leading zero in the tens place.
At one fixed decimal place, only the current product modulo \(10\) matters. Let \(v_t^{(j)}(r)\) be the number of ordered choices of \(t\) numbers from \([0,M]\) whose digitwise product at place \(10^j\) equals \(r\in\{0,\dots,9\}\).
Before choosing any number, the product is the multiplicative identity, so
$$v_0^{(j)}(1)=1,\qquad v_0^{(j)}(r)=0\ \text{for }r\ne 1.$$
If the current residue is \(r\) and the next chosen digit is \(d\), the new residue is
$$r'\equiv rd \pmod{10}.$$
This gives a linear transition matrix \(T_j\) of size \(10\times 10\):
$$T_j(r',r)=\sum_{\substack{0\le d\le 9\\ rd\equiv r' \pmod{10}}} c_d(10^j).$$
Then the state update is simply
$$v_{t+1}^{(j)}=T_j\,v_t^{(j)}.$$
These entries are counts, not probabilities: every column sums to \(M+1\), because from any current residue there are \(M+1\) possible next numbers.
Let \(e_1\) be the basis vector concentrated at residue \(1\). After choosing \(R\) numbers,
$$v_R^{(j)}=T_j^R e_1.$$
The total digit contribution at place \(10^j\) is therefore
$$S_j=\sum_{r=0}^9 r\,v_R^{(j)}(r)=\sum_{r=0}^9 r\,(T_j^R e_1)_r.$$
Since \(R\) can be very large, binary exponentiation computes \(T_j^R\) in \(O(10^3\log R)\) operations for that place.
Putting everything together gives the exact formula implemented by the program:
$$\boxed{F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j \sum_{r=0}^9 r\,(T_j^R e_1)_r \pmod{10^9+9}.}$$
The only place-dependent ingredient is the digit-count vector \(c_d(10^j)\); once those ten counts are known, the rest is the same \(10\)-state linear algebra for every decimal position.
Here only the units place exists, because every number from \(0\) to \(7\) has just one relevant digit. The digit counts are
$$c_0(1)=c_1(1)=\cdots=c_7(1)=1,\qquad c_8(1)=c_9(1)=0.$$
So the desired sum is simply
$$F(2,7)=\sum_{a=0}^7\sum_{b=0}^7 (ab\bmod 10).$$
Evaluating row by row gives
$$\begin{aligned} a=0&:&&0,\\ a=1&:&&0+1+2+3+4+5+6+7=28,\\ a=2&:&&0+2+4+6+8+0+2+4=26,\\ a=3&:&&0+3+6+9+2+5+8+1=34,\\ a=4&:&&0+4+8+2+6+0+4+8=32,\\ a=5&:&&0+5+0+5+0+5+0+5=20,\\ a=6&:&&0+6+2+8+4+0+6+2=28,\\ a=7&:&&0+7+4+1+8+5+2+9=36. \end{aligned}$$
Hence
$$0+28+26+34+32+20+28+36=204,$$
so \(F(2,7)=204\), matching the implementation checkpoint.
The C++, Python, and Java implementations follow the same pipeline. They iterate over the place values \(1,10,100,\dots\) up to the largest nonzero digit of \(M\). For each place they compute the ten digit frequencies in \([0,M]\) from the block formula above, assemble the \(10\times 10\) transition matrix on residues modulo \(10\), raise that matrix to the \(R\)-th power by binary exponentiation, and read the weighted digit sum from the column corresponding to the initial residue \(1\). That place contribution is then multiplied by the place value and added to the running answer modulo \(10^9+9\). The three implementations differ only in language syntax and integer handling; the mathematics and the sequence of steps are identical.
Let \(L=\lfloor\log_{10} M\rfloor+1\) be the number of decimal positions that must be processed. For one position, computing the digit counts costs \(O(10)\), building the transition matrix costs \(O(10^2)\), and exponentiating a \(10\times 10\) matrix costs \(O(10^3\log R)\). Therefore the total running time is
$$O\bigl(L\cdot 10^3\log R\bigr),$$
which is effectively \(O(L\log R)\) because the state space size \(10\) is fixed. The memory usage is \(O(10^2)\) for a few small matrices and digit-count vectors.
Jede nichtnegative Zahl wird dezimal geschrieben; fehlende Stellen werden bei Bedarf mit führenden Nullen aufgefüllt, damit alle Positionen ausgerichtet sind. Beim freshman's product werden nur Ziffern derselben Stelle multipliziert, und von jedem Teilprodukt bleibt nur die letzte Ziffer erhalten. Überträge zwischen Stellen gibt es nicht. Mit
$$d_j(n)=\left\lfloor\frac{n}{10^j}\right\rfloor \bmod 10$$
gilt für zwei Zahlen
$$a\odot b=\sum_{j\ge 0}\left(d_j(a)d_j(b)\bmod 10\right)10^j.$$
Da die Multiplikation modulo \(10\) auf jeder Stelle assoziativ ist, erweitert sich das sofort auf \(R\) Faktoren:
$$n_1\odot n_2\odot \cdots \odot n_R=\sum_{j\ge 0}\left(\prod_{t=1}^R d_j(n_t)\bmod 10\right)10^j.$$
Gesucht ist
$$F(R,M)=\sum_{0\le n_1,\dots,n_R\le M} n_1\odot n_2\odot \cdots \odot n_R \pmod{10^9+9}.$$
Direktes Durchprobieren aller \((M+1)^R\) geordneten Tupel ist unmöglich. Die Lösung zerlegt deshalb die Aufgabe nach Dezimalstellen und fasst die wiederholte Ziffernmultiplikation in einer festen \(10\times 10\)-Übergangsmatrix zusammen.
Die entscheidende Beobachtung lautet: Beim freshman's product entstehen keine Überträge. Deshalb kann jede Dezimalstelle unabhängig analysiert und am Ende mit ihrem Stellenwert zurückgewichtet werden.
Fixiere eine Stelle \(p=10^j\). Für ein geordnetes \(R\)-Tupel \((n_1,\dots,n_R)\) ist die an dieser Stelle entstehende Ziffer
$$g_p(n_1,\dots,n_R)=\left(\prod_{t=1}^R d_j(n_t)\right)\bmod 10.$$
Damit zerfällt die Gesamtsumme in
$$F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j S_j \pmod{10^9+9},$$
wobei
$$S_j=\sum_{0\le n_1,\dots,n_R\le M} g_{10^j}(n_1,\dots,n_R).$$
Für alle höheren Stellen verschwindet der Beitrag automatisch, weil dort jede Zahl aus \([0,M]\) die Ziffer \(0\) hat.
Für eine feste Stelle \(p=10^j\) sei \(c_d(p)\) die Anzahl der Zahlen aus \([0,M]\), deren Ziffer dort gleich \(d\) ist. Setze
$$N=M+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad u=N\bmod(10p).$$
Jeder volle Block der Länge \(10p\) enthält jede Ziffer genau \(p\)-mal. Die \(q\) vollen Blöcke liefern also \(qp\), und der Restblock ergänzt nur noch einen Teil davon. Daher
$$c_d(p)=qp+\min\bigl(\max(u-dp,0),\,p\bigr),\qquad 0\le d\le 9.$$
Die Formel berücksichtigt führende Nullen automatisch. Beispiel: Für \(M=27\) und \(p=10\) gilt
$$c_0(10)=10,\qquad c_1(10)=10,\qquad c_2(10)=8,\qquad c_d(10)=0\ \text{für }d\ge 3,$$
denn die Zahlen \(0\) bis \(9\) tragen in der Zehnerstelle eine führende Null.
An einer festen Stelle zählt nur das aktuelle Produkt modulo \(10\). Sei \(v_t^{(j)}(r)\) die Anzahl geordneter Wahlen von \(t\) Zahlen aus \([0,M]\), deren Ziffernprodukt an der Stelle \(10^j\) den Rest \(r\in\{0,\dots,9\}\) hat.
Vor der ersten Wahl ist das Produkt die multiplikative Eins, also
$$v_0^{(j)}(1)=1,\qquad v_0^{(j)}(r)=0\ \text{für }r\ne 1.$$
Wenn der aktuelle Rest \(r\) ist und die nächste gewählte Ziffer \(d\) lautet, dann wird der neue Rest
$$r'\equiv rd \pmod{10}.$$
Daraus entsteht eine lineare Übergangsmatrix \(T_j\) der Größe \(10\times 10\):
$$T_j(r',r)=\sum_{\substack{0\le d\le 9\\ rd\equiv r' \pmod{10}}} c_d(10^j).$$
Dann lautet die Rekursion schlicht
$$v_{t+1}^{(j)}=T_j\,v_t^{(j)}.$$
Die Matrixeinträge sind Zählwerte, keine Wahrscheinlichkeiten: Jede Spalte summiert sich zu \(M+1\), weil es zu jedem Zustand genau \(M+1\) mögliche nächste Zahlen gibt.
Sei \(e_1\) der Basisvektor, der auf Rest \(1\) konzentriert ist. Nach der Wahl von \(R\) Zahlen gilt
$$v_R^{(j)}=T_j^R e_1.$$
Der gesamte Ziffernbeitrag der Stelle \(10^j\) ist damit
$$S_j=\sum_{r=0}^9 r\,v_R^{(j)}(r)=\sum_{r=0}^9 r\,(T_j^R e_1)_r.$$
Da \(R\) sehr groß sein kann, wird \(T_j^R\) per binärer Exponentiation in \(O(10^3\log R)\) berechnet.
Zusammen ergibt das genau die Formel, die das Programm umsetzt:
$$\boxed{F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j \sum_{r=0}^9 r\,(T_j^R e_1)_r \pmod{10^9+9}.}$$
Der einzige stellenspezifische Teil ist also der Ziffernvektor \(c_d(10^j)\); danach läuft für jede Stelle dieselbe \(10\)-zuständige lineare Algebra ab.
Hier gibt es nur die Einerstelle, denn alle Zahlen von \(0\) bis \(7\) besitzen nur eine relevante Ziffer. Die Ziffernhäufigkeiten sind
$$c_0(1)=c_1(1)=\cdots=c_7(1)=1,\qquad c_8(1)=c_9(1)=0.$$
Damit reduziert sich die gesuchte Summe auf
$$F(2,7)=\sum_{a=0}^7\sum_{b=0}^7 (ab\bmod 10).$$
Zeilenweise ausgewertet erhält man
$$\begin{aligned} a=0&:&&0,\\ a=1&:&&0+1+2+3+4+5+6+7=28,\\ a=2&:&&0+2+4+6+8+0+2+4=26,\\ a=3&:&&0+3+6+9+2+5+8+1=34,\\ a=4&:&&0+4+8+2+6+0+4+8=32,\\ a=5&:&&0+5+0+5+0+5+0+5=20,\\ a=6&:&&0+6+2+8+4+0+6+2=28,\\ a=7&:&&0+7+4+1+8+5+2+9=36. \end{aligned}$$
Also
$$0+28+26+34+32+20+28+36=204,$$
und damit \(F(2,7)=204\), genau wie im Kontrolltest der Implementierung.
Die C++-, Python- und Java-Implementierungen benutzen exakt dieselbe Pipeline. Sie laufen über die Stellenwerte \(1,10,100,\dots\) bis zur höchsten von \(M\) benötigten Dezimalstelle. Für jede Stelle werden zunächst die zehn Ziffernhäufigkeiten in \([0,M]\) mit der Blockformel berechnet. Daraus entsteht die \(10\times 10\)-Übergangsmatrix für Restklassen modulo \(10\). Diese Matrix wird per binärer Exponentiation zur \(R\)-ten Potenz erhoben, anschließend wird aus der Spalte des Startzustands \(1\) die gewichtete Ziffernsumme ausgelesen. Dieser Stellenbeitrag wird mit dem Stellenwert multipliziert und modulo \(10^9+9\) zum Ergebnis addiert. Zwischen den drei Sprachen unterscheiden sich nur Syntax und Zahlentypen; Mathematik und Ablauf sind identisch.
Sei \(L=\lfloor\log_{10} M\rfloor+1\) die Anzahl der zu verarbeitenden Dezimalstellen. Für eine Stelle kostet das Bestimmen der Ziffernhäufigkeiten \(O(10)\), das Aufbauen der Matrix \(O(10^2)\) und das Potenzieren einer \(10\times 10\)-Matrix \(O(10^3\log R)\). Insgesamt ergibt sich also
$$O\bigl(L\cdot 10^3\log R\bigr),$$
was wegen der festen Zustandszahl \(10\) effektiv \(O(L\log R)\) ist. Der Speicherbedarf beträgt \(O(10^2)\) für einige kleine Matrizen und Ziffernvektoren.
Her negatif olmayan tamsayıyı ondalık yazıp gerektiğinde başına sıfır ekleyerek basamakları hizalayalım. Freshman's product işleminde aynı basamaktaki rakamlar çarpılır, her basamakta sadece son rakam tutulur ve basamaklar arasında elde oluşmaz. Eğer
$$d_j(n)=\left\lfloor\frac{n}{10^j}\right\rfloor \bmod 10$$
olursa iki sayı için
$$a\odot b=\sum_{j\ge 0}\left(d_j(a)d_j(b)\bmod 10\right)10^j$$
tanımını elde ederiz. Her basamakta mod \(10\) çarpımı birleşmeli olduğundan bu tanım \(R\) çarpana doğrudan genişler:
$$n_1\odot n_2\odot \cdots \odot n_R=\sum_{j\ge 0}\left(\prod_{t=1}^R d_j(n_t)\bmod 10\right)10^j.$$
Hesaplanmak istenen büyüklük şudur:
$$F(R,M)=\sum_{0\le n_1,\dots,n_R\le M} n_1\odot n_2\odot \cdots \odot n_R \pmod{10^9+9}.$$
\((M+1)^R\) adet sıralı \(R\)-liyi doğrudan gezmek imkansız olduğundan çözüm her ondalık basamağın katkısını ayrı sayar ve tekrar eden rakam çarpımını sabit boyutlu bir \(10\times 10\) geçiş matrisine indirger.
Temel gözlem şudur: freshman's product işleminde elde yoktur. Bu yüzden her ondalık basamak bağımsız incelenebilir, sonra da kendi basamak değeriyle yeniden birleştirilebilir.
Bir \(p=10^j\) basamağını sabitleyelim. Sıralı bir \((n_1,\dots,n_R)\) \(R\)-lisi için bu basamağın ürettiği rakam
$$g_p(n_1,\dots,n_R)=\left(\prod_{t=1}^R d_j(n_t)\right)\bmod 10$$
olur. Böylece toplam ifade
$$F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j S_j \pmod{10^9+9}$$
şeklinde ayrışır; burada
$$S_j=\sum_{0\le n_1,\dots,n_R\le M} g_{10^j}(n_1,\dots,n_R).$$
\(M\)'nin üstündeki tüm daha yüksek basamaklar otomatik olarak sıfırdır, çünkü \([0,M]\) aralığındaki her sayının o basamakta rakamı \(0\) olur.
Sabit bir \(p=10^j\) için \(c_d(p)\), \([0,M]\) aralığında bu basamakta rakamı \(d\) olan sayı sayısı olsun. Şunları tanımlayalım:
$$N=M+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad u=N\bmod(10p).$$
Uzunluğu \(10p\) olan her tam blokta her rakam tam \(p\) kez görünür. Dolayısıyla \(q\) tam blok toplam \(qp\) katkı verir; kalan kuyruk blok ise bunun bir kısmını tamamlar. Sonuç:
$$c_d(p)=qp+\min\bigl(\max(u-dp,0),\,p\bigr),\qquad 0\le d\le 9.$$
Bu formül baştaki sıfırları da doğal biçimde kapsar. Örneğin \(M=27\) ve \(p=10\) için onlar basamağındaki sayımlar
$$c_0(10)=10,\qquad c_1(10)=10,\qquad c_2(10)=8,\qquad c_d(10)=0\ \text{for }d\ge 3$$
olur; çünkü \(0\) ile \(9\) arasındaki sayılar onlar basamağında baştaki sıfırı taşır.
Sabit bir basamakta sadece mevcut çarpımın mod \(10\) kalanı önemlidir. \(v_t^{(j)}(r)\), \([0,M]\) aralığından seçilmiş sıralı \(t\) sayıdan oluşan seçimlerin, \(10^j\) basamağındaki rakam çarpımını \(r\in\{0,\dots,9\}\) kalanı olacak şekilde üretme sayısı olsun.
Henüz hiç sayı seçilmeden önce çarpım çarpımsal birimdir, yani
$$v_0^{(j)}(1)=1,\qquad v_0^{(j)}(r)=0\ \text{for }r\ne 1.$$
Mevcut kalan \(r\), yeni gelen rakam \(d\) ise yeni kalan
$$r'\equiv rd \pmod{10}$$
olur. Bu da \(10\times 10\) boyutlu doğrusal bir geçiş matrisi verir:
$$T_j(r',r)=\sum_{\substack{0\le d\le 9\\ rd\equiv r' \pmod{10}}} c_d(10^j).$$
Dolayısıyla yineleme
$$v_{t+1}^{(j)}=T_j\,v_t^{(j)}$$
biçimindedir. Buradaki matris girişleri olasılık değil, sayım değeridir; her sütunun toplamı \(M+1\)'dir, çünkü her mevcut durumda seçilebilecek \(M+1\) farklı sayı vardır.
Kalan \(1\)'de yoğunlaşan birim vektöre \(e_1\) diyelim. \(R\) sayı seçildikten sonra
$$v_R^{(j)}=T_j^R e_1$$
olur. O halde \(10^j\) basamağının toplam katkısı
$$S_j=\sum_{r=0}^9 r\,v_R^{(j)}(r)=\sum_{r=0}^9 r\,(T_j^R e_1)_r$$
şeklindedir. \(R\) çok büyük olabildiği için \(T_j^R\) ikili üs alma ile \(O(10^3\log R)\) zamanda bulunur.
Hepsini bir araya getirince programın uyguladığı tam formül ortaya çıkar:
$$\boxed{F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j \sum_{r=0}^9 r\,(T_j^R e_1)_r \pmod{10^9+9}.}$$
Yani basamağa özgü tek bilgi \(c_d(10^j)\) rakam sayılarıdır; bunlar belirlendikten sonra her basamak için aynı \(10\) durumlu lineer cebir kullanılır.
Burada sadece birler basamağı vardır; çünkü \(0\) ile \(7\) arasındaki tüm sayılar için başka anlamlı bir basamak yoktur. Rakam sayımları
$$c_0(1)=c_1(1)=\cdots=c_7(1)=1,\qquad c_8(1)=c_9(1)=0$$
olur. Bu yüzden toplam
$$F(2,7)=\sum_{a=0}^7\sum_{b=0}^7 (ab\bmod 10)$$
şeklindedir. Satır satır hesaplayınca
$$\begin{aligned} a=0&:&&0,\\ a=1&:&&0+1+2+3+4+5+6+7=28,\\ a=2&:&&0+2+4+6+8+0+2+4=26,\\ a=3&:&&0+3+6+9+2+5+8+1=34,\\ a=4&:&&0+4+8+2+6+0+4+8=32,\\ a=5&:&&0+5+0+5+0+5+0+5=20,\\ a=6&:&&0+6+2+8+4+0+6+2=28,\\ a=7&:&&0+7+4+1+8+5+2+9=36. \end{aligned}$$
Dolayısıyla
$$0+28+26+34+32+20+28+36=204,$$
yani \(F(2,7)=204\). Bu değer uygulamadaki kontrol noktasıyla aynıdır.
C++, Python ve Java uygulamaları aynı işlem sırasını izler. Önce \(1,10,100,\dots\) basamak değerleri boyunca, \(M\)'nin en yüksek sıfır olmayan basamağına kadar dönerler. Her basamak için yukarıdaki blok formülüyle \([0,M]\) aralığındaki on rakamın frekansları hesaplanır. Sonra mod \(10\) kalıntıları üzerinde çalışan \(10\times 10\) geçiş matrisi kurulur. Bu matris ikili üs alma ile \(R\). kuvvete yükseltilir ve başlangıç kalanı \(1\) olan sütundan ağırlıklı rakam toplamı okunur. Elde edilen katkı ilgili basamak değeriyle çarpılır ve sonuç \(10^9+9\) modunda birikimli toplama eklenir. Üç dil arasındaki fark sadece sözdizimi ve tamsayı işlemedir; matematiksel yöntem aynıdır.
\(L=\lfloor\log_{10} M\rfloor+1\), işlenmesi gereken ondalık basamak sayısı olsun. Tek bir basamak için rakam sayımlarını çıkarmak \(O(10)\), matrisi kurmak \(O(10^2)\), \(10\times 10\) bir matrisi üs almak ise \(O(10^3\log R)\) zaman alır. Bu yüzden toplam süre
$$O\bigl(L\cdot 10^3\log R\bigr)$$
olur. Durum sayısı sabit \(10\) olduğundan bu pratikte \(O(L\log R)\) davranışıdır. Bellek kullanımı birkaç küçük matris ve rakam vektörü için \(O(10^2)\)'dir.
Escribimos cada entero no negativo en base diez y, cuando hace falta, añadimos ceros a la izquierda para alinear todas las posiciones. El freshman's product multiplica solo las cifras situadas en la misma posición y conserva únicamente la última cifra de cada producto, sin acarreo entre posiciones. Si
$$d_j(n)=\left\lfloor\frac{n}{10^j}\right\rfloor \bmod 10,$$
entonces para dos números
$$a\odot b=\sum_{j\ge 0}\left(d_j(a)d_j(b)\bmod 10\right)10^j.$$
Como la multiplicación módulo \(10\) es asociativa en cada cifra, la definición se extiende de inmediato a \(R\) factores:
$$n_1\odot n_2\odot \cdots \odot n_R=\sum_{j\ge 0}\left(\prod_{t=1}^R d_j(n_t)\bmod 10\right)10^j.$$
Lo que se debe calcular es
$$F(R,M)=\sum_{0\le n_1,\dots,n_R\le M} n_1\odot n_2\odot \cdots \odot n_R \pmod{10^9+9}.$$
Recorrer directamente los \((M+1)^R\) \(R\)-tuplos ordenados es inviable, así que la solución cuenta por separado la contribución de cada posición decimal y resume la multiplicación repetida de cifras mediante una matriz de transición fija de tamaño \(10\times 10\).
La observación central es que el freshman's product nunca genera acarreos. Por ello cada posición decimal puede analizarse de manera independiente y luego recombinarse con su peso \(10^j\).
Fijemos una posición \(p=10^j\). Para un \(R\)-tuplo ordenado \((n_1,\dots,n_R)\), la cifra producida en esa posición es
$$g_p(n_1,\dots,n_R)=\left(\prod_{t=1}^R d_j(n_t)\right)\bmod 10.$$
Entonces la suma total se descompone como
$$F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j S_j \pmod{10^9+9},$$
donde
$$S_j=\sum_{0\le n_1,\dots,n_R\le M} g_{10^j}(n_1,\dots,n_R).$$
Las posiciones más altas no aportan nada, porque todas las cifras allí son \(0\) para los números del intervalo \([0,M]\).
Para una posición fija \(p=10^j\), sea \(c_d(p)\) el número de enteros de \([0,M]\) cuya cifra en esa posición vale \(d\). Definimos
$$N=M+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad u=N\bmod(10p).$$
Cada bloque completo de longitud \(10p\) contiene exactamente \(p\) copias de cada cifra. Por tanto, los \(q\) bloques completos aportan \(qp\), y el resto añade solo un bloque parcial. El resultado exacto es
$$c_d(p)=qp+\min\bigl(\max(u-dp,0),\,p\bigr),\qquad 0\le d\le 9.$$
La fórmula incorpora automáticamente los ceros a la izquierda. Por ejemplo, si \(M=27\) y \(p=10\), las cuentas en la cifra de las decenas son
$$c_0(10)=10,\qquad c_1(10)=10,\qquad c_2(10)=8,\qquad c_d(10)=0\ \text{para }d\ge 3,$$
porque los números del \(0\) al \(9\) aportan una decena igual a \(0\).
En una posición fija solo importa el residuo actual del producto módulo \(10\). Sea \(v_t^{(j)}(r)\) el número de formas ordenadas de elegir \(t\) números de \([0,M]\) cuyo producto de cifras en la posición \(10^j\) deja residuo \(r\in\{0,\dots,9\}\).
Antes de elegir ningún número, el producto es la identidad multiplicativa, de modo que
$$v_0^{(j)}(1)=1,\qquad v_0^{(j)}(r)=0\ \text{para }r\ne 1.$$
Si el residuo actual es \(r\) y la siguiente cifra escogida es \(d\), el nuevo residuo es
$$r'\equiv rd \pmod{10}.$$
Esto define una matriz lineal de transición \(T_j\) de tamaño \(10\times 10\):
$$T_j(r',r)=\sum_{\substack{0\le d\le 9\\ rd\equiv r' \pmod{10}}} c_d(10^j).$$
La recurrencia queda
$$v_{t+1}^{(j)}=T_j\,v_t^{(j)}.$$
Sus entradas son conteos, no probabilidades: cada columna suma \(M+1\), ya que desde cualquier estado hay \(M+1\) posibles números siguientes.
Sea \(e_1\) el vector base concentrado en el residuo \(1\). Tras elegir \(R\) números se obtiene
$$v_R^{(j)}=T_j^R e_1.$$
Por tanto, la contribución total de la posición \(10^j\) es
$$S_j=\sum_{r=0}^9 r\,v_R^{(j)}(r)=\sum_{r=0}^9 r\,(T_j^R e_1)_r.$$
Como \(R\) puede ser enorme, \(T_j^R\) se calcula mediante exponenciación binaria en \(O(10^3\log R)\) operaciones para esa posición.
Al combinarlo todo aparece exactamente la fórmula que implementa el programa:
$$\boxed{F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j \sum_{r=0}^9 r\,(T_j^R e_1)_r \pmod{10^9+9}.}$$
El único ingrediente que cambia de una posición a otra es el vector de frecuencias \(c_d(10^j)\); una vez fijado, el resto del trabajo es la misma álgebra lineal de \(10\) estados.
Aquí solo existe la posición de unidades, porque todos los números entre \(0\) y \(7\) tienen una sola cifra relevante. Las frecuencias son
$$c_0(1)=c_1(1)=\cdots=c_7(1)=1,\qquad c_8(1)=c_9(1)=0.$$
Entonces la suma pedida se reduce a
$$F(2,7)=\sum_{a=0}^7\sum_{b=0}^7 (ab\bmod 10).$$
Evaluando fila por fila:
$$\begin{aligned} a=0&:&&0,\\ a=1&:&&0+1+2+3+4+5+6+7=28,\\ a=2&:&&0+2+4+6+8+0+2+4=26,\\ a=3&:&&0+3+6+9+2+5+8+1=34,\\ a=4&:&&0+4+8+2+6+0+4+8=32,\\ a=5&:&&0+5+0+5+0+5+0+5=20,\\ a=6&:&&0+6+2+8+4+0+6+2=28,\\ a=7&:&&0+7+4+1+8+5+2+9=36. \end{aligned}$$
Así,
$$0+28+26+34+32+20+28+36=204,$$
y por tanto \(F(2,7)=204\), exactamente el valor de comprobación usado por la implementación.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Recorren los valores posicionales \(1,10,100,\dots\) hasta la cifra no nula más alta de \(M\). En cada posición calculan las diez frecuencias de cifras en \([0,M]\) usando la fórmula por bloques, construyen la matriz de transición \(10\times 10\) sobre residuos módulo \(10\), elevan esa matriz a la potencia \(R\) mediante exponenciación binaria y extraen la suma ponderada de cifras desde la columna asociada al residuo inicial \(1\). Después multiplican esa contribución por el peso decimal correspondiente y la acumulan módulo \(10^9+9\). Entre los tres lenguajes solo cambian la sintaxis y el manejo de enteros; el algoritmo es el mismo.
Sea \(L=\lfloor\log_{10} M\rfloor+1\) el número de posiciones decimales relevantes. Para una posición, contar cifras cuesta \(O(10)\), construir la matriz cuesta \(O(10^2)\) y elevar una matriz \(10\times 10\) a una potencia cuesta \(O(10^3\log R)\). Por tanto, el tiempo total es
$$O\bigl(L\cdot 10^3\log R\bigr),$$
que en la práctica equivale a \(O(L\log R)\) porque el espacio de estados tiene tamaño fijo \(10\). La memoria es \(O(10^2)\) para unas pocas matrices pequeñas y los vectores de frecuencias.
把每个非负整数都写成十进制形式，并在需要时在高位补前导零，使所有位数对齐。Freshman's product 的规则是：只把同一数位上的数字相乘，每一位只保留乘积的个位数，而且不同数位之间完全没有进位。若记
$$d_j(n)=\left\lfloor\frac{n}{10^j}\right\rfloor \bmod 10,$$
那么两个数的 freshman's product 可以写成
$$a\odot b=\sum_{j\ge 0}\left(d_j(a)d_j(b)\bmod 10\right)10^j.$$
由于每一位上的模 \(10\) 乘法都是结合的，这个定义可以直接推广到 \(R\) 个因子：
$$n_1\odot n_2\odot \cdots \odot n_R=\sum_{j\ge 0}\left(\prod_{t=1}^R d_j(n_t)\bmod 10\right)10^j.$$
题目要求计算
$$F(R,M)=\sum_{0\le n_1,\dots,n_R\le M} n_1\odot n_2\odot \cdots \odot n_R \pmod{10^9+9}.$$
如果直接枚举所有有序 \(R\) 元组，就需要处理 \((M+1)^R\) 种选择，显然不可行。因此解法改为逐个十进制位统计贡献，再把“重复做数字乘法”的过程压缩成一个固定大小的 \(10\times 10\) 线性转移。
最关键的观察是：freshman's product 从头到尾都不会产生进位。也就是说，每个十进制位都可以独立分析，最后再乘回对应的位权。
固定某一位 \(p=10^j\)。对于一个有序 \(R\) 元组 \((n_1,\dots,n_R)\)，这一位上最终产生的数字是
$$g_p(n_1,\dots,n_R)=\left(\prod_{t=1}^R d_j(n_t)\right)\bmod 10.$$
因此总和可以写成
$$F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j S_j \pmod{10^9+9},$$
其中
$$S_j=\sum_{0\le n_1,\dots,n_R\le M} g_{10^j}(n_1,\dots,n_R).$$
超过 \(M\) 最高位的更高数位没有任何贡献，因为区间 \([0,M]\) 中所有数字在那些位置上的数字都为 \(0\)。
对固定位置 \(p=10^j\)，记 \(c_d(p)\) 为区间 \([0,M]\) 中该位数字等于 \(d\) 的整数个数。令
$$N=M+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad u=N\bmod(10p).$$
长度为 \(10p\) 的一个完整块中，每个数字都会在该位连续出现恰好 \(p\) 次，所以 \(q\) 个完整块总共贡献 \(qp\)。剩下的尾块只会补上一部分，于是有
$$c_d(p)=qp+\min\bigl(\max(u-dp,0),\,p\bigr),\qquad 0\le d\le 9.$$
这个公式天然包含前导零。比如 \(M=27\)、\(p=10\) 时，十位数字的计数为
$$c_0(10)=10,\qquad c_1(10)=10,\qquad c_2(10)=8,\qquad c_d(10)=0\ \text{当 }d\ge 3,$$
因为数字 \(0\) 到 \(9\) 在十位上都带着一个前导零。
在固定数位上，真正重要的只有当前数字乘积对 \(10\) 取模后的结果。设 \(v_t^{(j)}(r)\) 表示：从 \([0,M]\) 中按顺序选出 \(t\) 个数后，这一位上的数字乘积得到余数 \(r\in\{0,\dots,9\}\) 的方案数。
在还没有选任何数时，乘积是乘法单位元，所以
$$v_0^{(j)}(1)=1,\qquad v_0^{(j)}(r)=0\ \text{当 }r\ne 1.$$
如果当前余数是 \(r\)，下一个新选数字在这一位上的数字是 \(d\)，那么新余数满足
$$r'\equiv rd \pmod{10}.$$
于是得到一个 \(10\times 10\) 的转移矩阵 \(T_j\)：
$$T_j(r',r)=\sum_{\substack{0\le d\le 9\\ rd\equiv r' \pmod{10}}} c_d(10^j).$$
对应的递推关系就是
$$v_{t+1}^{(j)}=T_j\,v_t^{(j)}.$$
这里的矩阵元素是“计数”而不是“概率”。每一列的和都等于 \(M+1\)，因为无论当前余数是什么，下一步都可以从 \([0,M]\) 中选择 \(M+1\) 个不同的整数。
记 \(e_1\) 为只在余数 \(1\) 处为 \(1\) 的基向量。选完 \(R\) 个数之后有
$$v_R^{(j)}=T_j^R e_1.$$
因此，位置 \(10^j\) 对总答案的数字贡献是
$$S_j=\sum_{r=0}^9 r\,v_R^{(j)}(r)=\sum_{r=0}^9 r\,(T_j^R e_1)_r.$$
由于 \(R\) 可能非常大，必须用二进制快速幂来计算 \(T_j^R\)，这样每一位的代价就是 \(O(10^3\log R)\)。
综合起来，程序实现的正是下面这个公式：
$$\boxed{F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j \sum_{r=0}^9 r\,(T_j^R e_1)_r \pmod{10^9+9}.}$$
也就是说，不同数位之间真正变化的只有那十个数字频数 \(c_d(10^j)\)。一旦这些频数算出来，后续步骤始终是同一个 \(10\) 状态线性代数问题。
这里实际上只有个位，因为 \(0\) 到 \(7\) 的所有数都只有一位有效数字。对应的计数是
$$c_0(1)=c_1(1)=\cdots=c_7(1)=1,\qquad c_8(1)=c_9(1)=0.$$
因此要求的和直接变成
$$F(2,7)=\sum_{a=0}^7\sum_{b=0}^7 (ab\bmod 10).$$
按第一维逐行计算可得
$$\begin{aligned} a=0&:&&0,\\ a=1&:&&0+1+2+3+4+5+6+7=28,\\ a=2&:&&0+2+4+6+8+0+2+4=26,\\ a=3&:&&0+3+6+9+2+5+8+1=34,\\ a=4&:&&0+4+8+2+6+0+4+8=32,\\ a=5&:&&0+5+0+5+0+5+0+5=20,\\ a=6&:&&0+6+2+8+4+0+6+2=28,\\ a=7&:&&0+7+4+1+8+5+2+9=36. \end{aligned}$$
于是
$$0+28+26+34+32+20+28+36=204,$$
所以 \(F(2,7)=204\)。这和实现中使用的校验值完全一致。
C++、Python 和 Java 三个实现遵循完全相同的流程。它们依次处理位权 \(1,10,100,\dots\)，直到覆盖 \(M\) 的最高非零十进制位。对每一位，先用上面的整块加尾块公式求出区间 \([0,M]\) 中十个数字的出现次数；再据此建立一个作用在模 \(10\) 余数上的 \(10\times 10\) 转移矩阵；随后用二进制快速幂求出这个矩阵的 \(R\) 次幂；最后从“初始余数为 \(1\)”对应的列里读出加权数字和。该位的贡献再乘上位权，并按模 \(10^9+9\) 加入总答案。三个语言版本只是在语法和整数细节上不同，数学过程完全一致。
设 \(L=\lfloor\log_{10} M\rfloor+1\) 为需要处理的十进制位数。对单个数位而言，统计数字频数需要 \(O(10)\)，构造转移矩阵需要 \(O(10^2)\)，而对一个 \(10\times 10\) 矩阵做快速幂需要 \(O(10^3\log R)\)。因此总时间复杂度为
$$O\bigl(L\cdot 10^3\log R\bigr),$$
由于状态数固定为 \(10\)，也可以把它看成实质上的 \(O(L\log R)\)。额外空间复杂度是 \(O(10^2)\)，主要用于几个小矩阵和数字频数向量。
Каждое неотрицательное число записывается в десятичной системе; при необходимости слева мысленно дописываются нули, чтобы все разряды были выровнены. В freshman's product перемножаются только цифры, стоящие в одном и том же разряде, причём в каждом разряде сохраняется лишь последняя цифра произведения. Переносов между разрядами нет. Если
$$d_j(n)=\left\lfloor\frac{n}{10^j}\right\rfloor \bmod 10,$$
то для двух чисел
$$a\odot b=\sum_{j\ge 0}\left(d_j(a)d_j(b)\bmod 10\right)10^j.$$
Так как умножение по модулю \(10\) в каждом разряде ассоциативно, определение сразу переносится на \(R\) множителей:
$$n_1\odot n_2\odot \cdots \odot n_R=\sum_{j\ge 0}\left(\prod_{t=1}^R d_j(n_t)\bmod 10\right)10^j.$$
Нужно вычислить
$$F(R,M)=\sum_{0\le n_1,\dots,n_R\le M} n_1\odot n_2\odot \cdots \odot n_R \pmod{10^9+9}.$$
Перебор всех упорядоченных \(R\)-кортежей, а их \((M+1)^R\), невозможен. Поэтому решение считает вклад каждого десятичного разряда отдельно и сводит повторяющееся умножение цифр к фиксированной матрице перехода \(10\times 10\).
Главное наблюдение: freshman's product никогда не создаёт переносов. Значит, каждый десятичный разряд можно исследовать отдельно, а потом вернуть его вес \(10^j\).
Зафиксируем один разряд \(p=10^j\). Для упорядоченного \(R\)-кортежа \((n_1,\dots,n_R)\) цифра, получающаяся в этом разряде, равна
$$g_p(n_1,\dots,n_R)=\left(\prod_{t=1}^R d_j(n_t)\right)\bmod 10.$$
Тогда полная сумма раскладывается в
$$F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j S_j \pmod{10^9+9},$$
где
$$S_j=\sum_{0\le n_1,\dots,n_R\le M} g_{10^j}(n_1,\dots,n_R).$$
Все более высокие разряды автоматически дают нулевой вклад, потому что у каждого числа из \([0,M]\) там стоит цифра \(0\).
Для фиксированного \(p=10^j\) обозначим через \(c_d(p)\) количество чисел из \([0,M]\), у которых в этом разряде стоит цифра \(d\). Положим
$$N=M+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad u=N\bmod(10p).$$
Каждый полный блок длины \(10p\) содержит ровно \(p\) экземпляров каждой цифры. Поэтому \(q\) полных блоков дают вклад \(qp\), а хвостовой блок добавляет только частичный кусок. Получаем точную формулу
$$c_d(p)=qp+\min\bigl(\max(u-dp,0),\,p\bigr),\qquad 0\le d\le 9.$$
Она автоматически учитывает ведущие нули. Например, при \(M=27\) и \(p=10\) для разряда десятков имеем
$$c_0(10)=10,\qquad c_1(10)=10,\qquad c_2(10)=8,\qquad c_d(10)=0\ \text{при }d\ge 3,$$
поскольку числа от \(0\) до \(9\) дают ведущий ноль в разряде десятков.
В фиксированном разряде важно только текущее значение произведения по модулю \(10\). Пусть \(v_t^{(j)}(r)\) — число упорядоченных способов выбрать \(t\) чисел из \([0,M]\) так, чтобы произведение их цифр в разряде \(10^j\) давало остаток \(r\in\{0,\dots,9\}\).
До выбора первого числа произведение равно мультипликативной единице, поэтому
$$v_0^{(j)}(1)=1,\qquad v_0^{(j)}(r)=0\ \text{при }r\ne 1.$$
Если текущий остаток равен \(r\), а следующая выбранная цифра равна \(d\), новый остаток задаётся равенством
$$r'\equiv rd \pmod{10}.$$
Это задаёт линейную матрицу перехода \(T_j\) размера \(10\times 10\):
$$T_j(r',r)=\sum_{\substack{0\le d\le 9\\ rd\equiv r' \pmod{10}}} c_d(10^j).$$
Соответственно, рекурсия имеет вид
$$v_{t+1}^{(j)}=T_j\,v_t^{(j)}.$$
Элементы этой матрицы — именно количества, а не вероятности. Сумма в каждом столбце равна \(M+1\), потому что из любого текущего состояния есть \(M+1\) допустимых следующих чисел.
Пусть \(e_1\) — базисный вектор, сосредоточенный в состоянии с остатком \(1\). После выбора \(R\) чисел получаем
$$v_R^{(j)}=T_j^R e_1.$$
Следовательно, общий вклад разряда \(10^j\) равен
$$S_j=\sum_{r=0}^9 r\,v_R^{(j)}(r)=\sum_{r=0}^9 r\,(T_j^R e_1)_r.$$
Поскольку \(R\) может быть огромным, степень \(T_j^R\) вычисляется бинарным возведением в степень за \(O(10^3\log R)\) операций для одного разряда.
В итоге получаем именно ту формулу, которую реализует программа:
$$\boxed{F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j \sum_{r=0}^9 r\,(T_j^R e_1)_r \pmod{10^9+9}.}$$
Разряд зависит только от вектора частот \(c_d(10^j)\); после его вычисления вся остальная работа одинакова для каждого десятичного разряда.
Здесь существует только разряд единиц, потому что все числа от \(0\) до \(7\) имеют лишь одну существенную цифру. Частоты цифр таковы:
$$c_0(1)=c_1(1)=\cdots=c_7(1)=1,\qquad c_8(1)=c_9(1)=0.$$
Поэтому искомая сумма сводится к
$$F(2,7)=\sum_{a=0}^7\sum_{b=0}^7 (ab\bmod 10).$$
Если вычислить её построчно, получится
$$\begin{aligned} a=0&:&&0,\\ a=1&:&&0+1+2+3+4+5+6+7=28,\\ a=2&:&&0+2+4+6+8+0+2+4=26,\\ a=3&:&&0+3+6+9+2+5+8+1=34,\\ a=4&:&&0+4+8+2+6+0+4+8=32,\\ a=5&:&&0+5+0+5+0+5+0+5=20,\\ a=6&:&&0+6+2+8+4+0+6+2=28,\\ a=7&:&&0+7+4+1+8+5+2+9=36. \end{aligned}$$
Значит,
$$0+28+26+34+32+20+28+36=204,$$
то есть \(F(2,7)=204\). Это совпадает с контрольным значением, используемым в реализации.
Реализации на C++, Python и Java устроены одинаково. Они перебирают десятичные веса \(1,10,100,\dots\) до старшего ненулевого разряда числа \(M\). Для каждого разряда сначала по блочной формуле вычисляются десять частот цифр в диапазоне \([0,M]\). Затем строится матрица перехода \(10\times 10\) по остаткам modulo \(10\), эта матрица возводится в \(R\)-ю степень бинарным методом, а из столбца, соответствующего начальному остатку \(1\), извлекается взвешенная сумма цифр. Полученный вклад умножается на вес разряда и прибавляется к ответу по модулю \(10^9+9\). Во всех трёх языках различаются только синтаксис и детали работы с целыми числами; математический алгоритм полностью совпадает.
Пусть \(L=\lfloor\log_{10} M\rfloor+1\) — число значимых десятичных разрядов. Для одного разряда подсчёт частот цифр занимает \(O(10)\), построение матрицы — \(O(10^2)\), а быстрое возведение матрицы \(10\times 10\) в степень — \(O(10^3\log R)\). Поэтому итоговая временная сложность равна
$$O\bigl(L\cdot 10^3\log R\bigr),$$
что при фиксированном числе состояний \(10\) фактически эквивалентно \(O(L\log R)\). Память составляет \(O(10^2)\): нужны лишь несколько маленьких матриц и векторов частот.
نكتب كل عدد غير سالب بالصيغة العشرية، ومع الحاجة نضيف أصفارًا بادئة حتى تصطف جميع الخانات. في عملية freshman's product لا نضرب إلا الأرقام الواقعة في الخانة نفسها، ونحتفظ فقط بآخر رقم من حاصل الضرب في كل خانة، من دون أي حمل بين الخانات. إذا عرفنا
$$d_j(n)=\left\lfloor\frac{n}{10^j}\right\rfloor \bmod 10,$$
فإن حاصل freshman's product لعددين هو
$$a\odot b=\sum_{j\ge 0}\left(d_j(a)d_j(b)\bmod 10\right)10^j.$$
وبما أن الضرب modulo \(10\) ترابطي في كل خانة، فإن التعريف يمتد مباشرة إلى \(R\) عوامل:
$$n_1\odot n_2\odot \cdots \odot n_R=\sum_{j\ge 0}\left(\prod_{t=1}^R d_j(n_t)\bmod 10\right)10^j.$$
المطلوب هو حساب
$$F(R,M)=\sum_{0\le n_1,\dots,n_R\le M} n_1\odot n_2\odot \cdots \odot n_R \pmod{10^9+9}.$$
العد المباشر لكل المرتبات المرتبة وعددها \((M+1)^R\) غير عملي تمامًا، لذلك يفصل الحل مساهمة كل خانة عشرية على حدة، ثم يختزل عملية ضرب الأرقام المتكرر إلى مصفوفة انتقال ثابتة الحجم \(10\times 10\).
الفكرة الحاسمة هي أن freshman's product لا يولد أي حمل. لهذا يمكن تحليل كل خانة عشرية بصورة مستقلة، ثم إعادة تجميع النتائج مع وزنها العشري المناسب.
لنثبت خانة واحدة \(p=10^j\). إذا أخذنا مرتبًا مرتبًا \((n_1,\dots,n_R)\)، فإن الرقم الناتج في هذه الخانة يساوي
$$g_p(n_1,\dots,n_R)=\left(\prod_{t=1}^R d_j(n_t)\right)\bmod 10.$$
وعليه تتفكك المحصلة الكلية إلى
$$F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j S_j \pmod{10^9+9},$$
حيث
$$S_j=\sum_{0\le n_1,\dots,n_R\le M} g_{10^j}(n_1,\dots,n_R).$$
أما الخانات الأعلى من أعلى خانة غير صفرية في \(M\) فلا تضيف شيئًا، لأن كل الأعداد في \([0,M]\) تحمل الرقم \(0\) هناك.
لخانة ثابتة \(p=10^j\)، ولتكن \(c_d(p)\) عدد الأعداد في \([0,M]\) التي يساوي رقمها في هذه الخانة \(d\). نعرّف
$$N=M+1,\qquad q=\left\lfloor\frac{N}{10p}\right\rfloor,\qquad u=N\bmod(10p).$$
كل كتلة كاملة طولها \(10p\) تحتوي على كل رقم بالضبط \(p\) مرة في تلك الخانة، لذلك تساهم الكتل الكاملة وعددها \(q\) بمقدار \(qp\)، ثم تضيف الذيل المتبقي جزءًا من كتلة إضافية. ومن ثم
$$c_d(p)=qp+\min\bigl(\max(u-dp,0),\,p\bigr),\qquad 0\le d\le 9.$$
هذه الصيغة تتعامل تلقائيًا مع الأصفار البادئة. فمثلًا إذا كان \(M=27\) و\(p=10\)، فإن أعداد خانة العشرات هي
$$c_0(10)=10,\qquad c_1(10)=10,\qquad c_2(10)=8,\qquad c_d(10)=0,\qquad d\ge 3.$$
لأن الأعداد من \(0\) إلى \(9\) تحمل صفرًا بادئًا في خانة العشرات.
في خانة ثابتة، المهم فقط هو قيمة حاصل الضرب الحالية modulo \(10\). لنعرّف \(v_t^{(j)}(r)\) بأنه عدد الطرق المرتبة لاختيار \(t\) أعداد من \([0,M]\) بحيث يكون حاصل ضرب الأرقام في الخانة \(10^j\) ذا باقي \(r\in\{0,\dots,9\}\).
قبل اختيار أي عدد يكون حاصل الضرب هو العنصر المحايد الضربي، لذلك
$$v_0^{(j)}(1)=1,\qquad v_0^{(j)}(r)=0,\qquad r\ne 1.$$
إذا كان الباقي الحالي هو \(r\) والرقم التالي المختار هو \(d\)، فإن الباقي الجديد يحقق
$$r'\equiv rd \pmod{10}.$$
وهذا يحدد مصفوفة انتقال خطية \(T_j\) بحجم \(10\times 10\):
$$T_j(r',r)=\sum_{\substack{0\le d\le 9\\ rd\equiv r' \pmod{10}}} c_d(10^j).$$
وبالتالي تصبح العلاقة التكرارية
$$v_{t+1}^{(j)}=T_j\,v_t^{(j)}.$$
قيم هذه المصفوفة هي أعداد طرق وليست احتمالات؛ مجموع كل عمود يساوي \(M+1\)، لأننا من أي حالة حالية نملك \(M+1\) اختيارًا ممكنًا للعدد التالي.
لتكن \(e_1\) متجه الأساس المتركز عند الباقي \(1\). بعد اختيار \(R\) أعداد نحصل على
$$v_R^{(j)}=T_j^R e_1.$$
ومن ثم فإن المساهمة الكلية للخانة \(10^j\) هي
$$S_j=\sum_{r=0}^9 r\,v_R^{(j)}(r)=\sum_{r=0}^9 r\,(T_j^R e_1)_r.$$
ولأن \(R\) قد يكون كبيرًا جدًا، فإن حساب \(T_j^R\) يتم بالأس الثنائي في \(O(10^3\log R)\) عملية لهذه الخانة.
بتجميع كل ما سبق نحصل على الصيغة التي تنفذها الشيفرة حرفيًا:
$$\boxed{F(R,M)=\sum_{\substack{j\ge 0\\10^j\le M}} 10^j \sum_{r=0}^9 r\,(T_j^R e_1)_r \pmod{10^9+9}.}$$
المقدار الوحيد الذي يتغير من خانة إلى أخرى هو متجه تكرارات الأرقام \(c_d(10^j)\). بعد حساب هذا المتجه يصبح الباقي هو نفس مسألة الجبر الخطي ذات الحالات العشر.
هنا توجد فقط خانة الآحاد، لأن جميع الأعداد من \(0\) إلى \(7\) لها رقم فعّال واحد فقط. لذلك تكون التكرارات
$$c_0(1)=c_1(1)=\cdots=c_7(1)=1,\qquad c_8(1)=c_9(1)=0.$$
فتتبسط المحصلة المطلوبة إلى
$$F(2,7)=\sum_{a=0}^7\sum_{b=0}^7 (ab\bmod 10).$$
وبالحساب صفًا صفًا نحصل على
$$\begin{aligned} a=0&:&&0,\\ a=1&:&&0+1+2+3+4+5+6+7=28,\\ a=2&:&&0+2+4+6+8+0+2+4=26,\\ a=3&:&&0+3+6+9+2+5+8+1=34,\\ a=4&:&&0+4+8+2+6+0+4+8=32,\\ a=5&:&&0+5+0+5+0+5+0+5=20,\\ a=6&:&&0+6+2+8+4+0+6+2=28,\\ a=7&:&&0+7+4+1+8+5+2+9=36. \end{aligned}$$
إذن
$$0+28+26+34+32+20+28+36=204,$$
ومن ثم \(F(2,7)=204\)، وهو نفس مقدار التحقق الذي تنتجه التطبيقات.
تنفذ تطبيقات C++ وPython وJava السلسلة نفسها من الخطوات. فهي تمر على أوزان الخانات \(1,10,100,\dots\) حتى أعلى خانة غير صفرية في \(M\). في كل خانة تُحسب تكرارات الأرقام العشرة داخل \([0,M]\) باستعمال صيغة الكتل الكاملة والذيل الجزئي. بعد ذلك تُبنى مصفوفة الانتقال \(10\times 10\) على البواقي modulo \(10\)، ثم تُرفع هذه المصفوفة إلى القوة \(R\) بواسطة الأس الثنائي، ثم تُستخرج منها المحصلة الموزونة المنطلقة من حالة البداية ذات الباقي \(1\). وأخيرًا تُضرب مساهمة الخانة في وزنها العشري وتُضاف إلى الجواب modulo \(10^9+9\). الاختلاف بين اللغات الثلاث يقتصر على الصياغة البرمجية والتعامل مع الأعداد الصحيحة، أما الخطة الرياضية فهي نفسها تمامًا.
ليكن \(L=\lfloor\log_{10} M\rfloor+1\) عدد الخانات العشرية التي يجب معالجتها. في خانة واحدة، حساب تكرارات الأرقام يحتاج إلى \(O(10)\)، وبناء المصفوفة يحتاج إلى \(O(10^2)\)، ورفع مصفوفة \(10\times 10\) إلى قوة ما يحتاج إلى \(O(10^3\log R)\). لذا فإن الزمن الكلي هو
$$O\bigl(L\cdot 10^3\log R\bigr),$$
وهو فعليًا \(O(L\log R)\) لأن عدد الحالات ثابت ويساوي \(10\). أما الذاكرة فتبلغ \(O(10^2)\) فقط، لأنها تقتصر على بضع مصفوفات صغيرة ومتجهات للتكرارات.