Let \(F(k,n)\) denote the total requested in Problem 658. The target parameters are enormous, so any method that tries to enumerate words, states, or lengths directly is out of reach. The key observation encoded by the C++, Python, and Java implementations is that the whole quantity can be rewritten as a finite algebraic basis indexed only by \(r=0,1,\dots,k-1\).
After that transformation, the problem is no longer a direct combinatorial search over incomplete words. It becomes the evaluation of a weighted sum of geometric series modulo
$$M=10^9+7.$$
The implementations absorb the inclusion-exclusion coming from missing letters into coefficients \(A_r\). Once these coefficients are known, the dependence on the huge parameter \(n\) is isolated inside standard geometric sums.
The required total can be written as
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M},$$
where
$$G_r(n)=\sum_{t=0}^{n} r^t.$$
The index \(r\) behaves like an effective alphabet size that survives one stage of inclusion-exclusion. The difficult combinatorics is therefore compressed into the scalar weights \(A_r\), while the length parameter appears only inside a geometric progression.
For modular arithmetic, \(G_r(n)\) is handled by cases:
$$G_r(n)=\begin{cases} 1,& r=0,\\ n+1,& r=1,\\ \dfrac{r^{n+1}-1}{r-1},& r\ge 2. \end{cases}$$
The special cases \(r=0\) and \(r=1\) are treated separately so the formula remains exact and no division by zero appears. For \(r\ge 2\), division by \(r-1\) means multiplication by the modular inverse of \(r-1\) modulo \(M\).
The transformed coefficients satisfy
$$A_{k-1}=k,$$
$$A_r=2A_{r+1}+(-1)^{k-r+1}\binom{k+1}{k-r}-1\pmod{M}\qquad (0\le r\le k-2).$$
This is the algebraic core of the solution. Each step doubles the next coefficient, adds one signed binomial correction from inclusion-exclusion, and subtracts \(1\). Because the sweep runs from \(r=k-1\) down to \(0\), every new coefficient depends only on the next already-known coefficient and one current binomial term.
If one step uses \(\binom{k+1}{k-r}\), then the next step needs \(\binom{k+1}{k-r+1}\). These values satisfy
$$\binom{k+1}{k-r+1}=\binom{k+1}{k-r}\cdot\frac{r+1}{k-r+1}.$$
Since \(M\) is prime, the division by \(k-r+1\) is implemented as multiplication by its modular inverse. This avoids factorial tables and keeps the whole coefficient sweep linear in \(k\).
Once the coefficients are ready, the answer is simply
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M}.$$
For \(r\ge 2\), the only expensive subroutine is fast exponentiation of \(r^{n+1}\). That is why the dependence on the huge input \(n\) stays logarithmic.
This is the smallest checkpoint built into the implementations. The recurrence gives
$$\begin{aligned} A_3&=4,\\ A_2&=2A_3-\binom{5}{2}-1=8-10-1=-3,\\ A_1&=2A_2+\binom{5}{3}-1=-6+10-1=3,\\ A_0&=2A_1-\binom{5}{4}-1=6-5-1=0. \end{aligned}$$
So the signed coefficients are \((A_0,A_1,A_2,A_3)=(0,3,-3,4)\). In modular storage the negative value \(-3\) is represented by \(M-3\), but the arithmetic is identical.
The corresponding geometric sums are
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31,\qquad G_3(4)=1+3+9+27+81=121.$$
Therefore
$$F(4,4)=0\cdot 1+3\cdot 5-3\cdot 31+4\cdot 121=406,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations first precompute modular inverses for all integers from \(1\) to \(k+1\). That single table supports both the binomial updates and the division by \(r-1\) in the geometric-series formula.
Next, the implementation performs one descending pass over \(r\) to fill the coefficient table with the recurrence above. During the same pass it updates the current binomial coefficient multiplicatively, so no factorial arrays are required.
Finally, it evaluates each basis term. The cases \(r=0\) and \(r=1\) are handled directly, while \(r\ge 2\) uses binary exponentiation to compute \(r^{n+1}\bmod M\). The C++ implementation additionally splits the final summation across several threads when \(k\) is large enough; the Python and Java implementations perform the same arithmetic in a single pass.
Precomputing inverses costs \(O(k)\) time and \(O(k)\) memory. Building all coefficients also costs \(O(k)\). The final summation evaluates \(k-2\) nontrivial powers, each in \(O(\log n)\) time, so the dominant term is \(O(k\log n)\). The overall memory usage is \(O(k)\). Parallel summation in C++ improves wall-clock time but does not change the asymptotic bound.
Sei \(F(k,n)\) die in Problem 658 verlangte Gesamtgröße. Die Zielparameter sind so groß, dass direkte Enumeration über Wörter, Zustände oder Längen ausscheidet. Die zentrale Beobachtung der C++-, Python- und Java-Implementierungen ist, dass sich die gesamte Größe als endliche algebraische Basis mit Indizes \(r=0,1,\dots,k-1\) schreiben lässt.
Nach dieser Umformung ist das Problem keine unmittelbare kombinatorische Suche über unvollständige Wörter mehr. Stattdessen muss nur noch eine gewichtete Summe geometrischer Reihen modulo
$$M=10^9+7$$
ausgewertet werden.
Die Implementierungen absorbieren die Inklusions-Exklusions-Beiträge der fehlenden Buchstaben in Koeffizienten \(A_r\). Sobald diese Koeffizienten bekannt sind, steckt die gesamte Abhängigkeit von dem riesigen Parameter \(n\) nur noch in gewöhnlichen geometrischen Summen.
Die gesuchte Größe hat die Form
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M},$$
wobei
$$G_r(n)=\sum_{t=0}^{n} r^t.$$
Der Index \(r\) kann als Größe eines effektiven Alphabets verstanden werden, das nach einem Schritt der Inklusions-Exklusion übrig bleibt. Die schwierige Kombinatorik wird also in die skalaren Gewichte \(A_r\) ausgelagert, während die Längenabhängigkeit nur noch in einer geometrischen Reihe steckt.
Für die modulare Rechnung wird \(G_r(n)\) fallweise behandelt:
$$G_r(n)=\begin{cases} 1,& r=0,\\ n+1,& r=1,\\ \dfrac{r^{n+1}-1}{r-1},& r\ge 2. \end{cases}$$
Die Sonderfälle \(r=0\) und \(r=1\) werden getrennt behandelt, damit die Formel exakt bleibt und keine Division durch Null auftritt. Für \(r\ge 2\) bedeutet die Division durch \(r-1\) eine Multiplikation mit dem modularen Inversen von \(r-1\) modulo \(M\).
Die transformierten Koeffizienten erfüllen
$$A_{k-1}=k,$$
$$A_r=2A_{r+1}+(-1)^{k-r+1}\binom{k+1}{k-r}-1\pmod{M}\qquad (0\le r\le k-2).$$
Das ist der algebraische Kern der Lösung. Jeder Schritt verdoppelt den nächsten Koeffizienten, addiert eine vorzeichenbehaftete Binomialkorrektur aus der Inklusions-Exklusion und subtrahiert anschließend \(1\). Da von \(r=k-1\) bis \(0\) rückwärts gelaufen wird, hängt jeder neue Koeffizient nur vom bereits bekannten Nachfolger und einem aktuellen Binomialterm ab.
Wenn ein Schritt \(\binom{k+1}{k-r}\) verwendet, braucht der nächste Schritt \(\binom{k+1}{k-r+1}\). Zwischen beiden gilt
$$\binom{k+1}{k-r+1}=\binom{k+1}{k-r}\cdot\frac{r+1}{k-r+1}.$$
Weil \(M\) prim ist, wird die Division durch \(k-r+1\) als Multiplikation mit dem modularen Inversen umgesetzt. So sind keine Fakultätstabellen nötig, und der gesamte Koeffizientenlauf bleibt linear in \(k\).
Sobald alle Koeffizienten vorliegen, lautet die Antwort einfach
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M}.$$
Für \(r\ge 2\) ist die einzige teure Teiloperation die schnelle Berechnung von \(r^{n+1}\). Deshalb bleibt die Abhängigkeit vom riesigen Eingabewert \(n\) logarithmisch.
Das ist der kleinste Kontrollwert aus den Implementierungen. Die Rekurrenz liefert
$$\begin{aligned} A_3&=4,\\ A_2&=2A_3-\binom{5}{2}-1=8-10-1=-3,\\ A_1&=2A_2+\binom{5}{3}-1=-6+10-1=3,\\ A_0&=2A_1-\binom{5}{4}-1=6-5-1=0. \end{aligned}$$
Die vorzeichenbehafteten Koeffizienten sind also \((A_0,A_1,A_2,A_3)=(0,3,-3,4)\). In der modularen Speicherung wird \(-3\) als \(M-3\) dargestellt, mathematisch ist das aber derselbe Wert.
Die zugehörigen geometrischen Summen sind
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31,\qquad G_3(4)=1+3+9+27+81=121.$$
Damit ergibt sich
$$F(4,4)=0\cdot 1+3\cdot 5-3\cdot 31+4\cdot 121=406,$$
genau der Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen berechnen zuerst modulare Inverse für alle ganzen Zahlen von \(1\) bis \(k+1\) vor. Diese eine Tabelle unterstützt sowohl die Fortschreibung der Binomialterme als auch die Division durch \(r-1\) in der Formel für die geometrische Reihe.
Anschließend erfolgt genau ein rückwärts laufender Durchgang über \(r\), der die Koeffiziententabelle mit der obigen Rekurrenz füllt. Im selben Durchgang wird der jeweils benötigte Binomialkoeffizient multiplikativ aktualisiert, sodass keine Fakultätstabellen erforderlich sind.
Zum Schluss wird jeder Basisterm ausgewertet. Die Fälle \(r=0\) und \(r=1\) sind direkt, während für \(r\ge 2\) binäre Exponentiation zur Berechnung von \(r^{n+1}\bmod M\) verwendet wird. Die C++-Implementierung teilt die letzte Summation bei großem \(k\) zusätzlich auf mehrere Threads auf; die Python- und Java-Implementierungen führen dieselbe Arithmetik in einem einzigen Durchgang aus.
Das Vorberechnen der Inversen kostet \(O(k)\) Zeit und \(O(k)\) Speicher. Das Erzeugen aller Koeffizienten kostet ebenfalls \(O(k)\). In der Endsumme werden \(k-2\) nichttriviale Potenzen berechnet, jeweils in \(O(\log n)\) Zeit, sodass insgesamt \(O(k\log n)\) dominiert. Der Gesamtverbrauch an Speicher ist \(O(k)\). Die Parallelisierung in C++ verbessert nur die Laufzeit in der Praxis, nicht die asymptotische Schranke.
\(F(k,n)\), Problem 658'de istenen toplam büyüklük olsun. Hedef parametreler o kadar büyüktür ki kelimeleri, durumları veya uzunlukları tek tek sayan hiçbir yöntem uygulanabilir değildir. C++, Python ve Java uygulamalarının kullandığı temel gözlem, tüm ifadenin yalnızca \(r=0,1,\dots,k-1\) indisleriyle sonlu bir cebirsel baza indirgenebilmesidir.
Bu dönüşümden sonra problem artık eksik kelimeleri doğrudan üretme problemi değildir. Geriye sadece
$$M=10^9+7$$
modunda ağırlıklı bir geometrik seri toplamı hesaplamak kalır.
Uygulamalar, eksik harflerden gelen dahil et-çıkar katkılarını \(A_r\) katsayılarının içine gömer. Bu katsayılar elde edildiğinde, çok büyük olan \(n\) parametresine bağımlılık yalnızca sıradan geometrik toplamların içinde kalır.
İstenen toplam şu biçimde yazılabilir:
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M},$$
burada
$$G_r(n)=\sum_{t=0}^{n} r^t.$$
\(r\) indisi, dahil et-çıkarın bir aşamasından sonra ayakta kalan etkili alfabe büyüklüğü gibi düşünülebilir. Zor kombinatorik kısım böylece skaler ağırlıklar \(A_r\) içine sıkıştırılır; uzunluk parametresi ise sadece geometrik toplamda görünür.
Modüler aritmetikte \(G_r(n)\) şu durumlara ayrılır:
$$G_r(n)=\begin{cases} 1,& r=0,\\ n+1,& r=1,\\ \dfrac{r^{n+1}-1}{r-1},& r\ge 2. \end{cases}$$
\(r=0\) ve \(r=1\) özel olarak ele alınır; böylece formül tam kalır ve sıfıra bölme sorunu çıkmaz. \(r\ge 2\) için \(r-1\)'e bölme işlemi, \(M\) modunda \(r-1\)'in modüler tersiyle çarpma olarak uygulanır.
Dönüştürülmüş katsayılar şu bağıntıyı sağlar:
$$A_{k-1}=k,$$
$$A_r=2A_{r+1}+(-1)^{k-r+1}\binom{k+1}{k-r}-1\pmod{M}\qquad (0\le r\le k-2).$$
Çözümün cebirsel özü budur. Her adım bir sonraki katsayıyı ikiyle çarpar, dahil et-çıkar kaynaklı işaretli bir binom düzeltmesi ekler ve sonra \(1\) çıkarır. Tarama \(r=k-1\)'den \(0\)'a doğru yapıldığı için her yeni katsayı yalnızca zaten bilinen komşu katsayıya ve o adımdaki tek bir binom terimine bağlıdır.
Bir adımda \(\binom{k+1}{k-r}\) kullanılıyorsa, sonraki adımda gereken değer \(\binom{k+1}{k-r+1}\) olur. Aralarındaki ilişki
$$\binom{k+1}{k-r+1}=\binom{k+1}{k-r}\cdot\frac{r+1}{k-r+1}$$
şeklindedir. \(M\) asal olduğundan, \(k-r+1\)'e bölme modüler ters ile çarpma olarak yapılır. Böylece factorial tablolarına gerek kalmaz ve tüm katsayı geçişi \(k\) içinde doğrusal kalır.
Katsayılar hazır olduğunda cevap doğrudan
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M}$$
olur. \(r\ge 2\) için pahalı tek alt işlem \(r^{n+1}\) kuvvetini hızlı üs alma ile hesaplamaktır. Bu yüzden çok büyük olan \(n\)'ye bağımlılık logaritmik kalır.
Bu, uygulamalardaki en küçük kontrol örneğidir. Rekürans
$$\begin{aligned} A_3&=4,\\ A_2&=2A_3-\binom{5}{2}-1=8-10-1=-3,\\ A_1&=2A_2+\binom{5}{3}-1=-6+10-1=3,\\ A_0&=2A_1-\binom{5}{4}-1=6-5-1=0 \end{aligned}$$
değerlerini verir. Dolayısıyla işaretli katsayılar \((A_0,A_1,A_2,A_3)=(0,3,-3,4)\) olur. Modüler bellekte \(-3\), \(M-3\) olarak tutulur; fakat matematik aynıdır.
Karşılık gelen geometrik toplamlar
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31,\qquad G_3(4)=1+3+9+27+81=121$$
şeklindedir. Böylece
$$F(4,4)=0\cdot 1+3\cdot 5-3\cdot 31+4\cdot 121=406,$$
ve bu değer uygulamadaki kontrol sonucu ile aynıdır.
C++, Python ve Java uygulamaları önce \(1\) ile \(k+1\) arasındaki tüm sayılar için modüler tersleri önceden hesaplar. Bu tek tablo hem binom güncellemelerini hem de geometrik seri formülündeki \(r-1\)'e bölmeyi destekler.
Daha sonra uygulama \(r\) üzerinde tek bir geri yönde geçiş yaparak yukarıdaki reküransla katsayı tablosunu doldurur. Aynı geçiş sırasında gerekli binom katsayısı çarpımsal oran formülüyle güncellenir; dolayısıyla factorial dizilerine ihtiyaç yoktur.
Son aşamada her baz terimi değerlendirilir. \(r=0\) ve \(r=1\) durumları doğrudan işlenir; \(r\ge 2\) için ise \(r^{n+1}\bmod M\) değerini bulmak amacıyla ikili üs alma kullanılır. C++ uygulaması, \(k\) yeterince büyük olduğunda son toplamı birden fazla iş parçacığına böler; Python ve Java uygulamaları aynı aritmetiği tek geçişte yapar.
Modüler terslerin hazırlanması \(O(k)\) zaman ve \(O(k)\) bellek ister. Tüm katsayıları üretmek de \(O(k)\) sürer. Son toplamda \(k-2\) adet önemsiz olmayan üs hesabı vardır ve her biri \(O(\log n)\) zaman alır; bu nedenle baskın terim \(O(k\log n)\) olur. Toplam bellek kullanımı \(O(k)\)'dir. C++ içindeki paralel toplama yalnızca duvar saati süresini azaltır, asimptotik sınırı değiştirmez.
Sea \(F(k,n)\) la cantidad total pedida en el Problema 658. Los parámetros objetivo son tan grandes que cualquier método que enumere palabras, estados o longitudes de forma directa queda descartado. La observación clave reflejada en las implementaciones de C++, Python y Java es que toda la expresión puede reescribirse como una base algebraica finita indexada solo por \(r=0,1,\dots,k-1\).
Después de esa transformación, el problema deja de ser una búsqueda combinatoria directa sobre palabras incompletas. Pasa a ser la evaluación de una suma ponderada de progresiones geométricas módulo
$$M=10^9+7.$$
Las implementaciones incorporan toda la inclusión-exclusión asociada a letras ausentes dentro de coeficientes \(A_r\). Una vez conocidos esos coeficientes, la dependencia respecto al enorme parámetro \(n\) queda aislada en sumas geométricas estándar.
La cantidad buscada puede escribirse como
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M},$$
donde
$$G_r(n)=\sum_{t=0}^{n} r^t.$$
El índice \(r\) puede interpretarse como el tamaño de un alfabeto efectivo que sobrevive a una etapa de inclusión-exclusión. Así, la parte combinatoria difícil queda comprimida en los pesos escalares \(A_r\), mientras que la dependencia en la longitud aparece solo dentro de una progresión geométrica.
En aritmética modular, \(G_r(n)\) se trata por casos:
$$G_r(n)=\begin{cases} 1,& r=0,\\ n+1,& r=1,\\ \dfrac{r^{n+1}-1}{r-1},& r\ge 2. \end{cases}$$
Los casos especiales \(r=0\) y \(r=1\) se separan para mantener la fórmula exacta y evitar una división por cero. Para \(r\ge 2\), dividir por \(r-1\) significa multiplicar por el inverso modular de \(r-1\) módulo \(M\).
Los coeficientes transformados satisfacen
$$A_{k-1}=k,$$
$$A_r=2A_{r+1}+(-1)^{k-r+1}\binom{k+1}{k-r}-1\pmod{M}\qquad (0\le r\le k-2).$$
Este es el núcleo algebraico de la solución. Cada paso duplica el coeficiente siguiente, añade una corrección binomial con signo procedente de inclusión-exclusión y luego resta \(1\). Como el barrido va desde \(r=k-1\) hasta \(0\), cada coeficiente nuevo depende solo del siguiente ya calculado y de un único término binomial actual.
Si un paso usa \(\binom{k+1}{k-r}\), el siguiente necesita \(\binom{k+1}{k-r+1}\). Ambos valores cumplen
$$\binom{k+1}{k-r+1}=\binom{k+1}{k-r}\cdot\frac{r+1}{k-r+1}.$$
Como \(M\) es primo, la división por \(k-r+1\) se implementa como multiplicación por su inverso modular. Así se evitan tablas de factoriales y todo el barrido de coeficientes permanece lineal en \(k\).
Una vez calculados todos los coeficientes, la respuesta es simplemente
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M}.$$
Para \(r\ge 2\), la única subrutina costosa es la exponenciación rápida de \(r^{n+1}\). Por eso la dependencia respecto al enorme valor de \(n\) sigue siendo logarítmica.
Este es el control más pequeño incorporado en las implementaciones. La recurrencia produce
$$\begin{aligned} A_3&=4,\\ A_2&=2A_3-\binom{5}{2}-1=8-10-1=-3,\\ A_1&=2A_2+\binom{5}{3}-1=-6+10-1=3,\\ A_0&=2A_1-\binom{5}{4}-1=6-5-1=0. \end{aligned}$$
Por tanto, los coeficientes con signo son \((A_0,A_1,A_2,A_3)=(0,3,-3,4)\). En almacenamiento modular, el valor \(-3\) se representa como \(M-3\), pero la aritmética es la misma.
Las sumas geométricas correspondientes son
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31,\qquad G_3(4)=1+3+9+27+81=121.$$
Entonces
$$F(4,4)=0\cdot 1+3\cdot 5-3\cdot 31+4\cdot 121=406,$$
que coincide con el valor de control usado por la implementación.
Las implementaciones de C++, Python y Java primero precalculan los inversos modulares de todos los enteros entre \(1\) y \(k+1\). Esa única tabla sirve tanto para actualizar los binomiales como para dividir por \(r-1\) en la fórmula de la suma geométrica.
Después, la implementación realiza un único recorrido descendente sobre \(r\) para rellenar la tabla de coeficientes mediante la recurrencia anterior. Durante el mismo recorrido, el coeficiente binomial necesario se actualiza de forma multiplicativa, así que no hacen falta arreglos de factoriales.
Por último, evalúa cada término de la base. Los casos \(r=0\) y \(r=1\) se resuelven directamente, mientras que \(r\ge 2\) usa exponenciación binaria para calcular \(r^{n+1}\bmod M\). La implementación en C++ además divide la suma final en varios hilos cuando \(k\) es suficientemente grande; las implementaciones en Python y Java ejecutan la misma aritmética en una sola pasada.
Precalcular los inversos cuesta \(O(k)\) tiempo y \(O(k)\) memoria. Construir todos los coeficientes también cuesta \(O(k)\). La suma final evalúa \(k-2\) potencias no triviales, cada una en \(O(\log n)\), de modo que el término dominante es \(O(k\log n)\). El uso total de memoria es \(O(k)\). El paralelismo en C++ mejora el tiempo real de ejecución, pero no cambia la cota asintótica.
设 \(F(k,n)\) 表示 Problem 658 要求的总量。目标参数极大，任何直接枚举单词、状态或长度的方法都不可能通过。C++、Python 和 Java 三份实现共同揭示的关键事实是：整个目标值可以改写成一个只按 \(r=0,1,\dots,k-1\) 编号的有限代数基底。
完成这一步以后，问题就不再是对“不完整单词”做直接组合枚举，而是变成了在
$$M=10^9+7$$
模下求一个带权几何级数和。
实现把“缺失字母”带来的容斥贡献全部压缩进系数 \(A_r\) 中。一旦这些系数被求出，和巨大参数 \(n\) 有关的部分就只剩下标准的几何和。
所求总量可以写成
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M},$$
其中
$$G_r(n)=\sum_{t=0}^{n} r^t.$$
这里的 \(r\) 可以理解为在某一层容斥之后仍然保留下来的“有效字母表大小”。于是困难的组合结构都被吸收到标量权重 \(A_r\) 里，而长度参数只出现在一个有限几何级数中。
在模运算下，\(G_r(n)\) 需要分情况处理：
$$G_r(n)=\begin{cases} 1,& r=0,\\ n+1,& r=1,\\ \dfrac{r^{n+1}-1}{r-1},& r\ge 2. \end{cases}$$
\(r=0\) 和 \(r=1\) 被单独拿出来，是为了避免分母为零并保持公式精确。对于 \(r\ge 2\)，除以 \(r-1\) 在模 \(M\) 下等价于乘上 \(r-1\) 的模逆元。
变换后的系数满足
$$A_{k-1}=k,$$
$$A_r=2A_{r+1}+(-1)^{k-r+1}\binom{k+1}{k-r}-1\pmod{M}\qquad (0\le r\le k-2).$$
这就是整个解法的代数核心。每一步先把下一个系数乘以 \(2\)，再加上一个来自容斥的带符号二项式修正，最后减去 \(1\)。由于扫描顺序是从 \(r=k-1\) 一直向下到 \(0\)，所以当前系数只依赖于已经求出的相邻系数和当前这一个二项式项。
如果当前步使用的是 \(\binom{k+1}{k-r}\)，那么下一步需要的是 \(\binom{k+1}{k-r+1}\)。两者满足
$$\binom{k+1}{k-r+1}=\binom{k+1}{k-r}\cdot\frac{r+1}{k-r+1}.$$
因为 \(M\) 是素数，除以 \(k-r+1\) 可以改成乘以它的模逆元。这样就不需要阶乘表，整段系数递推仍然保持对 \(k\) 的线性复杂度。
当所有系数都已得到之后，答案就是
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M}.$$
对于 \(r\ge 2\)，唯一昂贵的子步骤是快速计算 \(r^{n+1}\)。因此即使 \(n\) 极大，对 \(n\) 的依赖仍然只是对数级。
这是实现中内置的最小校验点。按照递推关系有
$$\begin{aligned} A_3&=4,\\ A_2&=2A_3-\binom{5}{2}-1=8-10-1=-3,\\ A_1&=2A_2+\binom{5}{3}-1=-6+10-1=3,\\ A_0&=2A_1-\binom{5}{4}-1=6-5-1=0. \end{aligned}$$
所以带符号的系数是 \((A_0,A_1,A_2,A_3)=(0,3,-3,4)\)。在模 \(M\) 的存储形式里，\(-3\) 会写成 \(M-3\)，但数学意义完全相同。
对应的几何和为
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31,\qquad G_3(4)=1+3+9+27+81=121.$$
因此
$$F(4,4)=0\cdot 1+3\cdot 5-3\cdot 31+4\cdot 121=406,$$
与实现使用的校验值一致。
C++、Python 和 Java 实现首先预计算从 \(1\) 到 \(k+1\) 的所有模逆元。这一张表同时服务于二项式项更新，以及几何级数公式里对 \(r-1\) 的除法。
接着，实现对 \(r\) 做一次从大到小的单向扫描，用上面的递推式填满整张系数表。在同一个循环里，所需的二项式系数也通过乘法比例公式持续更新，因此完全不需要阶乘数组。
最后，程序逐项计算基底和。\(r=0\) 与 \(r=1\) 直接处理；\(r\ge 2\) 时用二进制快速幂求 \(r^{n+1}\bmod M\)。其中 C++ 实现在 \(k\) 足够大时还会把最终求和区间拆给多个线程；Python 与 Java 实现则在单次遍历中完成同样的算术。
预计算逆元需要 \(O(k)\) 时间和 \(O(k)\) 内存。构造全部系数同样是 \(O(k)\)。最终求和阶段要计算 \(k-2\) 个非平凡幂，每个幂需要 \(O(\log n)\) 时间，所以主导复杂度是 \(O(k\log n)\)。总内存复杂度为 \(O(k)\)。C++ 中的并行求和只改善实际运行时间，不改变渐近复杂度。
Обозначим через \(F(k,n)\) величину, которую требуется найти в Problem 658. Параметры настолько велики, что прямой перебор слов, состояний или длин невозможен. Главное наблюдение, заложенное в реализациях на C++, Python и Java, состоит в том, что весь ответ можно переписать в виде конечного алгебраического базиса, индексируемого только значениями \(r=0,1,\dots,k-1\).
После этого преобразования задача перестает быть непосредственным комбинаторным перебором неполных слов. Она сводится к вычислению взвешенной суммы геометрических рядов по модулю
$$M=10^9+7.$$
Реализации поглощают всю инклюзию-исключение, связанную с отсутствующими буквами, в коэффициенты \(A_r\). Когда эти коэффициенты известны, зависимость от огромного параметра \(n\) остается только внутри обычных геометрических сумм.
Искомая величина представляется в виде
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M},$$
где
$$G_r(n)=\sum_{t=0}^{n} r^t.$$
Индекс \(r\) можно понимать как размер эффективного алфавита, который остается после одного шага инклюзии-исключения. Сложная комбинаторная часть тем самым сжимается в скалярные веса \(A_r\), а зависимость от длины целиком уходит в конечный геометрический ряд.
В модульной арифметике \(G_r(n)\) удобно рассматривать по случаям:
$$G_r(n)=\begin{cases} 1,& r=0,\\ n+1,& r=1,\\ \dfrac{r^{n+1}-1}{r-1},& r\ge 2. \end{cases}$$
Случаи \(r=0\) и \(r=1\) выделяются отдельно, чтобы формула оставалась точной и не возникало деления на ноль. Для \(r\ge 2\) деление на \(r-1\) означает умножение на модульный обратный к \(r-1\) по модулю \(M\).
Преобразованные коэффициенты удовлетворяют равенствам
$$A_{k-1}=k,$$
$$A_r=2A_{r+1}+(-1)^{k-r+1}\binom{k+1}{k-r}-1\pmod{M}\qquad (0\le r\le k-2).$$
Это и есть алгебраическое ядро решения. На каждом шаге следующий коэффициент удваивается, затем добавляется знакопеременная биномиальная поправка из инклюзии-исключения, а после этого вычитается \(1\). Поскольку проход идет от \(r=k-1\) к \(0\), каждый новый коэффициент зависит только от уже вычисленного соседа и одного текущего биномиального слагаемого.
Если на текущем шаге используется \(\binom{k+1}{k-r}\), то на следующем нужен \(\binom{k+1}{k-r+1}\). Между ними выполняется соотношение
$$\binom{k+1}{k-r+1}=\binom{k+1}{k-r}\cdot\frac{r+1}{k-r+1}.$$
Так как \(M\) простое, деление на \(k-r+1\) реализуется как умножение на модульный обратный. Благодаря этому не нужны таблицы факториалов, а весь проход по коэффициентам остается линейным по \(k\).
Когда все коэффициенты уже известны, ответ равен
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M}.$$
Для \(r\ge 2\) единственной дорогой подзадачей остается быстрое вычисление \(r^{n+1}\). Именно поэтому зависимость от огромного \(n\) остается логарифмической.
Это минимальная контрольная точка, встроенная в реализации. Рекуррентная формула дает
$$\begin{aligned} A_3&=4,\\ A_2&=2A_3-\binom{5}{2}-1=8-10-1=-3,\\ A_1&=2A_2+\binom{5}{3}-1=-6+10-1=3,\\ A_0&=2A_1-\binom{5}{4}-1=6-5-1=0. \end{aligned}$$
Следовательно, знаковые коэффициенты равны \((A_0,A_1,A_2,A_3)=(0,3,-3,4)\). В модульном представлении значение \(-3\) хранится как \(M-3\), но математически это тот же самый коэффициент.
Соответствующие геометрические суммы равны
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31,\qquad G_3(4)=1+3+9+27+81=121.$$
Поэтому
$$F(4,4)=0\cdot 1+3\cdot 5-3\cdot 31+4\cdot 121=406,$$
что совпадает с контрольным значением, используемым в реализации.
Реализации на C++, Python и Java сначала предварительно вычисляют модульные обратные для всех целых чисел от \(1\) до \(k+1\). Эта одна таблица нужна и для обновления биномиальных коэффициентов, и для деления на \(r-1\) в формуле геометрической суммы.
Затем выполняется один нисходящий проход по \(r\), который заполняет таблицу коэффициентов по приведенной выше рекуррентной формуле. В том же проходе нужный биномиальный коэффициент обновляется мультипликативно, так что массивы факториалов не требуются.
После этого вычисляется каждый базисный член. Случаи \(r=0\) и \(r=1\) обрабатываются напрямую, а при \(r\ge 2\) используется бинарное возведение в степень для вычисления \(r^{n+1}\bmod M\). Реализация на C++ дополнительно распараллеливает заключительное суммирование, когда \(k\) достаточно велико; реализации на Python и Java выполняют ту же арифметику одним проходом.
Предварительное вычисление обратных элементов требует \(O(k)\) времени и \(O(k)\) памяти. Построение всех коэффициентов также занимает \(O(k)\). На финальном этапе нужно вычислить \(k-2\) нетривиальных степеней, каждая за \(O(\log n)\), поэтому доминирующая сложность равна \(O(k\log n)\). Общий расход памяти составляет \(O(k)\). Параллельное суммирование в C++ уменьшает только реальное время работы, но не меняет асимптотику.
لنرمز بـ \(F(k,n)\) إلى الكمية المطلوبة في Problem 658. قيم الإدخال المستهدفة كبيرة جدًا، لذلك فإن أي أسلوب يعتمد على تعداد الكلمات أو الحالات أو الأطوال مباشرة غير عملي تمامًا. الفكرة الأساسية الظاهرة في تطبيقات C++ وPython وJava هي أن المقدار كله يمكن إعادة كتابته على هيئة أساس جبري منتهٍ مفهرس فقط بالقيم \(r=0,1,\dots,k-1\).
بعد هذا التحويل لا تعود المسألة عدًا تركيبيًا مباشرًا للكلمات غير المكتملة، بل تصبح حساب مجموع موزون من متسلسلات هندسية بترديد
$$M=10^9+7.$$
تدمج التطبيقات جميع مساهمات مبدأ الشمول والاستبعاد الناتجة عن الحروف المفقودة داخل معاملات \(A_r\). وبعد معرفة هذه المعاملات، تبقى تبعية المعامل الضخم \(n\) محصورة داخل مجاميع هندسية معيارية.
يمكن كتابة الكمية المطلوبة على الصورة
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M},$$
حيث
$$G_r(n)=\sum_{t=0}^{n} r^t.$$
يمكن النظر إلى \(r\) على أنه حجم أبجدية فعالة يبقى بعد مرحلة واحدة من الشمول والاستبعاد. وهكذا تُضغط البنية التوافقية الصعبة كلها داخل الأوزان العددية \(A_r\)، بينما يظهر تأثير الطول فقط داخل متسلسلة هندسية محدودة.
في الحساب المعياري، تُعالج \(G_r(n)\) بحسب الحالات:
$$G_r(n)=\begin{cases} 1,& r=0,\\ n+1,& r=1,\\ \dfrac{r^{n+1}-1}{r-1},& r\ge 2. \end{cases}$$
تُفصل حالتا \(r=0\) و\(r=1\) حتى تبقى الصيغة دقيقة ولا يظهر مقام صفري. أما عندما \(r\ge 2\)، فإن القسمة على \(r-1\) تعني الضرب في المعكوس الضربي المعياري لـ \(r-1\) بترديد \(M\).
تحقق المعاملات المحولة العلاقة
$$A_{k-1}=k,$$
$$A_r=2A_{r+1}+(-1)^{k-r+1}\binom{k+1}{k-r}-1\pmod{M}\qquad (0\le r\le k-2).$$
وهذا هو القلب الجبري للحل. ففي كل خطوة نضاعف المعامل التالي، ثم نضيف تصحيحًا ثنائي الحد ذي إشارة ناتجًا عن الشمول والاستبعاد، ثم نطرح \(1\). وبما أن المسح يتم من \(r=k-1\) نزولًا إلى \(0\)، فإن كل معامل جديد يعتمد فقط على المعامل المجاور الذي حُسب مسبقًا وعلى حد ثنائي واحد في تلك الخطوة.
إذا كانت الخطوة الحالية تستخدم \(\binom{k+1}{k-r}\)، فإن الخطوة التالية تحتاج إلى \(\binom{k+1}{k-r+1}\). ويرتبط الحدّان بالعلاقة
$$\binom{k+1}{k-r+1}=\binom{k+1}{k-r}\cdot\frac{r+1}{k-r+1}.$$
وبما أن \(M\) عدد أولي، فإن القسمة على \(k-r+1\) تُنفذ باعتبارها ضربًا في معكوسه المعياري. وهذا يلغي الحاجة إلى جداول عامليات ويحافظ على خطية مرحلة توليد المعاملات بالنسبة إلى \(k\).
بعد تجهيز جميع المعاملات يصبح الجواب ببساطة
$$F(k,n)=\sum_{r=0}^{k-1} A_r\,G_r(n)\pmod{M}.$$
عندما \(r\ge 2\)، فإن الجزء المكلف الوحيد هو حساب \(r^{n+1}\) بالرفع السريع للأس. ولهذا تبقى تبعية الزمن بالنسبة إلى \(n\) لوغاريتمية رغم ضخامته.
هذا أصغر اختبار تحقق مضمَّن في التطبيقات. تعطي العلاقة الرجوعية
$$\begin{aligned} A_3&=4,\\ A_2&=2A_3-\binom{5}{2}-1=8-10-1=-3,\\ A_1&=2A_2+\binom{5}{3}-1=-6+10-1=3,\\ A_0&=2A_1-\binom{5}{4}-1=6-5-1=0. \end{aligned}$$
إذًا المعاملات الموقعة هي \((A_0,A_1,A_2,A_3)=(0,3,-3,4)\). وفي التمثيل المعياري تُخزن القيمة \(-3\) على صورة \(M-3\)، لكن المعنى الحسابي لا يتغير.
أما المجاميع الهندسية الموافقة فهي
$$G_0(4)=1,\qquad G_1(4)=5,\qquad G_2(4)=1+2+4+8+16=31,\qquad G_3(4)=1+3+9+27+81=121.$$
ومن ثم
$$F(4,4)=0\cdot 1+3\cdot 5-3\cdot 31+4\cdot 121=406,$$
وهو تمامًا مقدار التحقق المستخدم في التطبيق.
تبدأ تطبيقات C++ وPython وJava بحساب المعكوسات المعيارية لجميع الأعداد الصحيحة من \(1\) إلى \(k+1\). ويكفي هذا الجدول الواحد لدعم تحديثات معاملات ثنائية الحد وكذلك القسمة على \(r-1\) في صيغة المجموع الهندسي.
بعد ذلك تنفذ الخوارزمية مرورًا تنازليًا واحدًا على \(r\) لملء جدول المعاملات باستخدام العلاقة السابقة. وفي المرور نفسه يُحدَّث معامل ثنائي الحد المطلوب بصيغة ضرب نسبية، لذلك لا حاجة إلى أي جداول للعامليات.
أخيرًا تُقيَّم كل حدود الأساس. تعالج حالتا \(r=0\) و\(r=1\) مباشرة، بينما تستخدم الحالات \(r\ge 2\) الرفع الثنائي السريع لحساب \(r^{n+1}\bmod M\). ويضيف تطبيق C++ تقسيمًا متوازيًا للمجموع النهائي عندما يكون \(k\) كبيرًا بما يكفي، في حين تنفذ تطبيقا Python وJava الحساب نفسه في مرور واحد.
يستغرق حساب المعكوسات المعيارية \(O(k)\) زمنًا و\(O(k)\) ذاكرة. كما أن بناء جميع المعاملات يكلف \(O(k)\) أيضًا. وفي مرحلة الجمع النهائية تُحسب \(k-2\) قوى غير تافهة، وكل منها في \(O(\log n)\)، لذا فإن الحد المسيطر هو \(O(k\log n)\). ويبلغ الاستهلاك الكلي للذاكرة \(O(k)\). أما التجميع المتوازي في C++ فيحسن الزمن الفعلي فقط ولا يغير الرتبة التقاربية.