For fixed integers \(m\) and \(n\), let \(F(m,n)\) denote the number of distinct integers that can be written in the form
$$a_1a_2\cdots a_n,\qquad 1\le a_i\le m.$$
The target case is \(F(30,10001)\) modulo \(10^9+7\). Directly exploring all \(30^{10001}\) sequences is impossible, and even storing all distinct products becomes unmanageable very quickly. The solution therefore uses a closed generating-function identity specialized to \(m=30\).
The key observation is that equal products have equal prime-exponent data. Once the problem is translated into exponent vectors, the sequence \(F(30,n)\) is encoded by a rational generating function, and the coefficient of \(x^n\) can be extracted explicitly.
Every integer \(a\) with \(1\le a\le 30\) has a unique factorization over the ten primes not exceeding \(30\):
$$2,3,5,7,11,13,17,19,23,29.$$
Write
$$a=\prod_{p\le 30} p^{e_p(a)}.$$
Then the product \(a_1a_2\cdots a_n\) is determined by the sum of these exponent vectors:
$$E(a_1,\dots,a_n)=\sum_{j=1}^{n}\bigl(e_p(a_j)\bigr)_{p\le 30}.$$
Two products are equal if and only if their exponent sums are equal. Therefore \(F(30,n)\) is exactly the number of lattice points in \(\mathbb{Z}_{\ge 0}^{10}\) that can be reached as sums of \(n\) generator vectors coming from the numbers \(1,2,\dots,30\). Multiplication has been converted into addition.
For the fixed bound \(m=30\), those reachable exponent vectors form a finitely generated commutative semigroup. Counting distinct products of length \(n\) is therefore equivalent to taking the coefficient of \(x^n\) in the corresponding Hilbert series.
The central structural identity used by the implementation is
$$\sum_{n\ge 0} F(30,n)x^n=\frac{1+19x+33x^2+6x^3}{(1-x)^{11}}.$$
The denominator \((1-x)^{11}\) shows that the sequence behaves like a polynomial sequence of degree \(10\), while the short numerator provides the exact initial corrections needed for the fixed generator set \(\{1,2,\dots,30\}\).
Use the standard series identity
$$\frac{1}{(1-x)^{11}}=\sum_{t\ge 0}\binom{t+10}{10}x^t.$$
Multiplying by the numerator shifts the indices of those coefficients, so for every \(n\ge 0\) we get
$$F(30,n)=\binom{n+10}{10}+19\binom{n+9}{10}+33\binom{n+8}{10}+6\binom{n+7}{10}.$$
If the upper index of a binomial coefficient is smaller than \(10\), that term is interpreted as \(0\). This makes the formula valid uniformly, including the small cases \(n=0,1,2\).
Once the generating function is known, the difficult combinatorics is over. For \(n=10001\), the desired count is just the weighted sum
$$F(30,10001)=\binom{10011}{10}+19\binom{10010}{10}+33\binom{10009}{10}+6\binom{10008}{10},$$
followed by reduction modulo \(10^9+7\). Instead of tracking a gigantic set of products, we only need four combinatorial terms.
For \(n=2\), the formula gives
$$F(30,2)=\binom{12}{10}+19\binom{11}{10}+33\binom{10}{10}+6\binom{9}{10}.$$
Since \(\binom{9}{10}=0\), this becomes
$$F(30,2)=66+19\cdot 11+33\cdot 1=66+209+33=308.$$
For \(n=3\), we similarly obtain
$$F(30,3)=\binom{13}{10}+19\binom{12}{10}+33\binom{11}{10}+6\binom{10}{10}=286+1254+363+6=1909.$$
These values agree with the explicit small-case checks used by the implementation, so they serve as practical confirmation that the closed form has been applied correctly.
The C++, Python, and Java implementations all evaluate the same closed formula. They precompute factorials and inverse factorials up to \(n+10\) modulo \(10^9+7\), which allows each binomial coefficient \(\binom{r}{10}\) to be recovered in constant time.
Because \(10^9+7\) is prime, the inverse factorial table is obtained from one modular inverse and a backward sweep, using Fermat's little theorem:
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
After that preprocessing, the implementation forms the weighted sum of the four shifted binomial terms with coefficients \(1\), \(19\), \(33\), and \(6\). The C++ implementation also verifies several small exact cases by brute force, including \(F(9,2)=36\), \(F(30,2)=308\), \(F(30,3)=1909\), and \(F(30,4)=8679\), before evaluating the large target input.
Let the requested length be \(n\). Building factorial and inverse-factorial tables up to \(n+10\) costs \(O(n)\) time and \(O(n)\) memory. The final evaluation uses only four binomial coefficients and a few modular multiplications, so it is \(O(1)\) after preprocessing. This is exponentially better than enumerating all \(30^n\) sequences or storing all distinct products directly.
Für feste ganze Zahlen \(m\) und \(n\) bezeichne \(F(m,n)\) die Anzahl verschiedener ganzer Zahlen, die sich in der Form
$$a_1a_2\cdots a_n,\qquad 1\le a_i\le m.$$
darstellen lassen. Gesucht ist der Fall \(F(30,10001)\) modulo \(10^9+7\). Eine direkte Untersuchung aller \(30^{10001}\) Folgen ist unmöglich, und schon die Menge aller verschiedenen Produkte wächst viel zu schnell. Deshalb verwendet die Lösung eine geschlossene erzeugende Funktion, die speziell für \(m=30\) gilt.
Die entscheidende Beobachtung ist, dass gleiche Produkte dieselben Primexponenten besitzen. Nach der Übersetzung in Exponentenvektoren wird die Folge \(F(30,n)\) durch eine rationale erzeugende Funktion beschrieben, und der Koeffizient von \(x^n\) kann explizit bestimmt werden.
Jede Zahl \(a\) mit \(1\le a\le 30\) besitzt eine eindeutige Zerlegung über die zehn Primzahlen bis \(30\):
$$2,3,5,7,11,13,17,19,23,29.$$
Wir schreiben
$$a=\prod_{p\le 30} p^{e_p(a)}.$$
Dann wird das Produkt \(a_1a_2\cdots a_n\) durch die Summe dieser Exponentenvektoren beschrieben:
$$E(a_1,\dots,a_n)=\sum_{j=1}^{n}\bigl(e_p(a_j)\bigr)_{p\le 30}.$$
Zwei Produkte sind genau dann gleich, wenn ihre Exponentensummen übereinstimmen. Damit ist \(F(30,n)\) genau die Anzahl der Gitterpunkte in \(\mathbb{Z}_{\ge 0}^{10}\), die als Summe von \(n\) Erzeugervektoren aus den Zahlen \(1,2,\dots,30\) erreichbar sind. Multiplikation wurde also in Addition überführt.
Für die feste Schranke \(m=30\) bilden diese erreichbaren Exponentenvektoren eine endlich erzeugte kommutative Halbgruppe. Das Zählen verschiedener Produkte der Länge \(n\) entspricht daher der Bestimmung des Koeffizienten von \(x^n\) in der zugehörigen Hilbert-Reihe.
Die zentrale Strukturformel der Implementierung lautet
$$\sum_{n\ge 0} F(30,n)x^n=\frac{1+19x+33x^2+6x^3}{(1-x)^{11}}.$$
Der Nenner \((1-x)^{11}\) zeigt, dass sich die Folge wie eine Polynomfolge vom Grad \(10\) verhält, während der kurze Zähler die exakten Anfangskorrekturen für die feste Erzeugermenge \(\{1,2,\dots,30\}\) liefert.
Verwendet wird die Standardidentität
$$\frac{1}{(1-x)^{11}}=\sum_{t\ge 0}\binom{t+10}{10}x^t.$$
Durch Multiplikation mit dem Zähler verschieben sich die Indizes der Koeffizienten, also gilt für alle \(n\ge 0\)
$$F(30,n)=\binom{n+10}{10}+19\binom{n+9}{10}+33\binom{n+8}{10}+6\binom{n+7}{10}.$$
Falls der obere Index eines Binomialkoeffizienten kleiner als \(10\) ist, wird der betreffende Term als \(0\) interpretiert. Dadurch funktioniert dieselbe Formel ohne Sonderfälle auch für kleine Werte wie \(n=0,1,2\).
Sobald die erzeugende Funktion bekannt ist, ist die schwere Kombinatorik erledigt. Für \(n=10001\) ist der gesuchte Wert einfach die gewichtete Summe
$$F(30,10001)=\binom{10011}{10}+19\binom{10010}{10}+33\binom{10009}{10}+6\binom{10008}{10},$$
anschließend reduziert modulo \(10^9+7\). Statt eine riesige Produktmenge zu verfolgen, benötigt man nur vier kombinatorische Terme.
Für \(n=2\) ergibt die Formel
$$F(30,2)=\binom{12}{10}+19\binom{11}{10}+33\binom{10}{10}+6\binom{9}{10}.$$
Da \(\binom{9}{10}=0\), folgt
$$F(30,2)=66+19\cdot 11+33\cdot 1=66+209+33=308.$$
Für \(n=3\) erhalten wir entsprechend
$$F(30,3)=\binom{13}{10}+19\binom{12}{10}+33\binom{11}{10}+6\binom{10}{10}=286+1254+363+6=1909.$$
Diese Werte stimmen mit den expliziten Kleinfallprüfungen der Implementierung überein und bestätigen damit praktisch, dass die geschlossene Formel korrekt eingesetzt wird.
Die Implementierungen in C++, Python und Java werten alle dieselbe geschlossene Formel aus. Dazu werden Fakultäten und inverse Fakultäten bis \(n+10\) modulo \(10^9+7\) vorab berechnet, sodass jeder Binomialkoeffizient \(\binom{r}{10}\) in konstanter Zeit verfügbar ist.
Da \(10^9+7\) eine Primzahl ist, wird die Tabelle der inversen Fakultäten aus einem modularen Inversen und einem Rückwärtsdurchlauf aufgebaut, gestützt auf den kleinen Satz von Fermat:
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
Nach dieser Vorverarbeitung bildet die Implementierung die gewichtete Summe der vier verschobenen Binomialterme mit den Koeffizienten \(1\), \(19\), \(33\) und \(6\). Die C++-Implementierung prüft außerdem mehrere kleine exakte Fälle per Brute Force, darunter \(F(9,2)=36\), \(F(30,2)=308\), \(F(30,3)=1909\) und \(F(30,4)=8679\), bevor der große Zielwert berechnet wird.
Sei \(n\) die gewünschte Länge. Das Aufbauen der Fakultäts- und Inversfakultätstabellen bis \(n+10\) benötigt \(O(n)\) Zeit und \(O(n)\) Speicher. Die abschließende Auswertung verwendet nur vier Binomialkoeffizienten und einige modulare Multiplikationen und kostet daher nach der Vorverarbeitung \(O(1)\). Das ist exponentiell besser als die Enumeration aller \(30^n\) Folgen oder das direkte Speichern aller verschiedenen Produkte.
Sabit \(m\) ve \(n\) için \(F(m,n)\),
$$a_1a_2\cdots a_n,\qquad 1\le a_i\le m.$$
şeklinde yazılabilen farklı tamsayıların sayısını göstersin. Hedef durum \(F(30,10001)\)'in \(10^9+7\) modundaki değeridir. Tüm \(30^{10001}\) dizisini tek tek incelemek imkansızdır; ayrıca farklı çarpımların kümesini doğrudan saklamak da çok hızlı büyür. Bu nedenle çözüm, \(m=30\) için geçerli kapalı bir üreteç fonksiyon kimliği kullanır.
Temel gözlem şudur: aynı çarpıma sahip iki ifade, asal çarpan üsleri bakımından da aynıdır. Problem üs vektörlerine çevrildiğinde \(F(30,n)\) dizisi rasyonel bir üreteç fonksiyonla temsil edilir ve \(x^n\)'in katsayısı açık biçimde çıkarılabilir.
\(1\le a\le 30\) aralığındaki her sayı, \(30\)'u aşmayan şu on asal üzerinden tekil biçimde çarpanlarına ayrılır:
$$2,3,5,7,11,13,17,19,23,29.$$
Şöyle yazalım:
$$a=\prod_{p\le 30} p^{e_p(a)}.$$
O zaman \(a_1a_2\cdots a_n\) çarpımı, bu üs vektörlerinin toplamı ile belirlenir:
$$E(a_1,\dots,a_n)=\sum_{j=1}^{n}\bigl(e_p(a_j)\bigr)_{p\le 30}.$$
İki çarpım ancak ve ancak asal üs toplamları aynıysa eşittir. Dolayısıyla \(F(30,n)\), \(1,2,\dots,30\) sayılarından gelen üreteç vektörlerinin \(n\) tanesinin toplamı olarak ulaşılabilen \(\mathbb{Z}_{\ge 0}^{10}\) kafes noktalarının sayısıdır. Yani çarpma işlemi toplamsal bir probleme dönüşmüştür.
Sabit \(m=30\) için ulaşılabilen üs vektörleri, sonlu sayıda üreteçle oluşan komütatif bir yarıgrup meydana getirir. Bu yüzden uzunluğu \(n\) olan farklı çarpımların sayısı, ilgili Hilbert serisindeki \(x^n\) katsayısına eşittir.
Uygulamanın kullandığı ana yapısal özdeşlik şudur:
$$\sum_{n\ge 0} F(30,n)x^n=\frac{1+19x+33x^2+6x^3}{(1-x)^{11}}.$$
Paydadaki \((1-x)^{11}\) ifadesi dizinin derece \(10\) civarında polinom benzeri davrandığını gösterir. Kısa pay ise \(\{1,2,\dots,30\}\) sabit üreteç kümesi için gereken başlangıç düzeltmelerini tam olarak taşır.
Standart seri özdeşliğini kullanırız:
$$\frac{1}{(1-x)^{11}}=\sum_{t\ge 0}\binom{t+10}{10}x^t.$$
Pay ile çarpınca katsayı indisleri kayar ve her \(n\ge 0\) için
$$F(30,n)=\binom{n+10}{10}+19\binom{n+9}{10}+33\binom{n+8}{10}+6\binom{n+7}{10}$$
sonucu çıkar. Bir binom katsayısının üst indisi \(10\)'dan küçükse ilgili terim \(0\) kabul edilir. Böylece aynı formül \(n=0,1,2\) gibi küçük durumlarda da özel işlem gerektirmez.
Üreteç fonksiyon bir kez bilindiğinde asıl kombinatorik zorluk bitmiş olur. \(n=10001\) için gereken değer sadece şu ağırlıklı toplamdır:
$$F(30,10001)=\binom{10011}{10}+19\binom{10010}{10}+33\binom{10009}{10}+6\binom{10008}{10}.$$
Daha sonra sonuç \(10^9+7\) modunda alınır. Devasa bir çarpım kümesini takip etmek yerine yalnızca dört kombinasyon terimi hesaplanır.
\(n=2\) için formül
$$F(30,2)=\binom{12}{10}+19\binom{11}{10}+33\binom{10}{10}+6\binom{9}{10}$$
verir. \(\binom{9}{10}=0\) olduğundan
$$F(30,2)=66+19\cdot 11+33\cdot 1=66+209+33=308$$
elde edilir. \(n=3\) için de benzer şekilde
$$F(30,3)=\binom{13}{10}+19\binom{12}{10}+33\binom{11}{10}+6\binom{10}{10}=286+1254+363+6=1909$$
çıkar. Bu değerler uygulamadaki küçük örnek kontrolleriyle uyuşur; dolayısıyla kapalı formülün doğru uygulandığını pratik olarak doğrular.
C++, Python ve Java uygulamaları aynı kapalı formülü hesaplar. Bunun için \(n+10\)'a kadar faktöriyel ve ters faktöriyel tabloları \(10^9+7\) modunda önceden oluşturulur; böylece her \(\binom{r}{10}\) değeri sabit zamanda elde edilir.
\(10^9+7\) asal olduğu için ters faktöriyel tablosu, tek bir modüler ters alma işlemi ve geriye doğru bir tarama ile kurulabilir. Burada Fermat'nın küçük teoremi kullanılır:
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
Bu ön hesap tamamlandıktan sonra uygulama, dört kaydırılmış binom terimini \(1\), \(19\), \(33\) ve \(6\) katsayılarıyla toplar. C++ uygulaması ayrıca \(F(9,2)=36\), \(F(30,2)=308\), \(F(30,3)=1909\) ve \(F(30,4)=8679\) gibi küçük tam değerleri brute-force ile doğrulayarak büyük girdiye geçmeden önce formülün doğru bağlandığını kontrol eder.
İstenen uzunluk \(n\) olsun. \(n+10\)'a kadar faktöriyel ve ters faktöriyel tablolarını kurmak \(O(n)\) zaman ve \(O(n)\) bellek gerektirir. Son değerlendirme yalnızca dört binom katsayısı ve birkaç modüler çarpma içerdiği için ön hesaptan sonra \(O(1)\) maliyetlidir. Bu, tüm \(30^n\) dizilerini üretmeye ya da farklı çarpımların tamamını saklamaya göre üstel derecede daha verimlidir.
Para enteros fijos \(m\) y \(n\), sea \(F(m,n)\) el número de enteros distintos que pueden escribirse como
$$a_1a_2\cdots a_n,\qquad 1\le a_i\le m.$$
El caso objetivo es \(F(30,10001)\) módulo \(10^9+7\). Explorar directamente las \(30^{10001}\) secuencias es imposible, y aun guardar el conjunto de productos distintos se vuelve inmanejable enseguida. Por eso la solución usa una identidad cerrada de función generadora especializada en \(m=30\).
La observación clave es que dos productos iguales tienen los mismos exponentes primos. Cuando el problema se traduce a vectores de exponentes, la sucesión \(F(30,n)\) queda codificada por una función generadora racional y el coeficiente de \(x^n\) puede extraerse de forma explícita.
Cada entero \(a\) con \(1\le a\le 30\) tiene una factorización única sobre los diez primos no mayores que \(30\):
$$2,3,5,7,11,13,17,19,23,29.$$
Escribimos
$$a=\prod_{p\le 30} p^{e_p(a)}.$$
Entonces el producto \(a_1a_2\cdots a_n\) queda determinado por la suma de esos vectores de exponentes:
$$E(a_1,\dots,a_n)=\sum_{j=1}^{n}\bigl(e_p(a_j)\bigr)_{p\le 30}.$$
Dos productos son iguales si y solo si coinciden sus sumas de exponentes. Por tanto, \(F(30,n)\) es exactamente el número de puntos de la retícula \(\mathbb{Z}_{\ge 0}^{10}\) que pueden alcanzarse como suma de \(n\) vectores generadores procedentes de \(1,2,\dots,30\). La multiplicación se ha convertido en un problema aditivo.
Para la cota fija \(m=30\), esos vectores alcanzables forman un semigrupo conmutativo finitamente generado. Contar productos distintos de longitud \(n\) equivale entonces a tomar el coeficiente de \(x^n\) en la serie de Hilbert correspondiente.
La identidad estructural central utilizada por la implementación es
$$\sum_{n\ge 0} F(30,n)x^n=\frac{1+19x+33x^2+6x^3}{(1-x)^{11}}.$$
El denominador \((1-x)^{11}\) muestra que la sucesión se comporta como una sucesión polinómica de grado \(10\), mientras que el numerador corto incorpora exactamente las correcciones iniciales necesarias para el conjunto fijo de generadores \(\{1,2,\dots,30\}\).
Usamos la identidad clásica
$$\frac{1}{(1-x)^{11}}=\sum_{t\ge 0}\binom{t+10}{10}x^t.$$
Al multiplicar por el numerador, los índices se desplazan y para todo \(n\ge 0\) obtenemos
$$F(30,n)=\binom{n+10}{10}+19\binom{n+9}{10}+33\binom{n+8}{10}+6\binom{n+7}{10}.$$
Si el índice superior de un coeficiente binomial es menor que \(10\), ese término se interpreta como \(0\). Así la misma fórmula vale sin excepciones también para \(n=0,1,2\).
Una vez conocida la función generadora, la parte combinatoria difícil ya terminó. Para \(n=10001\), el valor buscado es simplemente la suma ponderada
$$F(30,10001)=\binom{10011}{10}+19\binom{10010}{10}+33\binom{10009}{10}+6\binom{10008}{10},$$
y luego se reduce módulo \(10^9+7\). En vez de seguir un conjunto gigantesco de productos, solo hay que evaluar cuatro términos combinatorios.
Para \(n=2\), la fórmula produce
$$F(30,2)=\binom{12}{10}+19\binom{11}{10}+33\binom{10}{10}+6\binom{9}{10}.$$
Como \(\binom{9}{10}=0\), resulta
$$F(30,2)=66+19\cdot 11+33\cdot 1=66+209+33=308.$$
Para \(n=3\) obtenemos del mismo modo
$$F(30,3)=\binom{13}{10}+19\binom{12}{10}+33\binom{11}{10}+6\binom{10}{10}=286+1254+363+6=1909.$$
Estos valores coinciden con las comprobaciones exactas de casos pequeños utilizadas por la implementación y sirven como validación práctica de la fórmula cerrada.
Las implementaciones en C++, Python y Java evalúan la misma fórmula cerrada. Primero precalculan factoriales e inversos factoriales hasta \(n+10\) módulo \(10^9+7\), de modo que cada coeficiente binomial \(\binom{r}{10}\) pueda recuperarse en tiempo constante.
Como \(10^9+7\) es primo, la tabla de inversos factoriales se obtiene a partir de un único inverso modular y un recorrido hacia atrás, apoyándose en el pequeño teorema de Fermat:
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
Tras ese preprocesamiento, la implementación suma los cuatro términos binomiales desplazados con pesos \(1\), \(19\), \(33\) y \(6\). La implementación en C++ también verifica varios casos exactos pequeños por fuerza bruta, entre ellos \(F(9,2)=36\), \(F(30,2)=308\), \(F(30,3)=1909\) y \(F(30,4)=8679\), antes de evaluar la entrada grande.
Sea \(n\) la longitud pedida. Construir las tablas de factoriales e inversos factoriales hasta \(n+10\) cuesta \(O(n)\) tiempo y \(O(n)\) memoria. La evaluación final usa solo cuatro coeficientes binomiales y unas pocas multiplicaciones modulares, así que después del preproceso es \(O(1)\). Esto es exponencialmente mejor que enumerar las \(30^n\) secuencias o almacenar directamente todos los productos distintos.
对固定整数 \(m\) 和 \(n\)，记 \(F(m,n)\) 为所有形如
$$a_1a_2\cdots a_n,\qquad 1\le a_i\le m.$$
的乘积里，不同整数值的个数。这里要求的是 \(F(30,10001)\bmod(10^9+7)\)。如果直接枚举全部 \(30^{10001}\) 个序列，规模完全不可处理；即使只存储不同乘积的集合，也会很快爆炸。因此解法必须改用只针对 \(m=30\) 的闭式生成函数恒等式。
核心观察是：两个乘积相等，当且仅当它们的素因子指数总和相同。把问题改写成指数向量以后，序列 \(F(30,n)\) 可以由一个有理生成函数统一编码，而 \(x^n\) 的系数又可以显式写成若干二项式系数的线性组合。
每个满足 \(1\le a\le 30\) 的整数，都可以按照不超过 \(30\) 的十个素数唯一分解：
$$2,3,5,7,11,13,17,19,23,29.$$
写成
$$a=\prod_{p\le 30} p^{e_p(a)}.$$
于是乘积 \(a_1a_2\cdots a_n\) 由这些指数向量的和唯一决定：
$$E(a_1,\dots,a_n)=\sum_{j=1}^{n}\bigl(e_p(a_j)\bigr)_{p\le 30}.$$
根据算术基本定理，两个乘积相同，等价于它们在每个素数上的总指数都相同。因此 \(F(30,n)\) 就是 \(\mathbb{Z}_{\ge 0}^{10}\) 中可达点的个数，其中“可达”指的是把 \(1,2,\dots,30\) 对应的十维生成向量取 \(n\) 个后相加得到。原本的乘法计数问题就被转化成了一个加法格点计数问题。
当上界固定为 \(30\) 时，这些可达指数向量构成一个有限生成的交换半群。于是长度为 \(n\) 的不同乘积个数，正好是该半群 Hilbert 级数中 \(x^n\) 的系数。
实现所依赖的关键结构恒等式是
$$\sum_{n\ge 0} F(30,n)x^n=\frac{1+19x+33x^2+6x^3}{(1-x)^{11}}.$$
这里的分母 \((1-x)^{11}\) 说明这列数呈现出“十次多项式型”增长；分子只有三次，是因为在固定生成集合 \(\{1,2,\dots,30\}\) 的情况下，只需要有限个低阶修正项就能把整个序列精确描述出来。
标准恒等式
$$\frac{1}{(1-x)^{11}}=\sum_{t\ge 0}\binom{t+10}{10}x^t$$
给出了分母部分的系数。再乘上分子 \(1+19x+33x^2+6x^3\)，系数下标只会发生平移，所以对任意 \(n\ge 0\) 都有
$$F(30,n)=\binom{n+10}{10}+19\binom{n+9}{10}+33\binom{n+8}{10}+6\binom{n+7}{10}.$$
如果某个二项式系数的上标小于 \(10\)，就把该项看成 \(0\)。因此这个表达式对所有非负整数 \(n\) 都成立，不需要再单独分情况讨论小 \(n\) 的边界。
一旦生成函数写出，真正困难的组合分析就结束了。题目中的目标是 \(n=10001\)，于是只需计算下面四项并做带权求和：
$$F(30,10001)=\binom{10011}{10}+19\binom{10010}{10}+33\binom{10009}{10}+6\binom{10008}{10}.$$
最后再对 \(10^9+7\) 取模即可。也就是说，程序根本不需要显式构造庞大的乘积集合；它只要高效地求出四个二项式系数，就已经得到目标答案。
先看 \(n=2\)。公式给出
$$F(30,2)=\binom{12}{10}+19\binom{11}{10}+33\binom{10}{10}+6\binom{9}{10}.$$
因为 \(\binom{9}{10}=0\)，所以
$$F(30,2)=66+19\cdot 11+33\cdot 1=66+209+33=308.$$
再看 \(n=3\)：
$$F(30,3)=\binom{13}{10}+19\binom{12}{10}+33\binom{11}{10}+6\binom{10}{10}=286+1254+363+6=1909.$$
这两个数都和实现中的小规模精确校验一致，因此它们是非常直接的工作示例，也说明闭式公式确实与实际计数相符。
C++、Python 和 Java 三个实现都在做同一件事：先为二项式系数准备好模 \(10^9+7\) 的阶乘表和逆阶乘表，然后代入上面的四项闭式公式。由于最高只需要到 \(n+10\)，预处理范围也非常明确。
因为模数 \(10^9+7\) 是素数，所以逆元可以通过费马小定理得到：
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
实现先求出最大的那个阶乘的逆元，再倒推得到全部逆阶乘。这样每个 \(\binom{r}{10}\) 都能在常数时间内写成阶乘与逆阶乘的乘积。之后程序把四个平移后的二项式项按权重 \(1\)、\(19\)、\(33\)、\(6\) 相加，即可得到结果。C++ 实现还额外做了若干小样例的暴力校验，例如 \(F(9,2)=36\)、\(F(30,2)=308\)、\(F(30,3)=1909\)、\(F(30,4)=8679\)，用来确认公式和模运算逻辑已经正确接通。
设目标长度为 \(n\)。预处理到 \(n+10\) 的阶乘和逆阶乘需要 \(O(n)\) 时间与 \(O(n)\) 空间。预处理完成后，最终求值只包含四个二项式系数和少量模乘加法，因此时间复杂度是 \(O(1)\)。和显式枚举 \(30^n\) 个序列，或者维护所有不同乘积的集合相比，这个方法有数量级上的优势。
Для фиксированных целых \(m\) и \(n\) обозначим через \(F(m,n)\) количество различных целых чисел, представимых в виде
$$a_1a_2\cdots a_n,\qquad 1\le a_i\le m.$$
Нас интересует значение \(F(30,10001)\) по модулю \(10^9+7\). Прямой перебор всех \(30^{10001}\) последовательностей невозможен, а хранение множества всех различных произведений очень быстро становится нереалистичным. Поэтому решение опирается на замкнутую формулу через производящую функцию, специально полученную для \(m=30\).
Главное наблюдение состоит в том, что равные произведения имеют одинаковые суммарные показатели простых множителей. После перехода к векторам показателей последовательность \(F(30,n)\) кодируется рациональной производящей функцией, а коэффициент при \(x^n\) выписывается явно.
Каждое число \(a\) при \(1\le a\le 30\) единственным образом раскладывается по десяти простым числам, не превосходящим \(30\):
$$2,3,5,7,11,13,17,19,23,29.$$
Пишем
$$a=\prod_{p\le 30} p^{e_p(a)}.$$
Тогда произведение \(a_1a_2\cdots a_n\) полностью определяется суммой этих векторов показателей:
$$E(a_1,\dots,a_n)=\sum_{j=1}^{n}\bigl(e_p(a_j)\bigr)_{p\le 30}.$$
Два произведения совпадают тогда и только тогда, когда совпадают их суммарные показатели по всем простым. Следовательно, \(F(30,n)\) равно числу точек решетки \(\mathbb{Z}_{\ge 0}^{10}\), достижимых как сумма \(n\) порождающих векторов, соответствующих числам \(1,2,\dots,30\). То есть задача о произведениях превращается в аддитивную задачу о векторах.
При фиксированной границе \(m=30\) множество достижимых векторов образует конечно порожденную коммутативную полугруппу. Поэтому число различных произведений длины \(n\) совпадает с коэффициентом при \(x^n\) в соответствующем ряде Гильберта.
Ключевая структурная тождественность, используемая в реализации, имеет вид
$$\sum_{n\ge 0} F(30,n)x^n=\frac{1+19x+33x^2+6x^3}{(1-x)^{11}}.$$
Знаменатель \((1-x)^{11}\) показывает, что последовательность ведет себя как полиномиальная последовательность степени \(10\), а короткий числитель вносит точные начальные поправки для фиксированного набора генераторов \(\{1,2,\dots,30\}\).
Используем стандартную формулу
$$\frac{1}{(1-x)^{11}}=\sum_{t\ge 0}\binom{t+10}{10}x^t.$$
После умножения на числитель индексы просто сдвигаются, и для любого \(n\ge 0\) получаем
$$F(30,n)=\binom{n+10}{10}+19\binom{n+9}{10}+33\binom{n+8}{10}+6\binom{n+7}{10}.$$
Если верхний индекс биномиального коэффициента меньше \(10\), соответствующий член считается равным \(0\). Поэтому одна и та же формула работает без дополнительных оговорок и для малых значений \(n\).
Как только производящая функция известна, тяжелая комбинаторика фактически завершена. Для \(n=10001\) нужно лишь вычислить
$$F(30,10001)=\binom{10011}{10}+19\binom{10010}{10}+33\binom{10009}{10}+6\binom{10008}{10}$$
и затем взять результат по модулю \(10^9+7\). Вместо отслеживания гигантского множества произведений достаточно четырех комбинаторных слагаемых.
Для \(n=2\) формула дает
$$F(30,2)=\binom{12}{10}+19\binom{11}{10}+33\binom{10}{10}+6\binom{9}{10}.$$
Так как \(\binom{9}{10}=0\), имеем
$$F(30,2)=66+19\cdot 11+33\cdot 1=66+209+33=308.$$
Для \(n=3\) аналогично получается
$$F(30,3)=\binom{13}{10}+19\binom{12}{10}+33\binom{11}{10}+6\binom{10}{10}=286+1254+363+6=1909.$$
Эти значения совпадают с точными малыми проверками в реализации, так что они служат наглядным подтверждением правильного применения замкнутой формулы.
Реализации на C++, Python и Java вычисляют одну и ту же замкнутую формулу. Сначала они предвычисляют факториалы и обратные факториалы до \(n+10\) по модулю \(10^9+7\), чтобы каждый биномиальный коэффициент \(\binom{r}{10}\) получать за \(O(1)\).
Поскольку \(10^9+7\) является простым модулем, таблица обратных факториалов строится из одного модульного обратного и обратного прохода, используя малую теорему Ферма:
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
После этой подготовки программа складывает четыре сдвинутых биномиальных члена с весами \(1\), \(19\), \(33\) и \(6\). Реализация на C++ дополнительно проверяет несколько малых точных случаев грубой силой, включая \(F(9,2)=36\), \(F(30,2)=308\), \(F(30,3)=1909\) и \(F(30,4)=8679\), прежде чем вычислять целевое большое значение.
Пусть \(n\) — требуемая длина. Построение таблиц факториалов и обратных факториалов до \(n+10\) требует \(O(n)\) времени и \(O(n)\) памяти. Финальное вычисление использует только четыре биномиальных коэффициента и несколько модульных умножений, поэтому после предобработки занимает \(O(1)\). Это экспоненциально лучше, чем перечислять все \(30^n\) последовательностей или хранить все различные произведения напрямую.
لعددين صحيحين ثابتين \(m\) و\(n\)، نرمز بـ \(F(m,n)\) إلى عدد القيم الصحيحة المختلفة التي يمكن كتابتها على الصورة
$$a_1a_2\cdots a_n,\qquad 1\le a_i\le m.$$
الحالة المطلوبة هنا هي \(F(30,10001)\) بترديد \(10^9+7\). من المستحيل فحص جميع المتتاليات وعددها \(30^{10001}\)، وحتى تخزين مجموعة الجداءات المختلفة نفسها يصبح غير عملي بسرعة كبيرة. لذلك تعتمد الطريقة على هوية مغلقة لدالة مولدة متخصصة في الحالة \(m=30\).
الفكرة الأساسية هي أن جداءين متساويين يملكان مجموعات الأسس الأولية نفسها. بعد تحويل المسألة إلى متجهات أسس، تصبح السلسلة \(F(30,n)\) ممثلة بدالة مولدة نسبية، ويمكن استخراج معامل \(x^n\) منها بصورة صريحة.
كل عدد \(a\) يحقق \(1\le a\le 30\) يملك تحليلاً وحيداً إلى عوامل أولية باستعمال الأعداد الأولية العشرة التي لا تتجاوز \(30\):
$$2,3,5,7,11,13,17,19,23,29.$$
نكتب
$$a=\prod_{p\le 30} p^{e_p(a)}.$$
وعندئذ يتحدد الجداء \(a_1a_2\cdots a_n\) بمجموع هذه المتجهات:
$$E(a_1,\dots,a_n)=\sum_{j=1}^{n}\bigl(e_p(a_j)\bigr)_{p\le 30}.$$
يتساوى جداءان إذا وفقط إذا تساوت مجاميع الأسس الأولية فيهما. لذلك فإن \(F(30,n)\) يساوي عدد نقاط الشبكة في \(\mathbb{Z}_{\ge 0}^{10}\) التي يمكن الوصول إليها بوصفها مجموع \(n\) متجهاً مولداً ناتجاً عن الأعداد \(1,2,\dots,30\). وهكذا تتحول المسألة من الضرب إلى مسألة جمع في فضاء متجهات.
عندما يكون الحد الأعلى ثابتاً ويساوي \(30\)، فإن متجهات الأسس الممكنة تشكل شبه زمرة تبديلية مولدة بعدد منته من العناصر. ومن ثم فإن عدد الجداءات المختلفة ذات الطول \(n\) يساوي معامل \(x^n\) في متسلسلة Hilbert الموافقة.
الهوية البنيوية المركزية التي يعتمد عليها التنفيذ هي
$$\sum_{n\ge 0} F(30,n)x^n=\frac{1+19x+33x^2+6x^3}{(1-x)^{11}}.$$
المقام \((1-x)^{11}\) يبين أن السلسلة تتصرف كسلسلة متعددة حدود من الدرجة \(10\)، أما البسط القصير فيحمل التصحيحات الابتدائية الدقيقة اللازمة لمجموعة المولدات الثابتة \(\{1,2,\dots,30\}\).
نستخدم الهوية القياسية
$$\frac{1}{(1-x)^{11}}=\sum_{t\ge 0}\binom{t+10}{10}x^t.$$
وبعد ضربها في البسط، لا يحدث إلا إزاحة في الفهارس، لذلك نحصل لكل \(n\ge 0\) على
$$F(30,n)=\binom{n+10}{10}+19\binom{n+9}{10}+33\binom{n+8}{10}+6\binom{n+7}{10}.$$
إذا كان الحد العلوي لمعامل ثنائي أصغر من \(10\)، فنعتبر هذا الحد مساوياً للصفر. وبهذا تكون الصيغة صحيحة لجميع القيم غير السالبة لـ \(n\) من دون الحاجة إلى حالات خاصة منفصلة.
ما إن تُعرف الدالة المولدة حتى تنتهي الصعوبة التوافقية الأساسية. ففي الحالة \(n=10001\) يصبح المطلوب مجرد حساب المجموع الموزون
$$F(30,10001)=\binom{10011}{10}+19\binom{10010}{10}+33\binom{10009}{10}+6\binom{10008}{10}$$
ثم أخذ الناتج بترديد \(10^9+7\). أي إن البرنامج لا يبني مجموعة الجداءات الضخمة صراحة، بل يكتفي بأربعة حدود توافقية فقط.
عندما \(n=2\)، تعطينا الصيغة
$$F(30,2)=\binom{12}{10}+19\binom{11}{10}+33\binom{10}{10}+6\binom{9}{10}.$$
وبما أن \(\binom{9}{10}=0\)، فإن
$$F(30,2)=66+19\cdot 11+33\cdot 1=66+209+33=308.$$
وعندما \(n=3\) نحصل كذلك على
$$F(30,3)=\binom{13}{10}+19\binom{12}{10}+33\binom{11}{10}+6\binom{10}{10}=286+1254+363+6=1909.$$
هذه القيم تطابق الفحوص الصغيرة الدقيقة الموجودة في التنفيذ، ولذلك فهي مثال عملي يوضح أن الصيغة المغلقة قد طُبقت بشكل صحيح.
تقوم تطبيقات C++ وPython وJava جميعها بتقييم الصيغة المغلقة نفسها. أولاً تُحضِّر جداول المضاريب ومضاريبها العكسية حتى \(n+10\) بترديد \(10^9+7\)، وبذلك يمكن حساب كل معامل ثنائي \(\binom{r}{10}\) في زمن ثابت.
وبما أن \(10^9+7\) عدد أولي، يمكن توليد جدول المضاريب العكسية انطلاقاً من معكوس معياري واحد ثم مسح عكسي، اعتماداً على مبرهنة فيرما الصغرى:
$$a^{-1}\equiv a^{10^9+5}\pmod{10^9+7}.$$
بعد هذا التحضير تجمع الشيفرة الحدود الأربعة المزاحة بالأوزان \(1\) و\(19\) و\(33\) و\(6\). كما أن تنفيذ C++ يجري بعض الفحوص الدقيقة الصغيرة بطريقة brute force، مثل \(F(9,2)=36\) و\(F(30,2)=308\) و\(F(30,3)=1909\) و\(F(30,4)=8679\)، وذلك للتأكد من أن الصيغة مرتبطة بالحساب المعياري كما ينبغي قبل الانتقال إلى الإدخال الكبير.
إذا كانت القيمة المطلوبة لطول الجداء هي \(n\)، فإن بناء جداول المضاريب والمضاريب العكسية حتى \(n+10\) يكلف \(O(n)\) زمناً و\(O(n)\) ذاكرة. أما التقييم النهائي فلا يحتاج إلا إلى أربعة معاملات ثنائية وبعض الضربات المعيارية، ولذلك يصبح \(O(1)\) بعد مرحلة التهيئة. وهذا أفضل بكثير، وبصورة أسية في الفرق، من تعداد جميع المتتاليات وعددها \(30^n\) أو تخزين جميع الجداءات المختلفة مباشرة.