For fixed integers \(N\) and \(K\), the task is to count all factorisations whose product is at most \(N\) and whose total length is at most \(K\), with the factors written in nondecreasing order. Factors equal to \(1\) are allowed, so each factorisation consists of some leading ones followed by a nondecreasing block of factors at least \(2\). The final total is taken modulo \(10^9+7\).
It is useful to separate the trivial factors \(1\) from the genuinely multiplicative part. For integers \(L \ge 1\), \(m \ge 2\), and \(p \ge 0\), define
$$C(L,m,p)=\#\left\{(a_1,\dots,a_p)\in \mathbb{Z}_{\ge 2}^p : m \le a_1 \le \cdots \le a_p,\ \prod_{i=1}^{p} a_i \le L\right\}.$$
When \(m=2\), this counts the core factorisations with exactly \(p\) nontrivial factors.
Every nontrivial factor is at least \(2\). Therefore any factorisation with \(p\) such factors has product at least \(2^p\). If \(2^p>N\), no such factorisation can contribute.
Hence the largest relevant value of \(p\) is
$$P=\left\lfloor \log_2 N \right\rfloor.$$
This explains why the implementations only need to compute counts up to that depth.
Fix \(p \ge 2\), and choose the first factor \(a_1=x\). Because the sequence is nondecreasing, every remaining factor is at least \(x\). Thus the remaining product is at least \(x^{p-1}\), and the whole product is at least \(x^p\). So we must have
$$x^p \le L,$$
which gives the sharp upper bound
$$x \le \left\lfloor L^{1/p} \right\rfloor.$$
After fixing \(x\), the remaining \(p-1\) factors must still be nondecreasing, each at least \(x\), and their product must be at most \(\lfloor L/x \rfloor\). Therefore
$$C(L,m,p)=\sum_{x=m}^{\left\lfloor L^{1/p} \right\rfloor} C\!\left(\left\lfloor \frac{L}{x} \right\rfloor, x, p-1\right).$$
The base cases are immediate:
$$C(L,m,0)=1,$$
because the empty tail contributes one valid completion, and
$$C(L,m,1)=\max\!\bigl(0,\,L-m+1\bigr),$$
because a single remaining factor can be any integer from \(m\) up to \(L\).
The condition \(m \le a_1 \le \cdots \le a_p\) fixes a canonical order, so no permutation duplicates appear. Every valid core factorisation has one and only one first factor \(x\), and once \(x\) is chosen, the rest of the sequence is described by the smaller problem with limit \(\lfloor L/x \rfloor\), lower bound \(x\), and one fewer position.
Thus the recursion is exact, not heuristic. Two different branches cannot represent the same factorisation, and every valid factorisation belongs to one branch.
Let
$$A_p=C(N,2,p)$$
for \(1 \le p \le P\). This counts the nondecreasing factorizations whose nontrivial part has exactly \(p\) factors, all at least \(2\).
If such a core factorisation has length \(p\), then for any total length \(t\) with \(p \le t \le K\), it extends uniquely to
$$(\underbrace{1,\dots,1}_{t-p\text{ times}},a_1,\dots,a_p),$$
because in nondecreasing order all ones must appear at the front. Therefore each core factorisation contributes exactly
$$K-p+1$$
times to the final answer.
There is also the purely trivial family consisting only of ones. For each length \(t=1,2,\dots,K\), the factorisation \((1,\dots,1)\) has product \(1\le N\), so these contribute another \(K\) in total.
Combining the previous steps gives
$$D(N,K)=K+\sum_{p=1}^{\min(P,K)} A_p\,(K-p+1)\pmod{10^9+7},$$
where \(P=\lfloor \log_2 N \rfloor\) and \(A_p=C(N,2,p)\). This is exactly the quantity accumulated by the implementations.
Here \(P=\lfloor \log_2 10 \rfloor=3\), because \(2^3 \le 10 \lt 2^4\).
For \(p=1\), the nontrivial core factorisations are simply \((2),(3),\dots,(10)\), so
$$A_1=9.$$
For \(p=2\), the valid nondecreasing pairs are
$$ (2,2),\ (2,3),\ (2,4),\ (2,5),\ (3,3), $$
so
$$A_2=5.$$
For \(p=3\), only
$$ (2,2,2) $$
works, hence
$$A_3=1.$$
No longer core factorisation is possible. Therefore
$$D(10,10)=10 + 9 \cdot 10 + 5 \cdot 9 + 1 \cdot 8 = 153,$$
which matches the built-in checkpoint.
The C++, Python, and Java implementations first determine the maximum relevant depth \(P\) by repeatedly doubling until the product would exceed \(N\). They then evaluate \(C(N,2,p)\) for each \(p=1,2,\dots,P\) using the same memoized recursion described above.
Each cached state is determined by three mathematical parameters: the remaining product limit, the minimum allowed next factor, and the number of factors still to place. An exact integer \(p\)-th root is used to compute \(\lfloor L^{1/p} \rfloor\) safely, so the loop bounds remain correct even near perfect powers.
After all core counts are known, the implementation adds the \(K\) all-one factorizations, applies the multiplicity \(K-p+1\) to each core count, and performs every arithmetic step modulo \(10^9+7\).
Let \(\mathcal{S}\) be the set of distinct states reached by the memoized recursion. A state with parameters \((L,m,p)\) performs
$$\max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)$$
transitions. Therefore the total running time is
$$O\!\left(\sum_{(L,m,p)\in\mathcal{S}} \max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)\right).$$
The recursion depth is at most \(\lfloor \log_2 N \rfloor\), because every nontrivial factor is at least \(2\). Memory usage is \(O(|\mathcal{S}|)\) for the memo table. In practice, many branches collapse to the same subproblem, so memoization removes a large amount of repeated work.
Für feste ganze Zahlen \(N\) und \(K\) sollen alle Faktorisierungen gezählt werden, deren Produkt höchstens \(N\) ist und deren Gesamtlänge höchstens \(K\) beträgt, wobei die Faktoren in nichtabsteigender Reihenfolge geschrieben werden. Faktoren gleich \(1\) sind erlaubt. Jede Faktorisierung besteht also aus einigen führenden Einsen und danach aus einem nichtabsteigenden Block von Faktoren mindestens \(2\). Das Ergebnis wird modulo \(10^9+7\) genommen.
Es ist sinnvoll, die trivialen Faktoren \(1\) vom eigentlichen multiplikativen Kern zu trennen. Für ganze Zahlen \(L \ge 1\), \(m \ge 2\) und \(p \ge 0\) definieren wir
$$C(L,m,p)=\#\left\{(a_1,\dots,a_p)\in \mathbb{Z}_{\ge 2}^p : m \le a_1 \le \cdots \le a_p,\ \prod_{i=1}^{p} a_i \le L\right\}.$$
Für \(m=2\) zählt diese Funktion genau die Kernfaktorisierungen mit exakt \(p\) nichttrivialen Faktoren.
Jeder nichttriviale Faktor ist mindestens \(2\). Deshalb hat jede Faktorisierung mit \(p\) solchen Faktoren Produkt mindestens \(2^p\). Falls \(2^p>N\), kann es keinen Beitrag geben.
Die größte relevante Tiefe ist also
$$P=\left\lfloor \log_2 N \right\rfloor.$$
Darum berechnen die Implementierungen nur Werte bis zu dieser Grenze.
Fixiere \(p \ge 2\) und wähle den ersten Faktor \(a_1=x\). Wegen der nichtabsteigenden Reihenfolge sind alle restlichen Faktoren ebenfalls mindestens \(x\). Damit ist das Restprodukt mindestens \(x^{p-1}\), also das Gesamtprodukt mindestens \(x^p\). Folglich muss gelten
$$x^p \le L,$$
also
$$x \le \left\lfloor L^{1/p} \right\rfloor.$$
Ist \(x\) fest gewählt, dann müssen die verbleibenden \(p-1\) Faktoren weiter nichtabsteigend sein, alle mindestens \(x\), und ihr Produkt darf höchstens \(\lfloor L/x \rfloor\) sein. Daher gilt
$$C(L,m,p)=\sum_{x=m}^{\left\lfloor L^{1/p} \right\rfloor} C\!\left(\left\lfloor \frac{L}{x} \right\rfloor, x, p-1\right).$$
Die Basisfälle sind unmittelbar:
$$C(L,m,0)=1,$$
weil der leere Rest genau eine gültige Fortsetzung liefert, und
$$C(L,m,1)=\max\!\bigl(0,\,L-m+1\bigr),$$
weil ein letzter Faktor jede ganze Zahl von \(m\) bis \(L\) sein kann.
Die Bedingung \(m \le a_1 \le \cdots \le a_p\) fixiert eine kanonische Ordnung, also entstehen keine Mehrfachzählungen durch Permutationen. Jede gültige Kernfaktorisierung besitzt genau einen ersten Faktor \(x\). Nach der Wahl von \(x\) wird der Rest durch das kleinere Teilproblem mit Grenze \(\lfloor L/x \rfloor\), Untergrenze \(x\) und einer Position weniger beschrieben.
Die Rekursion ist deshalb exakt. Zwei verschiedene Äste können niemals dieselbe Faktorisierung repräsentieren, und jede zulässige Faktorisierung liegt in genau einem Ast.
Setze
$$A_p=C(N,2,p)$$
für \(1 \le p \le P\). Das ist die Zahl der nichtabsteigenden Faktorisierungen, deren nichttrivialer Kern genau \(p\) Faktoren besitzt.
Hat eine solche Kernfaktorisierung Länge \(p\), dann gibt es für jede Gesamtlänge \(t\) mit \(p \le t \le K\) genau eine Erweiterung
$$ (\underbrace{1,\dots,1}_{t-p\text{ mal}},a_1,\dots,a_p). $$
In nichtabsteigender Reihenfolge müssen alle Einsen vorne stehen. Daher trägt jede Kernfaktorisierung genau
$$K-p+1$$
zum Gesamtergebnis bei.
Zusätzlich gibt es die rein triviale Familie, die nur aus Einsen besteht. Für jede Länge \(t=1,2,\dots,K\) ist \((1,\dots,1)\) zulässig, also kommen insgesamt noch \(K\) Beiträge hinzu.
Aus den vorherigen Schritten folgt
$$D(N,K)=K+\sum_{p=1}^{\min(P,K)} A_p\,(K-p+1)\pmod{10^9+7},$$
wobei \(P=\lfloor \log_2 N \rfloor\) und \(A_p=C(N,2,p)\). Genau diese Summe wird von den Implementierungen aufgebaut.
Hier ist \(P=\lfloor \log_2 10 \rfloor=3\), denn \(2^3 \le 10 \lt 2^4\).
Für \(p=1\) sind die Kernfaktorisierungen einfach \((2),(3),\dots,(10)\), also
$$A_1=9.$$
Für \(p=2\) lauten die zulässigen nichtabsteigenden Paare
$$ (2,2),\ (2,3),\ (2,4),\ (2,5),\ (3,3), $$
somit
$$A_2=5.$$
Für \(p=3\) funktioniert nur
$$ (2,2,2), $$
daher
$$A_3=1.$$
Längere Kernfaktorisierungen sind unmöglich. Also ergibt sich
$$D(10,10)=10 + 9 \cdot 10 + 5 \cdot 9 + 1 \cdot 8 = 153,$$
genau der Kontrollwert aus der Implementierung.
Die C++, Python- und Java-Implementierungen bestimmen zuerst die maximale relevante Tiefe \(P\), indem sie wiederholt verdoppeln, bis das Produkt \(N\) überschreiten würde. Anschließend berechnen sie \(C(N,2,p)\) für alle \(p=1,2,\dots,P\) mit derselben memoisierten Rekursion wie oben.
Jeder Cache-Eintrag wird durch drei mathematische Parameter festgelegt: die verbleibende Produktgrenze, die minimale zulässige nächste Zahl und die Anzahl der noch zu platzierenden Faktoren. Ein exakter ganzzahliger \(p\)-ter Wurzelwert liefert \(\lfloor L^{1/p} \rfloor\), damit die Schleifengrenzen auch in der Nähe perfekter Potenzen korrekt bleiben.
Wenn alle Kernzahlen vorliegen, addiert die Implementierung die \(K\) All-Eins-Faktorisierungen, gewichtet jede Kernzahl mit \(K-p+1\) und reduziert jeden Rechenschritt modulo \(10^9+7\).
Sei \(\mathcal{S}\) die Menge aller verschiedenen Zustände der memoisierten Rekursion. Ein Zustand mit Parametern \((L,m,p)\) führt
$$\max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)$$
Übergänge aus. Damit ist die Gesamtlaufzeit
$$O\!\left(\sum_{(L,m,p)\in\mathcal{S}} \max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)\right).$$
Die Rekursionstiefe ist höchstens \(\lfloor \log_2 N \rfloor\), weil jeder nichttriviale Faktor mindestens \(2\) ist. Der Speicherverbrauch beträgt \(O(|\mathcal{S}|)\) für die Memo-Tabelle. In der Praxis fallen viele Äste auf dasselbe Teilproblem zusammen, wodurch die Memoisierung sehr viele Wiederholungen vermeidet.
Sabit \(N\) ve \(K\) için, çarpımı en fazla \(N\) olan ve toplam uzunluğu en fazla \(K\) olan tüm çarpanlaşmaları saymamız gerekir. Çarpanlar azalmayan sırada yazılır. \(1\) değerine izin verildiği için her çarpanlaşma, başta gelen bazı birlerden ve ardından tüm çarpanları en az \(2\) olan azalmayan bir çekirdek bloktan oluşur. Sonuç \(10^9+7\) modunda alınır.
Önce trivial olan \(1\) çarpanlarını gerçek çarpımsal çekirdekten ayırmak faydalıdır. \(L \ge 1\), \(m \ge 2\) ve \(p \ge 0\) için
$$C(L,m,p)=\#\left\{(a_1,\dots,a_p)\in \mathbb{Z}_{\ge 2}^p : m \le a_1 \le \cdots \le a_p,\ \prod_{i=1}^{p} a_i \le L\right\}$$
tanımını yapalım. \(m=2\) olduğunda bu fonksiyon, tam olarak \(p\) tane trivial olmayan çarpanı olan çekirdek çarpanlaşmaları sayar.
Her trivial olmayan çarpan en az \(2\) olduğundan, bu tür \(p\) çarpan içeren her çarpanlaşmanın çarpımı en az \(2^p\) olur. Eğer \(2^p>N\) ise böyle bir yapı mümkün değildir.
Bu yüzden anlamlı en büyük derinlik
$$P=\left\lfloor \log_2 N \right\rfloor$$
olur. Uygulamalar yalnızca bu sınıra kadar sayım yapar.
\(p \ge 2\) için ilk çarpanı \(a_1=x\) olarak seçelim. Dizi azalmayan olduğundan geride kalan tüm çarpanlar da en az \(x\) olmalıdır. Bu durumda kalan kısmın çarpımı en az \(x^{p-1}\), tüm dizinin çarpımı ise en az \(x^p\) olur. Dolayısıyla
$$x^p \le L$$
olmalıdır ve buradan
$$x \le \left\lfloor L^{1/p} \right\rfloor$$
üst sınırı gelir. \(x\) sabitlendiğinde, geride kalan \(p-1\) çarpan yine azalmayan sırada olmalı, her biri en az \(x\) olmalı ve çarpımları en fazla \(\lfloor L/x \rfloor\) olmalıdır. Bu nedenle
$$C(L,m,p)=\sum_{x=m}^{\left\lfloor L^{1/p} \right\rfloor} C\!\left(\left\lfloor \frac{L}{x} \right\rfloor, x, p-1\right)$$
elde edilir. Taban durumları da doğrudandır:
$$C(L,m,0)=1,$$
çünkü boş kuyruk tek bir geçerli tamamlama verir, ve
$$C(L,m,1)=\max\!\bigl(0,\,L-m+1\bigr),$$
çünkü son kalan çarpan \(m\) ile \(L\) arasındaki herhangi bir tam sayı olabilir.
\(m \le a_1 \le \cdots \le a_p\) koşulu kanonik bir sıra sabitler; dolayısıyla permütasyonlardan kaynaklanan tekrar sayım yoktur. Her geçerli çekirdek çarpanlaşmanın tek bir ilk çarpanı \(x\) vardır. \(x\) seçildiğinde geri kalan kısım, sınırı \(\lfloor L/x \rfloor\), alt limiti \(x\) ve uzunluğu bir eksik olan daha küçük alt probleme dönüşür.
Bu yüzden özyineleme tamdır. İki farklı dal aynı çarpanlaşmayı temsil edemez ve her geçerli çarpanlaşma tek bir dalda yer alır.
$$A_p=C(N,2,p)$$
olsun. Bu, trivial olmayan kısmı tam \(p\) çarpandan oluşan azalmayan çekirdek çarpanlaşmaların sayısıdır.
Böyle bir çekirdeğin uzunluğu \(p\) ise, toplam uzunluk \(t\) için \(p \le t \le K\) aralığında tek bir genişleme vardır:
$$ (\underbrace{1,\dots,1}_{t-p\text{ adet}},a_1,\dots,a_p). $$
Azalmayan sırada bütün birler başta durmak zorundadır. Bu yüzden her çekirdek çarpanlaşmanın toplam katkısı
$$K-p+1$$
olur.
Ayrıca yalnızca birlerden oluşan tamamen trivial aile de vardır. \(t=1,2,\dots,K\) için \((1,\dots,1)\) çarpımı \(1\le N\) verdiğinden bunlar toplamda ek olarak \(K\) katkı yapar.
Önceki adımlar birleşince
$$D(N,K)=K+\sum_{p=1}^{\min(P,K)} A_p\,(K-p+1)\pmod{10^9+7}$$
sonucuna ulaşırız. Burada \(P=\lfloor \log_2 N \rfloor\) ve \(A_p=C(N,2,p)\) dir. Uygulamaların topladığı büyüklük tam olarak budur.
Bu durumda \(P=\lfloor \log_2 10 \rfloor=3\), çünkü \(2^3 \le 10 \lt 2^4\).
\(p=1\) için çekirdek çarpanlaşmalar \((2),(3),\dots,(10)\) olduğundan
$$A_1=9.$$
\(p=2\) için geçerli azalmayan çiftler
$$ (2,2),\ (2,3),\ (2,4),\ (2,5),\ (3,3) $$
olduğu için
$$A_2=5.$$
\(p=3\) için yalnızca
$$ (2,2,2) $$
mümkündür, dolayısıyla
$$A_3=1.$$
Daha uzun çekirdek mümkün değildir. Böylece
$$D(10,10)=10 + 9 \cdot 10 + 5 \cdot 9 + 1 \cdot 8 = 153,$$
elde edilir; bu da doğrulama değeriyle aynıdır.
C++, Python ve Java uygulamaları önce tekrarlı ikiyle çarpma yoluyla en büyük anlamlı derinlik \(P\)'yi bulur. Sonra yukarıdaki memoize edilmiş özyinelemeyi kullanarak \(p=1,2,\dots,P\) için \(C(N,2,p)\) değerlerini hesaplar.
Önbellekteki her durum üç matematiksel büyüklükle belirlenir: elde kalan çarpım sınırı, sıradaki çarpan için geçerli en küçük değer ve yerleştirilecek çarpan sayısı. Döngü üst sınırı olan \(\lfloor L^{1/p} \rfloor\) değeri tam bir tamsayı \(p\) inci dereceden kök hesabıyla bulunur; böylece mükemmel kuvvetlerin yakınında sınır hatası oluşmaz.
Bütün çekirdek sayımlar hazır olduğunda uygulama \(K\) tane tamamen birlerden oluşan durumu ekler, her çekirdek sayımı \(K-p+1\) ile çarpar ve tüm aritmetiği \(10^9+7\) modunda yürütür.
\(\mathcal{S}\), memoize edilmiş özyinelemede ulaşılan farklı durumların kümesi olsun. \((L,m,p)\) parametreli bir durum
$$\max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)$$
adet geçiş üretir. Bu nedenle toplam çalışma süresi
$$O\!\left(\sum_{(L,m,p)\in\mathcal{S}} \max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)\right)$$
şeklindedir. Özyineleme derinliği en fazla \(\lfloor \log_2 N \rfloor\) olur, çünkü her trivial olmayan çarpan en az \(2\)'dir. Bellek kullanımı memo tablosu için \(O(|\mathcal{S}|)\) kadardır. Pratikte birçok dal aynı alt probleme düştüğü için memoization büyük miktarda tekrar işi ortadan kaldırır.
Para enteros fijos \(N\) y \(K\), hay que contar todas las factorizaciones cuyo producto no supera \(N\) y cuya longitud total no supera \(K\), escribiendo los factores en orden no decreciente. Se permiten factores iguales a \(1\), de modo que cada factorización se compone de algunas unidades al principio y luego un bloque no decreciente de factores al menos \(2\). El resultado final se toma módulo \(10^9+7\).
Conviene separar los factores triviales \(1\) del núcleo multiplicativo real. Para enteros \(L \ge 1\), \(m \ge 2\) y \(p \ge 0\), definimos
$$C(L,m,p)=\#\left\{(a_1,\dots,a_p)\in \mathbb{Z}_{\ge 2}^p : m \le a_1 \le \cdots \le a_p,\ \prod_{i=1}^{p} a_i \le L\right\}.$$
Cuando \(m=2\), esta función cuenta exactamente las factorizaciones núcleo con \(p\) factores no triviales.
Cada factor no trivial es al menos \(2\). Por tanto, cualquier factorización con \(p\) factores de ese tipo tiene producto al menos \(2^p\). Si \(2^p>N\), tal factorización no puede existir.
El mayor valor relevante de \(p\) es entonces
$$P=\left\lfloor \log_2 N \right\rfloor.$$
Por eso las implementaciones solo necesitan calcular recuentos hasta esa profundidad.
Fijemos \(p \ge 2\) y elijamos el primer factor \(a_1=x\). Como la secuencia es no decreciente, todos los factores restantes son al menos \(x\). El producto restante es entonces al menos \(x^{p-1}\), y el producto total al menos \(x^p\). Debe cumplirse
$$x^p \le L,$$
de donde sale la cota exacta
$$x \le \left\lfloor L^{1/p} \right\rfloor.$$
Una vez fijado \(x\), los \(p-1\) factores restantes siguen siendo no decrecientes, todos al menos \(x\), y su producto debe ser como máximo \(\lfloor L/x \rfloor\). Por tanto,
$$C(L,m,p)=\sum_{x=m}^{\left\lfloor L^{1/p} \right\rfloor} C\!\left(\left\lfloor \frac{L}{x} \right\rfloor, x, p-1\right).$$
Los casos base son inmediatos:
$$C(L,m,0)=1,$$
porque la cola vacía aporta una única continuación válida, y
$$C(L,m,1)=\max\!\bigl(0,\,L-m+1\bigr),$$
porque el único factor restante puede ser cualquier entero entre \(m\) y \(L\).
La condición \(m \le a_1 \le \cdots \le a_p\) fija un orden canónico, así que no aparecen duplicados por permutación. Toda factorización núcleo válida tiene un único primer factor \(x\), y tras elegirlo el resto queda descrito por el subproblema con límite \(\lfloor L/x \rfloor\), mínimo permitido \(x\) y una posición menos.
La recurrencia, por tanto, es exacta. Dos ramas distintas no pueden representar la misma factorización, y toda factorización válida aparece en una única rama.
Sea
$$A_p=C(N,2,p)$$
para \(1 \le p \le P\). Esto cuenta las factorizaciones no decrecientes cuyo núcleo no trivial tiene exactamente \(p\) factores.
Si un núcleo tiene longitud \(p\), entonces para cada longitud total \(t\) con \(p \le t \le K\) existe una única extensión
$$ (\underbrace{1,\dots,1}_{t-p\text{ veces}},a_1,\dots,a_p). $$
En orden no decreciente, todas las unidades deben ir al principio. Por eso cada núcleo aporta exactamente
$$K-p+1$$
veces al total final.
Además existe la familia puramente trivial formada solo por unidades. Para cada longitud \(t=1,2,\dots,K\), la factorización \((1,\dots,1)\) tiene producto \(1\le N\), así que aporta en total otros \(K\).
Uniendo todo, obtenemos
$$D(N,K)=K+\sum_{p=1}^{\min(P,K)} A_p\,(K-p+1)\pmod{10^9+7},$$
donde \(P=\lfloor \log_2 N \rfloor\) y \(A_p=C(N,2,p)\). Esta es exactamente la cantidad que acumulan las implementaciones.
Aquí \(P=\lfloor \log_2 10 \rfloor=3\), porque \(2^3 \le 10 \lt 2^4\).
Para \(p=1\), las factorizaciones núcleo son \((2),(3),\dots,(10)\), así que
$$A_1=9.$$
Para \(p=2\), los pares válidos no decrecientes son
$$ (2,2),\ (2,3),\ (2,4),\ (2,5),\ (3,3), $$
y por tanto
$$A_2=5.$$
Para \(p=3\), solo sirve
$$ (2,2,2), $$
de modo que
$$A_3=1.$$
No hay núcleos más largos. Entonces
$$D(10,10)=10 + 9 \cdot 10 + 5 \cdot 9 + 1 \cdot 8 = 153,$$
que coincide con el valor de comprobación.
Las implementaciones en C++, Python y Java calculan primero la profundidad máxima relevante \(P\) duplicando repetidamente hasta que el producto superaría \(N\). Después evalúan \(C(N,2,p)\) para cada \(p=1,2,\dots,P\) mediante la misma recurrencia con memoización.
Cada estado almacenado en caché queda determinado por tres parámetros matemáticos: el límite de producto restante, el mínimo permitido para el siguiente factor y la cantidad de factores que faltan por colocar. Para obtener \(\lfloor L^{1/p} \rfloor\) se usa una raíz entera exacta, evitando errores de redondeo cerca de potencias perfectas.
Una vez conocidos todos los recuentos núcleo, la implementación añade las \(K\) factorizaciones formadas solo por unos, aplica el peso \(K-p+1\) a cada \(A_p\) y reduce toda la aritmética módulo \(10^9+7\).
Sea \(\mathcal{S}\) el conjunto de estados distintos alcanzados por la recurrencia con memoización. Un estado con parámetros \((L,m,p)\) realiza
$$\max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)$$
transiciones. Por tanto, el tiempo total es
$$O\!\left(\sum_{(L,m,p)\in\mathcal{S}} \max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)\right).$$
La profundidad de la recursión es como mucho \(\lfloor \log_2 N \rfloor\), porque cada factor no trivial es al menos \(2\). El uso de memoria es \(O(|\mathcal{S}|)\) para la tabla de memoización. En la práctica, muchas ramas terminan en el mismo subproblema y eso reduce mucho el trabajo repetido.
对给定的整数 \(N\) 和 \(K\)，需要统计所有满足“乘积不超过 \(N\)”且“总长度不超过 \(K\)”的因式分解，并且把因子按非降顺序书写。因子 \(1\) 允许出现，因此每个分解都可以唯一地看成“前面若干个 \(1\)”加上“后面一段所有因子都至少为 \(2\) 的非降核心部分”。最终答案对 \(10^9+7\) 取模。
最自然的做法，是先把平凡因子 \(1\) 从真正的乘法核心里剥离出来。对整数 \(L \ge 1\)、\(m \ge 2\)、\(p \ge 0\)，定义
$$C(L,m,p)=\#\left\{(a_1,\dots,a_p)\in \mathbb{Z}_{\ge 2}^p : m \le a_1 \le \cdots \le a_p,\ \prod_{i=1}^{p} a_i \le L\right\}.$$
当 \(m=2\) 时，这个函数统计的正好是“恰好有 \(p\) 个非平凡因子”的核心分解数。
每个非平凡因子都至少是 \(2\)。所以如果一个核心分解有 \(p\) 个这样的因子，那么它的乘积至少是 \(2^p\)。一旦 \(2^p>N\)，这种分解就不可能再出现。
因此真正需要考虑的最大深度是
$$P=\left\lfloor \log_2 N \right\rfloor.$$
这也解释了为什么程序只需要把计数做到这个深度，而不必无限向下递归。
固定 \(p \ge 2\)，先选第一个因子 \(a_1=x\)。由于序列必须非降，所以后面所有因子都至少是 \(x\)。于是剩余 \(p-1\) 个因子的乘积至少为 \(x^{p-1}\)，整个长度为 \(p\) 的序列乘积至少为 \(x^p\)。因此必须满足
$$x^p \le L,$$
也就是
$$x \le \left\lfloor L^{1/p} \right\rfloor.$$
一旦首项 \(x\) 选定，后面 \(p-1\) 个因子仍然要保持非降、每个都不少于 \(x\)，并且它们的乘积上界变成 \(\lfloor L/x \rfloor\)。所以有递推关系
$$C(L,m,p)=\sum_{x=m}^{\left\lfloor L^{1/p} \right\rfloor} C\!\left(\left\lfloor \frac{L}{x} \right\rfloor, x, p-1\right).$$
边界条件也很直接：
$$C(L,m,0)=1,$$
因为空尾部对应唯一一种完成方式；而
$$C(L,m,1)=\max\!\bigl(0,\,L-m+1\bigr),$$
因为只剩最后一个因子时，它可以是从 \(m\) 到 \(L\) 的任意整数。
条件 \(m \le a_1 \le \cdots \le a_p\) 给出了规范顺序，所以同一组因子不会因为排列不同而被重复统计。每个合法核心分解都有唯一的首因子 \(x\)，选定之后，剩余部分就精确对应到一个更小的同类问题：新的乘积上界是 \(\lfloor L/x \rfloor\)，新的最小允许因子是 \(x\)，剩余位置数是 \(p-1\)。
因此这个递推不是近似，而是精确分类。不同分支不可能表示同一个核心分解，而每个核心分解也一定会落入某个分支。
记
$$A_p=C(N,2,p)$$
其中 \(1 \le p \le P\)。它表示非平凡核心恰好有 \(p\) 个因子的非降分解数。
如果某个核心分解长度为 \(p\)，那么对于任意总长度 \(t\)，只要 \(p \le t \le K\)，它都能唯一扩展成
$$ (\underbrace{1,\dots,1}_{t-p\text{ 个}},a_1,\dots,a_p). $$
因为在非降顺序中，所有的 \(1\) 只能放在最前面。于是每个核心分解对最终答案的贡献次数恰好是
$$K-p+1.$$
此外，还有完全平凡的一类，即所有因子都等于 \(1\)。对每个长度 \(t=1,2,\dots,K\)，序列 \((1,\dots,1)\) 的乘积都是 \(1\le N\)，所以这部分总共再贡献 \(K\)。
综合以上各步，有
$$D(N,K)=K+\sum_{p=1}^{\min(P,K)} A_p\,(K-p+1)\pmod{10^9+7},$$
其中 \(P=\lfloor \log_2 N \rfloor\)，且 \(A_p=C(N,2,p)\)。这正是实现中累加的目标量。
这里 \(P=\lfloor \log_2 10 \rfloor=3\)，因为 \(2^3 \le 10 \lt 2^4\)。
当 \(p=1\) 时，核心分解就是 \((2),(3),\dots,(10)\)，所以
$$A_1=9.$$
当 \(p=2\) 时，合法的非降二元组为
$$ (2,2),\ (2,3),\ (2,4),\ (2,5),\ (3,3), $$
因此
$$A_2=5.$$
当 \(p=3\) 时，只有
$$ (2,2,2) $$
满足条件，所以
$$A_3=1.$$
更长的核心分解已经不可能存在。于是
$$D(10,10)=10 + 9 \cdot 10 + 5 \cdot 9 + 1 \cdot 8 = 153,$$
这与程序中的校验值一致。
C++、Python 和 Java 实现都会先通过不断翻倍，求出有意义的最大深度 \(P\)。接着，它们利用上面的记忆化递推，依次计算 \(p=1,2,\dots,P\) 时的 \(C(N,2,p)\)。
每个缓存状态都由三个数学参数唯一决定：当前剩余的乘积上界、下一个因子的最小允许值，以及还需要放置的因子个数。为了安全得到 \(\lfloor L^{1/p} \rfloor\)，实现中使用了精确的整数 \(p\) 次根计算，从而避免在接近完全幂时出现浮点误差导致的边界偏差。
当所有核心计数准备好以后，实现再加上那 \(K\) 个全为 \(1\) 的分解，对每个 \(A_p\) 乘上权重 \(K-p+1\)，并把整个过程始终放在 \(10^9+7\) 模下完成。
设 \(\mathcal{S}\) 是记忆化递推实际访问到的不同状态集合。参数为 \((L,m,p)\) 的一个状态需要进行
$$\max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)$$
次转移。因此总时间可以写成
$$O\!\left(\sum_{(L,m,p)\in\mathcal{S}} \max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)\right).$$
递归深度最多是 \(\lfloor \log_2 N \rfloor\)，因为每个非平凡因子至少为 \(2\)。内存使用为 \(O(|\mathcal{S}|)\)，主要来自记忆化表。实际运行时，很多不同分支会合并到同一个子问题，因此记忆化能显著削减重复计算。
Для фиксированных целых \(N\) и \(K\) нужно посчитать все факторизации, у которых произведение не превосходит \(N\), а общая длина не превосходит \(K\), причём множители записываются в неубывающем порядке. Множители, равные \(1\), разрешены, поэтому каждая факторизация единственным образом раскладывается на несколько ведущих единиц и затем на неубывающую ядровую часть, где все множители не меньше \(2\). Итог берётся по модулю \(10^9+7\).
Удобно сначала отделить тривиальные множители \(1\) от настоящей мультипликативной части. Для целых \(L \ge 1\), \(m \ge 2\) и \(p \ge 0\) определим
$$C(L,m,p)=\#\left\{(a_1,\dots,a_p)\in \mathbb{Z}_{\ge 2}^p : m \le a_1 \le \cdots \le a_p,\ \prod_{i=1}^{p} a_i \le L\right\}.$$
При \(m=2\) эта функция считает ровно те ядровые факторизации, в которых есть ровно \(p\) нетривиальных множителей.
Каждый нетривиальный множитель не меньше \(2\). Значит, любая факторизация с \(p\) такими множителями имеет произведение как минимум \(2^p\). Если \(2^p>N\), таких факторизаций быть не может.
Следовательно, максимально возможная глубина равна
$$P=\left\lfloor \log_2 N \right\rfloor.$$
Именно поэтому реализации считают только до этой глубины.
Зафиксируем \(p \ge 2\) и выберем первый множитель \(a_1=x\). Поскольку последовательность неубывающая, каждый оставшийся множитель тоже не меньше \(x\). Тогда произведение оставшихся \(p-1\) множителей не меньше \(x^{p-1}\), а всё произведение не меньше \(x^p\). Поэтому обязательно
$$x^p \le L,$$
то есть
$$x \le \left\lfloor L^{1/p} \right\rfloor.$$
После фиксации \(x\) оставшиеся \(p-1\) множителей должны по-прежнему образовывать неубывающую последовательность, быть не меньше \(x\) и иметь произведение не больше \(\lfloor L/x \rfloor\). Отсюда
$$C(L,m,p)=\sum_{x=m}^{\left\lfloor L^{1/p} \right\rfloor} C\!\left(\left\lfloor \frac{L}{x} \right\rfloor, x, p-1\right).$$
Базовые случаи очевидны:
$$C(L,m,0)=1,$$
потому что пустой хвост даёт одно допустимое завершение, и
$$C(L,m,1)=\max\!\bigl(0,\,L-m+1\bigr),$$
потому что последний множитель может быть любым целым числом от \(m\) до \(L\).
Условие \(m \le a_1 \le \cdots \le a_p\) задаёт канонический порядок, поэтому перестановки не дают повторного счёта. У каждой допустимой ядровой факторизации есть единственный первый множитель \(x\), а после его выбора остаётся подзадача того же типа, но меньшего размера: предел \(\lfloor L/x \rfloor\), нижняя граница \(x\) и на одну позицию меньше.
Следовательно, рекурсия точна. Разные ветви не могут описывать одну и ту же факторизацию, и каждая допустимая факторизация попадает ровно в одну ветвь.
Положим
$$A_p=C(N,2,p)$$
для \(1 \le p \le P\). Это количество неубывающих факторизаций, у которых нетривиальная часть содержит ровно \(p\) множителей.
Если длина такого ядра равна \(p\), то для любой общей длины \(t\), где \(p \le t \le K\), существует единственное расширение
$$ (\underbrace{1,\dots,1}_{t-p\text{ раз}},a_1,\dots,a_p). $$
В неубывающем порядке все единицы обязаны стоять впереди. Значит, каждая ядровая факторизация вносит в итог ровно
$$K-p+1$$
раз.
Кроме того, есть полностью тривиальное семейство, состоящее только из единиц. Для каждой длины \(t=1,2,\dots,K\) последовательность \((1,\dots,1)\) имеет произведение \(1\le N\), поэтому суммарно это даёт ещё \(K\).
Объединяя всё сказанное, получаем
$$D(N,K)=K+\sum_{p=1}^{\min(P,K)} A_p\,(K-p+1)\pmod{10^9+7},$$
где \(P=\lfloor \log_2 N \rfloor\), а \(A_p=C(N,2,p)\). Именно эту сумму накапливают реализации.
Здесь \(P=\lfloor \log_2 10 \rfloor=3\), потому что \(2^3 \le 10 \lt 2^4\).
При \(p=1\) ядровые факторизации таковы: \((2),(3),\dots,(10)\), поэтому
$$A_1=9.$$
При \(p=2\) допустимые неубывающие пары равны
$$ (2,2),\ (2,3),\ (2,4),\ (2,5),\ (3,3), $$
значит,
$$A_2=5.$$
При \(p=3\) подходит только
$$ (2,2,2), $$
следовательно,
$$A_3=1.$$
Более длинных ядер уже нет. Тогда
$$D(10,10)=10 + 9 \cdot 10 + 5 \cdot 9 + 1 \cdot 8 = 153,$$
что совпадает с контрольным значением.
Реализации на C++, Python и Java сначала находят максимальную полезную глубину \(P\), последовательно удваивая значение, пока произведение не превысит \(N\). Затем они вычисляют \(C(N,2,p)\) для всех \(p=1,2,\dots,P\) с помощью той же мемоизированной рекурсии.
Каждое кэшируемое состояние определяется тремя математическими параметрами: оставшимся пределом произведения, минимально допустимым следующим множителем и числом позиций, которые ещё нужно заполнить. Для вычисления \(\lfloor L^{1/p} \rfloor\) используется точный целочисленный \(p\)-й корень, чтобы избежать ошибок на границе около совершенных степеней.
После получения всех ядровых подсчётов реализация добавляет \(K\) факторизаций, состоящих только из единиц, умножает каждое \(A_p\) на вес \(K-p+1\) и все операции выполняет по модулю \(10^9+7\).
Пусть \(\mathcal{S}\) обозначает множество различных состояний, достигнутых в мемоизированной рекурсии. Состояние с параметрами \((L,m,p)\) выполняет
$$\max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)$$
переходов. Поэтому общее время работы равно
$$O\!\left(\sum_{(L,m,p)\in\mathcal{S}} \max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)\right).$$
Глубина рекурсии не превышает \(\lfloor \log_2 N \rfloor\), поскольку каждый нетривиальный множитель не меньше \(2\). Память составляет \(O(|\mathcal{S}|)\) из-за таблицы мемоизации. На практике многие ветви сводятся к одной и той же подзадаче, поэтому мемоизация резко сокращает количество повторных вычислений.
لدينا عددان صحيحان ثابتان \(N\) و \(K\)، والمطلوب هو عد جميع التفكيكات إلى عوامل التي لا يتجاوز حاصل ضربها \(N\) ولا يتجاوز طولها الكلي \(K\)، مع كتابة العوامل بترتيب غير تنازلي. العوامل التي تساوي \(1\) مسموح بها، ولذلك يمكن كتابة كل تفكيك على صورة عدد من الواحدات في البداية ثم جزء أساسي غير تنازلي تكون جميع عوامله على الأقل \(2\). النتيجة النهائية تؤخذ بترديد \(10^9+7\).
من المفيد فصل العوامل التافهة \(1\) عن الجزء الضربي الحقيقي. للأعداد الصحيحة \(L \ge 1\) و \(m \ge 2\) و \(p \ge 0\) نعرّف
$$C(L,m,p)=\#\left\{(a_1,\dots,a_p)\in \mathbb{Z}_{\ge 2}^p : m \le a_1 \le \cdots \le a_p,\ \prod_{i=1}^{p} a_i \le L\right\}.$$
عندما يكون \(m=2\)، فإن هذه الدالة تعد بالضبط التفكيكات الأساسية التي تحتوي على \(p\) عوامل غير تافهة.
كل عامل غير تافه يساوي على الأقل \(2\). لذلك فإن أي تفكيك يحوي \(p\) من هذه العوامل يملك حاصل ضرب لا يقل عن \(2^p\). فإذا كان \(2^p>N\) فلا يمكن أن يوجد مثل هذا التفكيك.
إذن أكبر عمق نحتاج إلى التعامل معه هو
$$P=\left\lfloor \log_2 N \right\rfloor.$$
ولهذا السبب تكتفي التطبيقات بالحساب حتى هذه القيمة فقط.
لنثبت \(p \ge 2\) ولنختر العامل الأول \(a_1=x\). بما أن الترتيب غير تنازلي، فجميع العوامل المتبقية لا بد أن تكون على الأقل \(x\). وعندئذ يكون حاصل ضرب العوامل المتبقية على الأقل \(x^{p-1}\)، وبالتالي يكون حاصل الضرب الكلي على الأقل \(x^p\). لذلك يجب أن يتحقق
$$x^p \le L,$$
ومن ثم نحصل على الحد الأعلى الدقيق
$$x \le \left\lfloor L^{1/p} \right\rfloor.$$
بعد تثبيت \(x\)، يجب أن تبقى العوامل \(p-1\) التالية غير تنازلية، وكل واحد منها لا يقل عن \(x\)، كما يجب أن لا يتجاوز حاصل ضربها \(\lfloor L/x \rfloor\). لذلك نحصل على
$$C(L,m,p)=\sum_{x=m}^{\left\lfloor L^{1/p} \right\rfloor} C\!\left(\left\lfloor \frac{L}{x} \right\rfloor, x, p-1\right).$$
أما حالتا الأساس فهما مباشرتان:
$$C(L,m,0)=1,$$
لأن الذيل الفارغ يعطي إكمالاً وحيداً صحيحاً، و
$$C(L,m,1)=\max\!\bigl(0,\,L-m+1\bigr),$$
لأن العامل الأخير يمكن أن يكون أي عدد صحيح من \(m\) حتى \(L\).
الشرط \(m \le a_1 \le \cdots \le a_p\) يثبت ترتيباً قانونياً واحداً، ولذلك لا توجد مضاعفات ناتجة عن تبديل العوامل. كل تفكيك أساسي صالح يملك عاملاً أولاً وحيداً هو \(x\)، وبعد اختياره يصبح الباقي مسألة أصغر من النوع نفسه بحد أعلى جديد \(\lfloor L/x \rfloor\)، وحد أدنى جديد \(x\)، وعدد أماكن أقل بمقدار واحد.
إذن العلاقة التراجعية دقيقة تماماً. لا يمكن لفرعين مختلفين أن يمثلا التفكيك نفسه، كما أن كل تفكيك صالح يظهر في فرع وحيد.
لنكتب
$$A_p=C(N,2,p)$$
لـ \(1 \le p \le P\). هذه الكمية تعد التفكيكات غير التنازلية التي يحتوي جزؤها غير التافه على \(p\) عوامل بالضبط.
إذا كان طول هذا الجزء الأساسي يساوي \(p\)، فلكل طول كلي \(t\) يحقق \(p \le t \le K\) يوجد امتداد وحيد على الصورة
$$ (\underbrace{1,\dots,1}_{t-p\text{ مرة}},a_1,\dots,a_p). $$
وبما أن الترتيب غير تنازلي، فلا بد أن تظهر جميع الواحدات في البداية. لذلك فإن كل تفكيك أساسي يساهم بعدد مرات يساوي
$$K-p+1.$$
وهناك أيضاً العائلة التافهة بالكامل، أي التفكيكات التي تتكوّن من واحدات فقط. لكل طول \(t=1,2,\dots,K\) يكون التفكيك \((1,\dots,1)\) ذا حاصل ضرب \(1\le N\)، ولذلك تضيف هذه الحالات \(K\) أخرى إلى الجواب.
بجمع الخطوات السابقة نحصل على
$$D(N,K)=K+\sum_{p=1}^{\min(P,K)} A_p\,(K-p+1)\pmod{10^9+7},$$
حيث \(P=\lfloor \log_2 N \rfloor\) و \(A_p=C(N,2,p)\). هذه هي بالضبط الكمية التي تجمعها التطبيقات.
هنا \(P=\lfloor \log_2 10 \rfloor=3\)، لأن \(2^3 \le 10 \lt 2^4\).
عند \(p=1\)، تكون التفكيكات الأساسية هي \((2),(3),\dots,(10)\)، ومن ثم
$$A_1=9.$$
وعند \(p=2\)، تكون الأزواج غير التنازلية الصالحة هي
$$ (2,2),\ (2,3),\ (2,4),\ (2,5),\ (3,3), $$
ولذلك
$$A_2=5.$$
وعند \(p=3\)، لا يصلح إلا
$$ (2,2,2), $$
ومن ثم
$$A_3=1.$$
ولا توجد تفكيكات أساسية أطول. بالتالي
$$D(10,10)=10 + 9 \cdot 10 + 5 \cdot 9 + 1 \cdot 8 = 153,$$
وهو نفس مقدار التحقق المستخدم في التنفيذ.
تبدأ تطبيقات C++ و Python و Java بحساب أكبر عمق مفيد \(P\) عن طريق المضاعفة المتكررة حتى يصبح تجاوز \(N\) حتمياً. بعد ذلك تحسب \(C(N,2,p)\) لكل \(p=1,2,\dots,P\) باستخدام العلاقة التراجعية نفسها مع التخزين المؤقت.
كل حالة مخزنة في الذاكرة المؤقتة تتحدد بثلاثة معلمات رياضية: حد حاصل الضرب المتبقي، والحد الأدنى المسموح للعامل التالي، وعدد العوامل التي ما زال يجب وضعها. كما تُستخدم دالة جذر صحيح من الرتبة \(p\) لحساب \(\lfloor L^{1/p} \rfloor\) بدقة، وذلك لتجنب أخطاء الحدود الناتجة عن التقريب العشري قرب القوى التامة.
بعد معرفة جميع أعداد التفكيكات الأساسية، يضيف التنفيذ \(K\) حالة الواحدات فقط، ويضرب كل \(A_p\) في الوزن \(K-p+1\)، ويجري جميع العمليات الحسابية بترديد \(10^9+7\).
لتكن \(\mathcal{S}\) مجموعة الحالات المختلفة التي تزورها العلاقة التراجعية مع التخزين المؤقت. الحالة ذات المعلمات \((L,m,p)\) تنفذ
$$\max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)$$
انتقالاً. لذلك يكون الزمن الكلي
$$O\!\left(\sum_{(L,m,p)\in\mathcal{S}} \max\!\left(0,\left\lfloor L^{1/p} \right\rfloor - m + 1\right)\right).$$
أما عمق الاستدعاء التراجعي فلا يزيد على \(\lfloor \log_2 N \rfloor\)، لأن كل عامل غير تافه لا يقل عن \(2\). واستهلاك الذاكرة يساوي \(O(|\mathcal{S}|)\) بسبب جدول التخزين المؤقت. عملياً، تندمج فروع كثيرة في المسألة الفرعية نفسها، ولذلك يزيل التخزين المؤقت قدراً كبيراً من العمل المكرر.