Let \(W(n,k)\) denote the number of ways to write \(n\) as a product of \(k\) distinct positive integers, with order ignored. The target instance in this problem is
$$W(10000!,30)\pmod{10^9+7}.$$
A direct search over divisors or over candidate factor sets is hopelessly large. The implementation therefore works with the prime-exponent vector of \(n\), converts the distinct-factor condition into a generating-function coefficient, and evaluates that coefficient through a sum over integer partitions of \(k\).
Write the prime factorization of \(n\) as
$$n=\prod_p p^{e_p}.$$
For the factorial input \(n=N!\), the exponents are obtained from Legendre's formula:
$$e_p=\sum_{j\ge 1}\left\lfloor\frac{N}{p^j}\right\rfloor.$$
Any factor in a valid decomposition can be written in the form
$$a_i=\prod_p p^{\alpha_{i,p}},\qquad 0\le \alpha_{i,p}\le e_p,$$
and the condition \(a_1a_2\cdots a_k=n\) is equivalent to
$$\alpha_{1,p}+\alpha_{2,p}+\cdots+\alpha_{k,p}=e_p \qquad \text{for every prime } p.$$
For each divisor \(d\mid n\), introduce the monomial
$$m(d)=\prod_p x_p^{v_p(d)}.$$
Now consider the product
$$F(t,\mathbf{x})=\prod_{d\mid n}\left(1+t\,m(d)\right).$$
Selecting the term \(t\,m(d)\) means that the divisor \(d\) is chosen; selecting \(1\) means that it is skipped. Because each divisor appears only once in the product, it can be selected at most once, so the distinctness condition is built in automatically.
The coefficient
$$[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x})$$
therefore counts unordered sets of \(k\) distinct divisors whose product is exactly \(n\). Hence
$$W(n,k)=[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x}).$$
If we denote by \(\mathcal{M}\) the set of all divisor monomials \(m(d)\), then
$$F(t,\mathbf{x})=\sum_{r\ge 0} e_r(\mathcal{M})\,t^r,$$
where \(e_r\) is the \(r\)-th elementary symmetric polynomial. So the problem is to extract the coefficient of \(\prod_p x_p^{e_p}\) inside \(e_k(\mathcal{M})\).
A standard identity expands \(e_k\) in terms of power sums:
$$e_k=\sum_{\lambda\vdash k}\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\,p_\lambda,$$
where \(\lambda=(\lambda_1,\dots,\lambda_r)\) is an integer partition of \(k\), \(\ell(\lambda)=r\), \(p_\lambda=\prod_{i=1}^r p_{\lambda_i}\), and
$$z_\lambda=\prod_v v^{m_v}m_v!.$$
Here \(m_v\) denotes how many times the part value \(v\) occurs in \(\lambda\). This identity is the reason the implementation iterates over partitions of \(k\) instead of over subsets of divisors.
The coefficient attached to \(\lambda\) can be rewritten as
$$\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda} =\left(\prod_{i=1}^r\frac{(-1)^{\lambda_i-1}}{\lambda_i}\right)\left(\prod_v\frac{1}{m_v!}\right).$$
So every partition contributes a rational weight determined by the sizes of its parts and by the multiplicities of repeated parts. In the final modular computation, those divisions are implemented with modular inverses modulo
$$M=10^9+7.$$
This matches the coefficient pattern used by the C++, Python, and Java implementations.
For a positive integer \(j\), the power sum is
$$p_j=\sum_{d\mid n} m(d)^j.$$
Since divisors are described independently prime by prime, this factorizes as
$$p_j=\prod_p \sum_{a=0}^{e_p} x_p^{ja}.$$
Now fix a partition \(\lambda=(\lambda_1,\dots,\lambda_r)\). For a single prime exponent \(e\), the needed one-variable coefficient is
$$d_\lambda(e)=[x^e]\prod_{i=1}^r\frac{1}{1-x^{\lambda_i}}.$$
This is safe because only terms of degree at most \(e\) can contribute to \([x^e]\). Equivalently, \(d_\lambda(e)\) is the number of nonnegative integer solutions of
$$\lambda_1 b_1+\lambda_2 b_2+\cdots+\lambda_r b_r=e.$$
The implementation computes these coefficients with an unbounded-knapsack dynamic program up to the largest exponent that occurs in the factorization of \(n\).
Many primes share the same exponent in \(n\). Let
$$f_e=\#\{p:e_p=e\}.$$
For a fixed partition \(\lambda\), all primes with the same exponent contribute the same coefficient, so the total partition weight becomes
$$S(\lambda)=\prod_e d_\lambda(e)^{f_e}.$$
Therefore the full answer is
$$W(n,k)=\sum_{\lambda\vdash k}\left(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\right)S(\lambda)\pmod{M}.$$
For the target \(n=N!\), the exponent profile \(e_p\) comes from Legendre's formula, and grouping equal values avoids repeating the same DP lookup for many different primes.
Take
$$144=2^4\cdot 3^2.$$
So the exponent multiset is \(\{4,2\}\), which means \(f_2=1\) and \(f_4=1\). The partitions of \(4\) are
$$1+1+1+1,\qquad 2+1+1,\qquad 2+2,\qquad 3+1,\qquad 4.$$
For each partition we evaluate its coefficient and the two needed values \(d_\lambda(2)\) and \(d_\lambda(4)\):
$$\begin{aligned} \lambda=1+1+1+1&:\quad \text{coeff}=\frac{1}{24},\quad d_\lambda(2)=10,\quad d_\lambda(4)=35,\quad \text{term}=\frac{350}{24},\\ \lambda=2+1+1&:\quad \text{coeff}=-\frac{1}{4},\quad d_\lambda(2)=4,\quad d_\lambda(4)=9,\quad \text{term}=-9,\\ \lambda=2+2&:\quad \text{coeff}=\frac{1}{8},\quad d_\lambda(2)=2,\quad d_\lambda(4)=3,\quad \text{term}=\frac{3}{4},\\ \lambda=3+1&:\quad \text{coeff}=\frac{1}{3},\quad d_\lambda(2)=1,\quad d_\lambda(4)=2,\quad \text{term}=\frac{2}{3},\\ \lambda=4&:\quad \text{coeff}=-\frac{1}{4},\quad d_\lambda(2)=0,\quad d_\lambda(4)=1,\quad \text{term}=0. \end{aligned}$$
Summing the five terms gives
$$\frac{350}{24}-9+\frac{3}{4}+\frac{2}{3}=7.$$
So \(W(144,4)=7\), exactly matching the checkpoint used by the implementation.
For the factorial target, the implementation first generates the relevant primes and computes each exponent \(e_p\) by Legendre's formula. It then compresses that data into the frequency table \(f_e\), because only the exponent values and how often they occur matter in the partition formula.
Next, it generates all integer partitions of \(k\). For each partition, it computes the modular version of the coefficient \(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\) using fast exponentiation for modular inverses and precomputed inverse factorials for repeated part multiplicities.
After that, the implementation runs an unbounded-knapsack DP up to the maximum exponent \(E=\max e_p\). The DP value at index \(e\) is precisely \(d_\lambda(e)\), the coefficient of \(x^e\) in \(\prod_i(1-x^{\lambda_i})^{-1}\). Using the frequency table \(f_e\), it multiplies the relevant DP values, raises them to the needed powers, and adds the weighted contribution of the partition to the total.
Because different partitions are independent, the C++, Python, and Java implementations process disjoint partition ranges in parallel and combine the partial sums modulo \(10^9+7\).
Let \(p(k)\) be the number of integer partitions of \(k\), and let \(E=\max_p e_p\). For the factorial input \(n=N!\), generating primes and evaluating Legendre's formula with the straightforward sieve-based approach costs \(O(N\log\log N)\) time and \(O(N)\) memory.
For a fixed partition \(\lambda\), the dynamic program runs to degree \(E\) and performs one complete-knapsack pass per part, so its cost is \(O(\ell(\lambda)E)\subseteq O(kE)\). Summing over all partitions gives total combinatorial work \(O(p(k)kE)\). The working memory is \(O(E)\) per worker, plus storage for the partition list and the exponent-frequency table. Parallelism reduces wall-clock time but not the asymptotic arithmetic count.
Sei \(W(n,k)\) die Anzahl der Darstellungen von \(n\) als Produkt von \(k\) verschiedenen positiven ganzen Zahlen, wobei die Reihenfolge keine Rolle spielt. Im eigentlichen Problem wird
$$W(10000!,30)\pmod{10^9+7}$$
gesucht. Eine direkte Suche über Teiler oder Kandidatenmengen ist viel zu groß. Deshalb arbeitet die Implementierung mit dem Primexponentenprofil von \(n\), formuliert die Bedingung „\(k\) verschiedene Faktoren“ als Koeffizientenproblem einer erzeugenden Funktion und wertet diesen Koeffizienten über eine Summe über Partitionen von \(k\) aus.
Schreibe
$$n=\prod_p p^{e_p}.$$
Für die Fakultäts-Eingabe \(n=N!\) erhält man die Exponenten mit der Legendre-Formel:
$$e_p=\sum_{j\ge 1}\left\lfloor\frac{N}{p^j}\right\rfloor.$$
Jeder Faktor einer zulässigen Zerlegung hat die Form
$$a_i=\prod_p p^{\alpha_{i,p}},\qquad 0\le \alpha_{i,p}\le e_p,$$
und die Produktbedingung \(a_1a_2\cdots a_k=n\) ist äquivalent zu
$$\alpha_{1,p}+\alpha_{2,p}+\cdots+\alpha_{k,p}=e_p \qquad \text{für jede Primzahl } p.$$
Für jeden Teiler \(d\mid n\) führen wir das Monom
$$m(d)=\prod_p x_p^{v_p(d)}$$
ein und betrachten
$$F(t,\mathbf{x})=\prod_{d\mid n}\left(1+t\,m(d)\right).$$
Wird der Term \(t\,m(d)\) gewählt, so wird der Teiler \(d\) ausgewählt; wird \(1\) gewählt, so wird er ausgelassen. Da jeder Teiler im Produkt nur einmal vorkommt, kann er höchstens einmal gewählt werden. Die Bedingung „verschieden“ ist also automatisch eingebaut.
Der Koeffizient
$$[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x})$$
zählt daher ungeordnete Mengen von \(k\) verschiedenen Teilern, deren Produkt genau \(n\) ist. Also gilt
$$W(n,k)=[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x}).$$
Bezeichne mit \(\mathcal{M}\) die Menge aller Teiler-Monome \(m(d)\). Dann ist
$$F(t,\mathbf{x})=\sum_{r\ge 0} e_r(\mathcal{M})\,t^r,$$
wobei \(e_r\) das \(r\)-te elementarsymmetrische Polynom ist. Gesucht ist also der Koeffizient von \(\prod_p x_p^{e_p}\) in \(e_k(\mathcal{M})\).
Eine Standardidentität entwickelt \(e_k\) in Potenzsummen:
$$e_k=\sum_{\lambda\vdash k}\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\,p_\lambda,$$
wobei \(\lambda=(\lambda_1,\dots,\lambda_r)\) eine Partition von \(k\), \(\ell(\lambda)=r\), \(p_\lambda=\prod_{i=1}^r p_{\lambda_i}\) und
$$z_\lambda=\prod_v v^{m_v}m_v!$$
ist. Hier bezeichnet \(m_v\), wie oft der Teilwert \(v\) in \(\lambda\) vorkommt. Genau deshalb iteriert das Programm über die Partitionen von \(k\) statt über Teilermengen.
Der zu \(\lambda\) gehörende Koeffizient lässt sich umschreiben zu
$$\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda} =\left(\prod_{i=1}^r\frac{(-1)^{\lambda_i-1}}{\lambda_i}\right)\left(\prod_v\frac{1}{m_v!}\right).$$
Jede Partition trägt also ein rationales Gewicht bei, das nur von den Teilgrößen und den Multiplizitäten gleicher Teile abhängt. In der modularen Rechnung werden diese Divisionen durch modulare Inversen modulo
$$M=10^9+7$$
realisiert. Genau dieses Koeffizientenmuster verwenden die C++-, Python- und Java-Implementierungen.
Für eine positive ganze Zahl \(j\) ist die Potenzsumme
$$p_j=\sum_{d\mid n} m(d)^j.$$
Da Teiler primweise unabhängig beschrieben werden, faktorisiert das zu
$$p_j=\prod_p \sum_{a=0}^{e_p} x_p^{ja}.$$
Fixiere nun eine Partition \(\lambda=(\lambda_1,\dots,\lambda_r)\). Für einen einzelnen Primexponenten \(e\) braucht man den eindimensionalen Koeffizienten
$$d_\lambda(e)=[x^e]\prod_{i=1}^r\frac{1}{1-x^{\lambda_i}}.$$
Das ist zulässig, weil zu \([x^e]\) nur Terme bis Grad \(e\) beitragen können. Äquivalent ist \(d_\lambda(e)\) die Anzahl nichtnegativer ganzzahliger Lösungen von
$$\lambda_1 b_1+\lambda_2 b_2+\cdots+\lambda_r b_r=e.$$
Diese Koeffizienten berechnet die Implementierung mit einer unbeschränkten Rucksack-DP bis zum größten auftretenden Exponenten.
Viele Primzahlen besitzen in \(n\) denselben Exponenten. Setze
$$f_e=\#\{p:e_p=e\}.$$
Für eine feste Partition \(\lambda\) liefern dann alle Primzahlen mit demselben Exponenten denselben Koeffizienten, und das Gesamtgewicht wird
$$S(\lambda)=\prod_e d_\lambda(e)^{f_e}.$$
Damit lautet die Gesamtformel
$$W(n,k)=\sum_{\lambda\vdash k}\left(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\right)S(\lambda)\pmod{M}.$$
Für das Ziel \(n=N!\) stammen die Werte \(e_p\) aus der Legendre-Formel, und das Zusammenfassen gleicher Exponenten vermeidet viele identische DP-Abfragen.
Betrachte
$$144=2^4\cdot 3^2.$$
Das Exponenten-Multiset ist also \(\{4,2\}\); damit gilt \(f_2=1\) und \(f_4=1\). Die Partitionen von \(4\) sind
$$1+1+1+1,\qquad 2+1+1,\qquad 2+2,\qquad 3+1,\qquad 4.$$
Für jede Partition benötigen wir ihren Koeffizienten sowie \(d_\lambda(2)\) und \(d_\lambda(4)\):
$$\begin{aligned} \lambda=1+1+1+1&:\quad \text{Koeff.}=\frac{1}{24},\quad d_\lambda(2)=10,\quad d_\lambda(4)=35,\quad \text{Term}=\frac{350}{24},\\ \lambda=2+1+1&:\quad \text{Koeff.}=-\frac{1}{4},\quad d_\lambda(2)=4,\quad d_\lambda(4)=9,\quad \text{Term}=-9,\\ \lambda=2+2&:\quad \text{Koeff.}=\frac{1}{8},\quad d_\lambda(2)=2,\quad d_\lambda(4)=3,\quad \text{Term}=\frac{3}{4},\\ \lambda=3+1&:\quad \text{Koeff.}=\frac{1}{3},\quad d_\lambda(2)=1,\quad d_\lambda(4)=2,\quad \text{Term}=\frac{2}{3},\\ \lambda=4&:\quad \text{Koeff.}=-\frac{1}{4},\quad d_\lambda(2)=0,\quad d_\lambda(4)=1,\quad \text{Term}=0. \end{aligned}$$
Die Summe dieser fünf Beiträge ist
$$\frac{350}{24}-9+\frac{3}{4}+\frac{2}{3}=7.$$
Also gilt \(W(144,4)=7\), genau wie im Kontrollbeispiel der Implementierung.
Für das Fakultätsziel erzeugt die Implementierung zunächst die relevanten Primzahlen und berechnet jeden Exponenten \(e_p\) mit der Legendre-Formel. Danach werden diese Daten in die Häufigkeitstabelle \(f_e\) verdichtet, denn in der Partitionsformel zählen nur die Exponentenwerte und ihre Häufigkeiten.
Anschließend werden alle Partitionen von \(k\) erzeugt. Für jede Partition berechnet die Implementierung den modularen Koeffizienten \(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\) mit schneller modularer Potenzierung für Inversen und mit vorab berechneten inversen Fakultäten für Vielfachheiten gleicher Teile.
Danach läuft eine unbeschränkte Rucksack-DP bis zum Maximalexponenten \(E=\max e_p\). Der DP-Wert an Position \(e\) ist genau \(d_\lambda(e)\), also der Koeffizient von \(x^e\) in \(\prod_i(1-x^{\lambda_i})^{-1}\). Mithilfe der Häufigkeitstabelle \(f_e\) werden die benötigten DP-Werte potenziert, multipliziert und mit dem Partitionskoeffizienten zum Gesamtergebnis addiert.
Da verschiedene Partitionen unabhängig sind, verarbeiten die C++-, Python- und Java-Implementierungen disjunkte Partitionsbereiche parallel und führen die Teilsummen modulo \(10^9+7\) zusammen.
Sei \(p(k)\) die Anzahl der Partitionen von \(k\), und sei \(E=\max_p e_p\). Für die Fakultäts-Eingabe \(n=N!\) kostet das Erzeugen der Primzahlen und das Auswerten der Legendre-Formel mit dem hier benutzten siebbasierten Ansatz \(O(N\log\log N)\) Zeit und \(O(N)\) Speicher.
Für eine feste Partition \(\lambda\) läuft die Dynamik bis Grad \(E\) und führt pro Teil einen vollständigen Rucksack-Durchlauf aus; das kostet also \(O(\ell(\lambda)E)\subseteq O(kE)\). Über alle Partitionen summiert ergibt sich \(O(p(k)kE)\) kombinatorische Arbeit. Der Arbeitsspeicher beträgt \(O(E)\) pro Worker, zuzüglich der gespeicherten Partitionen und der Häufigkeitstabelle der Exponenten. Parallelisierung verkürzt die Laufzeit in der Praxis, ändert aber nicht die asymptotische Anzahl der Rechenoperationen.
\(W(n,k)\), \(n\) sayısını sırası önemsiz olacak şekilde \(k\) farklı pozitif tamsayının çarpımı olarak yazma sayısı olsun. Bu problemde istenen değer
$$W(10000!,30)\pmod{10^9+7}$$
şeklindedir. Bölenleri veya aday çarpan kümelerini doğrudan taramak pratik değildir. Bu yüzden uygulama, \(n\)'nin asal üs profilini kullanır, “\(k\) farklı çarpan seç” koşulunu bir üreteç fonksiyon katsayısına dönüştürür ve bu katsayıyı \(k\)'nın tamsayı bölmeleri üzerinden hesaplar.
\(n\)'yi
$$n=\prod_p p^{e_p}$$
şeklinde yazalım. Girdi \(n=N!\) olduğunda üsler Legendre formülüyle bulunur:
$$e_p=\sum_{j\ge 1}\left\lfloor\frac{N}{p^j}\right\rfloor.$$
Geçerli bir ayrışım içindeki her çarpan
$$a_i=\prod_p p^{\alpha_{i,p}},\qquad 0\le \alpha_{i,p}\le e_p$$
biçimindedir ve \(a_1a_2\cdots a_k=n\) koşulu, her asal için
$$\alpha_{1,p}+\alpha_{2,p}+\cdots+\alpha_{k,p}=e_p$$
eşitliğine denktir.
Her \(d\mid n\) böleni için
$$m(d)=\prod_p x_p^{v_p(d)}$$
monomunu tanımlayalım. Sonra
$$F(t,\mathbf{x})=\prod_{d\mid n}\left(1+t\,m(d)\right)$$
çarpımına bakalım. \(t\,m(d)\) terimini seçmek, \(d\) bölenini seçmek demektir; \(1\) terimini seçmek ise onu atlamak demektir. Her bölen çarpımda yalnızca bir kez geçtiği için en fazla bir kez seçilebilir. Yani farklılık koşulu zaten bu yapının içine gömülüdür.
Dolayısıyla
$$[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x})$$
katsayısı, çarpımı tam olarak \(n\) olan \(k\) farklı bölenin sırasız seçimlerini sayar. Bu yüzden
$$W(n,k)=[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x})$$
olur.
Tüm bölen monomlarının kümesini \(\mathcal{M}\) ile gösterelim. O zaman
$$F(t,\mathbf{x})=\sum_{r\ge 0} e_r(\mathcal{M})\,t^r$$
olur; burada \(e_r\), \(r\). elemanter simetrik polinomdur. Demek ki asıl iş, \(e_k(\mathcal{M})\) içinde \(\prod_p x_p^{e_p}\) katsayısını çıkarmaktır.
Bunu yapmak için kullanılan standart özdeşlik şudur:
$$e_k=\sum_{\lambda\vdash k}\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\,p_\lambda,$$
burada \(\lambda=(\lambda_1,\dots,\lambda_r)\), \(k\)'nın bir tamsayı bölmesi, \(\ell(\lambda)=r\), \(p_\lambda=\prod_{i=1}^r p_{\lambda_i}\) ve
$$z_\lambda=\prod_v v^{m_v}m_v!$$
olur. Buradaki \(m_v\), bölmede \(v\) parçasının kaç kez geçtiğini gösterir. Kodun bölen altkümeleri yerine \(k\)'nın bölmeleri üzerinde dolaşmasının nedeni tam olarak budur.
\(\lambda\)'ya ait katsayı şu şekilde yeniden yazılabilir:
$$\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda} =\left(\prod_{i=1}^r\frac{(-1)^{\lambda_i-1}}{\lambda_i}\right)\left(\prod_v\frac{1}{m_v!}\right).$$
Yani her bölme, parça büyüklükleri ile aynı parçaların tekrar sayılarından oluşan rasyonel bir ağırlık getirir. Son modüler hesapta bu bölmeler
$$M=10^9+7$$
modunda tersler kullanılarak gerçekleştirilir. C++, Python ve Java uygulamalarındaki katsayı deseni tam olarak budur.
Pozitif bir \(j\) için kuvvet toplamı
$$p_j=\sum_{d\mid n} m(d)^j$$
şeklindedir. Bölen yapısı asallar arasında bağımsız olduğundan bu ifade
$$p_j=\prod_p \sum_{a=0}^{e_p} x_p^{ja}$$
şeklinde çarpanlara ayrılır. Şimdi \(\lambda=(\lambda_1,\dots,\lambda_r)\) bölmesini sabitleyelim. Tek bir asal üs değeri \(e\) için gereken tek değişkenli katsayı
$$d_\lambda(e)=[x^e]\prod_{i=1}^r\frac{1}{1-x^{\lambda_i}}$$
olur. Bu güvenlidir; çünkü \([x^e]\) için yalnızca derece \(e\)'ye kadar olan terimler katkı verebilir. Eşdeğer olarak \(d_\lambda(e)\),
$$\lambda_1 b_1+\lambda_2 b_2+\cdots+\lambda_r b_r=e$$
denklemindeki negatif olmayan tamsayı çözüm sayısıdır. Uygulama bu katsayıları, en büyük üs değerine kadar çalışan sınırsız çanta tipi bir DP ile bulur.
\(n\)'nin çarpanlaşmasında birçok asal aynı üs değerini paylaşır. Şunu tanımlayalım:
$$f_e=\#\{p:e_p=e\}.$$
Sabit bir \(\lambda\) bölmesi için aynı üs değerine sahip tüm asallar aynı katsayıyı verdiğinden toplam katkı
$$S(\lambda)=\prod_e d_\lambda(e)^{f_e}$$
olur. Böylece nihai formül
$$W(n,k)=\sum_{\lambda\vdash k}\left(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\right)S(\lambda)\pmod{M}$$
şeklini alır. Hedefte \(n=N!\) olduğu için \(e_p\) değerleri Legendre formülünden gelir; aynı üsleri gruplayarak aynı DP değerini defalarca hesaplama ihtiyacı ortadan kalkar.
Şunu ele alalım:
$$144=2^4\cdot 3^2.$$
Dolayısıyla üs çokluğu \(\{4,2\}\) olur; yani \(f_2=1\) ve \(f_4=1\). \(4\)'ün bölmeleri
$$1+1+1+1,\qquad 2+1+1,\qquad 2+2,\qquad 3+1,\qquad 4$$
şeklindedir. Her bölme için katsayı ile \(d_\lambda(2)\) ve \(d_\lambda(4)\) değerlerini yazalım:
$$\begin{aligned} \lambda=1+1+1+1&:\quad \text{katsayı}=\frac{1}{24},\quad d_\lambda(2)=10,\quad d_\lambda(4)=35,\quad \text{terim}=\frac{350}{24},\\ \lambda=2+1+1&:\quad \text{katsayı}=-\frac{1}{4},\quad d_\lambda(2)=4,\quad d_\lambda(4)=9,\quad \text{terim}=-9,\\ \lambda=2+2&:\quad \text{katsayı}=\frac{1}{8},\quad d_\lambda(2)=2,\quad d_\lambda(4)=3,\quad \text{terim}=\frac{3}{4},\\ \lambda=3+1&:\quad \text{katsayı}=\frac{1}{3},\quad d_\lambda(2)=1,\quad d_\lambda(4)=2,\quad \text{terim}=\frac{2}{3},\\ \lambda=4&:\quad \text{katsayı}=-\frac{1}{4},\quad d_\lambda(2)=0,\quad d_\lambda(4)=1,\quad \text{terim}=0. \end{aligned}$$
Bu beş terimin toplamı
$$\frac{350}{24}-9+\frac{3}{4}+\frac{2}{3}=7$$
eder. Yani \(W(144,4)=7\); bu da uygulamadaki kontrol değeriyle aynıdır.
Faktöriyel hedef için uygulama önce gerekli asalları üretir ve her \(e_p\) değerini Legendre formülüyle hesaplar. Ardından bu bilgiyi \(f_e\) sıklık tablosuna dönüştürür; çünkü bölme toplamında önemli olan, hangi üslerin kaç kez görüldüğüdür.
Sonra \(k\)'nın bütün tamsayı bölmeleri üretilir. Her bölme için \(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\) katsayısının modüler karşılığı, parça büyüklüklerinin modüler tersleri ve tekrar sayılarının ters faktöriyelleri kullanılarak hesaplanır.
Bundan sonra en büyük üs \(E=\max e_p\)'ye kadar çalışan sınırsız çanta DP'si kurulur. DP dizisinin \(e\) indeksindeki değer, tam olarak \(\prod_i(1-x^{\lambda_i})^{-1}\) içindeki \(x^e\) katsayısı olan \(d_\lambda(e)\)'dir. Daha sonra \(f_e\) tablosu kullanılarak gereken DP değerleri uygun kuvvetlere yükseltilir, çarpılır ve bölmenin ağırlıklı katkısı toplama eklenir.
Bölmeler birbirinden bağımsız olduğundan C++, Python ve Java uygulamaları farklı bölme aralıklarını paralel olarak işler ve kısmi toplamları \(10^9+7\) modunda birleştirir.
\(p(k)\), \(k\)'nın tamsayı bölme sayısı; \(E=\max_p e_p\) olsun. Faktöriyel girdi \(n=N!\) için asalları üretmek ve Legendre formülünü hesaplamak, burada kullanılan süzgeç tabanlı yaklaşımda \(O(N\log\log N)\) zaman ve \(O(N)\) bellek gerektirir.
Sabit bir \(\lambda\) bölmesi için DP, derece \(E\)'ye kadar gider ve her parça için tam bir çanta geçişi yapar; bu yüzden maliyet \(O(\ell(\lambda)E)\subseteq O(kE)\) olur. Tüm bölmeler üzerinde toplandığında toplam kombinatorik iş yükü \(O(p(k)kE)\)'dir. Çalışma belleği her işçi için \(O(E)\), ayrıca bölme listesi ve üs-sıklık tablosu için ek alandır. Paralellik pratikte süreyi azaltır, fakat asimptotik işlem sayısını değiştirmez.
Sea \(W(n,k)\) el número de formas de escribir \(n\) como producto de \(k\) enteros positivos distintos, sin importar el orden. En esta pregunta se busca
$$W(10000!,30)\pmod{10^9+7}.$$
Explorar directamente divisores o conjuntos candidatos de factores es imposible a esta escala. Por eso la implementación trabaja con el perfil de exponentes primos de \(n\), convierte la condición de “elegir \(k\) factores distintos” en la extracción de un coeficiente de función generadora y evalúa ese coeficiente mediante una suma sobre las particiones enteras de \(k\).
Escribimos
$$n=\prod_p p^{e_p}.$$
Para la entrada factorial \(n=N!\), los exponentes se obtienen con la fórmula de Legendre:
$$e_p=\sum_{j\ge 1}\left\lfloor\frac{N}{p^j}\right\rfloor.$$
Cada factor de una descomposición válida puede escribirse como
$$a_i=\prod_p p^{\alpha_{i,p}},\qquad 0\le \alpha_{i,p}\le e_p,$$
y la condición \(a_1a_2\cdots a_k=n\) equivale a
$$\alpha_{1,p}+\alpha_{2,p}+\cdots+\alpha_{k,p}=e_p \qquad \text{para todo primo } p.$$
Para cada divisor \(d\mid n\), introducimos el monomio
$$m(d)=\prod_p x_p^{v_p(d)}.$$
Ahora consideramos
$$F(t,\mathbf{x})=\prod_{d\mid n}\left(1+t\,m(d)\right).$$
Elegir el término \(t\,m(d)\) significa seleccionar el divisor \(d\); elegir \(1\) significa no tomarlo. Como cada divisor aparece una sola vez en el producto, puede elegirse como mucho una vez, de modo que la condición de distinción queda incorporada automáticamente.
Entonces el coeficiente
$$[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x})$$
cuenta conjuntos no ordenados de \(k\) divisores distintos cuyo producto es exactamente \(n\). Por tanto,
$$W(n,k)=[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x}).$$
Si \(\mathcal{M}\) es el conjunto de todos los monomios \(m(d)\), entonces
$$F(t,\mathbf{x})=\sum_{r\ge 0} e_r(\mathcal{M})\,t^r,$$
donde \(e_r\) es el \(r\)-ésimo polinomio simétrico elemental. Así que el problema se reduce a extraer el coeficiente de \(\prod_p x_p^{e_p}\) dentro de \(e_k(\mathcal{M})\).
Una identidad estándar expande \(e_k\) en términos de sumas de potencias:
$$e_k=\sum_{\lambda\vdash k}\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\,p_\lambda,$$
donde \(\lambda=(\lambda_1,\dots,\lambda_r)\) es una partición de \(k\), \(\ell(\lambda)=r\), \(p_\lambda=\prod_{i=1}^r p_{\lambda_i}\) y
$$z_\lambda=\prod_v v^{m_v}m_v!.$$
Aquí \(m_v\) es la multiplicidad de la parte \(v\) dentro de \(\lambda\). Esta identidad explica por qué la implementación recorre las particiones de \(k\) en lugar de recorrer subconjuntos de divisores.
El coeficiente asociado a \(\lambda\) puede reescribirse como
$$\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda} =\left(\prod_{i=1}^r\frac{(-1)^{\lambda_i-1}}{\lambda_i}\right)\left(\prod_v\frac{1}{m_v!}\right).$$
Así, cada partición aporta un peso racional determinado por sus tamaños de parte y por las multiplicidades de las partes repetidas. En la computación modular, esas divisiones se implementan mediante inversos módulo
$$M=10^9+7.$$
Ese es exactamente el patrón de coeficientes usado por las implementaciones en C++, Python y Java.
Para un entero positivo \(j\), la suma de potencias es
$$p_j=\sum_{d\mid n} m(d)^j.$$
Como los divisores se describen de forma independiente primo por primo, esto se factoriza como
$$p_j=\prod_p \sum_{a=0}^{e_p} x_p^{ja}.$$
Fijemos ahora una partición \(\lambda=(\lambda_1,\dots,\lambda_r)\). Para un único exponente primo \(e\), la cantidad univariable necesaria es
$$d_\lambda(e)=[x^e]\prod_{i=1}^r\frac{1}{1-x^{\lambda_i}}.$$
Esto es válido porque para \([x^e]\) solo pueden contribuir términos de grado a lo sumo \(e\). Equivalentemente, \(d_\lambda(e)\) es el número de soluciones enteras no negativas de
$$\lambda_1 b_1+\lambda_2 b_2+\cdots+\lambda_r b_r=e.$$
La implementación calcula estos coeficientes con una programación dinámica de mochila ilimitada hasta el mayor exponente presente en la factorización.
Muchos primos comparten el mismo exponente en \(n\). Definimos
$$f_e=\#\{p:e_p=e\}.$$
Para una partición fija \(\lambda\), todos los primos con el mismo exponente aportan el mismo coeficiente, así que el peso total queda
$$S(\lambda)=\prod_e d_\lambda(e)^{f_e}.$$
Por tanto, la respuesta final es
$$W(n,k)=\sum_{\lambda\vdash k}\left(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\right)S(\lambda)\pmod{M}.$$
En el objetivo factorial \(n=N!\), los valores \(e_p\) vienen de la fórmula de Legendre, y agrupar exponentes iguales evita repetir la misma consulta de DP para muchos primos distintos.
Tomemos
$$144=2^4\cdot 3^2.$$
El multiconjunto de exponentes es \(\{4,2\}\), así que \(f_2=1\) y \(f_4=1\). Las particiones de \(4\) son
$$1+1+1+1,\qquad 2+1+1,\qquad 2+2,\qquad 3+1,\qquad 4.$$
Para cada partición calculamos su coeficiente y los dos valores necesarios \(d_\lambda(2)\) y \(d_\lambda(4)\):
$$\begin{aligned} \lambda=1+1+1+1&:\quad \text{coef.}=\frac{1}{24},\quad d_\lambda(2)=10,\quad d_\lambda(4)=35,\quad \text{término}=\frac{350}{24},\\ \lambda=2+1+1&:\quad \text{coef.}=-\frac{1}{4},\quad d_\lambda(2)=4,\quad d_\lambda(4)=9,\quad \text{término}=-9,\\ \lambda=2+2&:\quad \text{coef.}=\frac{1}{8},\quad d_\lambda(2)=2,\quad d_\lambda(4)=3,\quad \text{término}=\frac{3}{4},\\ \lambda=3+1&:\quad \text{coef.}=\frac{1}{3},\quad d_\lambda(2)=1,\quad d_\lambda(4)=2,\quad \text{término}=\frac{2}{3},\\ \lambda=4&:\quad \text{coef.}=-\frac{1}{4},\quad d_\lambda(2)=0,\quad d_\lambda(4)=1,\quad \text{término}=0. \end{aligned}$$
La suma de estos cinco términos es
$$\frac{350}{24}-9+\frac{3}{4}+\frac{2}{3}=7.$$
Así obtenemos \(W(144,4)=7\), exactamente el mismo valor de comprobación que usa la implementación.
Para el objetivo factorial, la implementación primero genera los primos relevantes y calcula cada exponente \(e_p\) mediante la fórmula de Legendre. Después comprime esa información en la tabla de frecuencias \(f_e\), porque en la fórmula por particiones solo importan los valores de los exponentes y cuántas veces aparecen.
A continuación, genera todas las particiones enteras de \(k\). Para cada partición, calcula la versión modular del coeficiente \(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\) usando exponenciación rápida para obtener inversos modulares y factoriales inversos precomputados para las multiplicidades de partes repetidas.
Luego ejecuta una DP de mochila ilimitada hasta el exponente máximo \(E=\max e_p\). El valor de la DP en la posición \(e\) es exactamente \(d_\lambda(e)\), el coeficiente de \(x^e\) en \(\prod_i(1-x^{\lambda_i})^{-1}\). Con la tabla \(f_e\), eleva y multiplica los valores necesarios de la DP y agrega la contribución ponderada de la partición al total.
Como las particiones son independientes entre sí, las implementaciones en C++, Python y Java reparten rangos distintos de particiones en paralelo y combinan las sumas parciales módulo \(10^9+7\).
Sea \(p(k)\) el número de particiones enteras de \(k\), y sea \(E=\max_p e_p\). Para la entrada factorial \(n=N!\), generar los primos y evaluar la fórmula de Legendre con el método basado en criba empleado aquí cuesta \(O(N\log\log N)\) tiempo y \(O(N)\) memoria.
Para una partición fija \(\lambda\), la DP recorre grados hasta \(E\) y realiza una pasada de mochila completa por cada parte, así que cuesta \(O(\ell(\lambda)E)\subseteq O(kE)\). Sumando sobre todas las particiones, el trabajo combinatorio total es \(O(p(k)kE)\). La memoria de trabajo es \(O(E)\) por trabajador, más el almacenamiento de la lista de particiones y de la tabla de frecuencias de exponentes. El paralelismo reduce el tiempo real de ejecución, pero no cambia el orden asintótico del número de operaciones.
设 \(W(n,k)\) 表示把 \(n\) 写成 \(k\) 个互不相同正整数之积的方法数，并且不区分因子的顺序。本题真正要求的是
$$W(10000!,30)\pmod{10^9+7}.$$
如果直接枚举约数，或者直接枚举候选因子集合，规模都会大得无法处理。因此实现采用另一条路线：先把 \(n\) 转成素因子指数向量，把“选择 \(k\) 个互不相同的因子”改写成一个生成函数的系数提取问题，再把这个系数写成对 \(k\) 的整数分拆的求和。
把 \(n\) 的素因子分解写成
$$n=\prod_p p^{e_p}.$$
对于阶乘输入 \(n=N!\)，每个素数的指数由 Legendre 公式给出：
$$e_p=\sum_{j\ge 1}\left\lfloor\frac{N}{p^j}\right\rfloor.$$
若 \(a_1a_2\cdots a_k=n\) 是一个合法分解，那么每个因子都可写成
$$a_i=\prod_p p^{\alpha_{i,p}},\qquad 0\le \alpha_{i,p}\le e_p,$$
并且乘积条件等价于对每个素数 \(p\) 都满足
$$\alpha_{1,p}+\alpha_{2,p}+\cdots+\alpha_{k,p}=e_p.$$
对每个约数 \(d\mid n\)，引入单项式
$$m(d)=\prod_p x_p^{v_p(d)}.$$
考虑如下乘积：
$$F(t,\mathbf{x})=\prod_{d\mid n}\left(1+t\,m(d)\right).$$
在这个乘积里，选取 \(t\,m(d)\) 就表示把约数 \(d\) 选入因子集合；选取 \(1\) 则表示跳过它。由于每个约数在乘积中只出现一次，所以每个约数最多只能被选一次，互异性条件因此被自动编码进来了。
于是系数
$$[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x})$$
恰好统计了所有由 \(k\) 个互不相同约数组成、并且乘积等于 \(n\) 的无序集合。因此
$$W(n,k)=[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x}).$$
设所有约数单项式组成的集合为 \(\mathcal{M}\)。那么
$$F(t,\mathbf{x})=\sum_{r\ge 0} e_r(\mathcal{M})\,t^r,$$
其中 \(e_r\) 是第 \(r\) 个初等对称多项式。所以问题就变成：如何在 \(e_k(\mathcal{M})\) 中提取 \(\prod_p x_p^{e_p}\) 的系数。
一个标准恒等式把 \(e_k\) 展开成幂和的组合：
$$e_k=\sum_{\lambda\vdash k}\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\,p_\lambda,$$
这里 \(\lambda=(\lambda_1,\dots,\lambda_r)\) 是 \(k\) 的一个整数分拆，\(\ell(\lambda)=r\)，\(p_\lambda=\prod_{i=1}^r p_{\lambda_i}\)，并且
$$z_\lambda=\prod_v v^{m_v}m_v!.$$
其中 \(m_v\) 表示分拆中数值 \(v\) 这一部分出现了多少次。也正因为这个恒等式，程序才会遍历 \(k\) 的所有整数分拆，而不是遍历约数子集。
与 \(\lambda\) 对应的系数还可以改写成
$$\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda} =\left(\prod_{i=1}^r\frac{(-1)^{\lambda_i-1}}{\lambda_i}\right)\left(\prod_v\frac{1}{m_v!}\right).$$
也就是说，每个分拆都对应一个有理权重，这个权重只由分拆的各部分大小以及重复部分的重数决定。在模运算里，这些除法通过模
$$M=10^9+7$$
下的乘法逆元来实现。这正是 C++、Python 和 Java 实现所使用的系数形式。
对任意正整数 \(j\)，幂和为
$$p_j=\sum_{d\mid n} m(d)^j.$$
由于约数的素因子指数在不同素数之间相互独立，这个表达式可以分解为
$$p_j=\prod_p \sum_{a=0}^{e_p} x_p^{ja}.$$
现在固定一个分拆 \(\lambda=(\lambda_1,\dots,\lambda_r)\)。对于某一个素数指数 \(e\)，我们真正需要的是一元系数
$$d_\lambda(e)=[x^e]\prod_{i=1}^r\frac{1}{1-x^{\lambda_i}}.$$
这是安全的，因为要提取 \([x^e]\) 时，只有次数不超过 \(e\) 的项才可能产生贡献。等价地，\(d_\lambda(e)\) 就是下式非负整数解的个数：
$$\lambda_1 b_1+\lambda_2 b_2+\cdots+\lambda_r b_r=e.$$
实现里正是用一个“完全背包”型动态规划来计算这些系数，并且只做到分解中出现的最大指数为止。
在 \(n\) 的分解里，往往有很多不同的素数拥有相同的指数。定义
$$f_e=\#\{p:e_p=e\}.$$
对于固定分拆 \(\lambda\)，所有指数同为 \(e\) 的素数都会贡献同一个系数，因此该分拆的总权重可以写成
$$S(\lambda)=\prod_e d_\lambda(e)^{f_e}.$$
于是最终答案就是
$$W(n,k)=\sum_{\lambda\vdash k}\left(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\right)S(\lambda)\pmod{M}.$$
对于本题的阶乘目标 \(n=N!\)，所有 \(e_p\) 都来自 Legendre 公式，而把相同指数归并后，就不需要对许多不同素数重复查询同一个 DP 值。
考虑
$$144=2^4\cdot 3^2.$$
因此指数多重集是 \(\{4,2\}\)，也就是 \(f_2=1\)、\(f_4=1\)。数字 \(4\) 的整数分拆为
$$1+1+1+1,\qquad 2+1+1,\qquad 2+2,\qquad 3+1,\qquad 4.$$
对每个分拆，我们计算其系数以及所需的 \(d_\lambda(2)\) 和 \(d_\lambda(4)\)：
$$\begin{aligned} \lambda=1+1+1+1&:\quad \text{系数}=\frac{1}{24},\quad d_\lambda(2)=10,\quad d_\lambda(4)=35,\quad \text{项}=\frac{350}{24},\\ \lambda=2+1+1&:\quad \text{系数}=-\frac{1}{4},\quad d_\lambda(2)=4,\quad d_\lambda(4)=9,\quad \text{项}=-9,\\ \lambda=2+2&:\quad \text{系数}=\frac{1}{8},\quad d_\lambda(2)=2,\quad d_\lambda(4)=3,\quad \text{项}=\frac{3}{4},\\ \lambda=3+1&:\quad \text{系数}=\frac{1}{3},\quad d_\lambda(2)=1,\quad d_\lambda(4)=2,\quad \text{项}=\frac{2}{3},\\ \lambda=4&:\quad \text{系数}=-\frac{1}{4},\quad d_\lambda(2)=0,\quad d_\lambda(4)=1,\quad \text{项}=0. \end{aligned}$$
把这五项加起来得到
$$\frac{350}{24}-9+\frac{3}{4}+\frac{2}{3}=7.$$
因此 \(W(144,4)=7\)，这与实现中的校验值完全一致。
对于阶乘目标，实现首先生成所需的素数，并用 Legendre 公式算出每个 \(e_p\)。然后它把这些指数压缩成频率表 \(f_e\)，因为在分拆求和公式里，真正重要的是“某个指数出现了多少次”。
接下来，程序生成 \(k\) 的所有整数分拆。对每个分拆，它用快速幂求模逆元，并结合预处理好的逆阶乘，计算 \(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\) 的模意义版本。
之后程序建立一个上界为最大指数 \(E=\max e_p\) 的完全背包 DP。DP 在位置 \(e\) 上的值，正是 \(\prod_i(1-x^{\lambda_i})^{-1}\) 中 \(x^e\) 的系数 \(d_\lambda(e)\)。再结合频率表 \(f_e\)，把相应的 DP 值做幂、相乘，并把该分拆的加权贡献并入总和。
由于不同分拆之间彼此独立，C++、Python 和 Java 实现都会把不同的分拆区间分配到并行工作单元中，最后再把部分和在 \(10^9+7\) 下合并。
设 \(p(k)\) 是 \(k\) 的整数分拆数，\(E=\max_p e_p\)。对于阶乘输入 \(n=N!\)，利用这里采用的筛法生成素数并计算 Legendre 公式，需要 \(O(N\log\log N)\) 时间和 \(O(N)\) 空间。
对于固定分拆 \(\lambda\)，动态规划做到次数 \(E\)，并对分拆中的每一部分做一遍完全背包转移，因此代价是 \(O(\ell(\lambda)E)\subseteq O(kE)\)。对全部分拆求和后，主要组合计算量是 \(O(p(k)kE)\)。工作内存为每个并行工作单元 \(O(E)\)，外加分拆列表和指数频率表的存储。并行化只能降低实际运行时间，不会改变渐近运算量。
Пусть \(W(n,k)\) обозначает число представлений числа \(n\) в виде произведения \(k\) различных положительных целых чисел, причем порядок множителей не учитывается. В данной задаче требуется найти
$$W(10000!,30)\pmod{10^9+7}.$$
Прямой перебор делителей или наборов кандидатов здесь невозможен. Поэтому реализация работает с вектором простых показателей числа \(n\), переводит условие «выбрать \(k\) различных множителей» в задачу извлечения коэффициента из производящей функции, а затем вычисляет этот коэффициент через сумму по разбиениям числа \(k\).
Запишем
$$n=\prod_p p^{e_p}.$$
Для факториального входа \(n=N!\) показатели задаются формулой Лежандра:
$$e_p=\sum_{j\ge 1}\left\lfloor\frac{N}{p^j}\right\rfloor.$$
Каждый множитель в допустимом разложении имеет вид
$$a_i=\prod_p p^{\alpha_{i,p}},\qquad 0\le \alpha_{i,p}\le e_p,$$
а условие \(a_1a_2\cdots a_k=n\) равносильно системе
$$\alpha_{1,p}+\alpha_{2,p}+\cdots+\alpha_{k,p}=e_p \qquad \text{для каждого простого } p.$$
Для каждого делителя \(d\mid n\) введем моном
$$m(d)=\prod_p x_p^{v_p(d)}.$$
Рассмотрим произведение
$$F(t,\mathbf{x})=\prod_{d\mid n}\left(1+t\,m(d)\right).$$
Выбор члена \(t\,m(d)\) означает, что делитель \(d\) включен в набор; выбор \(1\) означает, что он пропущен. Так как каждый делитель встречается в произведении только один раз, его можно выбрать не более одного раза, то есть условие различия встроено автоматически.
Следовательно, коэффициент
$$[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x})$$
считает неупорядоченные наборы из \(k\) различных делителей, произведение которых равно \(n\). Значит,
$$W(n,k)=[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x}).$$
Пусть \(\mathcal{M}\) обозначает множество всех мономов \(m(d)\). Тогда
$$F(t,\mathbf{x})=\sum_{r\ge 0} e_r(\mathcal{M})\,t^r,$$
где \(e_r\) - \(r\)-й элементарный симметрический многочлен. Значит, задача сводится к извлечению коэффициента при \(\prod_p x_p^{e_p}\) из \(e_k(\mathcal{M})\).
Стандартная формула выражает \(e_k\) через степенные суммы:
$$e_k=\sum_{\lambda\vdash k}\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\,p_\lambda,$$
где \(\lambda=(\lambda_1,\dots,\lambda_r)\) - разбиение числа \(k\), \(\ell(\lambda)=r\), \(p_\lambda=\prod_{i=1}^r p_{\lambda_i}\), а
$$z_\lambda=\prod_v v^{m_v}m_v!.$$
Здесь \(m_v\) - сколько раз часть \(v\) встречается в разбиении \(\lambda\). Именно поэтому программа перебирает разбиения числа \(k\), а не наборы делителей.
Коэффициент при \(\lambda\) можно переписать как
$$\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda} =\left(\prod_{i=1}^r\frac{(-1)^{\lambda_i-1}}{\lambda_i}\right)\left(\prod_v\frac{1}{m_v!}\right).$$
То есть каждому разбиению соответствует рациональный вес, зависящий только от размеров частей и от кратностей повторяющихся частей. В вычислениях по модулю эти деления заменяются умножением на обратные элементы по модулю
$$M=10^9+7.$$
Именно такой шаблон коэффициентов реализован в версиях на C++, Python и Java.
Для положительного целого \(j\) степенная сумма равна
$$p_j=\sum_{d\mid n} m(d)^j.$$
Поскольку структура делителей независима по простым, получаем факторизацию
$$p_j=\prod_p \sum_{a=0}^{e_p} x_p^{ja}.$$
Теперь зафиксируем разбиение \(\lambda=(\lambda_1,\dots,\lambda_r)\). Для одного значения простого показателя \(e\) нужна величина
$$d_\lambda(e)=[x^e]\prod_{i=1}^r\frac{1}{1-x^{\lambda_i}}.$$
Это корректно, потому что в коэффициент \([x^e]\) могут внести вклад только члены степени не выше \(e\). Эквивалентно, \(d_\lambda(e)\) - число неотрицательных целочисленных решений уравнения
$$\lambda_1 b_1+\lambda_2 b_2+\cdots+\lambda_r b_r=e.$$
Именно эти коэффициенты реализация находит с помощью динамики типа неограниченного рюкзака вплоть до максимального показателя в разложении \(n\).
У многих простых в разложении \(n\) показатель совпадает. Введем
$$f_e=\#\{p:e_p=e\}.$$
Для фиксированного разбиения \(\lambda\) все простые с одним и тем же показателем дают одинаковый коэффициент, поэтому суммарный вклад равен
$$S(\lambda)=\prod_e d_\lambda(e)^{f_e}.$$
Тогда итоговая формула принимает вид
$$W(n,k)=\sum_{\lambda\vdash k}\left(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\right)S(\lambda)\pmod{M}.$$
Для целевого случая \(n=N!\) значения \(e_p\) вычисляются по формуле Лежандра, а группировка одинаковых показателей избавляет от повторных обращений к одним и тем же значениям DP для разных простых.
Возьмем
$$144=2^4\cdot 3^2.$$
Тогда мультимножество показателей равно \(\{4,2\}\), то есть \(f_2=1\) и \(f_4=1\). Разбиения числа \(4\):
$$1+1+1+1,\qquad 2+1+1,\qquad 2+2,\qquad 3+1,\qquad 4.$$
Для каждого разбиения вычислим коэффициент и величины \(d_\lambda(2)\), \(d_\lambda(4)\):
$$\begin{aligned} \lambda=1+1+1+1&:\quad \text{коэфф.}=\frac{1}{24},\quad d_\lambda(2)=10,\quad d_\lambda(4)=35,\quad \text{вклад}=\frac{350}{24},\\ \lambda=2+1+1&:\quad \text{коэфф.}=-\frac{1}{4},\quad d_\lambda(2)=4,\quad d_\lambda(4)=9,\quad \text{вклад}=-9,\\ \lambda=2+2&:\quad \text{коэфф.}=\frac{1}{8},\quad d_\lambda(2)=2,\quad d_\lambda(4)=3,\quad \text{вклад}=\frac{3}{4},\\ \lambda=3+1&:\quad \text{коэфф.}=\frac{1}{3},\quad d_\lambda(2)=1,\quad d_\lambda(4)=2,\quad \text{вклад}=\frac{2}{3},\\ \lambda=4&:\quad \text{коэфф.}=-\frac{1}{4},\quad d_\lambda(2)=0,\quad d_\lambda(4)=1,\quad \text{вклад}=0. \end{aligned}$$
Сумма этих пяти вкладов равна
$$\frac{350}{24}-9+\frac{3}{4}+\frac{2}{3}=7.$$
Следовательно, \(W(144,4)=7\), что в точности совпадает с контрольным значением реализации.
Для факториальной цели реализация сначала генерирует нужные простые числа и вычисляет каждый показатель \(e_p\) по формуле Лежандра. Затем эти данные сжимаются в таблицу частот \(f_e\), потому что в формуле по разбиениям важны только сами значения показателей и число их повторений.
После этого строятся все разбиения числа \(k\). Для каждого разбиения программа вычисляет модульный вариант коэффициента \(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\), используя быстрое возведение в степень для нахождения обратных элементов и заранее посчитанные обратные факториалы для кратностей одинаковых частей.
Далее запускается динамика типа неограниченного рюкзака до максимального показателя \(E=\max e_p\). Значение DP в позиции \(e\) и есть \(d_\lambda(e)\), то есть коэффициент при \(x^e\) в \(\prod_i(1-x^{\lambda_i})^{-1}\). Затем по таблице \(f_e\) нужные значения DP возводятся в степени, перемножаются и дают взвешенный вклад данного разбиения в итоговую сумму.
Так как разные разбиения независимы, реализации на C++, Python и Java обрабатывают непересекающиеся диапазоны разбиений параллельно и затем складывают частичные суммы по модулю \(10^9+7\).
Пусть \(p(k)\) - число разбиений числа \(k\), а \(E=\max_p e_p\). Для факториального входа \(n=N!\) генерация простых и вычисление формулы Лежандра в использованном здесь решетном варианте требуют \(O(N\log\log N)\) времени и \(O(N)\) памяти.
Для фиксированного разбиения \(\lambda\) динамика идет до степени \(E\) и выполняет по одному полному проходу рюкзака на каждую часть, то есть стоит \(O(\ell(\lambda)E)\subseteq O(kE)\). После суммирования по всем разбиениям получаем основную комбинаторную трудоемкость \(O(p(k)kE)\). Рабочая память составляет \(O(E)\) на одного работника, плюс хранение списка разбиений и таблицы частот показателей. Параллелизм уменьшает реальное время счета, но не меняет асимптотику числа операций.
لنرمز بـ \(W(n,k)\) إلى عدد طرق كتابة \(n\) على صورة حاصل ضرب \(k\) أعداد صحيحة موجبة ومختلفة، من دون اعتبار للترتيب. المطلوب في هذه المسألة هو
$$W(10000!,30)\pmod{10^9+7}.$$
العد المباشر للقواسم أو لمجموعات العوامل المرشحة غير عملي إطلاقًا عند هذه الأحجام. لذلك يعتمد التنفيذ على متجه أسس التحليل الأولي للعدد \(n\)، ثم يحول شرط «اختيار \(k\) عوامل مختلفة» إلى مسألة استخراج معامل من دالة مولدة، وبعد ذلك يحسب هذا المعامل بواسطة مجموع على تجزئات العدد \(k\).
نكتب
$$n=\prod_p p^{e_p}.$$
وعندما تكون المدخلة من الشكل \(n=N!\)، فإن الأسس تحسب بصيغة ليجاندر:
$$e_p=\sum_{j\ge 1}\left\lfloor\frac{N}{p^j}\right\rfloor.$$
وكل عامل في تحليل صحيح يمكن كتابته على الصورة
$$a_i=\prod_p p^{\alpha_{i,p}},\qquad 0\le \alpha_{i,p}\le e_p,$$
ويصبح الشرط \(a_1a_2\cdots a_k=n\) مكافئًا للعلاقة التالية لكل عدد أولي \(p\):
$$\alpha_{1,p}+\alpha_{2,p}+\cdots+\alpha_{k,p}=e_p.$$
لكل قاسم \(d\mid n\) نعرّف المونوم
$$m(d)=\prod_p x_p^{v_p(d)}.$$
ثم ننظر إلى الجداء
$$F(t,\mathbf{x})=\prod_{d\mid n}\left(1+t\,m(d)\right).$$
اختيار الحد \(t\,m(d)\) يعني أن القاسم \(d\) قد اختير ضمن مجموعة العوامل، واختيار \(1\) يعني تجاهله. وبما أن كل قاسم يظهر مرة واحدة فقط داخل الجداء، فلا يمكن اختياره أكثر من مرة، وبالتالي فإن شرط التمايز مدمج في هذا الترميز تلقائيًا.
لذلك فإن المعامل
$$[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x})$$
يعد المجموعات غير المرتبة المؤلفة من \(k\) قواسم مختلفة والتي يساوي حاصل ضربها العدد \(n\). ومن ثم
$$W(n,k)=[t^k\prod_p x_p^{e_p}]\,F(t,\mathbf{x}).$$
إذا رمزنا بمجموعة جميع مونومات القواسم إلى \(\mathcal{M}\)، فإن
$$F(t,\mathbf{x})=\sum_{r\ge 0} e_r(\mathcal{M})\,t^r,$$
حيث \(e_r\) هو كثير الحدود التناظري الابتدائي من الرتبة \(r\). وبالتالي تصبح المسألة هي استخراج معامل \(\prod_p x_p^{e_p}\) من \(e_k(\mathcal{M})\).
هناك متطابقة قياسية تكتب \(e_k\) بدلالة مجاميع القوى:
$$e_k=\sum_{\lambda\vdash k}\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\,p_\lambda,$$
حيث \(\lambda=(\lambda_1,\dots,\lambda_r)\) تجزئة للعدد \(k\)، و\(\ell(\lambda)=r\)، و\(p_\lambda=\prod_{i=1}^r p_{\lambda_i}\)، و
$$z_\lambda=\prod_v v^{m_v}m_v!.$$
وهنا \(m_v\) هو عدد مرات ظهور الجزء \(v\) داخل التجزئة \(\lambda\). وهذا يفسر مباشرة لماذا يمر التنفيذ على جميع تجزئات \(k\) بدلًا من المرور على مجموعات القواسم نفسها.
يمكن إعادة كتابة المعامل الموافق للتجزئة \(\lambda\) على الصورة
$$\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda} =\left(\prod_{i=1}^r\frac{(-1)^{\lambda_i-1}}{\lambda_i}\right)\left(\prod_v\frac{1}{m_v!}\right).$$
أي إن كل تجزئة تساهم بوزن نسبي يعتمد فقط على أحجام الأجزاء وعدد تكرار الأجزاء المتساوية. وفي الحساب بترديد ثابت، تنفذ هذه القسمة باستعمال المعكوسات الضربية بترديد
$$M=10^9+7.$$
وهذا هو بالضبط نمط المعاملات المستخدم في تطبيقات C++ وPython وJava.
لكل عدد صحيح موجب \(j\)، يكون مجموع القوى
$$p_j=\sum_{d\mid n} m(d)^j.$$
وبما أن وصف القواسم ينفصل بين الأعداد الأولية المختلفة، فإن هذا يتحلل إلى
$$p_j=\prod_p \sum_{a=0}^{e_p} x_p^{ja}.$$
ثبّت الآن تجزئة \(\lambda=(\lambda_1,\dots,\lambda_r)\). ولأجل أس أولي واحد قيمته \(e\)، فإن المقدار أحادي المتغير المطلوب هو
$$d_\lambda(e)=[x^e]\prod_{i=1}^r\frac{1}{1-x^{\lambda_i}}.$$
وهذا صحيح لأن استخراج \([x^e]\) لا يتأثر إلا بالحدود ذات الدرجة حتى \(e\). وبصورة مكافئة، فإن \(d_\lambda(e)\) هو عدد الحلول الصحيحة غير السالبة للمعادلة
$$\lambda_1 b_1+\lambda_2 b_2+\cdots+\lambda_r b_r=e.$$
ولهذا السبب يحسب التنفيذ هذه المعاملات بواسطة برمجة ديناميكية من نوع «حقيبة غير محدودة» حتى أكبر أس يظهر في تحليل \(n\).
غالبًا ما تشترك عدة أعداد أولية في نفس الأس داخل تحليل \(n\). نعرّف
$$f_e=\#\{p:e_p=e\}.$$
ولأجل تجزئة ثابتة \(\lambda\)، فإن جميع الأعداد الأولية ذات الأس نفسه تعطي نفس المعامل، ولذلك تصبح المساهمة الكلية
$$S(\lambda)=\prod_e d_\lambda(e)^{f_e}.$$
وعندها تأخذ الصيغة النهائية الشكل
$$W(n,k)=\sum_{\lambda\vdash k}\left(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\right)S(\lambda)\pmod{M}.$$
وفي الحالة الهدفية \(n=N!\)، تأتي القيم \(e_p\) من صيغة ليجاندر، أما جمع الأسس المتساوية فيمنع تكرار الرجوع إلى نفس قيمة البرمجة الديناميكية لعدة أعداد أولية مختلفة.
لنأخذ
$$144=2^4\cdot 3^2.$$
إذن متعدد الأسس هو \(\{4,2\}\)، أي \(f_2=1\) و\(f_4=1\). وتجزئات العدد \(4\) هي
$$1+1+1+1,\qquad 2+1+1,\qquad 2+2,\qquad 3+1,\qquad 4.$$
لكل تجزئة نحسب معاملها وكذلك القيمتين \(d_\lambda(2)\) و\(d_\lambda(4)\):
$$\begin{aligned} \lambda=1+1+1+1&:\quad c=\frac{1}{24},\quad d_\lambda(2)=10,\quad d_\lambda(4)=35,\quad T=\frac{350}{24},\\ \lambda=2+1+1&:\quad c=-\frac{1}{4},\quad d_\lambda(2)=4,\quad d_\lambda(4)=9,\quad T=-9,\\ \lambda=2+2&:\quad c=\frac{1}{8},\quad d_\lambda(2)=2,\quad d_\lambda(4)=3,\quad T=\frac{3}{4},\\ \lambda=3+1&:\quad c=\frac{1}{3},\quad d_\lambda(2)=1,\quad d_\lambda(4)=2,\quad T=\frac{2}{3},\\ \lambda=4&:\quad c=-\frac{1}{4},\quad d_\lambda(2)=0,\quad d_\lambda(4)=1,\quad T=0. \end{aligned}$$
وبجمع هذه المساهمات الخمس نحصل على
$$\frac{350}{24}-9+\frac{3}{4}+\frac{2}{3}=7.$$
إذن \(W(144,4)=7\)، وهو نفس مقدار التحقق الذي تعتمد عليه التنفيذات.
بالنسبة إلى الهدف العاملـي، يبدأ التنفيذ بتوليد الأعداد الأولية اللازمة، ثم يحسب كل \(e_p\) بواسطة صيغة ليجاندر. وبعد ذلك يضغط هذه البيانات في جدول تكرارات \(f_e\)، لأن صيغة الجمع على التجزئات تعتمد فقط على قيم الأسس وعدد مرات ظهور كل قيمة.
بعدها يولد جميع تجزئات العدد \(k\). ولكل تجزئة يحسب النسخة المعيارية من المعامل \(\frac{(-1)^{k-\ell(\lambda)}}{z_\lambda}\) باستخدام الأس السريع لحساب المعكوسات المعيارية، وباستخدام مقلوبات المضروب المحسوبة مسبقًا من أجل تكرارات الأجزاء المتساوية.
ثم يشغّل برمجة ديناميكية من نوع حقيبة غير محدودة حتى أكبر أس \(E=\max e_p\). والقيمة الموجودة عند الموضع \(e\) في مصفوفة DP هي بالضبط \(d_\lambda(e)\)، أي معامل \(x^e\) في \(\prod_i(1-x^{\lambda_i})^{-1}\). وبعد ذلك يستعمل جدول \(f_e\) لرفع القيم المناسبة إلى القوى المطلوبة وضربها، ثم يضيف مساهمة التجزئة الموزونة إلى المجموع النهائي.
وبما أن التجزئات مستقلة عن بعضها، فإن تطبيقات C++ وPython وJava تعالج مجالات مختلفة من التجزئات بالتوازي ثم تجمع المجاميع الجزئية بترديد \(10^9+7\).
لنرمز بـ \(p(k)\) إلى عدد تجزئات العدد \(k\)، ولتكن \(E=\max_p e_p\). في حالة الإدخال العاملـي \(n=N!\)، فإن توليد الأعداد الأولية وحساب صيغة ليجاندر بالطريقة المعتمدة على الغربال هنا يكلف \(O(N\log\log N)\) زمنًا و\(O(N)\) ذاكرة.
أما بالنسبة إلى تجزئة ثابتة \(\lambda\)، فإن البرمجة الديناميكية تعمل حتى الدرجة \(E\) وتنفذ مرورًا كاملًا من نوع الحقيبة لكل جزء، ولذلك تكون كلفتها \(O(\ell(\lambda)E)\subseteq O(kE)\). وبعد الجمع على جميع التجزئات يصبح العمل التوافقي الأساسي \(O(p(k)kE)\). وتبلغ الذاكرة العاملة \(O(E)\) لكل عامل متواز، إضافة إلى تخزين قائمة التجزئات وجدول تكرارات الأسس. التنفيذ المتوازي يخفض الزمن الفعلي فقط، ولا يغير الرتبة الأسيمبتوطية لعدد العمليات.