For an alphabet with \(\alpha\) symbols, we must count all incomplete words whose lengths range from \(0\) to \(n\). A word is called incomplete when at least one symbol of the alphabet does not appear in it. The final answer is required modulo \(10^9+7\).
If we tried to inspect every word directly, we would face \(\alpha^t\) possibilities at length \(t\), which is hopeless for the real parameters. The solution instead counts words by inclusion-exclusion, then sums those counts across all lengths in one algebraic expression.
Let \(I_t(\alpha)\) be the number of incomplete words of exact length \(t\), and let
$$T(\alpha,n)=\sum_{t=0}^{n} I_t(\alpha).$$
The goal is to evaluate \(T(\alpha,n)\) efficiently.
For a fixed length \(t\), there are exactly
$$\alpha^t$$
words over the full alphabet, because each of the \(t\) positions can use any of the \(\alpha\) symbols.
Among these words, some are complete and use every symbol at least once. If \(C_t(\alpha)\) denotes the number of complete words of length \(t\), then the incomplete words are simply the complement:
$$I_t(\alpha)=\alpha^t-C_t(\alpha).$$
For each symbol, consider the event that this symbol is missing. If we choose a set of exactly \(j\) symbols that are forbidden, then the word may use only the remaining \(\alpha-j\) symbols, so there are
$$ (\alpha-j)^t $$
such words.
By inclusion-exclusion, the number of complete words of length \(t\) is
$$C_t(\alpha)=\sum_{j=0}^{\alpha}(-1)^j\binom{\alpha}{j}(\alpha-j)^t.$$
Therefore
$$I_t(\alpha)=\alpha^t-C_t(\alpha)=\sum_{j=1}^{\alpha}(-1)^{j+1}\binom{\alpha}{j}(\alpha-j)^t.$$
Now reindex with \(k=\alpha-j\). Then \(k\) runs from \(0\) to \(\alpha-1\), and we obtain the form used by the implementations:
$$I_t(\alpha)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
This formula already explains why the summation stops at \(\alpha-1\): the missing \(k=\alpha\) term corresponds to the full alphabet and is exactly what disappears when we pass from complete words to incomplete words.
Insert the fixed-length formula into the outer sum:
$$T(\alpha,n)=\sum_{t=0}^{n}\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
Because the summation is finite, we may swap the order:
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}\sum_{t=0}^{n}k^t.$$
Define the geometric block
$$G_k(n)=\sum_{t=0}^{n}k^t.$$
Then
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}G_k(n).$$
The three cases for \(G_k(n)\) are
$$G_k(n)= \begin{cases} 1, & k=0,\\ n+1, & k=1,\\ \dfrac{k^{n+1}-1}{k-1}, & k\ge 2. \end{cases}$$
The case \(k=0\) is special because only the empty word contributes: \(0^0\) is interpreted combinatorially as \(1\), while \(0^t=0\) for \(t>0\). The case \(k=1\) is also special because there is exactly one word at every length.
The answer is required modulo the prime
$$M=10^9+7.$$
For the actual parameters, \(\alpha<M\), so every integer \(1,2,\dots,\alpha\) has a modular inverse modulo \(M\). This makes two parts efficient.
First, the geometric term for \(k\ge 2\) becomes
$$G_k(n)\equiv \left(k^{n+1}-1\right)(k-1)^{-1}\pmod M,$$
where \(k^{n+1}\) is obtained by fast exponentiation.
Second, the binomial coefficients are generated incrementally instead of by factorial tables:
$$\binom{\alpha}{0}=1,\qquad \binom{\alpha}{k+1}=\binom{\alpha}{k}\cdot\frac{\alpha-k}{k+1}.$$
Modulo \(M\), division by \(k+1\) is replaced by multiplication with the modular inverse of \(k+1\). This is exactly why the code precomputes inverses from \(1\) to \(\alpha\).
For \(\alpha=3\), the transformed formula is
$$T(3,4)=\sum_{k=0}^{2}(-1)^{4-k}\binom{3}{k}G_k(4).$$
Now evaluate each geometric block:
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31.$$
So
$$T(3,4)=\binom{3}{0}\cdot 1-\binom{3}{1}\cdot 5+\binom{3}{2}\cdot 31=1-15+93=79.$$
This also matches the direct length-by-length count:
$$I_0=1,\quad I_1=3,\quad I_2=9,\quad I_3=21,\quad I_4=45,\quad 1+3+9+21+45=79.$$
The example is useful because it checks both the combinatorial interpretation and the algebraic transformation used by the code.
The C++, Python, and Java implementations all evaluate the same summation formula modulo \(10^9+7\). They first build modular inverses for the integers \(1\) through \(\alpha\), then generate the binomial coefficients \(\binom{\alpha}{k}\) one after another with the multiplicative recurrence above. This avoids storing factorial tables for such a large alphabet size.
Next, the implementation loops over \(k=0,1,\dots,\alpha-1\). For each \(k\), it evaluates the geometric block \(G_k(n)\). The cases \(k=0\) and \(k=1\) are handled directly, while \(k\ge 2\) uses fast modular exponentiation together with the inverse of \(k-1\).
Each term is multiplied by the corresponding binomial coefficient and inserted with alternating sign. The C++ implementation additionally splits the \(k\)-range across several threads for large inputs, but the mathematical expression is identical in all three languages.
Precomputing modular inverses takes \(O(\alpha)\) time and \(O(\alpha)\) memory. Generating all binomial coefficients also takes \(O(\alpha)\) time and \(O(\alpha)\) memory. The final summation has \(\alpha\) terms, and for every \(k\ge 2\) it performs one fast exponentiation costing \(O(\log n)\). Therefore the overall running time is
$$O(\alpha\log n),$$
with total memory usage
$$O(\alpha).$$
Parallel execution in the C++ version improves wall-clock time on large machines but does not change the asymptotic bound.
Für ein Alphabet mit \(\alpha\) Symbolen soll die Anzahl aller unvollständigen Wörter der Längen \(0\) bis \(n\) bestimmt werden. Ein Wort heißt unvollständig, wenn mindestens ein Symbol des Alphabets darin überhaupt nicht vorkommt. Das Ergebnis wird modulo \(10^9+7\) verlangt.
Eine direkte Aufzählung wäre unmöglich, denn schon für feste Länge \(t\) gibt es \(\alpha^t\) Wörter. Deshalb zählt die Lösung nicht die Wörter selbst, sondern formt das Problem mit Inklusion-Exklusion und einer geometrischen Summe in eine effizient berechenbare Formel um.
Sei \(I_t(\alpha)\) die Anzahl unvollständiger Wörter der exakten Länge \(t\). Gesucht ist
$$T(\alpha,n)=\sum_{t=0}^{n} I_t(\alpha).$$
Für eine feste Länge \(t\) gibt es insgesamt
$$\alpha^t$$
Wörter, weil an jeder der \(t\) Positionen eines von \(\alpha\) Symbolen stehen darf.
Die unvollständigen Wörter sind das Komplement der vollständigen Wörter. Bezeichnet \(C_t(\alpha)\) deren Anzahl, so gilt:
$$I_t(\alpha)=\alpha^t-C_t(\alpha).$$
Wähle \(j\) Symbole, die verboten sein sollen. Dann dürfen nur noch \(\alpha-j\) Symbole benutzt werden, also gibt es
$$(\alpha-j)^t$$
solche Wörter.
Mit Inklusion-Exklusion erhält man für die vollständigen Wörter
$$C_t(\alpha)=\sum_{j=0}^{\alpha}(-1)^j\binom{\alpha}{j}(\alpha-j)^t.$$
Folglich gilt
$$I_t(\alpha)=\alpha^t-C_t(\alpha)=\sum_{j=1}^{\alpha}(-1)^{j+1}\binom{\alpha}{j}(\alpha-j)^t.$$
Mit der Umnummerierung \(k=\alpha-j\) folgt genau die Gestalt, die auch im Programm auftaucht:
$$I_t(\alpha)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
Dass die Summe bei \(\alpha-1\) endet, ist also kein Zufall: Der Term \(k=\alpha\) gehört zur vollständigen Nutzung des ganzen Alphabets und verschwindet beim Übergang zum Komplement.
Setzt man die Formel für feste Länge in die Gesamtsumme ein, so erhält man
$$T(\alpha,n)=\sum_{t=0}^{n}\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
Da beide Summen endlich sind, darf man die Reihenfolge vertauschen:
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}\sum_{t=0}^{n}k^t.$$
Definiere
$$G_k(n)=\sum_{t=0}^{n}k^t.$$
Dann wird die Aufgabe zu
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}G_k(n).$$
Die geometrische Summe hat die Form
$$G_k(n)= \begin{cases} 1, & k=0,\\ n+1, & k=1,\\ \dfrac{k^{n+1}-1}{k-1}, & k\ge 2. \end{cases}$$
Bei \(k=0\) trägt nur das leere Wort bei, deshalb ist \(G_0(n)=1\). Bei \(k=1\) gibt es für jede Länge genau ein Wort, also \(G_1(n)=n+1\).
Gearbeitet wird modulo
$$M=10^9+7.$$
Da für die echten Parameter \(\alpha<M\) gilt, besitzt jede Zahl \(1,2,\dots,\alpha\) ein Inverses modulo \(M\). Das ist für zwei Teile entscheidend.
Erstens wird für \(k\ge 2\)
$$G_k(n)\equiv \left(k^{n+1}-1\right)(k-1)^{-1}\pmod M$$
verwendet, wobei \(k^{n+1}\) per schneller modularer Exponentiation berechnet wird.
Zweitens werden die Binomialkoeffizienten iterativ erzeugt:
$$\binom{\alpha}{0}=1,\qquad \binom{\alpha}{k+1}=\binom{\alpha}{k}\cdot\frac{\alpha-k}{k+1}.$$
Im Modulo-Rechnen ersetzt man die Division durch Multiplikation mit dem inversen Element von \(k+1\). Genau deshalb berechnet die Implementierung die Inversen linear vor.
Hier lautet die transformierte Formel
$$T(3,4)=\sum_{k=0}^{2}(-1)^{4-k}\binom{3}{k}G_k(4).$$
Die einzelnen geometrischen Summen sind
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31.$$
Daraus folgt
$$T(3,4)=\binom{3}{0}\cdot 1-\binom{3}{1}\cdot 5+\binom{3}{2}\cdot 31=1-15+93=79.$$
Zur Kontrolle kann man auch nach Längen zählen:
$$I_0=1,\quad I_1=3,\quad I_2=9,\quad I_3=21,\quad I_4=45,\quad 1+3+9+21+45=79.$$
Damit ist die Formel nicht nur algebraisch korrekt, sondern auch kombinatorisch plausibel.
Die C++-, Python- und Java-Implementierungen werten alle dieselbe Summenformel modulo \(10^9+7\) aus. Zuerst werden die modularen Inversen für \(1\) bis \(\alpha\) erzeugt. Anschließend werden daraus die Binomialkoeffizienten \(\binom{\alpha}{k}\) schrittweise aufgebaut, sodass keine großen Fakultätstabellen nötig sind.
Danach läuft die Implementierung über alle \(k=0,1,\dots,\alpha-1\). Für jedes \(k\) wird der Block \(G_k(n)\) ausgewertet: direkt für \(k=0\) und \(k=1\), sonst über schnelle Exponentiation und das Inverse von \(k-1\). Der entsprechende Beitrag wird mit alternierendem Vorzeichen zur Gesamtsumme addiert.
Die C++-Version verteilt diese letzte Summation bei großen Eingaben zusätzlich auf mehrere Threads. Mathematisch bleibt das Verfahren in allen drei Sprachen jedoch identisch.
Die Vorberechnung der Inversen benötigt \(O(\alpha)\) Zeit und \(O(\alpha)\) Speicher. Dasselbe gilt für die iterativ erzeugten Binomialkoeffizienten. In der Hauptsumme gibt es \(\alpha\) Terme, und jeder Term mit \(k\ge 2\) benötigt eine modulare Potenzierung in \(O(\log n)\). Insgesamt ergibt sich daher
$$O(\alpha\log n)$$
Zeit und
$$O(\alpha)$$
Speicher. Parallelisierung verkürzt nur die Laufzeit in der Praxis, nicht die asymptotische Ordnung.
\(\alpha\) harfli bir alfabe için, uzunluğu \(0\) ile \(n\) arasında olan tüm eksik kelimelerin sayısı istenir. Bir kelime, alfabedeki en az bir sembol hiç görünmüyorsa eksik kabul edilir. Sonuç \(10^9+7\) modunda verilir.
Doğrudan sayım mümkün değildir; çünkü yalnızca sabit bir \(t\) uzunluğu için bile \(\alpha^t\) farklı kelime vardır. Bu yüzden çözüm, tek tek kelimeleri üretmek yerine dahil etme-hariç tutma ve geometrik seri yardımıyla kapalı bir toplam elde eder.
Uzunluğu tam olarak \(t\) olan eksik kelime sayısını \(I_t(\alpha)\) ile gösterelim. Aranan toplam
$$T(\alpha,n)=\sum_{t=0}^{n} I_t(\alpha)$$
şeklindedir.
Uzunluk \(t\) sabitken toplam kelime sayısı
$$\alpha^t$$
olur; çünkü her konumda \(\alpha\) seçim vardır.
Tüm harfleri en az bir kez kullanan tam kelime sayısını \(C_t(\alpha)\) ile gösterirsek, eksik kelimeler bunun tüm kelimelerden çıkarılmasıyla elde edilir:
$$I_t(\alpha)=\alpha^t-C_t(\alpha).$$
Tam olarak \(j\) harfin kullanılmasının yasaklandığını düşünelim. O zaman yalnızca kalan \(\alpha-j\) harf kullanılabilir ve böyle kelime sayısı
$$(\alpha-j)^t$$
olur.
Dahil etme-hariç tutma ilkesine göre tam kelime sayısı
$$C_t(\alpha)=\sum_{j=0}^{\alpha}(-1)^j\binom{\alpha}{j}(\alpha-j)^t$$
şeklindedir. Dolayısıyla
$$I_t(\alpha)=\alpha^t-C_t(\alpha)=\sum_{j=1}^{\alpha}(-1)^{j+1}\binom{\alpha}{j}(\alpha-j)^t.$$
Şimdi \(k=\alpha-j\) dönüşümünü yaparsak, uygulamaların kullandığı biçim ortaya çıkar:
$$I_t(\alpha)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
Toplamın \(\alpha\) yerine \(\alpha-1\)'de bitmesi önemlidir: \(k=\alpha\) terimi tüm alfabenin kullanıldığı duruma karşılık gelir ve tamamlayandan eksik kelime sayısına geçerken doğal olarak yok olur.
Şimdi bu ifadeyi \(0\) ile \(n\) arasındaki tüm uzunluklar üzerinde toplayalım:
$$T(\alpha,n)=\sum_{t=0}^{n}\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
Sonlu toplamlar olduğu için sıralamayı değiştirebiliriz:
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}\sum_{t=0}^{n}k^t.$$
Burada
$$G_k(n)=\sum_{t=0}^{n}k^t$$
tanımını yapalım. Böylece
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}G_k(n).$$
Geometrik blok şu kapalı forma sahiptir:
$$G_k(n)= \begin{cases} 1, & k=0,\\ n+1, & k=1,\\ \dfrac{k^{n+1}-1}{k-1}, & k\ge 2. \end{cases}$$
\(k=0\) durumu yalnızca boş kelimeden gelir; \(k=1\) durumunda ise her uzunluk için tam olarak bir kelime vardır.
Hesaplar
$$M=10^9+7$$
asal modunda yapılır. Gerçek parametrelerde \(\alpha<M\) olduğundan \(1,2,\dots,\alpha\) sayılarının hepsinin modüler tersi vardır.
Böylece \(k\ge 2\) için
$$G_k(n)\equiv \left(k^{n+1}-1\right)(k-1)^{-1}\pmod M$$
yazılabilir. Burada \(k^{n+1}\) hızlı üs alma ile hesaplanır.
Ayrıca binom katsayıları da artımlı olarak üretilir:
$$\binom{\alpha}{0}=1,\qquad \binom{\alpha}{k+1}=\binom{\alpha}{k}\cdot\frac{\alpha-k}{k+1}.$$
Mod altında bölme yerine \(k+1\)'in modüler tersiyle çarpma yapılır. Bu nedenle uygulamalar önce tersleri hesaplar, sonra tüm binom katsayılarını sırayla üretir.
Formül
$$T(3,4)=\sum_{k=0}^{2}(-1)^{4-k}\binom{3}{k}G_k(4)$$
olur.
Geometrik toplamlar:
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31.$$
Dolayısıyla
$$T(3,4)=\binom{3}{0}\cdot 1-\binom{3}{1}\cdot 5+\binom{3}{2}\cdot 31=1-15+93=79.$$
Bunu doğrudan uzunluklara göre de görebiliriz:
$$I_0=1,\quad I_1=3,\quad I_2=9,\quad I_3=21,\quad I_4=45,\quad 1+3+9+21+45=79.$$
Bu örnek, formülün hem kombinatorik anlamını hem de kodda kullanılan dönüşümü doğrular.
C++, Python ve Java uygulamaları aynı matematiksel toplamı \(10^9+7\) modunda hesaplar. Önce \(1\) ile \(\alpha\) arasındaki sayılar için modüler tersler üretilir. Ardından bu tersler kullanılarak \(\binom{\alpha}{k}\) katsayıları yinelemeli biçimde hesaplanır; böylece devasa faktöriyel dizilerine gerek kalmaz.
Sonra uygulama \(k=0,1,\dots,\alpha-1\) boyunca dolaşır. Her \(k\) için \(G_k(n)\) değerlendirilir: \(k=0\) ve \(k=1\) için doğrudan, diğer durumlarda hızlı modüler üs alma ve \(k-1\)'in tersi ile. Her terim ilgili işaretiyle ana toplama eklenir.
C++ uygulaması, giriş çok büyük olduğunda bu son toplamı birden çok çekirdeğe bölebilir. Ancak kullanılan formül ve elde edilen sonuç üç dilde de aynıdır.
Modüler terslerin ön hesabı \(O(\alpha)\) zaman ve \(O(\alpha)\) bellek gerektirir. Binom katsayılarının üretilmesi de aynı maliyettedir. Ana toplamda \(\alpha\) terim vardır ve \(k\ge 2\) olan her terim için hızlı üs alma nedeniyle \(O(\log n)\) iş yapılır. Bu yüzden toplam zaman karmaşıklığı
$$O(\alpha\log n)$$
ve bellek kullanımı
$$O(\alpha)$$
olur. C++ tarafındaki paralelleştirme pratik süreyi azaltır, fakat asimptotik büyüklüğü değiştirmez.
Para un alfabeto de \(\alpha\) símbolos, debemos contar todas las palabras incompletas cuyas longitudes van de \(0\) a \(n\). Una palabra es incompleta si al menos un símbolo del alfabeto no aparece en ella. La respuesta final se toma módulo \(10^9+7\).
Enumerar palabras directamente es inviable, porque para una longitud fija \(t\) ya existen \(\alpha^t\) posibilidades. La solución reorganiza el conteo con inclusión-exclusión y después suma todas las longitudes mediante una serie geométrica.
Sea \(I_t(\alpha)\) el número de palabras incompletas de longitud exacta \(t\). Lo que se busca es
$$T(\alpha,n)=\sum_{t=0}^{n} I_t(\alpha).$$
Si la longitud es \(t\), el número total de palabras es
$$\alpha^t,$$
porque cada una de las \(t\) posiciones admite cualquiera de los \(\alpha\) símbolos.
Si \(C_t(\alpha)\) representa el número de palabras completas de longitud \(t\), entonces las incompletas forman el complemento:
$$I_t(\alpha)=\alpha^t-C_t(\alpha).$$
Supongamos que fijamos \(j\) símbolos prohibidos. Entonces la palabra solo puede usar los \(\alpha-j\) símbolos restantes, y el número de palabras posibles es
$$(\alpha-j)^t.$$
Por el principio de inclusión-exclusión, el número de palabras completas vale
$$C_t(\alpha)=\sum_{j=0}^{\alpha}(-1)^j\binom{\alpha}{j}(\alpha-j)^t.$$
En consecuencia,
$$I_t(\alpha)=\alpha^t-C_t(\alpha)=\sum_{j=1}^{\alpha}(-1)^{j+1}\binom{\alpha}{j}(\alpha-j)^t.$$
Si reindexamos con \(k=\alpha-j\), obtenemos exactamente la forma usada por la implementación:
$$I_t(\alpha)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
Esto explica por qué el índice máximo es \(\alpha-1\): el término \(k=\alpha\) corresponde a no excluir ninguna letra y desaparece al pasar del conteo de palabras completas al de palabras incompletas.
Ahora sumamos desde \(t=0\) hasta \(t=n\):
$$T(\alpha,n)=\sum_{t=0}^{n}\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
Como la suma es finita, podemos intercambiar el orden:
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}\sum_{t=0}^{n}k^t.$$
Definimos
$$G_k(n)=\sum_{t=0}^{n}k^t.$$
Entonces
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}G_k(n).$$
La parte geométrica es
$$G_k(n)= \begin{cases} 1, & k=0,\\ n+1, & k=1,\\ \dfrac{k^{n+1}-1}{k-1}, & k\ge 2. \end{cases}$$
Cuando \(k=0\), solo contribuye la palabra vacía. Cuando \(k=1\), hay exactamente una palabra por cada longitud.
Todo se calcula módulo
$$M=10^9+7.$$
En los parámetros reales del problema se cumple \(\alpha<M\), así que cada número \(1,2,\dots,\alpha\) posee inverso modular.
Para \(k\ge 2\), la suma geométrica se evalúa como
$$G_k(n)\equiv \left(k^{n+1}-1\right)(k-1)^{-1}\pmod M,$$
y la potencia \(k^{n+1}\) se obtiene con exponenciación rápida.
Además, los coeficientes binomiales se generan de forma incremental:
$$\binom{\alpha}{0}=1,\qquad \binom{\alpha}{k+1}=\binom{\alpha}{k}\cdot\frac{\alpha-k}{k+1}.$$
En aritmética modular, la división por \(k+1\) se sustituye por la multiplicación por su inverso. Así se evita construir tablas gigantes de factoriales.
La fórmula queda
$$T(3,4)=\sum_{k=0}^{2}(-1)^{4-k}\binom{3}{k}G_k(4).$$
Calculamos:
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31.$$
Por tanto,
$$T(3,4)=\binom{3}{0}\cdot 1-\binom{3}{1}\cdot 5+\binom{3}{2}\cdot 31=1-15+93=79.$$
El mismo resultado aparece si contamos por longitud:
$$I_0=1,\quad I_1=3,\quad I_2=9,\quad I_3=21,\quad I_4=45,\quad 1+3+9+21+45=79.$$
Este ejemplo muestra que la transformación algebraica coincide con la interpretación combinatoria original.
Las implementaciones en C++, Python y Java evalúan exactamente la misma suma módulo \(10^9+7\). Primero calculan los inversos modulares de \(1\) a \(\alpha\). Después generan secuencialmente los coeficientes \(\binom{\alpha}{k}\) usando la relación multiplicativa, lo que evita arreglos de factoriales de tamaño enorme.
Luego recorren \(k=0,1,\dots,\alpha-1\). Para cada \(k\), calculan \(G_k(n)\): de manera directa en los casos \(k=0\) y \(k=1\), y con exponenciación rápida e inverso modular cuando \(k\ge 2\). Cada término se incorpora a la suma total con el signo alternante correcto.
La versión en C++ puede repartir el rango de \(k\) entre varios hilos cuando la entrada es grande, pero el algoritmo matemático es el mismo en los tres lenguajes.
La precalculación de inversos modulares requiere \(O(\alpha)\) tiempo y \(O(\alpha)\) memoria. La generación de todos los coeficientes binomiales también cuesta \(O(\alpha)\). En la suma principal hay \(\alpha\) términos, y cada uno con \(k\ge 2\) usa una exponenciación rápida de costo \(O(\log n)\). En conjunto, la complejidad total es
$$O(\alpha\log n),$$
con memoria
$$O(\alpha).$$
La paralelización de la implementación en C++ mejora el tiempo real de ejecución, pero no cambia el orden asintótico.
给定一个大小为 \(\alpha\) 的字母表，我们要统计长度从 \(0\) 到 \(n\) 的所有“不完整单词”总数。所谓不完整，是指这个单词没有把字母表中的每个符号都至少使用一次，也就是至少缺少一个字母。最终答案对 \(10^9+7\) 取模。
如果直接枚举单词，那么长度为 \(t\) 时就有 \(\alpha^t\) 种可能，在真实参数下完全不可行。因此解法不去逐个构造单词，而是先用容斥原理计算固定长度的不完整单词数，再把不同长度的结果合并成一个可以高效求值的总和。
记长度恰好为 \(t\) 的不完整单词数为 \(I_t(\alpha)\)，题目要求的是
$$T(\alpha,n)=\sum_{t=0}^{n} I_t(\alpha).$$
如果长度固定为 \(t\)，那么每个位置都可以从 \(\alpha\) 个符号中任选一个，所以总单词数是
$$\alpha^t.$$
其中一部分单词会把所有字母都至少用到一次，这类单词可以称为“完整单词”。如果把这部分数量记为 \(C_t(\alpha)\)，那么不完整单词数就是它的补集：
$$I_t(\alpha)=\alpha^t-C_t(\alpha).$$
因此真正的难点在于如何高效地数出完整单词，而不是直接数不完整单词。
对每个字母，考虑“这个字母没有出现”这个事件。如果指定有 \(j\) 个字母被禁止出现，那么单词只能从剩下的 \(\alpha-j\) 个字母中选择，因此这样的单词一共有
$$(\alpha-j)^t$$
个。
按容斥原理，长度为 \(t\) 的完整单词数为
$$C_t(\alpha)=\sum_{j=0}^{\alpha}(-1)^j\binom{\alpha}{j}(\alpha-j)^t.$$
于是
$$I_t(\alpha)=\alpha^t-C_t(\alpha)=\sum_{j=1}^{\alpha}(-1)^{j+1}\binom{\alpha}{j}(\alpha-j)^t.$$
再令 \(k=\alpha-j\)，就得到程序实际使用的形式：
$$I_t(\alpha)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
这个变形很关键，因为它把“缺少多少个字母”的视角，转成了“只允许使用 \(k\) 个字母”的视角。上限之所以是 \(\alpha-1\)，是因为 \(k=\alpha\) 对应“所有字母都可用”，那部分已经被完整单词的补集处理掉了。
将固定长度公式从 \(t=0\) 累加到 \(t=n\)，得到
$$T(\alpha,n)=\sum_{t=0}^{n}\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
由于这里都是有限求和，可以交换求和次序：
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}\sum_{t=0}^{n}k^t.$$
定义几何求和块
$$G_k(n)=\sum_{t=0}^{n}k^t.$$
于是总答案变成
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}G_k(n).$$
这里的 \(G_k(n)\) 有三个自然情况：
$$G_k(n)= \begin{cases} 1, & k=0,\\ n+1, & k=1,\\ \dfrac{k^{n+1}-1}{k-1}, & k\ge 2. \end{cases}$$
\(k=0\) 时，只能形成空单词，所以总贡献只有长度 \(0\) 的那一项。\(k=1\) 时，每个长度都只有一个单词，因此总和就是 \(n+1\)。\(k\ge 2\) 时则是标准的等比数列求和公式。
题目要求模
$$M=10^9+7$$
计算。这个模数是质数，而且真实输入中 \(\alpha<M\)，所以 \(1,2,\dots,\alpha\) 在模 \(M\) 意义下都有乘法逆元。
这样一来，当 \(k\ge 2\) 时，几何求和可以写成
$$G_k(n)\equiv \left(k^{n+1}-1\right)(k-1)^{-1}\pmod M.$$
其中 \(k^{n+1}\) 通过快速幂计算。
同样，二项式系数不需要用庞大的阶乘表来构造，而是可以递推：
$$\binom{\alpha}{0}=1,\qquad \binom{\alpha}{k+1}=\binom{\alpha}{k}\cdot\frac{\alpha-k}{k+1}.$$
在模运算中，除以 \(k+1\) 就变成乘以 \((k+1)^{-1}\)。因此实现会先线性预处理逆元，再顺次生成所有需要的二项式系数。
此时公式变为
$$T(3,4)=\sum_{k=0}^{2}(-1)^{4-k}\binom{3}{k}G_k(4).$$
分别计算几何块：
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31.$$
代回去可得
$$T(3,4)=\binom{3}{0}\cdot 1-\binom{3}{1}\cdot 5+\binom{3}{2}\cdot 31=1-15+93=79.$$
如果按长度直接验证，也完全一致：
$$I_0=1,\quad I_1=3,\quad I_2=9,\quad I_3=21,\quad I_4=45,$$
所以
$$1+3+9+21+45=79.$$
这个例子非常重要，因为它同时验证了容斥公式、等比求和以及最终累加方式。
C++、Python 和 Java 实现计算的是同一个模意义下的交错求和。第一步先预处理 \(1\) 到 \(\alpha\) 的模逆元。第二步利用递推关系逐个生成 \(\binom{\alpha}{k}\)，避免构造超大的阶乘和逆阶乘数组。
接着，程序遍历 \(k=0,1,\dots,\alpha-1\)。对于每个 \(k\)，先求出 \(G_k(n)\)：当 \(k=0\) 或 \(k=1\) 时直接给出结果；当 \(k\ge 2\) 时使用快速幂得到 \(k^{n+1}\)，再乘以 \(k-1\) 的逆元。然后把这个值与对应的二项式系数相乘，并按正确的正负号加入总和。
C++ 实现还会在输入很大时把 \(k\) 的区间拆分给多个线程，以减少实际运行时间；Python 和 Java 版本保持相同数学逻辑，只是按单线程方式执行。
预处理所有模逆元需要 \(O(\alpha)\) 时间和 \(O(\alpha)\) 空间。生成所有二项式系数同样是 \(O(\alpha)\)。主求和共有 \(\alpha\) 项，而每个 \(k\ge 2\) 的项都要做一次快速幂，因此总时间复杂度为
$$O(\alpha\log n),$$
空间复杂度为
$$O(\alpha).$$
C++ 版本的并行化只会改善常数因子，不改变这个渐近数量级。
Для алфавита из \(\alpha\) символов нужно посчитать общее число неполных слов длины от \(0\) до \(n\). Слово называется неполным, если хотя бы один символ алфавита в нём ни разу не встречается. Ответ требуется по модулю \(10^9+7\).
Прямой перебор невозможен: уже для фиксированной длины \(t\) существует \(\alpha^t\) слов. Поэтому решение не строит слова явно, а сначала выражает количество неполных слов через принцип включения-исключения, а затем суммирует по всем длинам при помощи геометрической прогрессии.
Обозначим через \(I_t(\alpha)\) число неполных слов точной длины \(t\). Тогда требуется найти
$$T(\alpha,n)=\sum_{t=0}^{n} I_t(\alpha).$$
Если длина равна \(t\), то общее число слов равно
$$\alpha^t,$$
поскольку в каждой из \(t\) позиций можно выбрать любой из \(\alpha\) символов.
Если обозначить через \(C_t(\alpha)\) число полных слов длины \(t\), то неполные слова образуют к ним дополнение:
$$I_t(\alpha)=\alpha^t-C_t(\alpha).$$
Пусть выбраны \(j\) символов, которые запрещено использовать. Тогда слово может строиться только из оставшихся \(\alpha-j\) символов, а значит, таких слов
$$(\alpha-j)^t.$$
По принципу включения-исключения число полных слов равно
$$C_t(\alpha)=\sum_{j=0}^{\alpha}(-1)^j\binom{\alpha}{j}(\alpha-j)^t.$$
Следовательно,
$$I_t(\alpha)=\alpha^t-C_t(\alpha)=\sum_{j=1}^{\alpha}(-1)^{j+1}\binom{\alpha}{j}(\alpha-j)^t.$$
Если теперь сделать замену \(k=\alpha-j\), получим именно ту форму, которую используют реализации:
$$I_t(\alpha)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
Верхняя граница \(\alpha-1\) здесь естественна: случай \(k=\alpha\) соответствует использованию всего алфавита и исчезает, когда мы переходим от полных слов к их дополнению.
Суммируем от \(t=0\) до \(t=n\):
$$T(\alpha,n)=\sum_{t=0}^{n}\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
Поскольку сумма конечна, можно поменять порядок суммирования:
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}\sum_{t=0}^{n}k^t.$$
Обозначим
$$G_k(n)=\sum_{t=0}^{n}k^t.$$
Тогда ответ принимает вид
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}G_k(n).$$
Для геометрического блока имеем
$$G_k(n)= \begin{cases} 1, & k=0,\\ n+1, & k=1,\\ \dfrac{k^{n+1}-1}{k-1}, & k\ge 2. \end{cases}$$
Случай \(k=0\) соответствует только пустому слову, а при \(k=1\) для каждой длины существует ровно одно слово.
Все вычисления выполняются по модулю
$$M=10^9+7.$$
Это простое число, и в реальных параметрах \(\alpha<M\), поэтому числа \(1,2,\dots,\alpha\) имеют обратные элементы по модулю \(M\).
Значит, для \(k\ge 2\) можно писать
$$G_k(n)\equiv \left(k^{n+1}-1\right)(k-1)^{-1}\pmod M,$$
а степень \(k^{n+1}\) вычислять быстрым возведением в степень.
Биномиальные коэффициенты тоже строятся итеративно:
$$\binom{\alpha}{0}=1,\qquad \binom{\alpha}{k+1}=\binom{\alpha}{k}\cdot\frac{\alpha-k}{k+1}.$$
Деление заменяется умножением на модульный обратный элемент к \(k+1\). Благодаря этому не нужны гигантские таблицы факториалов.
Получаем
$$T(3,4)=\sum_{k=0}^{2}(-1)^{4-k}\binom{3}{k}G_k(4).$$
Вычислим блоки:
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31.$$
Тогда
$$T(3,4)=\binom{3}{0}\cdot 1-\binom{3}{1}\cdot 5+\binom{3}{2}\cdot 31=1-15+93=79.$$
Проверка по длинам даёт тот же результат:
$$I_0=1,\quad I_1=3,\quad I_2=9,\quad I_3=21,\quad I_4=45,\quad 1+3+9+21+45=79.$$
Этот пример подтверждает и комбинаторную идею, и итоговую формулу, используемую в коде.
Реализации на C++, Python и Java вычисляют одну и ту же чередующуюся сумму по модулю \(10^9+7\). Сначала они предвычисляют модульные обратные для всех чисел от \(1\) до \(\alpha\). Затем на их основе последовательно строят коэффициенты \(\binom{\alpha}{k}\), не используя огромные массивы факториалов.
После этого выполняется цикл по \(k=0,1,\dots,\alpha-1\). Для каждого \(k\) вычисляется \(G_k(n)\): напрямую при \(k=0\) и \(k=1\), либо через быстрое возведение в степень и обратный к \(k-1\) при \(k\ge 2\). Полученный блок умножается на соответствующий биномиальный коэффициент и добавляется в сумму с нужным знаком.
В версии на C++ этот последний этап при больших входных данных может быть разделён между несколькими потоками. Однако сама математическая схема во всех трёх языках полностью одинакова.
Предвычисление обратных элементов требует \(O(\alpha)\) времени и \(O(\alpha)\) памяти. Построение всех биномиальных коэффициентов также занимает \(O(\alpha)\). В главной сумме \(\alpha\) слагаемых, и для каждого \(k\ge 2\) выполняется быстрое возведение в степень за \(O(\log n)\). Поэтому общая временная сложность равна
$$O(\alpha\log n),$$
а потребление памяти равно
$$O(\alpha).$$
Параллелизм в C++ улучшает только реальное время выполнения, но не асимптотику.
لدينا أبجدية حجمها \(\alpha\)، والمطلوب هو عدّ جميع الكلمات غير المكتملة التي تتراوح أطوالها من \(0\) إلى \(n\). وتسمى الكلمة غير مكتملة إذا كان هناك حرف واحد على الأقل من الأبجدية لا يظهر فيها إطلاقًا. النتيجة النهائية مطلوبة بترديد \(10^9+7\).
العدّ المباشر غير ممكن عمليًا، لأن عدد الكلمات بطول ثابت \(t\) يساوي \(\alpha^t\). لذلك تعتمد الفكرة على إعادة صياغة العدّ باستخدام مبدأ الشمول والاستبعاد، ثم جمع المساهمات على جميع الأطوال عبر متسلسلة هندسية.
لنرمز بعدد الكلمات غير المكتملة ذات الطول الدقيق \(t\) بالرمز \(I_t(\alpha)\). المطلوب إذن هو
$$T(\alpha,n)=\sum_{t=0}^{n} I_t(\alpha).$$
إذا كان الطول مساويًا لـ \(t\)، فإن عدد الكلمات الكلي هو
$$\alpha^t,$$
لأن كل موضع من المواضع \(t\) يمكن أن يأخذ أي واحد من \(\alpha\) حرفًا.
إذا رمزنا بعدد الكلمات الكاملة ذات الطول \(t\) بالرمز \(C_t(\alpha)\)، فإن الكلمات غير المكتملة تكون متممتها. لذلك
$$I_t(\alpha)=\alpha^t-C_t(\alpha).$$
افترض أننا اخترنا \(j\) أحرف لتكون ممنوعة من الظهور. عندها لا يبقى مسموحًا إلا باستخدام \(\alpha-j\) حرفًا، وبالتالي يكون عدد الكلمات الممكنة
$$(\alpha-j)^t.$$
وبحسب مبدأ الشمول والاستبعاد فإن عدد الكلمات الكاملة يساوي
$$C_t(\alpha)=\sum_{j=0}^{\alpha}(-1)^j\binom{\alpha}{j}(\alpha-j)^t.$$
ومن ثم
$$I_t(\alpha)=\alpha^t-C_t(\alpha)=\sum_{j=1}^{\alpha}(-1)^{j+1}\binom{\alpha}{j}(\alpha-j)^t.$$
إذا أعدنا الفهرسة بوضع \(k=\alpha-j\)، نحصل على الصيغة نفسها التي تعتمد عليها التطبيقات:
$$I_t(\alpha)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
وهذا يوضح لماذا يتوقف المجموع عند \(\alpha-1\): الحد المقابل لـ \(k=\alpha\) يمثل السماح بجميع الحروف، وهو الجزء الذي يختفي عندما ننتقل من عدّ الكلمات الكاملة إلى عدّ الكلمات غير المكتملة.
نجمع الآن من \(t=0\) حتى \(t=n\):
$$T(\alpha,n)=\sum_{t=0}^{n}\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}k^t.$$
وبما أن المجموعات منتهية، يمكن تبديل ترتيب الجمع:
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}\sum_{t=0}^{n}k^t.$$
لنعرف
$$G_k(n)=\sum_{t=0}^{n}k^t.$$
فتصبح الصيغة النهائية
$$T(\alpha,n)=\sum_{k=0}^{\alpha-1}(-1)^{\alpha-k+1}\binom{\alpha}{k}G_k(n).$$
والحد الهندسي يأخذ الصورة
$$G_k(n)= \begin{cases} 1, & k=0,\\ n+1, & k=1,\\ \dfrac{k^{n+1}-1}{k-1}, & k\ge 2. \end{cases}$$
في الحالة \(k=0\) لا يظهر إلا السلسلة الفارغة، ولذلك يكون المجموع \(1\). وفي الحالة \(k=1\) توجد كلمة واحدة فقط لكل طول، ولهذا نحصل على \(n+1\).
كل الحسابات تنفذ بترديد
$$M=10^9+7.$$
هذا عدد أولي، ومع معاملات المسألة الحقيقية لدينا \(\alpha<M\)، ولهذا فكل عدد من \(1\) إلى \(\alpha\) يملك معكوسًا ضربيًا modulo \(M\).
لذلك عندما يكون \(k\ge 2\) نستطيع كتابة
$$G_k(n)\equiv \left(k^{n+1}-1\right)(k-1)^{-1}\pmod M,$$
وتُحسب القوة \(k^{n+1}\) بواسطة الرفع السريع للأس.
كما أن معاملات ثنائية الحد تولَّد تزايديًا بدل الاعتماد على جداول عوامِل ضخمة:
$$\binom{\alpha}{0}=1,\qquad \binom{\alpha}{k+1}=\binom{\alpha}{k}\cdot\frac{\alpha-k}{k+1}.$$
وفي الحساب المعياري نستبدل القسمة على \(k+1\) بالضرب في معكوسه الضربي. لهذا تبدأ التطبيقات بحساب المعكوسات، ثم تبني معاملات ثنائية الحد واحدًا بعد الآخر.
تصبح الصيغة
$$T(3,4)=\sum_{k=0}^{2}(-1)^{4-k}\binom{3}{k}G_k(4).$$
نحسب الكتل الهندسية:
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31.$$
ومن ثم
$$T(3,4)=\binom{3}{0}\cdot 1-\binom{3}{1}\cdot 5+\binom{3}{2}\cdot 31=1-15+93=79.$$
ويمكن التحقق بالطريقة المباشرة حسب الأطوال:
$$I_0=1,\quad I_1=3,\quad I_2=9,\quad I_3=21,\quad I_4=45,$$
وبالتالي
$$1+3+9+21+45=79.$$
هذا المثال يربط بوضوح بين المعنى التوافقي للمسألة والصيغة الجبرية التي تنفذها الشفرة.
تنفذ تطبيقات C++ وPython وJava المجموع نفسه بترديد \(10^9+7\). تبدأ أولًا بحساب المعكوسات الضربية للأعداد من \(1\) إلى \(\alpha\). وبعد ذلك تُنشئ معاملات \(\binom{\alpha}{k}\) تتابعيًا باستخدام العلاقة الضربية السابقة، من دون اللجوء إلى جداول ضخمة للعوامل.
بعد ذلك تمرّ الشفرة على جميع القيم \(k=0,1,\dots,\alpha-1\). لكل قيمة \(k\)، تحسب \(G_k(n)\): مباشرة في حالتي \(k=0\) و\(k=1\)، وبالرفع السريع للأس ومعكوس \(k-1\) عندما \(k\ge 2\). ثم يُضرب هذا الناتج في معامل ثنائي الحد المناسب ويُضاف إلى المجموع مع الإشارة المتناوبة الصحيحة.
نسخة C++ قد تقسّم المجال الأخير على عدة خيوط عندما تكون المدخلات كبيرة جدًا، لكن الصيغة الرياضية نفسها تبقى هي نفسها في اللغات الثلاث.
حساب جميع المعكوسات الضربية يحتاج إلى \(O(\alpha)\) زمنًا و\(O(\alpha)\) ذاكرة. وتوليد معاملات ثنائية الحد يكلف أيضًا \(O(\alpha)\). في المجموع الرئيسي توجد \(\alpha\) حدود، وكل حد عند \(k\ge 2\) يتطلب عملية رفع سريع للأس بتكلفة \(O(\log n)\). لذلك يكون التعقيد الكلي
$$O(\alpha\log n),$$
أما استهلاك الذاكرة فهو
$$O(\alpha).$$
التنفيذ المتوازي في نسخة C++ يحسن الزمن العملي فقط، ولا يغير الرتبة التقاربية.