A \(5\)-smooth number has the form \(2^a3^b5^c\) with \(a,b,c\ge 0\). If we write
$$\Omega(2^a3^b5^c)=a+b+c,\qquad \operatorname{sopfr}(2^a3^b5^c)=2a+3b+5c,$$
then the counting problem solved by the implementations can be expressed through
$$C_k(s)=\#\left\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:\ a+b+c=k,\ 2a+3b+5c=s\right\}.$$
The target sequence is
$$f(n)=\sum_{k\ge 0}\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
So \(f(n)\) counts ordered pairs of \(5\)-smooth numbers with the same total number of prime factors, while their weighted prime-factor sums add up to \(n\). The goal is to compute \(f(10^7)\bmod (10^9+7)\).
The brute-force definition is useful for understanding the sequence, but it is far too slow at \(n=10^7\). The key is to convert the double count into one rational generating function and then read off a sparse linear recurrence.
For fixed \(k\), define the ordinary generating polynomial
$$P_k(q)=\sum_{s\ge 0} C_k(s)\,q^s=\sum_{a+b+c=k} q^{2a+3b+5c}.$$
Introduce a second marker \(x\) for the value of \(k\). Summing over all triples gives
$$\sum_{k\ge 0} P_k(q)x^k=\sum_{a,b,c\ge 0} x^{a+b+c}q^{2a+3b+5c}=\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)}.$$
This compactly stores every allowed exponent triple, with \(x\) recording the total exponent count and \(q\) recording the weighted sum \(2a+3b+5c\).
For one fixed \(k\), the coefficient of \(q^n\) in \(P_k(q)^2\) is exactly
$$\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
Therefore the full generating function of the target sequence is
$$F(q)=\sum_{n\ge 0} f(n)q^n=\sum_{k\ge 0} P_k(q)^2.$$
To sum the squares while forcing the same value of \(k\) on both sides, use constant-term extraction:
$$F(q)=\mathrm{CT}_x\!\left(\sum_{k\ge 0} P_k(q)x^k\right)\!\left(\sum_{m\ge 0} P_m(q)x^{-m}\right).$$
Substituting the bivariate generating function from Step 1 yields
$$F(q)=\mathrm{CT}_x\!\left(\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)(1-q^2/x)(1-q^3/x)(1-q^5/x)}\right).$$
The coefficient of \(x^0\) is what keeps only the terms with identical total exponent count on both sides of the pair.
For \(|q|<1\), the poles in the \(x\)-plane that lie inside the unit circle are \(x=q^2\), \(x=q^3\), and \(x=q^5\). Summing the three corresponding residues gives the exact rational form
$$F(q)=\frac{1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12}}{1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}}.$$
This single fraction is the decisive step: once \(F(q)\) is rational, the sequence \(f(n)\) must satisfy a linear recurrence with constant coefficients.
Write
$$N(q)=1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12},$$
$$D(q)=1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}.$$
Since \(D(q)F(q)=N(q)\), coefficient comparison gives
$$\begin{aligned} f(n)=\nu_n&+f(n-1)+f(n-6)-f(n-9)+f(n-10)-f(n-11)-f(n-13)\\ &+f(n-19)+f(n-21)-f(n-22)+f(n-23)-f(n-26)-f(n-31)+f(n-32), \end{aligned}$$
where \(f(m)=0\) for \(m<0\), and \(\nu_n\) comes from the numerator \(N(q)\):
$$\nu_n=\begin{cases} 1, & n\in\{0,4,5,7,8,12\},\\ -1, & n\in\{1,11\},\\ -2, & n=6,\\ 0, & \text{otherwise.} \end{cases}$$
The implementations use exactly this recurrence, always reducing modulo \(10^9+7\).
At \(n=10\), the count is small enough to inspect directly.
For \(k=1\), the only possible weighted sum is \(5\), coming from \(5=5^1\). This contributes one ordered pair: \((5,5)\).
For \(k=2\), the available \(5\)-smooth numbers are
$$2^2=4,\qquad 2\cdot 3=6,\qquad 3^2=9,$$
with weighted sums \(4\), \(5\), and \(6\), respectively. To total \(10\), the ordered pairs are
$$ (4,9),\qquad (6,6),\qquad (9,4). $$
No other value of \(k\) works, so
$$f(10)=1+3=4,$$
which matches the small checkpoint used by the implementations.
The C++, Python, and Java implementations do not enumerate exponent triples once \(n\) becomes large. Instead, they build the sequence from left to right using the recurrence above. At each index they start from the forcing term \(\nu_n\), add or subtract the 13 lagged values dictated by the denominator polynomial, and normalize the result modulo \(10^9+7\).
The current implementations store all values from \(0\) through \(n\), so looking up each lagged term is immediate. One implementation also performs a small direct enumeration up to \(120\) and checks the sample values \(f(10)=4\) and \(f(100)=3629\) before computing the final answer.
The direct combinatorial definition is far too expensive for \(n=10^7\), because it repeatedly scans many exponent triples and many convolutions. The optimized method performs only a constant amount of work per index: one forcing lookup, 13 additions or subtractions, and one modular reduction. Therefore the running time is \(O(n)\).
As written, the implementations keep the whole sequence array, so the memory usage is \(O(n)\). Since the largest lag is \(32\), the same recurrence could be implemented with a rolling window and \(O(1)\) memory, but that optimization is not used here.
Eine \(5\)-glatte Zahl hat die Form \(2^a3^b5^c\) mit \(a,b,c\ge 0\). Schreibt man
$$\Omega(2^a3^b5^c)=a+b+c,\qquad \operatorname{sopfr}(2^a3^b5^c)=2a+3b+5c,$$
dann lässt sich die in den Implementierungen verwendete Zählfunktion über
$$C_k(s)=\#\left\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:\ a+b+c=k,\ 2a+3b+5c=s\right\}$$
beschreiben. Gesucht ist die Folge
$$f(n)=\sum_{k\ge 0}\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
Damit zählt \(f(n)\) geordnete Paare von \(5\)-glatten Zahlen mit derselben Gesamtzahl von Primfaktoren, deren gewichtete Primfaktorsummen zusammen \(n\) ergeben. Benötigt wird \(f(10^7)\bmod(10^9+7)\).
Die rohe Definition erklärt die Bedeutung der Folge, ist aber für \(n=10^7\) viel zu langsam. Der entscheidende Schritt besteht darin, die Doppelsumme in eine rationale erzeugende Funktion zu verwandeln und daraus eine dünn besetzte lineare Rekurrenz abzulesen.
Für festes \(k\) definieren wir das gewöhnliche erzeugende Polynom
$$P_k(q)=\sum_{s\ge 0} C_k(s)\,q^s=\sum_{a+b+c=k} q^{2a+3b+5c}.$$
Mit einer zweiten Markierungsvariablen \(x\) für den Wert von \(k\) ergibt die Summation über alle Tripel
$$\sum_{k\ge 0} P_k(q)x^k=\sum_{a,b,c\ge 0} x^{a+b+c}q^{2a+3b+5c}=\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)}.$$
Diese Funktion speichert alle zulässigen Exponententripel kompakt: \(x\) verfolgt die Gesamtzahl der Exponenten, \(q\) die gewichtete Summe \(2a+3b+5c\).
Für ein festes \(k\) ist der Koeffizient von \(q^n\) in \(P_k(q)^2\) genau
$$\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
Also lautet die erzeugende Funktion der Zielfolge
$$F(q)=\sum_{n\ge 0} f(n)q^n=\sum_{k\ge 0} P_k(q)^2.$$
Um die Quadratsumme zu bilden und zugleich gleiche Werte von \(k\) auf beiden Seiten zu erzwingen, verwendet man den konstanten Term:
$$F(q)=\mathrm{CT}_x\!\left(\sum_{k\ge 0} P_k(q)x^k\right)\!\left(\sum_{m\ge 0} P_m(q)x^{-m}\right).$$
Mit der bivariaten erzeugenden Funktion aus Schritt 1 wird daraus
$$F(q)=\mathrm{CT}_x\!\left(\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)(1-q^2/x)(1-q^3/x)(1-q^5/x)}\right).$$
Der Koeffizient von \(x^0\) lässt genau die Terme übrig, bei denen beide Elemente des Paares dieselbe Gesamtzahl von Primfaktoren besitzen.
Für \(|q|<1\) liegen im \(x\)-Bereich die Pole \(x=q^2\), \(x=q^3\) und \(x=q^5\) innerhalb des Einheitskreises. Die Summe der zugehörigen Residuen liefert die exakte rationale Form
$$F(q)=\frac{1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12}}{1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}}.$$
Genau hier wird das Problem handhabbar: Eine rationale erzeugende Funktion impliziert sofort eine lineare Rekurrenz mit konstanten Koeffizienten.
Setze
$$N(q)=1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12},$$
$$D(q)=1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}.$$
Aus \(D(q)F(q)=N(q)\) erhält man durch Koeffizientenvergleich
$$\begin{aligned} f(n)=\nu_n&+f(n-1)+f(n-6)-f(n-9)+f(n-10)-f(n-11)-f(n-13)\\ &+f(n-19)+f(n-21)-f(n-22)+f(n-23)-f(n-26)-f(n-31)+f(n-32), \end{aligned}$$
wobei \(f(m)=0\) für \(m<0\) gilt und \(\nu_n\) aus dem Zähler \(N(q)\) stammt:
$$\nu_n=\begin{cases} 1, & n\in\{0,4,5,7,8,12\},\\ -1, & n\in\{1,11\},\\ -2, & n=6,\\ 0, & \text{sonst.} \end{cases}$$
Genau diese Rekurrenz wird in den Implementierungen modulo \(10^9+7\) verwendet.
Für \(n=10\) lässt sich die Zählung noch direkt nachvollziehen.
Bei \(k=1\) ist die einzige mögliche gewichtete Summe \(5\), nämlich durch \(5=5^1\). Das liefert genau ein geordnetes Paar: \((5,5)\).
Bei \(k=2\) sind die verfügbaren \(5\)-glatten Zahlen
$$2^2=4,\qquad 2\cdot 3=6,\qquad 3^2=9,$$
mit gewichteten Summen \(4\), \(5\) und \(6\). Um insgesamt \(10\) zu erhalten, gibt es die geordneten Paare
$$ (4,9),\qquad (6,6),\qquad (9,4). $$
Andere Werte von \(k\) tragen nichts bei. Also
$$f(10)=1+3=4,$$
genau wie im Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen enumerieren für großes \(n\) keine Exponententripel mehr. Stattdessen bauen sie die Folge von links nach rechts mit der obigen Rekurrenz auf. Für jeden Index beginnt der Wert mit dem Forcing-Term \(\nu_n\), danach werden die 13 verzögerten Folgewerte gemäß dem Nennerpolynom addiert oder subtrahiert, und am Ende wird modulo \(10^9+7\) reduziert.
Die aktuellen Implementierungen speichern alle Werte von \(0\) bis \(n\), sodass jeder benötigte verzögerte Wert direkt zugreifbar ist. Eine Implementierung prüft zusätzlich per direkter Enumeration bis \(120\) sowie mit den Stichproben \(f(10)=4\) und \(f(100)=3629\), bevor das Endergebnis berechnet wird.
Die direkte kombinatorische Definition ist für \(n=10^7\) viel zu teuer, weil sie zahlreiche Exponententripel und Faltungen wiederholt auswertet. Das optimierte Verfahren führt pro Index nur konstant viele Operationen aus: einen Zugriff auf \(\nu_n\), 13 Additionen oder Subtraktionen und eine Modulo-Reduktion. Daher beträgt die Laufzeit \(O(n)\).
So wie die Implementierungen geschrieben sind, halten sie das gesamte Folgenarray im Speicher, also \(O(n)\) Speicher. Da die größte Verzögerung \(32\) ist, könnte man dieselbe Rekurrenz auch mit einem Ringpuffer und \(O(1)\) Speicher umsetzen; diese Optimierung wird hier jedoch nicht verwendet.
Bir \(5\)-smooth sayı \(2^a3^b5^c\) biçimindedir; burada \(a,b,c\ge 0\). Eğer
$$\Omega(2^a3^b5^c)=a+b+c,\qquad \operatorname{sopfr}(2^a3^b5^c)=2a+3b+5c$$
yazarsak, uygulamaların çözdüğü sayım problemi
$$C_k(s)=\#\left\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:\ a+b+c=k,\ 2a+3b+5c=s\right\}$$
yardımıyla ifade edilir. Hedef dizi şudur:
$$f(n)=\sum_{k\ge 0}\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
Yani \(f(n)\), asal çarpan sayıları aynı olan sıralı \(5\)-smooth sayı çiftlerini sayar; ayrıca iki sayının ağırlıklı asal-toplamları birlikte \(n\) olmalıdır. İstenen değer \(f(10^7)\bmod(10^9+7)\)'dir.
Doğrudan tanım dizinin neyi saydığını açıklar, fakat \(n=10^7\) için pratik değildir. Çözümün özü, bu çift toplamını tek bir rasyonel üreteç fonksiyonuna indirgemek ve oradan seyrek bir lineer rekürans çıkarmaktır.
Sabit bir \(k\) için şu olağan üreteç polinomunu tanımlayalım:
$$P_k(q)=\sum_{s\ge 0} C_k(s)\,q^s=\sum_{a+b+c=k} q^{2a+3b+5c}.$$
\(k\) değerini ayrıca işaretlemek için ikinci bir değişken \(x\) kullanalım. Tüm üçlüler üzerinden toplarsak
$$\sum_{k\ge 0} P_k(q)x^k=\sum_{a,b,c\ge 0} x^{a+b+c}q^{2a+3b+5c}=\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)}$$
elde edilir. Burada \(x\), toplam üs sayısını; \(q\) ise ağırlıklı toplam \(2a+3b+5c\)'yi izler.
Sabit \(k\) için \(P_k(q)^2\) içindeki \(q^n\) katsayısı tam olarak
$$\sum_{s=0}^{n} C_k(s)\,C_k(n-s)$$
olur. Dolayısıyla hedef dizinin üreteç fonksiyonu
$$F(q)=\sum_{n\ge 0} f(n)q^n=\sum_{k\ge 0} P_k(q)^2$$
şeklindedir. Kare toplamını alırken iki tarafta da aynı \(k\) değerini seçmek için sabit terim çıkarımı kullanılır:
$$F(q)=\mathrm{CT}_x\!\left(\sum_{k\ge 0} P_k(q)x^k\right)\!\left(\sum_{m\ge 0} P_m(q)x^{-m}\right).$$
Adım 1'deki iki değişkenli üreteç yerine konunca
$$F(q)=\mathrm{CT}_x\!\left(\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)(1-q^2/x)(1-q^3/x)(1-q^5/x)}\right)$$
elde edilir. \(x^0\) katsayısı, çiftin iki tarafında toplam üs sayısının aynı olmasını garanti eder.
\(|q|<1\) iken \(x\)-düzleminde birim çemberin içinde kalan kutuplar \(x=q^2\), \(x=q^3\) ve \(x=q^5\)'tir. Bu üç rezidünün toplamı tam olarak
$$F(q)=\frac{1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12}}{1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}}$$
sonucunu verir. Problem bu noktada yönetilebilir hale gelir; çünkü rasyonel üreteç fonksiyon, sabit katsayılı lineer rekürans anlamına gelir.
Şöyle tanımlayalım:
$$N(q)=1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12},$$
$$D(q)=1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}.$$
\(D(q)F(q)=N(q)\) eşitliğinde katsayıları karşılaştırınca
$$\begin{aligned} f(n)=\nu_n&+f(n-1)+f(n-6)-f(n-9)+f(n-10)-f(n-11)-f(n-13)\\ &+f(n-19)+f(n-21)-f(n-22)+f(n-23)-f(n-26)-f(n-31)+f(n-32) \end{aligned}$$
elde edilir. Burada \(m<0\) için \(f(m)=0\) kabul edilir ve \(\nu_n\) pay polinomundan gelir:
$$\nu_n=\begin{cases} 1, & n\in\{0,4,5,7,8,12\},\\ -1, & n\in\{1,11\},\\ -2, & n=6,\\ 0, & \text{aksi halde.} \end{cases}$$
C++, Python ve Java uygulamaları tam olarak bu reküransı \(10^9+7\) modunda yürütür.
\(n=10\) için sayım doğrudan görülebilir.
\(k=1\) iken tek mümkün ağırlıklı toplam \(5\)'tir; bu da \(5=5^1\) sayısından gelir. Katkı yapan tek sıralı çift \((5,5)\)'tir.
\(k=2\) iken mümkün \(5\)-smooth sayılar
$$2^2=4,\qquad 2\cdot 3=6,\qquad 3^2=9$$
olur; bunların ağırlıklı toplamları sırasıyla \(4\), \(5\) ve \(6\)'dır. Toplamı \(10\) yapan sıralı çiftler
$$ (4,9),\qquad (6,6),\qquad (9,4) $$
şeklindedir. Başka \(k\) değeri katkı yapmaz; dolayısıyla
$$f(10)=1+3=4$$
olur. Bu da uygulamaların kullandığı küçük doğrulama değeriyle aynıdır.
C++, Python ve Java uygulamaları büyük \(n\) için üs üçlülerini tek tek dolaşmaz. Bunun yerine diziyi soldan sağa doğru yukarıdaki reküransla inşa eder. Her adımda önce \(\nu_n\) düzeltme terimi alınır, sonra paydadaki polinomun belirlediği 13 gecikmeli terim eklenir veya çıkarılır, en sonda sonuç \(10^9+7\) modunda normalize edilir.
Mevcut uygulamalar \(0\) ile \(n\) arasındaki tüm değerleri sakladığı için gereken gecikmeli terimler doğrudan okunabilir. Dillerden birindeki sürüm ayrıca \(120\)'ye kadar doğrudan sayım yapıp \(f(10)=4\) ve \(f(100)=3629\) kontrollerini doğruladıktan sonra büyük girdiye geçer.
Doğrudan kombinatoryal tanım \(n=10^7\) için çok pahalıdır; çünkü çok sayıda üs üçlüsü ve konvolüsyon tekrar tekrar değerlendirilir. Optimizasyonlu yöntemde her indis için sabit sayıda işlem vardır: bir düzeltme terimi, 13 toplama ya da çıkarma ve bir mod alma. Bu yüzden zaman karmaşıklığı \(O(n)\)'dir.
Uygulamalar tüm diziyi bellekte tuttuğu için uzay karmaşıklığı \(O(n)\)'dir. En büyük gecikme \(32\) olduğundan, aynı rekürans döngüsel bir pencereyle \(O(1)\) bellekte de çalıştırılabilir; ancak burada o iyileştirme kullanılmamıştır.
Un número \(5\)-smooth tiene la forma \(2^a3^b5^c\) con \(a,b,c\ge 0\). Si escribimos
$$\Omega(2^a3^b5^c)=a+b+c,\qquad \operatorname{sopfr}(2^a3^b5^c)=2a+3b+5c,$$
entonces el conteo utilizado por las implementaciones puede expresarse mediante
$$C_k(s)=\#\left\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:\ a+b+c=k,\ 2a+3b+5c=s\right\}.$$
La sucesión objetivo es
$$f(n)=\sum_{k\ge 0}\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
Así, \(f(n)\) cuenta pares ordenados de números \(5\)-smooth con el mismo número total de factores primos, mientras que la suma ponderada de esos factores primos vale \(n\). Se requiere calcular \(f(10^7)\bmod(10^9+7)\).
La definición bruta aclara qué se está contando, pero es inviable para \(n=10^7\). La idea central es transformar esa doble suma en una sola función generadora racional y, a partir de ella, leer una recurrencia lineal muy dispersa.
Para un \(k\) fijo, definimos el polinomio generador ordinario
$$P_k(q)=\sum_{s\ge 0} C_k(s)\,q^s=\sum_{a+b+c=k} q^{2a+3b+5c}.$$
Introducimos una segunda variable \(x\) para marcar el valor de \(k\). Al sumar sobre todos los triples obtenemos
$$\sum_{k\ge 0} P_k(q)x^k=\sum_{a,b,c\ge 0} x^{a+b+c}q^{2a+3b+5c}=\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)}.$$
Esta expresión codifica todos los triples admisibles: \(x\) controla cuántos factores primos hay en total y \(q\) registra la suma ponderada \(2a+3b+5c\).
Para un \(k\) fijo, el coeficiente de \(q^n\) en \(P_k(q)^2\) es exactamente
$$\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
Por lo tanto, la función generadora de la sucesión buscada es
$$F(q)=\sum_{n\ge 0} f(n)q^n=\sum_{k\ge 0} P_k(q)^2.$$
Para sumar esos cuadrados obligando a que ambos términos tengan el mismo \(k\), usamos extracción de término constante:
$$F(q)=\mathrm{CT}_x\!\left(\sum_{k\ge 0} P_k(q)x^k\right)\!\left(\sum_{m\ge 0} P_m(q)x^{-m}\right).$$
Sustituyendo la función generadora bivariante del paso anterior, queda
$$F(q)=\mathrm{CT}_x\!\left(\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)(1-q^2/x)(1-q^3/x)(1-q^5/x)}\right).$$
El coeficiente de \(x^0\) es precisamente el mecanismo que conserva solo los pares con la misma suma total de exponentes.
Cuando \(|q|<1\), los polos del plano \(x\) que quedan dentro del círculo unidad son \(x=q^2\), \(x=q^3\) y \(x=q^5\). La suma de esos tres residuos se simplifica hasta
$$F(q)=\frac{1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12}}{1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}}.$$
Este es el paso decisivo: al ser racional, \(F(q)\) obliga a que \(f(n)\) satisfaga una recurrencia lineal de coeficientes constantes.
Escribimos
$$N(q)=1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12},$$
$$D(q)=1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}.$$
Como \(D(q)F(q)=N(q)\), al comparar coeficientes aparece
$$\begin{aligned} f(n)=\nu_n&+f(n-1)+f(n-6)-f(n-9)+f(n-10)-f(n-11)-f(n-13)\\ &+f(n-19)+f(n-21)-f(n-22)+f(n-23)-f(n-26)-f(n-31)+f(n-32), \end{aligned}$$
donde \(f(m)=0\) para \(m<0\), y \(\nu_n\) proviene del numerador:
$$\nu_n=\begin{cases} 1, & n\in\{0,4,5,7,8,12\},\\ -1, & n\in\{1,11\},\\ -2, & n=6,\\ 0, & \text{en otro caso.} \end{cases}$$
Las implementaciones en C++, Python y Java usan exactamente esta recurrencia y reducen todo módulo \(10^9+7\).
Para \(n=10\), el recuento aún puede verse a mano.
Con \(k=1\), la única suma ponderada posible es \(5\), correspondiente a \(5=5^1\). Eso produce un solo par ordenado: \((5,5)\).
Con \(k=2\), los números \(5\)-smooth disponibles son
$$2^2=4,\qquad 2\cdot 3=6,\qquad 3^2=9,$$
cuyas sumas ponderadas son \(4\), \(5\) y \(6\). Para totalizar \(10\), los pares ordenados son
$$ (4,9),\qquad (6,6),\qquad (9,4). $$
No hay contribuciones de otros valores de \(k\), así que
$$f(10)=1+3=4,$$
en acuerdo con el punto de control pequeño de las implementaciones.
Las implementaciones en C++, Python y Java no enumeran triples de exponentes cuando \(n\) es grande. En su lugar, construyen la sucesión de izquierda a derecha usando la recurrencia anterior. En cada índice parten del término de corrección \(\nu_n\), añaden o restan los 13 valores atrasados prescritos por el denominador y normalizan el resultado módulo \(10^9+7\).
Tal como están escritas, las implementaciones guardan todos los valores desde \(0\) hasta \(n\), de modo que cada acceso atrasado es inmediato. Una de ellas también compara los primeros términos con una enumeración directa hasta \(120\) y verifica \(f(10)=4\) y \(f(100)=3629\) antes de imprimir la respuesta final.
La definición combinatoria directa es demasiado costosa para \(n=10^7\), porque reexplora muchos triples y muchas convoluciones. El método optimizado realiza una cantidad constante de trabajo por índice: una consulta de \(\nu_n\), 13 sumas o restas y una reducción modular. Por eso el tiempo total es \(O(n)\).
En la forma actual, las implementaciones almacenan el arreglo completo de la sucesión, así que el uso de memoria es \(O(n)\). Como el mayor retraso es \(32\), la misma recurrencia podría ejecutarse con una ventana circular y \(O(1)\) memoria, pero esa optimización no se emplea aquí.
一个 \(5\)-smooth 数可以写成 \(2^a3^b5^c\)，其中 \(a,b,c\ge 0\)。如果记
$$\Omega(2^a3^b5^c)=a+b+c,\qquad \operatorname{sopfr}(2^a3^b5^c)=2a+3b+5c,$$
那么实现中实际计算的计数函数可以写成
$$C_k(s)=\#\left\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:\ a+b+c=k,\ 2a+3b+5c=s\right\}.$$
目标序列是
$$f(n)=\sum_{k\ge 0}\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
也就是说，\(f(n)\) 统计的是有序的 \(5\)-smooth 数对：两边拥有相同的素因子总重数，而两边的加权素因子和相加等于 \(n\)。题目要求的是 \(f(10^7)\bmod(10^9+7)\)。
直接按照定义去枚举，能够说明序列是什么意思，但在 \(n=10^7\) 时完全不可行。真正有效的方法，是把这类“双层计数”压缩成一个有理型生成函数，再从生成函数直接读出稀疏线性递推。
对固定的 \(k\)，定义普通生成多项式
$$P_k(q)=\sum_{s\ge 0} C_k(s)\,q^s=\sum_{a+b+c=k} q^{2a+3b+5c}.$$
再引入第二个变量 \(x\) 来记录 \(k\)。对所有非负三元组求和，有
$$\sum_{k\ge 0} P_k(q)x^k=\sum_{a,b,c\ge 0} x^{a+b+c}q^{2a+3b+5c}=\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)}.$$
这个式子把所有可能的指数三元组一次性编码起来：\(x\) 跟踪总指数个数 \(a+b+c\)，\(q\) 跟踪加权和 \(2a+3b+5c\)。
对于固定的 \(k\)，\(P_k(q)^2\) 中 \(q^n\) 的系数正好是
$$\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
因此，目标序列的生成函数可以写成
$$F(q)=\sum_{n\ge 0} f(n)q^n=\sum_{k\ge 0} P_k(q)^2.$$
问题在于，这里必须确保两边选中的项拥有同一个 \(k\)。最自然的做法是使用常数项提取：
$$F(q)=\mathrm{CT}_x\!\left(\sum_{k\ge 0} P_k(q)x^k\right)\!\left(\sum_{m\ge 0} P_m(q)x^{-m}\right).$$
把上一步得到的双变量生成函数代进去，就得到
$$F(q)=\mathrm{CT}_x\!\left(\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)(1-q^2/x)(1-q^3/x)(1-q^5/x)}\right).$$
这里取 \(x^0\) 项的意义非常清楚：只有当左右两侧的总指数个数相同，也就是 \(k\) 相同时，乘积中的 \(x\) 次数才会相互抵消。
当 \(|q|<1\) 时，在 \(x\)-平面单位圆内部的极点只有 \(x=q^2\)、\(x=q^3\)、\(x=q^5\) 三个。把这三个极点的留数相加，化简后可得
$$F(q)=\frac{1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12}}{1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}}.$$
这一步是全题的核心。因为一旦生成函数是有理函数，序列 \(f(n)\) 就必然满足一个常系数线性递推，而且递推系数可以直接从分母多项式读出来。
记
$$N(q)=1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12},$$
$$D(q)=1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}.$$
由 \(D(q)F(q)=N(q)\) 比较系数，就得到
$$\begin{aligned} f(n)=\nu_n&+f(n-1)+f(n-6)-f(n-9)+f(n-10)-f(n-11)-f(n-13)\\ &+f(n-19)+f(n-21)-f(n-22)+f(n-23)-f(n-26)-f(n-31)+f(n-32), \end{aligned}$$
其中对所有 \(m<0\) 约定 \(f(m)=0\)，而 \(\nu_n\) 则来自分子多项式：
$$\nu_n=\begin{cases} 1, & n\in\{0,4,5,7,8,12\},\\ -1, & n\in\{1,11\},\\ -2, & n=6,\\ 0, & \text{其他情形。} \end{cases}$$
实际的 C++、Python 和 Java 实现，正是逐项执行这条递推，并且每一步都对 \(10^9+7\) 取模。
当 \(n=10\) 时，可以直接把所有可能情况列出来。
先看 \(k=1\)。这时唯一可能的加权和是 \(5\)，对应的 \(5\)-smooth 数只有 \(5=5^1\)。因此这里贡献一个有序数对：\((5,5)\)。
再看 \(k=2\)。此时可能的 \(5\)-smooth 数为
$$2^2=4,\qquad 2\cdot 3=6,\qquad 3^2=9,$$
它们对应的加权和分别是 \(4\)、\(5\)、\(6\)。要让总和等于 \(10\)，只能出现以下三个有序对：
$$ (4,9),\qquad (6,6),\qquad (9,4). $$
其它 \(k\) 值都不会贡献，因此
$$f(10)=1+3=4.$$
这正好与实现里的小规模校验值一致，也能帮助确认递推的组合含义没有偏差。
C++、Python 和 Java 实现都不会在大规模时继续枚举指数三元组。它们改为从左到右构造整个序列。对于每个下标，先放入来自分子多项式的修正项 \(\nu_n\)，再按照分母给出的 13 个滞后位置做加减，最后把结果规约到 \(10^9+7\) 模下。
当前写法会把从 \(0\) 到 \(n\) 的所有序列值都保存下来，因此访问任何滞后项都很直接。其中一个实现还在正式计算前，用直接枚举把前 \(120\) 项做了交叉检查，并验证了 \(f(10)=4\) 与 \(f(100)=3629\) 这两个检查点。
直接按组合定义去算，代价会随着 \(n\) 增大而迅速爆炸，因为要反复遍历大量指数三元组并做卷积。优化后的方法在每个下标上只执行常数次操作：一次读取 \(\nu_n\)，13 次加减，以及一次取模，所以总时间复杂度是 \(O(n)\)。
按当前实现方式，整个序列数组都会被保留，因此空间复杂度是 \(O(n)\)。由于最大的滞后只有 \(32\)，理论上完全可以改成滚动窗口，把空间降到 \(O(1)\)；不过现有实现没有采用这一点。
\(5\)-гладкое число имеет вид \(2^a3^b5^c\), где \(a,b,c\ge 0\). Если обозначить
$$\Omega(2^a3^b5^c)=a+b+c,\qquad \operatorname{sopfr}(2^a3^b5^c)=2a+3b+5c,$$
то используемую в реализации функцию подсчета можно записать как
$$C_k(s)=\#\left\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:\ a+b+c=k,\ 2a+3b+5c=s\right\}.$$
Требуемая последовательность равна
$$f(n)=\sum_{k\ge 0}\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
Иными словами, \(f(n)\) считает упорядоченные пары \(5\)-гладких чисел с одинаковым общим числом простых множителей, причем сумма их взвешенных простых вкладов равна \(n\). Нужно вычислить \(f(10^7)\bmod(10^9+7)\).
Прямое определение полезно для понимания того, что именно считается, но для \(n=10^7\) оно непригодно. Основная идея состоит в том, чтобы заменить двойной комбинаторный подсчет одной рациональной производящей функцией, а затем извлечь из нее разреженную линейную рекуррентность.
Для фиксированного \(k\) введем обычный производящий полином
$$P_k(q)=\sum_{s\ge 0} C_k(s)\,q^s=\sum_{a+b+c=k} q^{2a+3b+5c}.$$
Добавим вторую переменную \(x\), которая отслеживает значение \(k\). Суммирование по всем тройкам дает
$$\sum_{k\ge 0} P_k(q)x^k=\sum_{a,b,c\ge 0} x^{a+b+c}q^{2a+3b+5c}=\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)}.$$
Здесь \(x\) запоминает общее число простых множителей, а \(q\) запоминает взвешенную сумму \(2a+3b+5c\).
Для одного фиксированного \(k\) коэффициент при \(q^n\) в \(P_k(q)^2\) равен
$$\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
Следовательно, производящая функция искомой последовательности равна
$$F(q)=\sum_{n\ge 0} f(n)q^n=\sum_{k\ge 0} P_k(q)^2.$$
Чтобы суммировать квадраты и при этом заставить обе стороны пары иметь одинаковое \(k\), удобно использовать извлечение постоянного члена:
$$F(q)=\mathrm{CT}_x\!\left(\sum_{k\ge 0} P_k(q)x^k\right)\!\left(\sum_{m\ge 0} P_m(q)x^{-m}\right).$$
После подстановки результата из шага 1 получаем
$$F(q)=\mathrm{CT}_x\!\left(\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)(1-q^2/x)(1-q^3/x)(1-q^5/x)}\right).$$
Постоянный член по \(x\) оставляет только те пары, у которых суммарное число показателей совпадает.
При \(|q|<1\) внутри единичной окружности в плоскости \(x\) находятся только полюса \(x=q^2\), \(x=q^3\) и \(x=q^5\). Сумма соответствующих вычетов упрощается до точной формулы
$$F(q)=\frac{1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12}}{1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}}.$$
Это и есть ключевой переломный момент: рациональная производящая функция автоматически означает линейную рекуррентность с постоянными коэффициентами.
Положим
$$N(q)=1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12},$$
$$D(q)=1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}.$$
Из равенства \(D(q)F(q)=N(q)\) по коэффициентам следует
$$\begin{aligned} f(n)=\nu_n&+f(n-1)+f(n-6)-f(n-9)+f(n-10)-f(n-11)-f(n-13)\\ &+f(n-19)+f(n-21)-f(n-22)+f(n-23)-f(n-26)-f(n-31)+f(n-32), \end{aligned}$$
где \(f(m)=0\) для \(m<0\), а \(\nu_n\) задается коэффициентами числителя:
$$\nu_n=\begin{cases} 1, & n\in\{0,4,5,7,8,12\},\\ -1, & n\in\{1,11\},\\ -2, & n=6,\\ 0, & \text{иначе.} \end{cases}$$
Именно эту рекуррентность и реализуют версии на C++, Python и Java, каждый раз выполняя приведение по модулю \(10^9+7\).
При \(n=10\) все еще можно перечислить допустимые случаи вручную.
Если \(k=1\), то возможная взвешенная сумма только одна: \(5\), соответствующая числу \(5=5^1\). Это дает один упорядоченный вклад: \((5,5)\).
Если \(k=2\), то возможные \(5\)-гладкие числа таковы:
$$2^2=4,\qquad 2\cdot 3=6,\qquad 3^2=9,$$
а их взвешенные суммы равны \(4\), \(5\) и \(6\). Чтобы в сумме получить \(10\), подходят только три упорядоченные пары:
$$ (4,9),\qquad (6,6),\qquad (9,4). $$
Другие значения \(k\) не вносят вклада, поэтому
$$f(10)=1+3=4,$$
что совпадает с контрольным значением из реализации.
Реализации на C++, Python и Java не перечисляют тройки показателей при больших \(n\). Вместо этого они строят последовательность слева направо по рекуррентной формуле. На каждом шаге берется корректирующий член \(\nu_n\), затем прибавляются или вычитаются 13 отстоящих назад значений, указанных знаменателем, после чего результат нормализуется по модулю \(10^9+7\).
В текущем виде реализации сохраняют все значения от \(0\) до \(n\), поэтому доступ к любому нужному лагу выполняется мгновенно. Одна из версий дополнительно сверяет первые члены с прямым перебором до \(120\) и проверяет точки \(f(10)=4\) и \(f(100)=3629\), прежде чем выводить окончательный ответ.
Прямое комбинаторное определение слишком дорого для \(n=10^7\), поскольку в нем многократно перебираются одни и те же тройки показателей и свертки. Оптимизированный метод выполняет для каждого индекса только постоянное число операций: одно чтение \(\nu_n\), 13 сложений или вычитаний и одно взятие по модулю. Следовательно, время работы равно \(O(n)\).
В существующих реализациях хранится весь массив последовательности, поэтому расход памяти составляет \(O(n)\). Поскольку максимальный лаг равен \(32\), ту же рекуррентность можно было бы реализовать кольцевым буфером с \(O(1)\) памятью, но здесь это не сделано.
العدد \(5\)-smooth يكتب على الصورة \(2^a3^b5^c\) حيث \(a,b,c\ge 0\). وإذا كتبنا
$$\Omega(2^a3^b5^c)=a+b+c,\qquad \operatorname{sopfr}(2^a3^b5^c)=2a+3b+5c,$$
فإن دالة العد التي تعتمدها الحلول يمكن صياغتها عبر
$$C_k(s)=\#\left\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:\ a+b+c=k,\ 2a+3b+5c=s\right\}.$$
والمتتالية المطلوبة هي
$$f(n)=\sum_{k\ge 0}\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
أي أن \(f(n)\) تعد الأزواج المرتبة من الأعداد \(5\)-smooth التي لها العدد الكلي نفسه من العوامل الأولية، بحيث يكون مجموع الأوزان الأولية في الطرفين مساويًا لـ \(n\). المطلوب هو حساب \(f(10^7)\bmod(10^9+7)\).
التعريف المباشر يوضح معنى المتتالية، لكنه غير عملي إطلاقًا عند \(n=10^7\). الفكرة الحاسمة هي تحويل هذا العد المزدوج إلى دالة توليد كسرية واحدة، ثم استخراج علاقة عودية خطية متناثرة الحدود من تلك الدالة.
عند تثبيت \(k\)، نعرف كثير الحدود المولد العادي
$$P_k(q)=\sum_{s\ge 0} C_k(s)\,q^s=\sum_{a+b+c=k} q^{2a+3b+5c}.$$
ثم ندخل متغيرًا ثانيًا \(x\) ليتتبع قيمة \(k\). عند الجمع على جميع الثلاثيات غير السالبة نحصل على
$$\sum_{k\ge 0} P_k(q)x^k=\sum_{a,b,c\ge 0} x^{a+b+c}q^{2a+3b+5c}=\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)}.$$
هذا الترميز يلتقط كل ثلاثية أسس مسموح بها دفعة واحدة: \(x\) يسجل عدد العوامل الأولية الكلي، و\(q\) يسجل الوزن \(2a+3b+5c\).
لـ \(k\) ثابت، فإن معامل \(q^n\) في \(P_k(q)^2\) يساوي بالضبط
$$\sum_{s=0}^{n} C_k(s)\,C_k(n-s).$$
ومن ثم تكون دالة التوليد للمتتالية المطلوبة
$$F(q)=\sum_{n\ge 0} f(n)q^n=\sum_{k\ge 0} P_k(q)^2.$$
لكننا نحتاج إلى ضمان أن الطرفين في الزوج يستخدمان القيمة نفسها من \(k\). لهذا نستخدم استخراج الحد الثابت:
$$F(q)=\mathrm{CT}_x\!\left(\sum_{k\ge 0} P_k(q)x^k\right)\!\left(\sum_{m\ge 0} P_m(q)x^{-m}\right).$$
وبالتعويض من الخطوة الأولى نحصل على
$$F(q)=\mathrm{CT}_x\!\left(\frac{1}{(1-xq^2)(1-xq^3)(1-xq^5)(1-q^2/x)(1-q^3/x)(1-q^5/x)}\right).$$
وجود \(x^0\) هو الذي يبقي فقط الحدود التي تتطابق فيها القيمة الكلية للأسس على الجانبين.
عندما يكون \(|q|<1\)، فإن الأقطاب الواقعة داخل دائرة الوحدة في مستوى \(x\) هي فقط \(x=q^2\) و\(x=q^3\) و\(x=q^5\). بجمع البواقي عند هذه الأقطاب الثلاثة نحصل بعد التبسيط على
$$F(q)=\frac{1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12}}{1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}}.$$
هذه هي النقطة المفصلية في الحل. ما دام \(F(q)\) دالة كسرية، فهذا يعني مباشرة أن \(f(n)\) تحقق علاقة عودية خطية بمعاملات ثابتة.
لنكتب
$$N(q)=1-q+q^4+q^5-2q^6+q^7+q^8-q^{11}+q^{12},$$
$$D(q)=1-q-q^6+q^9-q^{10}+q^{11}+q^{13}-q^{19}-q^{21}+q^{22}-q^{23}+q^{26}+q^{31}-q^{32}.$$
من العلاقة \(D(q)F(q)=N(q)\) ومقارنة المعاملات نستنتج
$$\begin{aligned} f(n)=\nu_n&+f(n-1)+f(n-6)-f(n-9)+f(n-10)-f(n-11)-f(n-13)\\ &+f(n-19)+f(n-21)-f(n-22)+f(n-23)-f(n-26)-f(n-31)+f(n-32), \end{aligned}$$
مع الاتفاق على أن \(f(m)=0\) لكل \(m<0\)، وأن \(\nu_n\) تأتي من كثير الحدود البسط:
$$\nu_n=\begin{cases} 1, & n\in\{0,4,5,7,8,12\},\\ -1, & n\in\{1,11\},\\ -2, & n=6,\\ 0, & \text{otherwise.} \end{cases}$$
هذه هي العلاقة نفسها التي تنفذها الحلول بلغة C++ وPython وJava، مع الاختزال المستمر modulo \(10^9+7\).
عند \(n=10\) يمكن فحص الحالات يدويًا.
إذا كان \(k=1\)، فإن الوزن الممكن الوحيد هو \(5\)، الموافق للعدد \(5=5^1\). وهذا يعطي زوجًا مرتبًا واحدًا فقط هو \((5,5)\).
أما إذا كان \(k=2\)، فالأعداد \(5\)-smooth الممكنة هي
$$2^2=4,\qquad 2\cdot 3=6,\qquad 3^2=9,$$
وأوزانها هي \(4\) و\(5\) و\(6\) على الترتيب. لكي يكون المجموع \(10\)، فإن الأزواج المرتبة الممكنة هي
$$ (4,9),\qquad (6,6),\qquad (9,4). $$
ولا توجد مساهمات من قيم أخرى لـ \(k\)، ومن ثم
$$f(10)=1+3=4,$$
وهو تمامًا نفس مقدار التحقق الصغير المستخدم في التنفيذ.
تنفيذات C++ وPython وJava لا تعود إلى تعداد ثلاثيات الأسس عندما يصبح \(n\) كبيرًا. بدلًا من ذلك، تبني المتتالية من اليسار إلى اليمين اعتمادًا على العلاقة العودية السابقة. عند كل فهرس تبدأ من الحد التصحيحي \(\nu_n\)، ثم تضيف أو تطرح القيم المؤخرة الثلاث عشرة التي يحددها المقام، وبعد ذلك تطبع النتيجة ضمن modulo \(10^9+7\).
في صورتها الحالية، تحتفظ التنفيذات بكل قيم المتتالية من \(0\) حتى \(n\)، لذلك يكون الوصول إلى أي حد متأخر مباشرًا. كما أن أحد التنفيذات يجري فحصًا صغيرًا بالمقارنة مع تعداد مباشر حتى \(120\)، ويتحقق من القيمتين \(f(10)=4\) و\(f(100)=3629\) قبل حساب الناتج النهائي.
التعريف التوافقي المباشر مكلف جدًا عند \(n=10^7\)، لأنه يعيد استكشاف عدد كبير من ثلاثيات الأسس والالتفافات مرات كثيرة. أما الطريقة المحسنة فتنجز عددًا ثابتًا من العمليات لكل فهرس: قراءة واحدة لـ \(\nu_n\)، وثلاث عشرة عملية جمع أو طرح، وعملية أخذ باقي واحدة. لذلك يكون الزمن الكلي \(O(n)\).
وبما أن التنفيذات الحالية تخزن كامل المصفوفة، فإن الذاكرة المستعملة هي \(O(n)\). ولأن أكبر إزاحة في العلاقة هي \(32\)، فمن الممكن تنفيذ العلاقة نفسها بنافذة دائرية وبذاكرة \(O(1)\)، لكن هذا التحسين غير مستخدم هنا.