This problem asks for the quantity \(A(k,n)\) arising from the matrix setup, under the condition \(k\mid n\), with the final value taken modulo \(M=10^9+7\). The concrete target is extremely large, so the essential task is to turn the definition into a summation that can be streamed term by term rather than expanded combinatorially from scratch.
The C++, Python, and Java implementations all reveal the same structure: once we write \(q=n/k\) and reduce \(2^q\) modulo \(M\), the whole computation becomes a weighted central-trinomial-type sum whose consecutive terms differ by a simple rational factor.
Throughout the derivation let
$$M=10^9+7,\qquad q=\frac{n}{k},\qquad b=2^q \pmod{M}.$$
The implementations do not build the answer from factorial tables. Instead they exploit a closed form for the summand and a recurrence between neighboring terms.
Modulo \(M\), a convenient reformulation is
$$A(k,n)\equiv [z^0]\,(b+z+z^{-1})^k \pmod{M},$$
where \([z^0]\) means the coefficient of \(z^0\). To contribute to the constant term, an expansion term must contain the same number of \(z\) and \(z^{-1}\) factors. If we choose exactly \(x\) copies of \(z\) and \(x\) copies of \(z^{-1}\), then the remaining \(k-2x\) factors contribute \(b\).
This gives the explicit sum
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
An equivalent binomial form is
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\binom{k}{2x}\binom{2x}{x}b^{k-2x}\pmod{M}.$$
This is why the sequence behaves like a weighted version of the central trinomial coefficients.
Define
$$T_x=\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
Then \(A(k,n)=\sum_x T_x\). The key simplification is that \(T_x\) can be obtained from \(T_{x-1}\) without recomputing any factorials:
$$\frac{T_x}{T_{x-1}}=\frac{(k-2x+2)(k-2x+1)}{x^2}\,b^{-2}.$$
The factorial part collapses because
$$\frac{(x-1)!^2(k-2x+2)!}{x!^2(k-2x)!}=\frac{(k-2x+2)(k-2x+1)}{x^2},$$
and the power of \(b\) drops by two at every step. Therefore
$$T_x=T_{x-1}\cdot \frac{(k-2x+2)(k-2x+1)}{x^2}\cdot b^{-2}\pmod{M},$$
starting from
$$T_0=b^k.$$
Because \(M\) is prime and \(b=2^q\) is nonzero modulo \(M\), every required division can be turned into multiplication by an inverse. Fermat's little theorem gives
$$a^{-1}\equiv a^{M-2}\pmod{M}$$
for any nonzero \(a\). In particular, the implementations compute \(b^{-1}\) as \(b^{M-2}\) and then square it once to get the fixed multiplier \(b^{-2}\).
They also need \(x^{-1}\) for all \(1\le x\le \lfloor k/2\rfloor\). Rather than calling fast exponentiation for each \(x\), they precompute inverses in linear time using
$$\operatorname{inv}(1)=1,\qquad \operatorname{inv}(i)=M-\left\lfloor\frac{M}{i}\right\rfloor \operatorname{inv}(M\bmod i)\pmod{M}.$$
Then the factor \(x^{-2}\) becomes two multiplications by \(\operatorname{inv}(x)\).
A direct factorial-based method would require large factorial and inverse-factorial tables up to \(k\), which is unnecessary here. The ratio formula reduces the update at step \(x\) to five ingredients: the previous term, two descending numerator factors, two copies of \(x^{-1}\), and the constant factor \(b^{-2}\).
So the computation can march from \(x=0\) to \(x=\lfloor k/2\rfloor\), updating the current term and adding it to the running total immediately. Nothing from earlier terms needs to be revisited.
For the checkpoint \(A(3,9)\), we have
$$q=\frac{9}{3}=3,\qquad b=2^3=8.$$
Since \(\lfloor 3/2\rfloor=1\), the sum has only two terms:
$$T_0=b^3=8^3=512,$$
$$T_1=\frac{3!}{1!^2\,1!}b^{1}=6\cdot 8=48.$$
Hence
$$A(3,9)=512+48=560,$$
matching the checkpoint used by the implementation. A second checkpoint is
$$A(4,20)=32^4+12\cdot 32^2+6=1{,}060{,}870.$$
The C++, Python, and Java implementations all follow the same algorithm. First they compute \(q=n/k\), then evaluate \(b=2^q\pmod{M}\) by fast modular exponentiation, and finally initialize the first summand as \(b^k\pmod{M}\). The running answer starts from that same initial term.
Next they compute the inverse of \(b\), square it to obtain \(b^{-2}\), and build an inverse table for the integers \(1\) through \(\lfloor k/2\rfloor\). During the main loop, the implementation updates the current summand by multiplying with the next two descending numerator factors, the inverse of the current index twice, and the fixed factor \(b^{-2}\). The new summand is then added to the running total modulo \(M\).
This approach avoids storing factorial arrays, inverse-factorial arrays, or any large polynomial object. The code keeps only the current summand, the running total, the inverse table, and a few loop variables.
Let \(h=\lfloor k/2\rfloor\). The modular exponentiations cost \(O(\log q+\log M)\) time, which is tiny compared with the main loop. Filling the inverse table costs \(O(h)\) time and \(O(h)\) memory, and the streaming summation also costs \(O(h)\) time. Therefore the full method runs in \(O(k)\) time and uses \(O(k)\) memory.
Gesucht ist die Groesse \(A(k,n)\), die in der Matrixformulierung des Problems entsteht, unter der Bedingung \(k\mid n\), modulo \(M=10^9+7\). Die Zielparameter sind so gross, dass eine direkte kombinatorische Auswertung unpraktisch ist. Entscheidend ist daher, die Definition in eine Summe zu ueberfuehren, deren Terme nacheinander aktualisiert werden koennen.
Die C++-, Python- und Java-Implementierungen zeigen dieselbe Struktur: Mit \(q=n/k\) und \(b=2^q \pmod{M}\) wird die Aufgabe zu einer gewichteteten zentral-trinomialen Summe, bei der benachbarte Summanden durch einen einfachen Quotienten verbunden sind.
Im Folgenden setzen wir
$$M=10^9+7,\qquad q=\frac{n}{k},\qquad b=2^q \pmod{M}.$$
Die Implementierung arbeitet nicht mit grossen Fakultaetstabellen, sondern mit einer geschlossenen Form fuer den Summanden und einer Rekursion zwischen aufeinanderfolgenden Termen.
Modulo \(M\) ist die folgende Darstellung sehr nuetzlich:
$$A(k,n)\equiv [z^0]\,(b+z+z^{-1})^k \pmod{M}.$$
Dabei bezeichnet \([z^0]\) den Koeffizienten von \(z^0\). Ein konstanter Term entsteht genau dann, wenn in der Entwicklung gleich viele Faktoren \(z\) und \(z^{-1}\) gewaehlt werden. Waehlt man genau \(x\) Kopien von \(z\) und \(x\) Kopien von \(z^{-1}\), dann liefern die verbleibenden \(k-2x\) Faktoren den Beitrag \(b\).
Daraus folgt die explizite Summe
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
In Binomialschreibweise ist das gleichbedeutend mit
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\binom{k}{2x}\binom{2x}{x}b^{k-2x}\pmod{M}.$$
Deshalb erinnert die Folge an eine gewichtete Version der zentralen Trinomialkoeffizienten.
Definiere
$$T_x=\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
Dann gilt \(A(k,n)=\sum_x T_x\). Der entscheidende Punkt ist, dass sich \(T_x\) direkt aus \(T_{x-1}\) berechnen laesst:
$$\frac{T_x}{T_{x-1}}=\frac{(k-2x+2)(k-2x+1)}{x^2}\,b^{-2}.$$
Der Fakultaeilteil vereinfacht sich zu
$$\frac{(x-1)!^2(k-2x+2)!}{x!^2(k-2x)!}=\frac{(k-2x+2)(k-2x+1)}{x^2},$$
und die Potenz von \(b\) sinkt pro Schritt um zwei. Also
$$T_x=T_{x-1}\cdot \frac{(k-2x+2)(k-2x+1)}{x^2}\cdot b^{-2}\pmod{M},$$
mit Startwert
$$T_0=b^k.$$
Weil \(M\) prim ist und \(b=2^q\) modulo \(M\) ungleich null ist, kann jede Division als Multiplikation mit einem Inversen geschrieben werden. Nach dem kleinen Satz von Fermat gilt
$$a^{-1}\equiv a^{M-2}\pmod{M}$$
fuer jedes von null verschiedene \(a\). Damit berechnet die Implementierung zunaechst \(b^{-1}\) und daraus einmalig den festen Faktor \(b^{-2}\).
Ausserdem werden die Inversen von \(1\) bis \(\lfloor k/2\rfloor\) nicht einzeln per Potenzierung erzeugt, sondern linear vorab berechnet durch
$$\operatorname{inv}(1)=1,\qquad \operatorname{inv}(i)=M-\left\lfloor\frac{M}{i}\right\rfloor \operatorname{inv}(M\bmod i)\pmod{M}.$$
Dadurch wird der Faktor \(x^{-2}\) zu zwei Multiplikationen mit \(\operatorname{inv}(x)\).
Ein direkter Ansatz mit Fakultaeten und inversen Fakultaeten bis \(k\) waere fuer diese Groessenordnung unnötig schwergewichtig. Die Quotientenformel reduziert jeden Schritt auf den vorherigen Summanden, zwei fallende Zaehlerfaktoren, zweimal \(x^{-1}\) und den festen Faktor \(b^{-2}\).
So laesst sich die gesamte Summe von \(x=0\) bis \(x=\lfloor k/2\rfloor\) einmal durchlaufen, wobei jeder neue Summand sofort zum Ergebnis addiert wird. Aeltere Terme muessen nicht gespeichert oder erneut betrachtet werden.
Fuer den Kontrollwert \(A(3,9)\) gilt
$$q=\frac{9}{3}=3,\qquad b=2^3=8.$$
Da \(\lfloor 3/2\rfloor=1\), gibt es nur zwei Summanden:
$$T_0=b^3=8^3=512,$$
$$T_1=\frac{3!}{1!^2\,1!}b^{1}=6\cdot 8=48.$$
Somit
$$A(3,9)=512+48=560,$$
genau wie im Kontrolltest der Implementierung. Ein zweiter Kontrollwert ist
$$A(4,20)=32^4+12\cdot 32^2+6=1{,}060{,}870.$$
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf. Zuerst werden \(q=n/k\), dann \(b=2^q\pmod{M}\) und anschliessend der erste Summand \(b^k\pmod{M}\) berechnet. Dieser erste Summand ist zugleich der Anfangswert der laufenden Summe.
Danach bestimmt die Implementierung das Inverse von \(b\), quadriert es zu \(b^{-2}\) und fuellt eine Inversentabelle fuer die Zahlen \(1\) bis \(\lfloor k/2\rfloor\). In der Hauptschleife wird der aktuelle Summand mit den naechsten beiden fallenden Zaehlerfaktoren, zweimal dem Inversen des aktuellen Index und dem festen Faktor \(b^{-2}\) aktualisiert. Anschliessend wird der neue Summand modulo \(M\) zur Gesamtsumme addiert.
Gespeichert werden nur der aktuelle Summand, die laufende Summe, die Inversentabelle und wenige Schleifenvariablen. Grosse Fakultaets- oder Polynomtabellen sind nicht noetig.
Mit \(h=\lfloor k/2\rfloor\) kosten die modularen Potenzierungen \(O(\log q+\log M)\) Zeit. Die Inversentabelle benoetigt \(O(h)\) Zeit und \(O(h)\) Speicher, und auch die Summation ueber alle Terme kostet \(O(h)\) Zeit. Insgesamt arbeitet das Verfahren also in \(O(k)\) Zeit und mit \(O(k)\) Speicher.
Bu problem, matris baglamindan gelen \(A(k,n)\) buyuklugunu \(k\mid n\) kosulu altinda ve \(M=10^9+7\) modunda hesaplamayi ister. Hedef parametreler cok buyuk oldugu icin tanimi dogrudan acmak yerine, her terimi bir onceki terimden ureten bir toplama formulune gecmek gerekir.
C++, Python ve Java uygulamalari ayni yapiyi ortaya koyar: \(q=n/k\) ve \(b=2^q \pmod{M}\) yazildiginda problem, ardiskik terimleri cok basit bir orana sahip agirlikli bir merkezi trinomial-toplam haline gelir.
Asagidaki kisaltmalari kullanalim:
$$M=10^9+7,\qquad q=\frac{n}{k},\qquad b=2^q \pmod{M}.$$
Uygulama buyuk faktoriyel tablolarina yaslanmaz; bunun yerine terimin kapali bicimini ve komsu terimler arasindaki yinelemeyi kullanir.
Modulo \(M\) altinda su yazim cok kullanislidir:
$$A(k,n)\equiv [z^0]\,(b+z+z^{-1})^k \pmod{M}.$$
Burada \([z^0]\), \(z^0\) katsayisini ifade eder. Sabit terim elde etmek icin acilimda secilen \(z\) ve \(z^{-1}\) sayilarinin esit olmasi gerekir. Eger tam olarak \(x\) tane \(z\) ve \(x\) tane \(z^{-1}\) secilirse, kalan \(k-2x\) carpan \(b\) verir.
Bu nedenle
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
Ayni ifade binom katsayilariyla
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\binom{k}{2x}\binom{2x}{x}b^{k-2x}\pmod{M}$$
seklinde de yazilir. Bu yuzden dizi, agirlikli merkezi trinomial katsayilara benzer.
Simdi
$$T_x=\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}$$
tanimini yapalim. O zaman \(A(k,n)=\sum_x T_x\) olur. Kritik gozlem, \(T_x\)'in \(T_{x-1}\)'den dogrudan elde edilmesidir:
$$\frac{T_x}{T_{x-1}}=\frac{(k-2x+2)(k-2x+1)}{x^2}\,b^{-2}.$$
Cunku faktoriyel kisim
$$\frac{(x-1)!^2(k-2x+2)!}{x!^2(k-2x)!}=\frac{(k-2x+2)(k-2x+1)}{x^2}$$
olarak sadeleşir ve \(b\)'nin ussu her adimda iki azalir. Dolayisiyla
$$T_x=T_{x-1}\cdot \frac{(k-2x+2)(k-2x+1)}{x^2}\cdot b^{-2}\pmod{M},$$
baslangicta da
$$T_0=b^k$$
vardir.
\(M\) asal oldugu ve \(b=2^q\) modulo \(M\) sifir olmadigi icin gereken her bolme, ters ile carpma bicimine cevrilir. Fermat'nin kucuk teoremi
$$a^{-1}\equiv a^{M-2}\pmod{M}$$
ifadesini verir. Bu sayede uygulama once \(b^{-1}\)'i, sonra da sabit carpan olarak kullanacagi \(b^{-2}\)'yi hesaplar.
Ayrica \(1\le x\le \lfloor k/2\rfloor\) araligindaki tum \(x^{-1}\) degerleri tek tek us alma ile degil, lineer bir formul ile onceden uretilir:
$$\operatorname{inv}(1)=1,\qquad \operatorname{inv}(i)=M-\left\lfloor\frac{M}{i}\right\rfloor \operatorname{inv}(M\bmod i)\pmod{M}.$$
Boylece \(x^{-2}\) carpanı, \(\operatorname{inv}(x)\) ile iki carpima donusur.
Dogrudan faktoriyel ve ters faktoriyel tablolari kurmak, bu buyuklukte gereksizdir. Oran formulu her adimi onceki terim, asagi inen iki pay carpanı, iki adet \(x^{-1}\) ve sabit \(b^{-2}\) ile tamamlar.
Boylece hesaplama \(x=0\)'dan \(x=\lfloor k/2\rfloor\)'ye kadar tek geciste ilerler; her yeni terim hemen sonuca eklenir. Eski terimleri saklamaya veya tekrar kullanmaya gerek yoktur.
Kontrol ornegi olarak \(A(3,9)\) icin
$$q=\frac{9}{3}=3,\qquad b=2^3=8$$
olur. \(\lfloor 3/2\rfloor=1\) oldugu icin sadece iki terim vardir:
$$T_0=b^3=8^3=512,$$
$$T_1=\frac{3!}{1!^2\,1!}b^1=6\cdot 8=48.$$
Buradan
$$A(3,9)=512+48=560$$
elde edilir; bu da uygulamanin kullandigi kontrol degeriyle aynidir. Ikinci bir kontrol noktasi da
$$A(4,20)=32^4+12\cdot 32^2+6=1{,}060{,}870$$
seklindedir.
C++, Python ve Java uygulamalari ayni algoritmayi izler. Once \(q=n/k\) hesaplanir, sonra hizli moduler us alma ile \(b=2^q\pmod{M}\) bulunur ve ilk terim \(b^k\pmod{M}\) olarak baslatilir. Toplam da bu ilk terimle acilir.
Daha sonra \(b\)'nin moduler tersi hesaplanir, karesi alinarak \(b^{-2}\) elde edilir ve \(1\) ile \(\lfloor k/2\rfloor\) arasindaki tum sayilar icin bir ters tablosu doldurulur. Ana dongude guncel terim, siradaki iki azalan pay carpanı, mevcut indeksin tersi iki kez ve sabit \(b^{-2}\) ile guncellenir. Her adimdan sonra yeni terim modulo \(M\) toplama eklenir.
Bu yontem buyuk faktoriyel dizilerini, ters faktoriyel dizilerini veya dev bir polinom acilimini saklamaz. Bellekte sadece guncel terim, toplam, ters tablosu ve birkac dongu degiskeni bulunur.
\(h=\lfloor k/2\rfloor\) olsun. Moduler us almalar \(O(\log q+\log M)\) zamanda biter. Ters tablosu \(O(h)\) zamanda ve \(O(h)\) bellekte kurulur; akici toplama dongusu da \(O(h)\) zamanda calisir. Dolayisiyla toplam karmasiklik \(O(k)\) zaman ve \(O(k)\) bellek olur.
El problema pide calcular la cantidad \(A(k,n)\) que aparece en la formulacion matricial, bajo la condicion \(k\mid n\), modulo \(M=10^9+7\). Como los parametros finales son enormes, no sirve desarrollar la definicion de forma directa; hace falta transformar el problema en una suma cuyos terminos puedan actualizarse de uno en uno.
Las implementaciones en C++, Python y Java muestran la misma idea central: si escribimos \(q=n/k\) y \(b=2^q \pmod{M}\), toda la expresion se convierte en una suma de tipo trinomial central ponderado, y los terminos consecutivos estan ligados por una razon muy simple.
Usaremos la notacion
$$M=10^9+7,\qquad q=\frac{n}{k},\qquad b=2^q \pmod{M}.$$
La implementacion evita tablas gigantes de factoriales. En su lugar utiliza una forma cerrada del sumando y una recurrencia entre terminos consecutivos.
Modulo \(M\), resulta util escribir
$$A(k,n)\equiv [z^0]\,(b+z+z^{-1})^k \pmod{M},$$
donde \([z^0]\) indica el coeficiente de \(z^0\). Para que un termino del desarrollo contribuya al termino constante, debe contener la misma cantidad de factores \(z\) que de factores \(z^{-1}\). Si elegimos exactamente \(x\) copias de \(z\) y \(x\) copias de \(z^{-1}\), entonces los \(k-2x\) factores restantes aportan \(b\).
Asi se obtiene
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
De forma equivalente,
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\binom{k}{2x}\binom{2x}{x}b^{k-2x}\pmod{M}.$$
Por eso la expresion tiene el aspecto de una version ponderada de los coeficientes trinomiales centrales.
Definamos
$$T_x=\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
Entonces \(A(k,n)=\sum_x T_x\). El punto clave es que no hace falta reconstruir cada termino desde cero, porque
$$\frac{T_x}{T_{x-1}}=\frac{(k-2x+2)(k-2x+1)}{x^2}\,b^{-2}.$$
La parte factorial se simplifica como
$$\frac{(x-1)!^2(k-2x+2)!}{x!^2(k-2x)!}=\frac{(k-2x+2)(k-2x+1)}{x^2},$$
y la potencia de \(b\) disminuye en dos unidades cada vez. Asi,
$$T_x=T_{x-1}\cdot \frac{(k-2x+2)(k-2x+1)}{x^2}\cdot b^{-2}\pmod{M},$$
con valor inicial
$$T_0=b^k.$$
Como \(M\) es primo y \(b=2^q\) no es cero modulo \(M\), toda division necesaria puede convertirse en una multiplicacion por un inverso. El pequeno teorema de Fermat da
$$a^{-1}\equiv a^{M-2}\pmod{M}$$
para todo \(a\neq 0\). Por eso la implementacion calcula primero \(b^{-1}\) y luego fija el factor constante \(b^{-2}\).
Ademas, para todos los valores \(1\le x\le \lfloor k/2\rfloor\), los inversos se precalculan en tiempo lineal mediante
$$\operatorname{inv}(1)=1,\qquad \operatorname{inv}(i)=M-\left\lfloor\frac{M}{i}\right\rfloor \operatorname{inv}(M\bmod i)\pmod{M}.$$
De esta manera, el factor \(x^{-2}\) se implementa como dos multiplicaciones por \(\operatorname{inv}(x)\).
Un enfoque ingenuo con factoriales e inversos factoriales hasta \(k\) seria innecesariamente pesado. La formula de la razon reduce cada paso al termino anterior, dos factores numeradores decrecientes, dos copias de \(x^{-1}\) y el factor fijo \(b^{-2}\).
Por tanto, la suma completa puede recorrerse desde \(x=0\) hasta \(x=\lfloor k/2\rfloor\) en una sola pasada, actualizando el termino actual y agregandolo enseguida al total. No hace falta volver a mirar terminos previos.
Para el punto de control \(A(3,9)\), tenemos
$$q=\frac{9}{3}=3,\qquad b=2^3=8.$$
Como \(\lfloor 3/2\rfloor=1\), solo aparecen dos terminos:
$$T_0=b^3=8^3=512,$$
$$T_1=\frac{3!}{1!^2\,1!}b^{1}=6\cdot 8=48.$$
Entonces
$$A(3,9)=512+48=560,$$
que coincide con la comprobacion usada por la implementacion. Un segundo punto de control es
$$A(4,20)=32^4+12\cdot 32^2+6=1{,}060{,}870.$$
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Primero calculan \(q=n/k\), luego \(b=2^q\pmod{M}\) mediante exponenciacion modular rapida y despues inicializan el primer sumando como \(b^k\pmod{M}\). Ese mismo valor sirve como inicio de la suma acumulada.
A continuacion calculan el inverso modular de \(b\), lo elevan al cuadrado para obtener \(b^{-2}\) y construyen una tabla de inversos para los enteros entre \(1\) y \(\lfloor k/2\rfloor\). En el bucle principal, el termino actual se actualiza multiplicando por los siguientes dos factores numeradores decrecientes, por el inverso del indice actual dos veces y por el factor fijo \(b^{-2}\). Tras cada actualizacion, el nuevo termino se suma al total modulo \(M\).
El metodo evita almacenar tablas grandes de factoriales, de inversos factoriales o una expansion polinomica completa. Solo conserva el termino actual, la suma acumulada, la tabla de inversos y unas pocas variables auxiliares.
Sea \(h=\lfloor k/2\rfloor\). Las exponenciaciones modulares cuestan \(O(\log q+\log M)\), insignificante frente al bucle principal. La tabla de inversos requiere \(O(h)\) tiempo y \(O(h)\) memoria, y la suma en streaming tambien consume \(O(h)\) tiempo. En consecuencia, el algoritmo completo es \(O(k)\) en tiempo y \(O(k)\) en memoria.
这道题要求计算矩阵背景下定义的量 \(A(k,n)\)，其中满足 \(k\mid n\)，最后对 \(M=10^9+7\) 取模。真正要代入的参数极大，因此不能按定义做直接展开，核心在于把问题改写成一个可以顺次更新的求和式。
C++、Python 和 Java 三份实现都说明了同一件事：一旦写出 \(q=n/k\)，并把 \(2^q\) 在模 \(M\) 下记作 \(b\)，整个问题就化成了一个带权的中心三项式型求和，而且相邻两项之间只有一个非常简单的乘法比值。
下面统一记
$$M=10^9+7,\qquad q=\frac{n}{k},\qquad b=2^q \pmod{M}.$$
实现并没有建立庞大的阶乘表，而是利用求和项的闭式表达和相邻项之间的递推关系。
在模 \(M\) 的意义下，可以把目标写成
$$A(k,n)\equiv [z^0]\,(b+z+z^{-1})^k \pmod{M},$$
其中 \([z^0]\) 表示取 \(z^0\) 的系数。要在展开后得到常数项，就必须让 \(z\) 和 \(z^{-1}\) 的选择次数相同。若恰好选了 \(x\) 个 \(z\) 和 \(x\) 个 \(z^{-1}\)，那么剩余的 \(k-2x\) 个因子全部贡献 \(b\)。
于是得到显式求和式
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
也可以写成组合数形式
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\binom{k}{2x}\binom{2x}{x}b^{k-2x}\pmod{M}.$$
这正是它看起来像“带权中心三项式系数”的原因。
定义
$$T_x=\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
那么 \(A(k,n)=\sum_x T_x\)。真正关键的是，不必从头计算每一项，因为
$$\frac{T_x}{T_{x-1}}=\frac{(k-2x+2)(k-2x+1)}{x^2}\,b^{-2}.$$
阶乘部分的约化非常直接：
$$\frac{(x-1)!^2(k-2x+2)!}{x!^2(k-2x)!}=\frac{(k-2x+2)(k-2x+1)}{x^2}.$$
与此同时，\(b\) 的幂次每前进一步恰好减少 \(2\)。因此有递推式
$$T_x=T_{x-1}\cdot \frac{(k-2x+2)(k-2x+1)}{x^2}\cdot b^{-2}\pmod{M},$$
并且初始项就是
$$T_0=b^k.$$
因为 \(M\) 是素数，而 \(b=2^q\) 在模 \(M\) 下不为零，所以所有除法都可以改写成乘以模逆。根据费马小定理，任意非零 \(a\) 都满足
$$a^{-1}\equiv a^{M-2}\pmod{M}.$$
因此实现先用快速幂求出 \(b^{-1}\)，再平方得到整个循环都会反复使用的常数因子 \(b^{-2}\)。
此外，所有 \(1\le x\le \lfloor k/2\rfloor\) 的逆元并不是逐个做快速幂，而是用线性递推一次性预处理：
$$\operatorname{inv}(1)=1,\qquad \operatorname{inv}(i)=M-\left\lfloor\frac{M}{i}\right\rfloor \operatorname{inv}(M\bmod i)\pmod{M}.$$
这样 \(x^{-2}\) 就变成了两次乘以 \(\operatorname{inv}(x)\)。
如果直接建立到 \(k\) 为止的阶乘和逆阶乘表，规模会过于庞大，而且这里并不需要。利用上面的比值公式，每一步只要知道前一项、两个递减的分子因子、当前下标的逆元两次，以及固定的 \(b^{-2}\)，就能得到下一项。
于是算法可以从 \(x=0\) 一直扫到 \(x=\lfloor k/2\rfloor\)，每得到一个新项就立刻加进答案。旧项不需要回看，也不需要保存整张组合表。
先看校验样例 \(A(3,9)\)。此时
$$q=\frac{9}{3}=3,\qquad b=2^3=8.$$
因为 \(\lfloor 3/2\rfloor=1\)，求和只有两项：
$$T_0=b^3=8^3=512,$$
$$T_1=\frac{3!}{1!^2\,1!}b^{1}=6\cdot 8=48.$$
所以
$$A(3,9)=512+48=560,$$
这与实现中使用的校验值完全一致。第二个校验值是
$$A(4,20)=32^4+12\cdot 32^2+6=1{,}060{,}870.$$
C++、Python 和 Java 实现遵循完全相同的流程。首先计算 \(q=n/k\)，然后用快速模幂得到 \(b=2^q\pmod{M}\)，再把第一项初始化为 \(b^k\pmod{M}\)。累计答案也从这一项开始。
接着，实现会求出 \(b\) 的模逆，并平方得到 \(b^{-2}\)，同时建立从 \(1\) 到 \(\lfloor k/2\rfloor\) 的逆元表。在主循环里，当前项乘上下一个两个递减分子因子、当前下标的逆元两次，以及固定因子 \(b^{-2}\)，就得到下一项。每次更新后都立即把新项加到答案里，并在模 \(M\) 下约简。
整个过程中不需要保存阶乘数组、逆阶乘数组，也不需要显式展开任何大多项式。代码只维护当前项、累计和、逆元表以及少量循环状态。
设 \(h=\lfloor k/2\rfloor\)。快速幂部分的时间复杂度是 \(O(\log q+\log M)\)，相对主循环几乎可以忽略。逆元表的预处理需要 \(O(h)\) 时间和 \(O(h)\) 空间，随后的一次线性求和同样需要 \(O(h)\) 时间。因此总复杂度为 \(O(k)\) 时间、\(O(k)\) 空间。
В задаче требуется вычислить величину \(A(k,n)\), возникающую в матричной постановке, при условии \(k\mid n\), по модулю \(M=10^9+7\). Итоговые параметры огромны, поэтому прямое раскрытие определения непрактично. Нужно привести задачу к сумме, члены которой можно обновлять последовательно.
Реализации на C++, Python и Java показывают одну и ту же структуру: если обозначить \(q=n/k\) и \(b=2^q \pmod{M}\), то вычисление сводится к взвешенной сумме триomialьного типа, а соседние слагаемые связаны очень простым множителем.
Будем использовать обозначения
$$M=10^9+7,\qquad q=\frac{n}{k},\qquad b=2^q \pmod{M}.$$
Реализация не строит огромные таблицы факториалов. Вместо этого она использует замкнутую форму для слагаемого и рекуррентное отношение между соседними членами суммы.
По модулю \(M\) удобно записать
$$A(k,n)\equiv [z^0]\,(b+z+z^{-1})^k \pmod{M},$$
где \([z^0]\) означает коэффициент при \(z^0\). Чтобы в разложении получить постоянный член, нужно выбрать одинаковое число множителей \(z\) и \(z^{-1}\). Если выбрано ровно \(x\) копий \(z\) и \(x\) копий \(z^{-1}\), то оставшиеся \(k-2x\) множителей дают вклад \(b\).
Отсюда следует явная сумма
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
Эквивалентно можно написать
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\binom{k}{2x}\binom{2x}{x}b^{k-2x}\pmod{M}.$$
Именно поэтому выражение похоже на взвешенную версию центральных триномиальных коэффициентов.
Обозначим
$$T_x=\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
Тогда \(A(k,n)=\sum_x T_x\). Главное наблюдение состоит в том, что каждый следующий член можно получить из предыдущего без повторного вычисления факториалов:
$$\frac{T_x}{T_{x-1}}=\frac{(k-2x+2)(k-2x+1)}{x^2}\,b^{-2}.$$
Факториальная часть сокращается так:
$$\frac{(x-1)!^2(k-2x+2)!}{x!^2(k-2x)!}=\frac{(k-2x+2)(k-2x+1)}{x^2},$$
а степень \(b\) на каждом шаге уменьшается на \(2\). Поэтому
$$T_x=T_{x-1}\cdot \frac{(k-2x+2)(k-2x+1)}{x^2}\cdot b^{-2}\pmod{M},$$
начиная с
$$T_0=b^k.$$
Так как \(M\) простое и \(b=2^q\) не равно нулю по модулю \(M\), все деления можно заменить умножением на обратные элементы. По малой теореме Ферма
$$a^{-1}\equiv a^{M-2}\pmod{M}$$
для любого ненулевого \(a\). Поэтому реализация сначала находит \(b^{-1}\), а затем получает постоянный множитель \(b^{-2}\).
Кроме того, обратные для всех \(1\le x\le \lfloor k/2\rfloor\) предвычисляются за линейное время по формуле
$$\operatorname{inv}(1)=1,\qquad \operatorname{inv}(i)=M-\left\lfloor\frac{M}{i}\right\rfloor \operatorname{inv}(M\bmod i)\pmod{M}.$$
Тогда множитель \(x^{-2}\) превращается в два умножения на \(\operatorname{inv}(x)\).
Наивный подход с таблицами факториалов и обратных факториалов до \(k\) здесь избыточен. Формула отношения показывает, что для перехода к следующему члену нужны только предыдущий член, два убывающих множителя в числителе, два множителя \(x^{-1}\) и постоянный фактор \(b^{-2}\).
Значит, сумма вычисляется одним линейным проходом от \(x=0\) до \(x=\lfloor k/2\rfloor\), причём каждый новый член сразу добавляется к ответу. Хранить всю историю слагаемых не требуется.
Для контрольного значения \(A(3,9)\) имеем
$$q=\frac{9}{3}=3,\qquad b=2^3=8.$$
Так как \(\lfloor 3/2\rfloor=1\), в сумме только два слагаемых:
$$T_0=b^3=8^3=512,$$
$$T_1=\frac{3!}{1!^2\,1!}b^{1}=6\cdot 8=48.$$
Следовательно,
$$A(3,9)=512+48=560,$$
что совпадает с контрольной проверкой в реализации. Второе контрольное значение:
$$A(4,20)=32^4+12\cdot 32^2+6=1{,}060{,}870.$$
Реализации на C++, Python и Java следуют одному и тому же плану. Сначала вычисляются \(q=n/k\), затем \(b=2^q\pmod{M}\) с помощью быстрого возведения в степень, после чего первый член инициализируется как \(b^k\pmod{M}\). С этого же значения начинается накопление ответа.
Далее код находит модульную обратную к \(b\), возводит её в квадрат, получая \(b^{-2}\), и строит таблицу обратных для чисел от \(1\) до \(\lfloor k/2\rfloor\). В основном цикле текущий член обновляется умножением на два следующих убывающих множителя числителя, на обратный элемент к текущему индексу дважды и на постоянный множитель \(b^{-2}\). После этого новый член сразу прибавляется к сумме по модулю \(M\).
Код не хранит массивы факториалов, обратных факториалов и не разворачивает большие полиномы. Ему достаточно текущего члена, накопленной суммы, таблицы обратных и нескольких переменных цикла.
Пусть \(h=\lfloor k/2\rfloor\). Быстрые возведения в степень требуют \(O(\log q+\log M)\) времени, что мало по сравнению с основным циклом. Построение таблицы обратных занимает \(O(h)\) времени и \(O(h)\) памяти, и сама суммирующая петля тоже работает за \(O(h)\). Итак, полный алгоритм имеет сложность \(O(k)\) по времени и \(O(k)\) по памяти.
تطلب المسألة حساب الكمية \(A(k,n)\) الناتجة عن الصياغة المصفوفية مع الشرط \(k\mid n\)، ثم اخذ الناتج بترديد \(M=10^9+7\). بما ان القيم المطلوبة ضخمة جدا، فلا يمكن الاعتماد على التوسع المباشر للتعريف. الفكرة الحاسمة هي تحويل المسألة إلى مجموع يمكن تحديث حدوده حدًا بعد حد.
توضح تطبيقات C++ وPython وJava البنية نفسها: بعد كتابة \(q=n/k\) وتعريف \(b=2^q \pmod{M}\)، تصبح المسألة مجموعا من نوع ثلاثي مركزي موزون، وتكون النسبة بين كل حد والذي يليه بسيطة جدا.
سنستخدم الترميز
$$M=10^9+7,\qquad q=\frac{n}{k},\qquad b=2^q \pmod{M}.$$
لا تعتمد الخوارزمية على جداول ضخمة للعوامل، بل على صيغة مغلقة لكل حد وعلى علاقة تكرارية بين الحدود المتتالية.
بترديد \(M\)، من الملائم كتابة
$$A(k,n)\equiv [z^0]\,(b+z+z^{-1})^k \pmod{M},$$
حيث \([z^0]\) تعني معامل \(z^0\). لكي يساهم حد من التوسع في المعامل الثابت، يجب اختيار عدد متساو من العوامل \(z\) و\(z^{-1}\). فإذا اخترنا بالضبط \(x\) نسخا من \(z\) و\(x\) نسخا من \(z^{-1}\)، فان العوامل المتبقية وعددها \(k-2x\) تعطي العامل \(b\).
ومن ثم نحصل على المجموع الصريح
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
وبصيغة معاملات ثنائية الحد يمكن كتابة ذلك على الشكل
$$A(k,n)=\sum_{x=0}^{\lfloor k/2\rfloor}\binom{k}{2x}\binom{2x}{x}b^{k-2x}\pmod{M}.$$
ولهذا يبدو التعبير كنسخة موزونة من معاملات ثلاثية مركزية.
لنعرّف
$$T_x=\frac{k!}{x!^2(k-2x)!}\,b^{k-2x}\pmod{M}.$$
عندئذ يكون \(A(k,n)=\sum_x T_x\). والملاحظة الاهم هي ان \(T_x\) يمكن استخراجه من \(T_{x-1}\) مباشرة دون اعادة حساب العوامل من البداية:
$$\frac{T_x}{T_{x-1}}=\frac{(k-2x+2)(k-2x+1)}{x^2}\,b^{-2}.$$
وذلك لان الجزء العاملي يختزل إلى
$$\frac{(x-1)!^2(k-2x+2)!}{x!^2(k-2x)!}=\frac{(k-2x+2)(k-2x+1)}{x^2},$$
كما ان اس \(b\) ينخفض بمقدار \(2\) في كل خطوة. لذلك نحصل على العلاقة
$$T_x=T_{x-1}\cdot \frac{(k-2x+2)(k-2x+1)}{x^2}\cdot b^{-2}\pmod{M},$$
مع البداية
$$T_0=b^k.$$
بما ان \(M\) عدد اولي و\(b=2^q\) غير صفري بترديد \(M\)، يمكن تحويل كل قسمة لازمة إلى ضرب في معكوس معياري. تعطي مبرهنة فيرما الصغرى
$$a^{-1}\equiv a^{M-2}\pmod{M}$$
لكل \(a\neq 0\). ولذلك تحسب التطبيقات اولا \(b^{-1}\)، ثم تربع النتيجة للحصول على العامل الثابت \(b^{-2}\).
كذلك لا يتم حساب معكوس كل \(x\) على حدة بواسطة اس سريع، بل يتم تجهيز جميع المعكوسات من \(1\) حتى \(\lfloor k/2\rfloor\) بخطية زمنية وفق
$$\operatorname{inv}(1)=1,\qquad \operatorname{inv}(i)=M-\left\lfloor\frac{M}{i}\right\rfloor \operatorname{inv}(M\bmod i)\pmod{M}.$$
وعندها يصبح العامل \(x^{-2}\) مجرد ضربتين في \(\operatorname{inv}(x)\).
النهج الساذج الذي يبني جداول للعوامل ولمعكوسات العوامل حتى \(k\) ثقيل بلا حاجة هنا. صيغة النسبة توضح ان كل خطوة تحتاج فقط إلى الحد السابق، وعاملين متناقصين في البسط، ومعكوس \(x\) مرتين، والعامل الثابت \(b^{-2}\).
وهكذا يمكن المرور على القيم من \(x=0\) حتى \(x=\lfloor k/2\rfloor\) مرة واحدة فقط، مع تحديث الحد الحالي واضافته فورا إلى المجموع. لا حاجة لتخزين جميع الحدود السابقة.
في نقطة التحقق \(A(3,9)\) نحصل على
$$q=\frac{9}{3}=3,\qquad b=2^3=8.$$
ولان \(\lfloor 3/2\rfloor=1\)، فالمجموع يتكون من حدين فقط:
$$T_0=b^3=8^3=512,$$
$$T_1=\frac{3!}{1!^2\,1!}b^{1}=6\cdot 8=48.$$
ومن ثم
$$A(3,9)=512+48=560,$$
وهو نفس مقدار التحقق المستخدم في التنفيذ. كما ان نقطة تحقق ثانية هي
$$A(4,20)=32^4+12\cdot 32^2+6=1{,}060{,}870.$$
تتبع تطبيقات C++ وPython وJava الخطة نفسها. اولا تحسب \(q=n/k\)، ثم تحسب \(b=2^q\pmod{M}\) بواسطة الاس السريع المعياري، وبعد ذلك تهيئ الحد الاول على صورة \(b^k\pmod{M}\). ويبدأ مجموع الاجابة من هذا الحد نفسه.
بعد ذلك تحسب المعكوس المعياري لـ \(b\)، وتربعُه للحصول على \(b^{-2}\)، ثم تبني جدولا لمعكوسات الاعداد من \(1\) حتى \(\lfloor k/2\rfloor\). داخل الحلقة الرئيسية يتم تحديث الحد الحالي بضربه في العاملين المتناقصين التاليين من البسط، وفي معكوس الفهرس الحالي مرتين، وفي العامل الثابت \(b^{-2}\). وبعد كل تحديث يضاف الحد الجديد مباشرة إلى المجموع بترديد \(M\).
لا يخزن التنفيذ جداول ضخمة للعوامل او لمعكوسات العوامل، ولا يبني تمددا كثير حدود كاملا. كل ما يحتاجه هو الحد الحالي، والمجموع الجاري، وجدول المعكوسات، وبعض متغيرات الحلقة.
ليكن \(h=\lfloor k/2\rfloor\). عمليات الاس السريع تكلف \(O(\log q+\log M)\) زمنا، وهي صغيرة مقارنة بالحلقة الرئيسية. بناء جدول المعكوسات يحتاج \(O(h)\) زمنا و\(O(h)\) ذاكرة، كما ان الجمع الخطي نفسه يحتاج \(O(h)\) زمنا. لذلك تكون الكلفة الكلية \(O(k)\) زمنا و\(O(k)\) ذاكرة.