The quantity \(F(n)\) counts restricted factorisations of \(n!\) of the shape
$$n!=b_1\,b_2^2\,b_3^2\,b_4^3\,b_5^3\,b_6^3\,b_7^4\,b_8^4\,b_9^4\,b_{10}^4.$$
The computation is organized in two stages. First, the ten slots are treated as labeled so that equal-base collisions can be handled systematically by inclusion-exclusion. Second, the labels inside the equal-exponent groups are forgotten, because swapping the two square slots, the three cube slots, or the four fourth-power slots does not change the underlying factorisation. The goal is to evaluate \(F(10^6)\bmod(10^9+7)\).
Let the exponent pattern be
$$\alpha=(\alpha_1,\dots,\alpha_{10})=(1,2,2,3,3,3,4,4,4,4).$$
If we temporarily label the bases as \(b_1,\dots,b_{10}\), then the only real difficulty is that some of these bases may coincide. The implementations resolve that by working on the partition lattice of the ten labels and by treating each prime of \(n!\) independently.
For each prime \(p\le n\), Legendre's formula gives
$$e_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
Prime powers are independent, so the global count factors over the multiset of values \(\{e_p\}\). It is therefore enough to store the histogram
$$c_e=\#\{p\le n:\ v_p(n!)=e\}.$$
Once the numbers \(c_e\) are known, every partition profile contributes through repeated powers of the same local coefficient \(g(e)\).
Suppose several labeled slots share the same base. Their collision pattern is a set partition \(\pi\) of \(\{1,\dots,10\}\). Every block \(B\in\pi\) represents one actual base, and the exponents attached to that base add up to
$$S_B=\sum_{i\in B}\alpha_i.$$
So after choosing \(\pi\), the original labels only matter through the multiset of block sums \(\{S_B\}\). Two different partitions that produce the same sorted block-sum vector have the same local generating function, so they can be merged by adding their Möbius weights. The implementations do exactly that.
Fix a prime \(p\) with exponent \(e=e_p\). If block \(B\) receives \(u_B\ge 0\) copies of \(p\) in its common base, then the exponent balance is
$$\sum_{B\in\pi} S_Bu_B=e.$$
The number of nonnegative solutions is the coefficient of
$$G_\pi(x)=\prod_{B\in\pi}\frac{1}{1-x^{S_B}}=\sum_{m\ge 0} g_\pi(m)x^m.$$
Therefore \(g_\pi(e)\) is exactly the number of ways a single prime of valuation \(e\) can be distributed across the bases while respecting the collision pattern \(\pi\).
Counting every partition \(\pi\) would allow equal bases. To force the ten labeled bases to be distinct, we use Möbius inversion on the partition lattice. Its weight is
$$\mu(\pi)=(-1)^{10-|\pi|}\prod_{B\in\pi}(|B|-1)!.$$
Because primes are independent, the total labeled contribution of \(\pi\) is
$$W_\pi(n)=\prod_{p\le n} g_\pi(e_p)=\prod_{e\ge 1} g_\pi(e)^{c_e}.$$
Hence the number of factorizations with fully labeled and pairwise distinct bases is
$$L(n)=\sum_{\pi}\mu(\pi)\,W_\pi(n).$$
The labeled model distinguishes the two exponent-\(2\) slots, the three exponent-\(3\) slots, and the four exponent-\(4\) slots. The original problem does not. Every genuine restricted factorisation is therefore counted
$$2!\,3!\,4!=288$$
times inside \(L(n)\). The desired answer is
$$F(n)=\frac{L(n)}{288}\pmod{10^9+7}.$$
Since the modulus is prime, the division is implemented by multiplying with the modular inverse of \(288\).
For small exponents, \(g_\pi(e)\) is computed directly by unbounded knapsack on the block sums \(S_B\). This is exactly coefficient extraction for \(G_\pi(x)\).
For large exponents, the denominator of \(G_\pi(x)\) has degree at most
$$1+2+2+3+3+3+4+4+4+4=30,$$
so if
$$Q_\pi(x)=\prod_{B\in\pi}(1-x^{S_B})=1+q_1x+\cdots+q_{30}x^{30},$$
then the coefficients satisfy the linear recurrence
$$g_\pi(m)=-\sum_{j=1}^{30}q_j\,g_\pi(m-j)\qquad(m\ge 30).$$
This fixed order is the key reason the implementation can jump to distant coefficients quickly instead of extending the dynamic program all the way to \(v_2(n!)\).
If every labeled base is distinct, all ten blocks are singletons and the local series becomes
$$G(x)=\frac{1}{(1-x)(1-x^2)^2(1-x^3)^3(1-x^4)^4}.$$
Now read off a few coefficients. We have \(g(1)=1\), because an exponent \(1\) can only come from the first slot. We also have \(g(2)=3\), because exponent \(2\) can be formed either as \(2\cdot 1\) in the first slot or as one copy of either of the two square slots.
This tiny example illustrates two implementation ideas at once. First, the local coefficients are genuine coin-change counts for the block sums. Second, if a partition profile had all block sums divisible by some \(d>1\), then \(g_\pi(1)=0\). For the target input \(n=10^6\), primes with valuation \(1\) do occur in \(n!\), so such profiles can be discarded immediately.
The C++, Python, and Java implementations follow the same mathematical pipeline. They first enumerate set partitions of the ten exponent slots, convert each partition to its sorted block-sum vector, merge profiles with identical vectors, and store the corresponding Möbius weight. They also keep the gcd of each profile so that obviously impossible profiles can be pruned when exponent \(1\) appears in the histogram.
Next, the implementation sieves primes up to \(n\), applies Legendre's formula to every prime, and compresses the result into the frequency table \(c_e\). For each surviving profile it computes all small coefficients \(g_\pi(e)\) by dynamic programming, then uses the degree-\(30\) recurrence to evaluate larger exponents. The contribution \(\mu(\pi)\prod_e g_\pi(e)^{c_e}\) is accumulated modulo \(10^9+7\), and the final sum is multiplied by the modular inverse of \(288\). The C++ version parallelizes independent profile evaluations, the Java version keeps the same arithmetic sequentially, and the Python version delegates to the same C++ core.
The partition-lattice work depends only on the fixed exponent multiset \((1,2,2,3,3,3,4,4,4,4)\), so it is constant-size preprocessing for this problem. After that, building the prime table up to \(n\) costs \(O(n\log\log n)\) time and \(O(n)\) memory. Let \(P\) be the number of distinct block-sum profiles after aggregation; \(P\) is again a problem-specific constant. The dynamic-programming phase for each profile only goes up to about \(\sqrt n\), while larger coefficients are recovered from an order-\(30\) recurrence in logarithmic time. Consequently the overall asymptotic cost is dominated by the sieve, with \(O(n\log\log n)\) time and \(O(n)\) memory, and the partition-profile work contributes a manageable constant factor.
Gesucht ist die Anzahl eingeschränkter Faktorisierungen von \(n!\) der Form
$$n!=b_1\,b_2^2\,b_3^2\,b_4^3\,b_5^3\,b_6^3\,b_7^4\,b_8^4\,b_9^4\,b_{10}^4.$$
Die Rechnung wird in zwei Stufen organisiert. Zuerst werden die zehn Positionen als markierte Slots behandelt, damit Kollisionen gleicher Basen systematisch per Inklusion-Exklusion erfasst werden können. Danach werden Vertauschungen innerhalb der beiden Quadratslots, der drei Kubikslots und der vier Viertpotenzslots wieder vergessen, weil sie dieselbe Faktorisierung beschreiben. Gesucht ist also \(F(10^6)\bmod(10^9+7)\).
Das Exponentenmuster lautet
$$\alpha=(\alpha_1,\dots,\alpha_{10})=(1,2,2,3,3,3,4,4,4,4).$$
Wenn wir die Basen vorübergehend als \(b_1,\dots,b_{10}\) markieren, bleibt als eigentliche Schwierigkeit nur noch übrig, dass einige dieser Basen gleich sein können. Die Implementierungen lösen das mit Möbius-Inversion auf dem Partitionsgitter der zehn Labels und mit einer vom Primzahlfaktor unabhängigen lokalen Zählung.
Für jede Primzahl \(p\le n\) liefert die Legendre-Formel
$$e_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
Verschiedene Primzahlen wirken unabhängig, daher faktorisiert die Gesamtzahl über die Multimenge der Werte \(\{e_p\}\). Statt die Primzahlen selbst zu behalten, reicht das Histogramm
$$c_e=\#\{p\le n:\ v_p(n!)=e\}.$$
Sobald die Häufigkeiten \(c_e\) bekannt sind, trägt jedes Partitionsprofil nur noch über wiederholte Potenzen derselben lokalen Koeffizienten \(g(e)\) bei.
Angenommen, mehrere markierte Slots verwenden dieselbe Basis. Dann beschreibt eine Mengenpartition \(\pi\) von \(\{1,\dots,10\}\) genau dieses Kollisionsmuster. Jeder Block \(B\in\pi\) steht für eine tatsächliche Basis, und die an diese Basis gebundenen Exponenten summieren sich zu
$$S_B=\sum_{i\in B}\alpha_i.$$
Nach Wahl von \(\pi\) sind die ursprünglichen Labels also nur noch über die Multimenge der Blocksummen \(\{S_B\}\) relevant. Zwei verschiedene Partitionen mit demselben sortierten Blocksummenvektor besitzen dieselbe erzeugende Funktion und können daher zusammengefasst werden, indem man ihre Möbius-Gewichte addiert. Genau das tun die Implementierungen.
Fixiere eine Primzahl \(p\) mit Exponent \(e=e_p\). Erhält Block \(B\) in seiner gemeinsamen Basis \(u_B\ge 0\) Kopien von \(p\), dann gilt die Exponentenbilanz
$$\sum_{B\in\pi} S_Bu_B=e.$$
Die Anzahl nichtnegativer Lösungen ist der Koeffizient von
$$G_\pi(x)=\prod_{B\in\pi}\frac{1}{1-x^{S_B}}=\sum_{m\ge 0} g_\pi(m)x^m.$$
Somit ist \(g_\pi(e)\) genau die Anzahl der Möglichkeiten, eine einzelne Primzahl vom Wert \(e\) unter dem Kollisionsmuster \(\pi\) auf die Basen zu verteilen.
Würde man einfach über alle Partitionen \(\pi\) summieren, wären gleiche Basen zugelassen. Um wirklich zehn paarweise verschiedene markierte Basen zu erzwingen, verwendet man Möbius-Inversion auf dem Partitionsgitter. Das Gewicht lautet
$$\mu(\pi)=(-1)^{10-|\pi|}\prod_{B\in\pi}(|B|-1)!.$$
Da die Primzahlen unabhängig sind, ist der gesamte markierte Beitrag von \(\pi\)
$$W_\pi(n)=\prod_{p\le n} g_\pi(e_p)=\prod_{e\ge 1} g_\pi(e)^{c_e}.$$
Damit ergibt sich die Zahl der Faktorisierungen mit vollständig markierten und paarweise verschiedenen Basen zu
$$L(n)=\sum_{\pi}\mu(\pi)\,W_\pi(n).$$
Im markierten Modell sind die beiden Exponenten-\(2\)-Slots, die drei Exponenten-\(3\)-Slots und die vier Exponenten-\(4\)-Slots unterscheidbar. Im eigentlichen Problem sind sie es nicht. Jede echte eingeschränkte Faktorisierung wird in \(L(n)\) daher genau
$$2!\,3!\,4!=288$$
Mal gezählt. Die gesuchte Zahl ist also
$$F(n)=\frac{L(n)}{288}\pmod{10^9+7}.$$
Da der Modulus prim ist, wird die Division durch Multiplikation mit dem modularen Inversen von \(288\) ausgeführt.
Für kleine Exponenten wird \(g_\pi(e)\) direkt durch unbeschränkten Knapsack auf den Blocksummen \(S_B\) berechnet. Das ist genau die Koeffizientenextraktion der Reihe \(G_\pi(x)\).
Für große Exponenten hat der Nenner von \(G_\pi(x)\) höchstens den Grad
$$1+2+2+3+3+3+4+4+4+4=30,$$
also gilt für
$$Q_\pi(x)=\prod_{B\in\pi}(1-x^{S_B})=1+q_1x+\cdots+q_{30}x^{30}$$
die lineare Rekurrenz
$$g_\pi(m)=-\sum_{j=1}^{30}q_j\,g_\pi(m-j)\qquad(m\ge 30).$$
Gerade diese feste Ordnung erlaubt es, weit entfernte Koeffizienten schnell zu berechnen, statt das dynamische Programm bis zum größten Exponenten \(v_2(n!)\) auszudehnen.
Wenn alle markierten Basen verschieden sind, bestehen alle zehn Blöcke aus Einzelmengen und die lokale Reihe ist
$$G(x)=\frac{1}{(1-x)(1-x^2)^2(1-x^3)^3(1-x^4)^4}.$$
Einige Koeffizienten lassen sich sofort ablesen. Es gilt \(g(1)=1\), denn ein Exponent \(1\) kann nur aus dem ersten Slot stammen. Außerdem gilt \(g(2)=3\), denn Exponent \(2\) entsteht entweder als \(2\cdot 1\) im ersten Slot oder als eine Kopie eines der beiden Quadratslots.
Dieses kleine Beispiel erklärt zwei wichtige Implementierungsentscheidungen. Erstens sind die lokalen Koeffizienten echte Münzwechsel-Zahlen für die Blocksummen. Zweitens gilt bei einem Profil, dessen Blocksummen alle durch ein \(d>1\) teilbar sind, automatisch \(g_\pi(1)=0\). Für den Zieleingabewert \(n=10^6\) treten in \(n!\) aber Primzahlen mit Exponent \(1\) auf, daher können solche Profile sofort verworfen werden.
Die C++-, Python- und Java-Implementierungen folgen derselben mathematischen Pipeline. Zuerst werden alle Mengenpartitionen der zehn Exponentenslots erzeugt, in sortierte Blocksummenvektoren umgewandelt, nach gleichen Profilen zusammengefasst und mit ihrem jeweiligen Möbius-Gewicht gespeichert. Zusätzlich wird der ggT jeder Blocksummenliste gemerkt, damit offensichtlich unmögliche Profile verworfen werden können, sobald Exponent \(1\) im Histogramm vorkommt.
Anschließend siebt die Implementierung alle Primzahlen bis \(n\), berechnet für jede Primzahl per Legendre-Formel den Wert \(v_p(n!)\) und verdichtet das Ergebnis zur Häufigkeitstabelle \(c_e\). Für jedes verbleibende Profil werden die kleinen Koeffizienten \(g_\pi(e)\) per dynamischem Programm berechnet, während größere Exponenten über die Rekurrenz vom Grad \(30\) ausgewertet werden. Der Beitrag \(\mu(\pi)\prod_e g_\pi(e)^{c_e}\) wird modulo \(10^9+7\) akkumuliert und am Ende mit dem modularen Inversen von \(288\) multipliziert. Die C++-Version parallelisiert unabhängige Profilberechnungen, die Java-Version führt dieselbe Arithmetik sequentiell aus, und die Python-Version delegiert an denselben C++-Kern.
Die Arbeit auf dem Partitionsgitter hängt nur vom festen Exponentenmuster \((1,2,2,3,3,3,4,4,4,4)\) ab und ist daher für dieses Problem eine Vorverarbeitung konstanter Größe. Danach kostet das Sieb bis \(n\) insgesamt \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Sei \(P\) die Anzahl der verschiedenen Blocksummenprofile nach dem Zusammenfassen; auch \(P\) ist eine problemspezifische Konstante. Das dynamische Programm je Profil reicht nur bis ungefähr \(\sqrt n\), während größere Koeffizienten über eine Rekurrenz 30-ter Ordnung in logarithmischer Zeit gewonnen werden. Damit wird der asymptotische Aufwand vom Sieb dominiert: \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher, ergänzt um einen gut beherrschbaren konstanten Faktor durch die Profilberechnungen.
İstenen nicelik, \(n!\) için şu biçimdeki kısıtlı çarpanlaştırmaların sayısıdır:
$$n!=b_1\,b_2^2\,b_3^2\,b_4^3\,b_5^3\,b_6^3\,b_7^4\,b_8^4\,b_9^4\,b_{10}^4.$$
Hesap iki aşamada kuruluyor. Önce on konum etiketli kabul edilerek eşit taban çakışmaları dahil etme-çıkarma ile yönetiliyor. Daha sonra, üsleri aynı olan gruplar içindeki etiketler unutuluyor; çünkü iki kare konumunun, üç küp konumunun veya dört dördüncü kuvvet konumunun kendi aralarında yer değiştirmesi aynı çarpanlaştırmayı verir. Hedef, \(F(10^6)\bmod(10^9+7)\) değeridir.
Üs deseni
$$\alpha=(\alpha_1,\dots,\alpha_{10})=(1,2,2,3,3,3,4,4,4,4)$$
olsun. Tabanları geçici olarak \(b_1,\dots,b_{10}\) diye etiketlediğimizde, asıl zorluk bazı tabanların eşit olabilmesidir. Uygulamalar bunu, on etiketin partition kafesi üzerinde Möbius terslemesi yaparak ve her asalı bağımsız ele alarak çözer.
Her \(p\le n\) asalı için Legendre formülü
$$e_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor$$
değerini verir. Farklı asallar birbirinden bağımsız olduğu için toplam sayı, \(\{e_p\}\) çoklu kümesi üzerinden çarpımsal biçimde ayrılır. Bu yüzden asalların kendisini değil,
$$c_e=\#\{p\le n:\ v_p(n!)=e\}$$
histogramını tutmak yeterlidir. \(c_e\) değerleri bilindiğinde, her partition profili aynı yerel katsayının tekrar eden üsleri üzerinden katkı yapar.
Bazı etiketli konumların aynı tabanı kullandığını varsayalım. Bu eşitlik örüntüsü, \(\{1,\dots,10\}\) kümesinin bir partition'ı \(\pi\) ile gösterilir. Her \(B\in\pi\) bloğu tek bir gerçek tabanı temsil eder ve o tabana bağlanan üslerin toplamı
$$S_B=\sum_{i\in B}\alpha_i$$
olur. Dolayısıyla \(\pi\) seçildikten sonra asıl önemli olan şey etiketler değil, blok toplamlarının çoklu kümesi \(\{S_B\}\)'dir. Aynı sıralı blok-toplam vektörünü veren iki farklı partition aynı üreteç fonksiyonunu üretir; bu yüzden Möbius ağırlıkları toplanarak tek profile indirgenebilir. Uygulama bunu baştan yapar.
\(e=e_p\) olan sabit bir asal \(p\) seçelim. Eğer \(B\) bloğunun ortak tabanında bu asaldan \(u_B\ge 0\) adet varsa, toplam üs dengesi
$$\sum_{B\in\pi} S_Bu_B=e$$
olmalıdır. Negatif olmayan çözüm sayısı şu serinin katsayısıdır:
$$G_\pi(x)=\prod_{B\in\pi}\frac{1}{1-x^{S_B}}=\sum_{m\ge 0} g_\pi(m)x^m.$$
Yani \(g_\pi(e)\), değeri \(e\) olan tek bir asalın, çakışma deseni \(\pi\) altında tabanlar arasında kaç farklı biçimde dağıtılabileceğini tam olarak verir.
Tüm partition'ları doğrudan saymak, eşit tabanlara da izin verir. On etiketli tabanın gerçekten birbirinden farklı olmasını zorlamak için partition kafesi üzerinde Möbius terslemesi uygulanır. Ağırlık
$$\mu(\pi)=(-1)^{10-|\pi|}\prod_{B\in\pi}(|B|-1)!$$
şeklindedir. Asallar bağımsız olduğundan, \(\pi\)'nin toplam etiketli katkısı
$$W_\pi(n)=\prod_{p\le n} g_\pi(e_p)=\prod_{e\ge 1} g_\pi(e)^{c_e}$$
olur. Böylece tamamen etiketli ve çift çift farklı tabanlara sahip sayım
$$L(n)=\sum_{\pi}\mu(\pi)\,W_\pi(n)$$
biçimine iner.
Etiketli model, iki tane üs-\(2\) konumunu, üç tane üs-\(3\) konumunu ve dört tane üs-\(4\) konumunu birbirinden ayırır. Orijinal problem ayırmaz. Bu yüzden gerçek her kısıtlı çarpanlaştırma, \(L(n)\) içinde tam
$$2!\,3!\,4!=288$$
kez sayılır. Aranan sonuç
$$F(n)=\frac{L(n)}{288}\pmod{10^9+7}$$
olur. Modül asal olduğu için bu bölme, \(288\)'in modüler tersiyle çarpma olarak uygulanır.
Küçük üsler için \(g_\pi(e)\), blok toplamları \(S_B\) üzerinde sınırsız knapsack ile doğrudan hesaplanır. Bu, \(G_\pi(x)\) serisinden katsayı çekmenin ta kendisidir.
Büyük üslerde ise \(G_\pi(x)\)'in paydasının derecesi en fazla
$$1+2+2+3+3+3+4+4+4+4=30$$
olur. Dolayısıyla
$$Q_\pi(x)=\prod_{B\in\pi}(1-x^{S_B})=1+q_1x+\cdots+q_{30}x^{30}$$
yazılırsa katsayılar
$$g_\pi(m)=-\sum_{j=1}^{30}q_j\,g_\pi(m-j)\qquad(m\ge 30)$$
doğrusal bağıntısını sağlar. Sabit dereceli bu rekürans sayesinde, dinamik programı \(v_2(n!)\)'ye kadar uzatmak yerine uzak katsayılar logaritmik maliyetle bulunur.
Eğer tüm etiketli tabanlar farklıysa, on bloğun hepsi tek elemanlıdır ve yerel seri
$$G(x)=\frac{1}{(1-x)(1-x^2)^2(1-x^3)^3(1-x^4)^4}$$
olur. Buradan birkaç katsayı hemen okunabilir. \(g(1)=1\) çünkü üs \(1\) yalnızca ilk konumdan gelebilir. Ayrıca \(g(2)=3\) çünkü üs \(2\), ya ilk konumda \(2\cdot 1\) olarak ya da iki kare konumundan birinin tek katkısıyla oluşur.
Bu küçük örnek iki önemli uygulama fikrini açıklar. Birincisi, yerel katsayılar gerçekten blok toplamları için para bozdurma sayılarıdır. İkincisi, bir profilin tüm blok toplamları \(d>1\) ile bölünüyorsa otomatik olarak \(g_\pi(1)=0\) olur. Hedef girdi \(n=10^6\) için \(n!\) içinde üssü \(1\) olan asallar bulunduğundan, böyle profiller baştan elenir.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. Önce on üs konumunun tüm küme partition'ları üretilir, her partition sıralı blok-toplam vektörüne çevrilir, aynı vektörü veren profiller birleştirilir ve ilgili Möbius ağırlığı saklanır. Ayrıca her profilin blok toplamlarının EBOB'u tutulur; böylece histogramda üs \(1\) bulunduğunda açıkça imkansız profiller hızlıca atılır.
Daha sonra uygulama \(n\)'ye kadar asalları eleyip her asal için Legendre formülüyle \(v_p(n!)\) değerini hesaplar ve sonucu \(c_e\) frekans tablosuna sıkıştırır. Kalan her profil için küçük \(g_\pi(e)\) katsayıları dinamik programla, büyük olanlar ise derece \(30\) reküransı ile bulunur. \(\mu(\pi)\prod_e g_\pi(e)^{c_e}\) katkısı \(10^9+7\) modunda toplanır ve son toplam \(288\)'in modüler tersiyle çarpılır. C++ sürümü bağımsız profilleri paralel değerlendirir, Java sürümü aynı aritmetiği tek iş parçacığında yürütür ve Python sürümü aynı C++ çekirdeğine delegasyon yapar.
Partition kafesi üzerindeki çalışma, sabit üs deseni \((1,2,2,3,3,3,4,4,4,4)\)'ye bağlı olduğundan bu problem için sabit boyutlu bir ön işlemdir. Bundan sonra \(n\)'ye kadar asal tablosu kurmak \(O(n\log\log n)\) zaman ve \(O(n)\) bellek ister. Birleştirmeden sonra kalan farklı blok-toplam profili sayısına \(P\) diyelim; \(P\) de probleme özgü sabit bir sayıdır. Her profil için dinamik program yalnızca yaklaşık \(\sqrt n\)'ye kadar gider, daha büyük katsayılar ise 30. dereceden bir reküransla logaritmik sürede hesaplanır. Bu nedenle toplam asimptotik maliyet süzgeç tarafından belirlenir: \(O(n\log\log n)\) zaman ve \(O(n)\) bellek; profil değerlendirmeleri ise yönetilebilir bir sabit katsayı ekler.
La función \(F(n)\) cuenta factorizaciones restringidas de \(n!\) de la forma
$$n!=b_1\,b_2^2\,b_3^2\,b_4^3\,b_5^3\,b_6^3\,b_7^4\,b_8^4\,b_9^4\,b_{10}^4.$$
El cálculo se organiza en dos fases. Primero se consideran las diez posiciones como etiquetas distintas, para tratar sistemáticamente los choques entre bases iguales mediante inclusión-exclusión. Después se olvidan las permutaciones dentro de los dos cuadrados, los tres cubos y las cuatro cuartas potencias, porque esas permutaciones no cambian la factorización subyacente. El objetivo es hallar \(F(10^6)\bmod(10^9+7)\).
Tomamos el patrón de exponentes
$$\alpha=(\alpha_1,\dots,\alpha_{10})=(1,2,2,3,3,3,4,4,4,4).$$
Si etiquetamos provisionalmente las bases como \(b_1,\dots,b_{10}\), la dificultad real es que algunas de ellas pueden coincidir. Las implementaciones resuelven eso con inversión de Möbius sobre la retícula de particiones de los diez rótulos y con un recuento local independiente para cada primo.
Para cada primo \(p\le n\), la fórmula de Legendre da
$$e_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
Los distintos primos actúan de manera independiente, así que el conteo global se factoriza sobre el multiconjunto \(\{e_p\}\). Por eso basta con guardar el histograma
$$c_e=\#\{p\le n:\ v_p(n!)=e\}.$$
Una vez conocidos los \(c_e\), cada perfil de partición aporta mediante potencias repetidas del mismo coeficiente local \(g(e)\).
Supongamos que varias posiciones etiquetadas usan la misma base. Ese patrón de igualdades es una partición \(\pi\) de \(\{1,\dots,10\}\). Cada bloque \(B\in\pi\) representa una base real, y los exponentes unidos a esa base suman
$$S_B=\sum_{i\in B}\alpha_i.$$
Por tanto, una vez fijada \(\pi\), las etiquetas originales solo importan a través del multiconjunto de sumas de bloque \(\{S_B\}\). Si dos particiones distintas producen el mismo vector ordenado de sumas, tienen la misma función generadora local y pueden fusionarse sumando sus pesos de Möbius. Eso es exactamente lo que hace la implementación.
Fijemos un primo \(p\) con exponente \(e=e_p\). Si el bloque \(B\) recibe \(u_B\ge 0\) copias de \(p\) en su base común, entonces el balance de exponentes es
$$\sum_{B\in\pi} S_Bu_B=e.$$
El número de soluciones no negativas es el coeficiente de
$$G_\pi(x)=\prod_{B\in\pi}\frac{1}{1-x^{S_B}}=\sum_{m\ge 0} g_\pi(m)x^m.$$
Así, \(g_\pi(e)\) es exactamente el número de maneras de repartir un único primo de valoración \(e\) entre las bases respetando el patrón de colisión \(\pi\).
Si sumáramos todas las particiones \(\pi\) sin más, las bases iguales quedarían permitidas. Para imponer que las diez bases etiquetadas sean realmente distintas, se aplica inversión de Möbius en la retícula de particiones. Su peso es
$$\mu(\pi)=(-1)^{10-|\pi|}\prod_{B\in\pi}(|B|-1)!.$$
Como los primos son independientes, la contribución etiquetada total de \(\pi\) es
$$W_\pi(n)=\prod_{p\le n} g_\pi(e_p)=\prod_{e\ge 1} g_\pi(e)^{c_e}.$$
Por tanto, el número de factorizaciones con bases completamente etiquetadas y dos a dos distintas es
$$L(n)=\sum_{\pi}\mu(\pi)\,W_\pi(n).$$
El modelo etiquetado distingue los dos exponentes \(2\), los tres exponentes \(3\) y los cuatro exponentes \(4\). El problema original no. En consecuencia, cada factorización real se cuenta en \(L(n)\) exactamente
$$2!\,3!\,4!=288$$
veces. La respuesta deseada es
$$F(n)=\frac{L(n)}{288}\pmod{10^9+7}.$$
Como el módulo es primo, dividir por \(288\) equivale a multiplicar por su inverso modular.
Para exponentes pequeños, \(g_\pi(e)\) se obtiene directamente mediante un knapsack ilimitado sobre las sumas \(S_B\). Eso no es más que extraer coeficientes de \(G_\pi(x)\).
Para exponentes grandes, el denominador de \(G_\pi(x)\) tiene grado a lo sumo
$$1+2+2+3+3+3+4+4+4+4=30,$$
de modo que, si
$$Q_\pi(x)=\prod_{B\in\pi}(1-x^{S_B})=1+q_1x+\cdots+q_{30}x^{30},$$
entonces los coeficientes satisfacen la recurrencia lineal
$$g_\pi(m)=-\sum_{j=1}^{30}q_j\,g_\pi(m-j)\qquad(m\ge 30).$$
Ese orden fijo permite saltar a coeficientes lejanos mucho más rápido que prolongando el programa dinámico hasta el mayor exponente \(v_2(n!)\).
Si todas las bases etiquetadas son distintas, los diez bloques son singletons y la serie local queda
$$G(x)=\frac{1}{(1-x)(1-x^2)^2(1-x^3)^3(1-x^4)^4}.$$
De aquí se leen algunos coeficientes de inmediato. Tenemos \(g(1)=1\), porque un exponente \(1\) solo puede venir del primer slot. También tenemos \(g(2)=3\), porque el exponente \(2\) puede aparecer como \(2\cdot 1\) en el primer slot o como una sola copia de cualquiera de los dos slots cuadrados.
Este ejemplo pequeño aclara dos decisiones importantes de la implementación. Primero, los coeficientes locales son auténticos conteos de cambio de monedas para las sumas de bloque. Segundo, si todas las sumas de un perfil fueran divisibles por algún \(d>1\), entonces \(g_\pi(1)=0\). Para la entrada objetivo \(n=10^6\), en \(n!\) sí aparecen primos con valoración \(1\), así que esos perfiles se descartan inmediatamente.
Las implementaciones en C++, Python y Java siguen el mismo flujo matemático. Primero enumeran las particiones de conjunto de los diez slots de exponentes, convierten cada una en su vector ordenado de sumas de bloque, fusionan los perfiles idénticos y almacenan el peso de Möbius correspondiente. También guardan el máximo común divisor de las sumas de cada perfil para poder eliminar de antemano los perfiles imposibles cuando aparece exponente \(1\) en el histograma.
Después, la implementación genera todos los primos hasta \(n\), aplica la fórmula de Legendre a cada primo y comprime el resultado en la tabla de frecuencias \(c_e\). Para cada perfil superviviente calcula los coeficientes pequeños \(g_\pi(e)\) por programación dinámica y evalúa los grandes mediante la recurrencia de grado \(30\). La contribución \(\mu(\pi)\prod_e g_\pi(e)^{c_e}\) se acumula módulo \(10^9+7\), y el total final se multiplica por el inverso modular de \(288\). La versión en C++ paraleliza perfiles independientes, la versión en Java conserva la misma aritmética de forma secuencial y la versión en Python delega en el mismo núcleo de C++.
El trabajo sobre la retícula de particiones depende solo del patrón fijo \((1,2,2,3,3,3,4,4,4,4)\), de modo que es un preprocesamiento de tamaño constante para este problema. Después, construir la criba de primos hasta \(n\) cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. Sea \(P\) el número de perfiles distintos de sumas de bloque tras la agregación; \(P\) vuelve a ser una constante específica del problema. La fase de programación dinámica de cada perfil solo llega hasta aproximadamente \(\sqrt n\), mientras que los coeficientes mayores se recuperan mediante una recurrencia de orden \(30\) en tiempo logarítmico. En consecuencia, el coste asintótico total está dominado por la criba: \(O(n\log\log n)\) tiempo y \(O(n)\) memoria, con un factor constante adicional manejable debido a la evaluación de perfiles.
这里要求的 \(F(n)\) 是 \(n!\) 的一种受限分解计数，形式为
$$n!=b_1\,b_2^2\,b_3^2\,b_4^3\,b_5^3\,b_6^3\,b_7^4\,b_8^4\,b_9^4\,b_{10}^4.$$
整个计算分成两个层次。第一层先把这十个位置看成带标签的槽位，这样“两个槽位实际用了同一个底数”这类碰撞就可以用容斥统一处理。第二层再把相同指数组内部的标签忘掉，因为两个平方位、三个立方位、四个四次方位内部互换，并不会改变最终的受限分解。目标是求出 \(F(10^6)\bmod(10^9+7)\)。
把指数模式记为
$$\alpha=(\alpha_1,\dots,\alpha_{10})=(1,2,2,3,3,3,4,4,4,4).$$
如果暂时把十个底数标成 \(b_1,\dots,b_{10}\)，那么真正的难点只有一个：这些底数未必彼此不同。实现采用的方法是，在十个标签的集合划分格上做 Möbius 反演，并且把 \(n!\) 的每个素因子贡献分开处理。
对每个素数 \(p\le n\)，Legendre 公式给出
$$e_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
不同素数之间是独立的，因为每个底数的素因子指数可以逐个素数拆开来分配。因此全局计数只依赖于多重集 \(\{e_p\}\)。实现里并不保存每个素数本身，而是压缩成频率直方图
$$c_e=\#\{p\le n:\ v_p(n!)=e\}.$$
一旦 \(c_e\) 确定，每一种划分轮廓只需要把同一个局部系数 \(g(e)\) 按频数反复乘起来即可。
假设若干个带标签的槽位实际上使用同一个底数，那么这种相等关系就对应于 \(\{1,\dots,10\}\) 的一个集合划分 \(\pi\)。划分中的每个块 \(B\in\pi\) 代表一个真正出现的底数，而挂在这个底数上的总指数是
$$S_B=\sum_{i\in B}\alpha_i.$$
也就是说，一旦选定了 \(\pi\)，原始标签的重要信息就只剩下块和 \(\{S_B\}\)。如果两个不同的划分产生同一个排好序的块和向量，那么它们的局部生成函数完全一样，所以可以先把它们合并，再把 Möbius 权重相加。实现中正是这样预聚合的。
固定某个素数 \(p\)，并设它在 \(n!\) 中的指数为 \(e=e_p\)。如果块 \(B\) 的公共底数中含有 \(u_B\ge 0\) 个 \(p\)，那么所有块的贡献必须满足
$$\sum_{B\in\pi} S_Bu_B=e.$$
非负整数解的个数正好是下面这个生成函数的系数：
$$G_\pi(x)=\prod_{B\in\pi}\frac{1}{1-x^{S_B}}=\sum_{m\ge 0} g_\pi(m)x^m.$$
因此，\(g_\pi(e)\) 的意义非常直接：它就是在碰撞模式 \(\pi\) 固定时，一个 valuation 为 \(e\) 的素数能够如何分配到各个底数上的方法数。
如果只是把所有划分 \(\pi\) 的贡献直接加起来，那么相等底数也会被算进去。为了强制十个带标签的底数彼此不同，需要在集合划分格上做 Möbius 反演。相应的权重为
$$\mu(\pi)=(-1)^{10-|\pi|}\prod_{B\in\pi}(|B|-1)!.$$
由于不同素数彼此独立，划分 \(\pi\) 的总带标签贡献为
$$W_\pi(n)=\prod_{p\le n} g_\pi(e_p)=\prod_{e\ge 1} g_\pi(e)^{c_e}.$$
于是，十个底数都带标签且两两不同的计数是
$$L(n)=\sum_{\pi}\mu(\pi)\,W_\pi(n).$$
在带标签模型中，两个指数为 \(2\) 的槽位是区分开的，三个指数为 \(3\) 的槽位也是区分开的，四个指数为 \(4\) 的槽位同样如此。而原问题并不区分这些内部交换。于是每一个真正的受限分解都会在 \(L(n)\) 中被重复计算
$$2!\,3!\,4!=288$$
次。因此最终答案是
$$F(n)=\frac{L(n)}{288}\pmod{10^9+7}.$$
因为模数是素数，所以这一步在程序里通过乘以 \(288\) 的模逆来完成。
对较小的指数，\(g_\pi(e)\) 直接用无界背包计算，这本质上就是在块和 \(S_B\) 上做“凑和计数”。
对较大的指数，关键观察是 \(G_\pi(x)\) 的分母次数最多只有
$$1+2+2+3+3+3+4+4+4+4=30,$$
因为所有块和加起来永远等于原始指数总和 \(30\)。若记
$$Q_\pi(x)=\prod_{B\in\pi}(1-x^{S_B})=1+q_1x+\cdots+q_{30}x^{30},$$
那么系数满足固定阶线性递推
$$g_\pi(m)=-\sum_{j=1}^{30}q_j\,g_\pi(m-j)\qquad(m\ge 30).$$
这说明只要先得到足够多的初始项，后面的远距离系数都可以用常系数线性递推快速跳算，而不必把动态规划一直延伸到最大的 \(v_2(n!)\)。
如果十个带标签的底数全都不同，那么所有块都是单元素块，局部生成函数就是
$$G(x)=\frac{1}{(1-x)(1-x^2)^2(1-x^3)^3(1-x^4)^4}.$$
从这个式子可以直接读出一些系数。例如 \(g(1)=1\)，因为指数 \(1\) 只能来自第一个槽位。再比如 \(g(2)=3\)，因为指数 \(2\) 的来源有三种：要么把第一个槽位里的指数 \(1\) 用两次，要么使用两个平方槽位中的任意一个一次。
这个小例子同时解释了实现里的两个技巧。第一，局部系数确实就是块和对应的“换零钱”计数。第二，如果某个划分轮廓的所有块和都被同一个 \(d>1\) 整除，那么 \(g_\pi(1)=0\)。而对目标输入 \(n=10^6\) 来说，\(n!\) 中确实存在 valuation 为 \(1\) 的素数，所以这种轮廓可以在一开始就直接剪枝。
C++、Python 和 Java 三个实现遵循同一条数学流水线。首先枚举十个指数槽位的集合划分，把每个划分转成排好序的块和向量，再把向量相同的划分合并起来，并累加它们的 Möbius 权重。同时，还会记录每个轮廓块和的最大公因数，以便在频率表中出现指数 \(1\) 时快速跳过明显不可能有贡献的轮廓。
接下来，程序筛出不超过 \(n\) 的全部素数，对每个素数应用 Legendre 公式，生成 \(v_p(n!)\) 的频率表 \(c_e\)。对每个保留下来的轮廓，较小的 \(g_\pi(e)\) 通过动态规划得到，较大的 \(g_\pi(e)\) 则通过 30 阶递推快速求值。每个轮廓的贡献 \(\mu(\pi)\prod_e g_\pi(e)^{c_e}\) 在模 \(10^9+7\) 下累加，最后再乘上 \(288\) 的模逆。C++ 版本会并行计算彼此独立的轮廓，Java 版本用同样的整数算法顺序执行，Python 版本则调用同一个 C++ 核心。
集合划分部分只依赖于固定的指数模式 \((1,2,2,3,3,3,4,4,4,4)\)，所以对本题来说属于常数规模的预处理。之后，建立 \(n\) 以内的素数筛需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 空间。设合并后的不同块和轮廓数量为 \(P\)；由于 \(P\) 也只与这道题的固定指数模式有关，因此仍是常数级。每个轮廓的动态规划只做到大约 \(\sqrt n\) 附近，而更大的系数通过 30 阶线性递推在对数时间内求出。所以总的渐近复杂度仍由筛法主导，为 \(O(n\log\log n)\) 时间和 \(O(n)\) 空间，轮廓评估只带来可控的常数因子。
Нужно посчитать число ограниченных факторизаций числа \(n!\) вида
$$n!=b_1\,b_2^2\,b_3^2\,b_4^3\,b_5^3\,b_6^3\,b_7^4\,b_8^4\,b_9^4\,b_{10}^4.$$
Вычисление удобно разбить на два этапа. Сначала десять позиций считаются помеченными, чтобы совпадения оснований можно было обработать принципом включения-исключения. Затем метки внутри групп с одинаковыми показателями забываются, потому что перестановка двух квадратов, трёх кубов или четырёх четвёртых степеней не меняет саму факторизацию. Требуется найти \(F(10^6)\bmod(10^9+7)\).
Обозначим шаблон показателей через
$$\alpha=(\alpha_1,\dots,\alpha_{10})=(1,2,2,3,3,3,4,4,4,4).$$
Если временно пометить основания как \(b_1,\dots,b_{10}\), то вся нетривиальная часть задачи сводится к тому, что некоторые из этих оснований могут совпадать. Реализации решают это с помощью инверсии Мёбиуса на решётке разбиений множества из десяти меток и независимого локального подсчёта для каждого простого числа.
Для каждого простого \(p\le n\) по формуле Лежандра имеем
$$e_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
Разные простые числа независимы, поэтому глобальный подсчёт раскладывается по мультимножеству значений \(\{e_p\}\). Значит, достаточно хранить только частотную таблицу
$$c_e=\#\{p\le n:\ v_p(n!)=e\}.$$
Как только известны числа \(c_e\), вклад каждого профиля разбиения выражается через повторные степени одного и того же локального коэффициента \(g(e)\).
Пусть несколько помеченных позиций используют одно и то же основание. Тогда схема этих совпадений задаётся разбиением \(\pi\) множества \(\{1,\dots,10\}\). Каждый блок \(B\in\pi\) соответствует одному реальному основанию, а суммарный показатель на этом основании равен
$$S_B=\sum_{i\in B}\alpha_i.$$
После выбора \(\pi\) исходные метки важны уже только через мультимножество сумм блоков \(\{S_B\}\). Если два различных разбиения дают один и тот же отсортированный вектор сумм блоков, то их локальные производящие функции совпадают, а значит такие профили можно заранее объединить, сложив их веса Мёбиуса. Именно так и устроен код.
Зафиксируем простое \(p\) с показателем \(e=e_p\). Если общий базовый множитель блока \(B\) получает \(u_B\ge 0\) копий простого \(p\), то баланс показателей имеет вид
$$\sum_{B\in\pi} S_Bu_B=e.$$
Число неотрицательных решений равно коэффициенту при \(x^e\) в ряде
$$G_\pi(x)=\prod_{B\in\pi}\frac{1}{1-x^{S_B}}=\sum_{m\ge 0} g_\pi(m)x^m.$$
Следовательно, \(g_\pi(e)\) точно равно числу способов распределить один простой множитель с valuation \(e\) по основаниям при фиксированном шаблоне совпадений \(\pi\).
Если просто суммировать вклады всех разбиений \(\pi\), то совпадающие основания будут разрешены. Чтобы потребовать, чтобы десять помеченных оснований были попарно различны, применяется инверсия Мёбиуса на решётке разбиений. Соответствующий вес равен
$$\mu(\pi)=(-1)^{10-|\pi|}\prod_{B\in\pi}(|B|-1)!.$$
Поскольку простые числа независимы, полный помеченный вклад разбиения \(\pi\) равен
$$W_\pi(n)=\prod_{p\le n} g_\pi(e_p)=\prod_{e\ge 1} g_\pi(e)^{c_e}.$$
Тем самым число факторизаций с полностью помеченными и попарно различными основаниями имеет вид
$$L(n)=\sum_{\pi}\mu(\pi)\,W_\pi(n).$$
В помеченной модели различаются два слота с показателем \(2\), три слота с показателем \(3\) и четыре слота с показателем \(4\). В исходной задаче этого различия нет. Поэтому каждая настоящая ограниченная факторизация посчитана в \(L(n)\) ровно
$$2!\,3!\,4!=288$$
раз. Искомый ответ равен
$$F(n)=\frac{L(n)}{288}\pmod{10^9+7}.$$
Так как модуль прост, деление реализуется умножением на обратный по модулю элемент к \(288\).
Для малых \(e\) значение \(g_\pi(e)\) находится напрямую неограниченным рюкзаком по суммам блоков \(S_B\). Это просто извлечение коэффициентов из \(G_\pi(x)\).
Для больших \(e\) важен тот факт, что знаменатель \(G_\pi(x)\) имеет степень не более
$$1+2+2+3+3+3+4+4+4+4=30,$$
потому что сумма всех исходных показателей равна \(30\). Если
$$Q_\pi(x)=\prod_{B\in\pi}(1-x^{S_B})=1+q_1x+\cdots+q_{30}x^{30},$$
то коэффициенты удовлетворяют линейной рекурренте
$$g_\pi(m)=-\sum_{j=1}^{30}q_j\,g_\pi(m-j)\qquad(m\ge 30).$$
Именно эта фиксированная длина рекурренты позволяет быстро вычислять далёкие коэффициенты, не продолжая динамику вплоть до максимального показателя \(v_2(n!)\).
Если все помеченные основания различны, то каждый из десяти блоков состоит из одного элемента, а локальный ряд равен
$$G(x)=\frac{1}{(1-x)(1-x^2)^2(1-x^3)^3(1-x^4)^4}.$$
Несколько коэффициентов видны сразу. Имеем \(g(1)=1\), потому что показатель \(1\) может прийти только из первого слота. Кроме того, \(g(2)=3\), потому что показатель \(2\) получается либо как \(2\cdot 1\) в первом слоте, либо как один вклад от любого из двух квадратных слотов.
Этот небольшой пример объясняет сразу две идеи из реализации. Во-первых, локальные коэффициенты действительно являются числами размена для сумм блоков. Во-вторых, если все суммы блоков какого-то профиля делятся на \(d>1\), то автоматически \(g_\pi(1)=0\). Для целевого входа \(n=10^6\) в \(n!\) есть простые с valuation \(1\), поэтому такие профили можно отбрасывать сразу.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала перечисляются разбиения десяти экспонентных слотов, каждое разбиение переводится в отсортированный вектор сумм блоков, профили с одинаковыми векторами объединяются, и для них суммируется вес Мёбиуса. Дополнительно сохраняется наибольший общий делитель сумм блоков, чтобы можно было заранее выкинуть заведомо невозможные профили, когда в частотной таблице встречается показатель \(1\).
Затем программа просеивает все простые числа до \(n\), применяет к каждому формулу Лежандра и строит частотную таблицу \(c_e\). Для каждого оставшегося профиля малые коэффициенты \(g_\pi(e)\) находятся динамическим программированием, а большие вычисляются по рекурренте порядка \(30\). Вклад \(\mu(\pi)\prod_e g_\pi(e)^{c_e}\) суммируется по модулю \(10^9+7\), а в конце общий результат умножается на модульно обратный элемент к \(288\). В версии на C++ независимые профили вычисляются параллельно, версия на Java выполняет ту же арифметику последовательно, а версия на Python использует тот же C++-ядро.
Работа с решёткой разбиений зависит только от фиксированного шаблона \((1,2,2,3,3,3,4,4,4,4)\), поэтому для данной задачи это предобработка постоянного размера. После этого построение решета простых до \(n\) требует \(O(n\log\log n)\) времени и \(O(n)\) памяти. Пусть \(P\) обозначает число различных профилей сумм блоков после объединения; \(P\) снова является константой, определяемой только условием задачи. Динамическое программирование для каждого профиля идёт лишь до порядка \(\sqrt n\), а более крупные коэффициенты восстанавливаются из линейной рекурренты порядка \(30\) за логарифмическое время. Поэтому итоговая асимптотика определяется главным образом решетом: \(O(n\log\log n)\) по времени и \(O(n)\) по памяти, а обработка профилей даёт лишь умеренный постоянный множитель.
الدالة \(F(n)\) تعدّ التفكيكات المقيّدة لـ \(n!\) من الشكل
$$n!=b_1\,b_2^2\,b_3^2\,b_4^3\,b_5^3\,b_6^3\,b_7^4\,b_8^4\,b_9^4\,b_{10}^4.$$
يُبنى الحساب على مرحلتين. في المرحلة الأولى نعامل المواضع العشرة على أنها مواضع موسومة، حتى يمكن ضبط حالات تساوي القواعد بطريقة منهجية بواسطة مبدأ الشمول والاستبعاد. وفي المرحلة الثانية نُلغي أثر تبديل العناصر داخل مجموعات الأسس المتساوية، لأن تبديل مربعيْن أو ثلاثة مكعبات أو أربع قوى رابعة لا يغيّر التفكيك نفسه. المطلوب هو حساب \(F(10^6)\bmod(10^9+7)\).
لنكتب نمط الأسس على الصورة
$$\alpha=(\alpha_1,\dots,\alpha_{10})=(1,2,2,3,3,3,4,4,4,4).$$
إذا وضعنا علامات مؤقتة على القواعد وسمّيناها \(b_1,\dots,b_{10}\)، فإن الصعوبة الحقيقية الوحيدة هي أن بعض هذه القواعد قد تتطابق. تعالج التطبيقات ذلك باستعمال معكوس Möbius على شبكة تقسيمات المجموعة المؤلفة من عشرة مواضع، مع فصل مساهمة كل عدد أولي على حدة.
لكل عدد أولي \(p\le n\)، تعطي صيغة ليجاندر
$$e_p=v_p(n!)=\sum_{k\ge 1}\left\lfloor\frac{n}{p^k}\right\rfloor.$$
الأوليات المختلفة مستقلة عن بعضها، ولذلك يتحلل العدّ الكلي بحسب مجموعة القيم \(\{e_p\}\). ولهذا يكفي تخزين جدول التكرارات
$$c_e=\#\{p\le n:\ v_p(n!)=e\}.$$
وبمجرد معرفة \(c_e\)، يصبح إسهام كل نمط تقسيم معتمدًا على رفع نفس المعامل المحلي \(g(e)\) إلى قوى مكررة.
افترض أن عدة مواضع موسومة تستعمل القاعدة نفسها. عندئذ يوصف هذا النمط بواسطة تقسيم \(\pi\) للمجموعة \(\{1,\dots,10\}\). كل كتلة \(B\in\pi\) تمثل قاعدة فعلية واحدة، ويكون مجموع الأسس المرتبطة بهذه القاعدة هو
$$S_B=\sum_{i\in B}\alpha_i.$$
إذن، بعد تثبيت \(\pi\)، لا تعود العلامات الأصلية مهمة إلا من خلال مجموعة مجاميع الكتل \(\{S_B\}\). وإذا أعطى تقسيمان مختلفان المتجه المرتب نفسه لمجاميع الكتل، فلهما دالة توليد محلية واحدة، ومن ثم يمكن دمجهما بجمع أوزان Möbius الخاصة بهما. هذا الدمج المسبق جزء أساسي من التنفيذ.
ثبّت عددًا أوليًا \(p\) له الأس \(e=e_p\) داخل \(n!\). إذا استلمت الكتلة \(B\) عددًا غير سالب \(u_B\) من نسخ \(p\) في قاعدتها المشتركة، فيجب أن يتحقق توازن الأسس
$$\sum_{B\in\pi} S_Bu_B=e.$$
عدد الحلول غير السالبة هو معامل السلسلة
$$G_\pi(x)=\prod_{B\in\pi}\frac{1}{1-x^{S_B}}=\sum_{m\ge 0} g_\pi(m)x^m.$$
ومن ثم فإن \(g_\pi(e)\) يساوي تمامًا عدد الطرق التي يمكن بها توزيع عدد أولي واحد قيمته \(e\) على القواعد مع احترام نمط التطابق \(\pi\).
لو جمعنا مساهمات جميع التقسيمات \(\pi\) مباشرةً، فسنسمح للقواعد المتساوية بالبقاء. لفرض أن القواعد العشر الموسومة مختلفة زوجيًا، نستخدم معكوس Möbius على شبكة التقسيمات. الوزن الموافق هو
$$\mu(\pi)=(-1)^{10-|\pi|}\prod_{B\in\pi}(|B|-1)!.$$
وبما أن الأعداد الأولية مستقلة، فإن الإسهام الكلي الموصوم للتقسيم \(\pi\) هو
$$W_\pi(n)=\prod_{p\le n} g_\pi(e_p)=\prod_{e\ge 1} g_\pi(e)^{c_e}.$$
وبالتالي يصبح عدد التفكيكات ذات القواعد الموسومة المختلفة زوجيًا
$$L(n)=\sum_{\pi}\mu(\pi)\,W_\pi(n).$$
في النموذج الموصوم نميّز بين موضعي الأس \(2\)، وبين المواضع الثلاثة للأس \(3\)، وبين المواضع الأربعة للأس \(4\). أما في المسألة الأصلية فلا يوجد هذا التمييز. لذلك فإن كل تفكيك مقيّد حقيقي يُحسب داخل \(L(n)\) بعدد مرات يساوي
$$2!\,3!\,4!=288$$
مرّة. إذن الجواب النهائي هو
$$F(n)=\frac{L(n)}{288}\pmod{10^9+7}.$$
وبما أن المودولو عدد أولي، فإن القسمة على \(288\) تُنفّذ بضرب المقلوب المعياري لـ \(288\).
عندما يكون الأس صغيرًا، يُحسب \(g_\pi(e)\) مباشرةً بطريقة الحقيبة غير المحدودة على مجاميع الكتل \(S_B\). وهذا يطابق تمامًا استخراج معاملات \(G_\pi(x)\).
أما عندما يكون الأس كبيرًا، فالملاحظة الحاسمة هي أن درجة مقام \(G_\pi(x)\) لا تتجاوز
$$1+2+2+3+3+3+4+4+4+4=30,$$
لأن مجموع الأسس الأصلية كلّه يساوي \(30\). فإذا كتبنا
$$Q_\pi(x)=\prod_{B\in\pi}(1-x^{S_B})=1+q_1x+\cdots+q_{30}x^{30},$$
فإن المعاملات تحقق العلاقة العودية الخطية
$$g_\pi(m)=-\sum_{j=1}^{30}q_j\,g_\pi(m-j)\qquad(m\ge 30).$$
وهذه الرتبة الثابتة هي ما يسمح بحساب المعاملات البعيدة بسرعة، بدلًا من مدّ البرمجة الديناميكية حتى أكبر أس ممكن وهو \(v_2(n!)\).
إذا كانت القواعد الموسومة كلها مختلفة، فإن كل كتلة تتكون من عنصر واحد فقط، وتصبح دالة التوليد المحلية
$$G(x)=\frac{1}{(1-x)(1-x^2)^2(1-x^3)^3(1-x^4)^4}.$$
يمكن قراءة بعض المعاملات مباشرة. لدينا \(g(1)=1\) لأن الأس \(1\) لا يمكن أن يأتي إلا من الموضع الأول. ولدينا أيضًا \(g(2)=3\)، لأن الأس \(2\) يمكن أن يتكون إما من \(2\cdot 1\) في الموضع الأول، أو من نسخة واحدة من أي موضع من موضعي التربيع.
هذا المثال الصغير يوضح فكرتين مهمتين في التنفيذ. أولًا، المعاملات المحلية هي فعلًا أعداد طرق تكوين مجموعات من مجاميع الكتل. وثانيًا، إذا كانت جميع مجاميع الكتل في نمط ما قابلة للقسمة على \(d>1\)، فحينها يكون \(g_\pi(1)=0\) تلقائيًا. ولأن \(n!\) عند الإدخال المستهدف \(n=10^6\) يحتوي على أوليات ذات valuation يساوي \(1\)، فإن مثل هذه الأنماط تُستبعد فورًا.
تتبع تطبيقات C++ وPython وJava السلسلة الرياضية نفسها. فهي تبدأ بتعداد جميع تقسيمات المواضع العشرة، ثم تحوّل كل تقسيم إلى متجه مرتب لمجاميع الكتل، وتدمج الأنماط المتطابقة، وتحفظ وزن Möbius الموافق لها. كما تحفظ القاسم المشترك الأكبر لمجاميع كل نمط حتى يمكن تجاهل الأنماط المستحيلة سريعًا عندما يظهر الأس \(1\) في جدول التكرارات.
بعد ذلك، تقوم الشيفرة بعمل غربال للأعداد الأولية حتى \(n\)، وتطبّق صيغة ليجاندر على كل عدد أولي، ثم تضغط النتيجة في جدول التكرارات \(c_e\). ولكل نمط باقٍ، تُحسب القيم الصغيرة من \(g_\pi(e)\) ببرمجة ديناميكية، بينما تُستخرج القيم الكبيرة من العلاقة العودية ذات الرتبة \(30\). يُجمع الإسهام \(\mu(\pi)\prod_e g_\pi(e)^{c_e}\) بترديد \(10^9+7\)، وفي النهاية يُضرب المجموع في المقلوب المعياري لـ \(288\). إصدار C++ يوازي بين الأنماط المستقلة، وإصدار Java ينفذ الحساب نفسه على خيط واحد، وإصدار Python يفوض التنفيذ إلى النواة نفسها المكتوبة بـ C++.
العمل الخاص بشبكة التقسيمات يعتمد فقط على نمط الأسس الثابت \((1,2,2,3,3,3,4,4,4,4)\)، ولذلك فهو معالجة أولية ذات حجم ثابت بالنسبة لهذه المسألة. بعد ذلك، فإن بناء غربال الأوليات حتى \(n\) يحتاج إلى \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة. إذا رمزنا بعدد أنماط مجاميع الكتل المختلفة بعد الدمج بالرمز \(P\)، فإن \(P\) نفسه ثابت خاص بهذه المسألة. مرحلة البرمجة الديناميكية لكل نمط تصل فقط إلى حدود \(\sqrt n\) تقريبًا، أما المعاملات الأكبر فتُستعاد بعلاقة عودية خطية من الرتبة \(30\) في زمن لوغاريتمي. لذلك تبقى الكلفة الأسيمبتوطية الكلية خاضعة للغربال: \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة، مع عامل ثابت إضافي معقول بسبب تقييم الأنماط.