Problem 984, Knights and Horses, ultimately asks for the value of a specific integer sequence at the enormous index \(n=10^{18}\), reduced modulo \(10^9+7\). The implementations make that sequence concrete through its first terms \(1,4,9,92,903,4411,14959,41083,98200,212418,425756,803074,1441065,2479669\).
The key point is that the computation is not done by any direct combinatorial search at size \(10^{18}\). Instead, the sequence has already been compressed into two exact algebraic descriptions: a parity-sensitive closed form for the tail of the sequence, and a linear-recurrence evaluator that can reproduce the remaining cases modulo the prime modulus.
The three implementations expose the same structure: after the first few exceptional indices, the Knights and Horses sequence is a quasi-polynomial in \(n\) with period 2. The recurrence engine and the explicit even formula are two faces of the same underlying mathematics.
From the stored initial values and the signed recurrence used in the exact checkpoint, the tail of the sequence satisfies
$$ f_n=7f_{n-1}-19f_{n-2}+21f_{n-3}+6f_{n-4}-42f_{n-5}+42f_{n-6}-6f_{n-7}-21f_{n-8}+19f_{n-9}-7f_{n-10}+f_{n-11}, \qquad n\ge 15. $$
This is the actual algebraic law extracted from the implementations. The final Project Euler answer is simply the value of this sequence at a huge even index.
The generic evaluator stores fourteen basis values, so its transition polynomial is
$$ \chi(x)=x^{14}-7x^{13}+19x^{12}-21x^{11}-6x^{10}+42x^9-42x^8+6x^7+21x^6-19x^5+7x^4-x^3. $$
Factoring it gives
$$ \chi(x)=x^3(x-1)^9(x+1)^2. $$
The factor \(x^3\) explains why the smallest indices are treated separately. After that transient prefix, the behavior is governed by the roots \(1\) and \(-1\): multiplicity 9 at \(1\), and multiplicity 2 at \(-1\).
A root \(1\) of multiplicity 9 contributes a polynomial of degree at most 8, while a root \(-1\) of multiplicity 2 contributes \((-1)^n\) times a polynomial of degree at most 1. Therefore, for \(n\ge 4\), the sequence must have the form
$$ f(n)=A_8(n)+(-1)^nB_1(n), $$
with \(\deg A_8\le 8\) and \(\deg B_1\le 1\). Matching this shape against the values encoded in the implementations yields
$$ f(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{941251}{4480}n-\frac{107261}{256}-(-1)^n\frac{2n+3}{256}, \qquad n\ge 4. $$
This single formula explains why the code can switch between a polynomial shortcut and a generic recurrence solver without changing the underlying sequence.
The required query is \(n=10^{18}\), which is even. Setting \((-1)^n=1\) collapses the quasi-polynomial to the degree-8 polynomial used directly by the implementations:
$$ P(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{29413}{140}n-419, \qquad n>3,\ n\equiv 0\pmod 2. $$
Because the modulus \(10^9+7\) is prime and larger than every denominator that appears here, each division is implemented as multiplication by a modular inverse.
The parity reduction is already enough to show the method on a concrete value. Since \(16\) is even and greater than 3, we use the closed polynomial:
$$ f(16)=P(16)=6623481. $$
The recurrence branch produces the same value from earlier terms, so the polynomial and the recurrence are not independent tricks; they are two exact descriptions of the same tail sequence.
The C++, Python, and Java implementations first notice that the requested index \(10^{18}\) is even. They compute \(n,n^2,\dots,n^8\) modulo \(10^9+7\), replace each rational denominator by its modular inverse, and evaluate the polynomial \(P(n)\) term by term. That is enough to obtain the final answer for the problem instance.
The implementations also keep a general recurrence solver. It represents \(x^{n-1}\) modulo the transition polynomial \(\chi(x)\), using repeated squaring on coefficient vectors. After each coefficient-vector multiplication, higher powers are reduced with the recurrence coefficients, which is the standard quotient-ring or Kitamasa viewpoint for linear recurrences. Although fourteen basis slots are stored, the last three recurrence coefficients are zero, so the genuine tail relation is the 11-term recurrence written above.
One implementation performs explicit sanity checks before the final evaluation. It verifies small values such as \(f(3)=9\) and \(f(5)=903\), checks the exact integer value \(f(100)=8658918531876\) using signed 128-bit recurrence arithmetic, and confirms the modular checkpoint \(f(10000)\equiv 377956308\pmod{10^9+7}\). These checks protect against indexing mistakes, sign errors, and incorrect modular reductions.
For the actual Project Euler query, the runtime is \(O(1)\): the target index is even, so only a fixed number of modular multiplications and inverses are needed to evaluate the degree-8 polynomial. Memory usage is also \(O(1)\).
The retained generic evaluator is more general. With a fixed state size \(K=14\), repeated squaring of reduced coefficient vectors costs \(O(K^2\log n)\) time and \(O(K)\) memory. Since only 11 recurrence coefficients are nonzero, the constant factor is small.
Problem 984, Knights and Horses, verlangt letztlich den Wert einer bestimmten ganzzahligen Folge beim riesigen Index \(n=10^{18}\), reduziert modulo \(10^9+7\). Die Implementierungen machen diese Folge durch ihre Anfangswerte konkret: \(1,4,9,92,903,4411,14959,41083,98200,212418,425756,803074,1441065,2479669\).
Entscheidend ist, dass die Rechnung nicht durch direkte kombinatorische Suche bei Größe \(10^{18}\) erfolgt. Stattdessen ist das Problem bereits auf zwei exakte algebraische Beschreibungen verdichtet: eine paritätsabhängige geschlossene Formel für den Folgenschwanz und einen linearen Rekurrenzauswerter für die übrigen Fälle modulo der Primzahl \(10^9+7\).
Die drei Implementierungen zeigen dieselbe Struktur: Nach wenigen Ausnahmeindizes ist die Knights-and-Horses-Folge ein Quasipolynom in \(n\) mit Periode 2. Rekurrenzmotor und explizite Formel für gerade \(n\) sind nur zwei Sichtweisen auf dieselbe Mathematik.
Aus den gespeicherten Anfangswerten und der vorzeichenbehafteten Rekurrenz, die für den exakten Kontrollwert benutzt wird, folgt für den Folgenschwanz
$$ f_n=7f_{n-1}-19f_{n-2}+21f_{n-3}+6f_{n-4}-42f_{n-5}+42f_{n-6}-6f_{n-7}-21f_{n-8}+19f_{n-9}-7f_{n-10}+f_{n-11}, \qquad n\ge 15. $$
Das ist das tatsächliche algebraische Gesetz, das aus den Implementierungen extrahiert wird. Die gesuchte Euler-Antwort ist einfach der Wert dieser Folge an einem sehr großen geraden Index.
Der generische Auswerter speichert vierzehn Basiswerte, daher lautet sein Übergangspolynom
$$ \chi(x)=x^{14}-7x^{13}+19x^{12}-21x^{11}-6x^{10}+42x^9-42x^8+6x^7+21x^6-19x^5+7x^4-x^3. $$
Die Faktorisierung ist
$$ \chi(x)=x^3(x-1)^9(x+1)^2. $$
Der Faktor \(x^3\) erklärt, warum die kleinsten Indizes separat behandelt werden. Danach wird das Verhalten nur noch von den Wurzeln \(1\) und \(-1\) gesteuert: Vielfachheit 9 bei \(1\) und Vielfachheit 2 bei \(-1\).
Eine Wurzel \(1\) der Vielfachheit 9 liefert einen Polynomanteil vom Grad höchstens 8, während eine Wurzel \(-1\) der Vielfachheit 2 einen Anteil der Form \((-1)^n\) mal Polynom vom Grad höchstens 1 erzeugt. Deshalb muss für \(n\ge 4\) gelten
$$ f(n)=A_8(n)+(-1)^nB_1(n), $$
wobei \(\deg A_8\le 8\) und \(\deg B_1\le 1\). Durch Abgleich mit den in den Implementierungen vorliegenden Werten erhält man
$$ f(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{941251}{4480}n-\frac{107261}{256}-(-1)^n\frac{2n+3}{256}, \qquad n\ge 4. $$
Diese eine Formel erklärt, warum der Code zwischen einer polynomiellen Abkürzung und einem generischen Rekurrenzauswerter wechseln kann, ohne die zugrunde liegende Folge zu verändern.
Die gesuchte Anfrage verwendet \(n=10^{18}\), also einen geraden Index. Setzt man \((-1)^n=1\), kollabiert das Quasipolynom zu dem Polynom achten Grades, das in den Implementierungen direkt ausgewertet wird:
$$ P(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{29413}{140}n-419, \qquad n>3,\ n\equiv 0\pmod 2. $$
Da der Modulus \(10^9+7\) prim ist und größer als alle vorkommenden Nenner, wird jede Division als Multiplikation mit einem modularen Inversen umgesetzt.
Die Paritätsreduktion reicht schon aus, um die Methode an einem konkreten Wert zu sehen. Weil \(16\) gerade und größer als 3 ist, verwenden wir das geschlossene Polynom:
$$ f(16)=P(16)=6623481. $$
Der Rekurrenzzweig liefert aus früheren Folgengliedern denselben Wert. Das Polynom und die Rekurrenz sind also keine voneinander unabhängigen Tricks, sondern zwei exakte Beschreibungen desselben Folgenschwanzes.
Die C++-, Python- und Java-Implementierungen erkennen zuerst, dass der angefragte Index \(10^{18}\) gerade ist. Dann berechnen sie \(n,n^2,\dots,n^8\) modulo \(10^9+7\), ersetzen jeden rationalen Nenner durch sein modulares Inverses und werten das Polynom \(P(n)\) Term für Term aus. Das genügt bereits für die endgültige Antwort dieses Problems.
Zusätzlich bleibt ein allgemeiner Rekurrenzauswerter erhalten. Er repräsentiert \(x^{n-1}\) modulo dem Übergangspolynom \(\chi(x)\) und benutzt wiederholtes Quadrieren auf Koeffizientenvektoren. Nach jeder Multiplikation von Koeffizientenvektoren werden hohe Potenzen mit den Rekurrenzkoeffizienten zurückgefaltet; das ist genau die Quotientenring- oder Kitamasa-Sicht auf lineare Rekurrenzen. Obwohl vierzehn Basisplätze gespeichert werden, sind die letzten drei Rekurrenzkoeffizienten null, daher ist die echte Schwanzrelation die oben angegebene 11-gliedrige Rekurrenz.
Eine Implementierung führt vor der Endauswertung explizite Plausibilitätsprüfungen durch. Kontrolliert werden unter anderem \(f(3)=9\) und \(f(5)=903\), der exakte Ganzzahlwert \(f(100)=8658918531876\) mit vorzeichenbehafteter 128-Bit-Rekurrenzarithmetik sowie der modulare Kontrollwert \(f(10000)\equiv 377956308\pmod{10^9+7}\). Dadurch werden Indexfehler, Vorzeichenfehler und falsche modulare Reduktionen früh erkannt.
Für die tatsächliche Project-Euler-Anfrage ist die Laufzeit \(O(1)\): Der Zielindex ist gerade, also genügt eine feste Anzahl modularer Multiplikationen und Inversen zur Auswertung des Polynoms achten Grades. Auch der Speicherbedarf ist \(O(1)\).
Der beibehaltene generische Auswerter ist allgemeiner. Bei fester Zustandsgröße \(K=14\) kostet wiederholtes Quadrieren reduzierter Koeffizientenvektoren \(O(K^2\log n)\) Zeit und \(O(K)\) Speicher. Weil nur 11 Rekurrenzkoeffizienten ungleich null sind, bleibt der konstante Faktor klein.
Problem 984, Knights and Horses, sonunda belirli bir tam sayı dizisinin \(n=10^{18}\) indeksindeki değerini \(10^9+7\) modunda istemektedir. Uygulamalar bu diziyi ilk terimleriyle somutlaştırır: \(1,4,9,92,903,4411,14959,41083,98200,212418,425756,803074,1441065,2479669\).
Önemli nokta şu: hesaplama \(10^{18}\) boyutunda doğrudan bir kombinatorik arama ile yapılmıyor. Bunun yerine dizi iki tam cebirsel tanıma indirgenmiş durumda: dizinin kuyruğu için pariteye duyarlı kapalı form ve geri kalan durumları asal mod altında üreten bir lineer rekürans değerlendiricisi.
Üç uygulama da aynı yapıyı gösteriyor: birkaç istisnai indisten sonra Knights and Horses dizisi, periyodu 2 olan bir kuazipolinoma dönüşüyor. Rekürans motoru ile açık çift-indis formülü, aynı matematiğin iki görünümüdür.
Saklanan başlangıç değerlerinden ve tam sayı kontrolünde kullanılan işaretli reküranstan, dizinin kuyruğu için
$$ f_n=7f_{n-1}-19f_{n-2}+21f_{n-3}+6f_{n-4}-42f_{n-5}+42f_{n-6}-6f_{n-7}-21f_{n-8}+19f_{n-9}-7f_{n-10}+f_{n-11}, \qquad n\ge 15. $$
bağıntısı elde edilir. Kodun gerçekten kullandığı cebirsel yasa budur. Son Euler cevabı da bu dizinin çok büyük bir çift indisteki değerinden ibarettir.
Genel amaçlı değerlendirici on dört temel değer tuttuğu için geçiş polinomu
$$ \chi(x)=x^{14}-7x^{13}+19x^{12}-21x^{11}-6x^{10}+42x^9-42x^8+6x^7+21x^6-19x^5+7x^4-x^3 $$
olur. Bunun çarpanlara ayrılması
$$ \chi(x)=x^3(x-1)^9(x+1)^2 $$
şeklindedir. \(x^3\) çarpanı, en küçük indislerin neden ayrı ele alındığını açıklar. Bu geçici başlangıç bölgesi geçildikten sonra davranış sadece \(1\) ve \(-1\) kökleri tarafından belirlenir: \(1\) kökü 9 katlı, \(-1\) kökü 2 katlıdır.
Çokluğu 9 olan \(1\) kökü en fazla 8. dereceden bir polinom katkısı üretir. Çokluğu 2 olan \(-1\) kökü ise \((-1)^n\) ile çarpılan en fazla 1. dereceden bir polinom getirir. Bu yüzden \(n\ge 4\) için dizinin biçimi mutlaka
$$ f(n)=A_8(n)+(-1)^nB_1(n) $$
olmalıdır; burada \(\deg A_8\le 8\) ve \(\deg B_1\le 1\). Bu kalıbı uygulamalardaki değerlerle eşleyince
$$ f(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{941251}{4480}n-\frac{107261}{256}-(-1)^n\frac{2n+3}{256}, \qquad n\ge 4 $$
elde edilir. Kodun bir yandan polinom kısayolu, bir yandan genel rekürans çözücüsü kullanabilmesinin nedeni tam olarak budur.
İstenen sorgu \(n=10^{18}\) olduğundan, hedef indis çifttir. Önceki ifadede \((-1)^n=1\) yazınca, uygulamaların doğrudan kullandığı 8. derece polinom ortaya çıkar:
$$ P(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{29413}{140}n-419, \qquad n>3,\ n\equiv 0\pmod 2. $$
Modül \(10^9+7\) asal olduğu ve burada görünen bütün paydalardan büyük olduğu için, her bölme işlemi modüler ters ile çarpma olarak uygulanır.
Parite indirgemesi yöntemin nasıl çalıştığını somut biçimde gösterir. \(16\) çift ve 3'ten büyük olduğu için kapalı polinomu kullanırız:
$$ f(16)=P(16)=6623481. $$
Rekürans kolu da önceki terimlerden aynı değeri üretir. Yani polinom ile rekürans birbirinden bağımsız iki hile değil, aynı kuyruk dizisinin iki tam ifadesidir.
C++, Python ve Java uygulamaları önce istenen indeksin \(10^{18}\) ve dolayısıyla çift olduğunu görür. Ardından \(n,n^2,\dots,n^8\) değerlerini \(10^9+7\) modunda hesaplar, her rasyonel paydayı modüler tersiyle değiştirir ve \(P(n)\) polinomunu terim terim toplar. Bu, problem örneğinin nihai cevabı için yeterlidir.
Uygulamalar ayrıca genel bir rekürans çözücüsünü de korur. Bu çözücü \(x^{n-1}\) ifadesini geçiş polinomu \(\chi(x)\) altında temsil eder ve katsayı vektörleri üzerinde hızlı üs alma uygular. Her katsayı-vektörü çarpımından sonra yüksek dereceler rekürans katsayılarıyla geri katlanır; bu, lineer reküransların bölüm halkası ya da Kitamasa bakış açısının doğrudan uygulanışıdır. On dört temel yuva tutulsa da son üç rekürans katsayısı sıfırdır; dolayısıyla dizinin gerçek kuyruk ilişkisi yukarıdaki 11 terimli bağıntıdır.
Uygulamalardan biri son hesaplamadan önce açık doğrulamalar yapar. \(f(3)=9\) ve \(f(5)=903\) gibi küçük değerler test edilir; ayrıca \(f(100)=8658918531876\) değeri işaretli 128 bit rekürans aritmetiğiyle tam olarak kontrol edilir ve modüler kontrol noktası olarak \(f(10000)\equiv 377956308\pmod{10^9+7}\) doğrulanır. Bu kontroller indeksleme hatalarını, işaret hatalarını ve yanlış modüler indirgemeleri yakalar.
Gerçek Project Euler sorgusu için çalışma süresi \(O(1)\)'dir: hedef indis çift olduğundan, 8. derece polinomu değerlendirmek için sabit sayıda modüler çarpma ve ters alma yeterlidir. Bellek kullanımı da \(O(1)\)'dir.
Korunan genel çözücü daha kapsayıcıdır. Sabit \(K=14\) durum boyutunda, indirgenmiş katsayı vektörleri üzerinde hızlı üs alma \(O(K^2\log n)\) zaman ve \(O(K)\) bellek gerektirir. Sadece 11 rekürans katsayısı sıfırdan farklı olduğu için sabit çarpan küçüktür.
El Problema 984, Knights and Horses, pide en esencia el valor de una cierta sucesión entera en el índice enorme \(n=10^{18}\), reducido módulo \(10^9+7\). Las implementaciones vuelven esa sucesión explícita a través de sus primeros términos: \(1,4,9,92,903,4411,14959,41083,98200,212418,425756,803074,1441065,2479669\).
La idea importante es que el cálculo no se hace mediante una búsqueda combinatoria directa en tamaño \(10^{18}\). En cambio, la sucesión ya ha sido comprimida en dos descripciones algebraicas exactas: una forma cerrada sensible a la paridad para la cola de la sucesión, y un evaluador por recurrencia lineal que cubre los casos restantes bajo el módulo primo.
Las tres implementaciones muestran la misma estructura: después de unos pocos índices excepcionales, la sucesión de Knights and Horses es un cuasipolinomio en \(n\) de período 2. El motor de recurrencia y la fórmula explícita para \(n\) par son dos manifestaciones de la misma matemática.
A partir de los valores iniciales almacenados y de la recurrencia con signo usada en la comprobación exacta, la cola de la sucesión satisface
$$ f_n=7f_{n-1}-19f_{n-2}+21f_{n-3}+6f_{n-4}-42f_{n-5}+42f_{n-6}-6f_{n-7}-21f_{n-8}+19f_{n-9}-7f_{n-10}+f_{n-11}, \qquad n\ge 15. $$
Esa es la ley algebraica real extraída de las implementaciones. La respuesta final de Project Euler no es otra cosa que el valor de esta sucesión en un índice par gigantesco.
El evaluador genérico guarda catorce valores base, así que su polinomio de transición es
$$ \chi(x)=x^{14}-7x^{13}+19x^{12}-21x^{11}-6x^{10}+42x^9-42x^8+6x^7+21x^6-19x^5+7x^4-x^3. $$
Su factorización es
$$ \chi(x)=x^3(x-1)^9(x+1)^2. $$
El factor \(x^3\) explica por qué los índices más pequeños se tratan aparte. Después de ese prefijo transitorio, el comportamiento queda gobernado por las raíces \(1\) y \(-1\): multiplicidad 9 en \(1\) y multiplicidad 2 en \(-1\).
Una raíz \(1\) de multiplicidad 9 aporta una parte polinómica de grado a lo sumo 8, mientras que una raíz \(-1\) de multiplicidad 2 aporta \((-1)^n\) multiplicado por un polinomio de grado a lo sumo 1. Por tanto, para \(n\ge 4\), la sucesión debe tener la forma
$$ f(n)=A_8(n)+(-1)^nB_1(n), $$
con \(\deg A_8\le 8\) y \(\deg B_1\le 1\). Ajustando esa forma a los valores codificados en las implementaciones se obtiene
$$ f(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{941251}{4480}n-\frac{107261}{256}-(-1)^n\frac{2n+3}{256}, \qquad n\ge 4. $$
Esta única fórmula explica por qué el código puede alternar entre un atajo polinómico y un resolvedor general de recurrencias sin cambiar la sucesión subyacente.
La consulta pedida usa \(n=10^{18}\), que es par. Al fijar \((-1)^n=1\), el cuasipolinomio colapsa al polinomio de grado 8 que las implementaciones evalúan de forma directa:
$$ P(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{29413}{140}n-419, \qquad n>3,\ n\equiv 0\pmod 2. $$
Como el módulo \(10^9+7\) es primo y mayor que todos los denominadores que aparecen, cada división se implementa como una multiplicación por un inverso modular.
La reducción por paridad basta para mostrar el método en un caso concreto. Como \(16\) es par y mayor que 3, usamos el polinomio cerrado:
$$ f(16)=P(16)=6623481. $$
La rama por recurrencia produce exactamente el mismo valor a partir de los términos anteriores, así que el polinomio y la recurrencia no son trucos independientes, sino dos descripciones exactas de la misma cola de la sucesión.
Las implementaciones en C++, Python y Java primero observan que el índice pedido \(10^{18}\) es par. Luego calculan \(n,n^2,\dots,n^8\) módulo \(10^9+7\), sustituyen cada denominador racional por su inverso modular y evalúan el polinomio \(P(n)\) término a término. Eso basta para obtener la respuesta final del caso pedido.
Las implementaciones también conservan un resolvedor general de recurrencias. Este representa \(x^{n-1}\) módulo el polinomio de transición \(\chi(x)\) y usa exponenciación binaria sobre vectores de coeficientes. Después de cada multiplicación de vectores, las potencias altas se reducen con los coeficientes de la recurrencia, que es exactamente la interpretación de anillo cociente o el enfoque de Kitamasa para recurrencias lineales. Aunque se almacenan catorce posiciones base, los últimos tres coeficientes de la recurrencia son cero, de modo que la relación real de la cola es la recurrencia de 11 términos escrita arriba.
Una de las implementaciones realiza comprobaciones explícitas antes de la evaluación final. Verifica valores pequeños como \(f(3)=9\) y \(f(5)=903\), comprueba el valor entero exacto \(f(100)=8658918531876\) usando aritmética de recurrencia con enteros con signo de 128 bits, y confirma el punto de control modular \(f(10000)\equiv 377956308\pmod{10^9+7}\). Estas pruebas protegen contra errores de índice, errores de signo y reducciones modulares incorrectas.
Para la consulta concreta de Project Euler, el tiempo de ejecución es \(O(1)\): el índice objetivo es par, así que solo hace falta un número fijo de multiplicaciones modulares e inversos para evaluar el polinomio de grado 8. El uso de memoria también es \(O(1)\).
El evaluador genérico retenido es más amplio. Con tamaño de estado fijo \(K=14\), la exponenciación binaria de vectores de coeficientes reducidos cuesta \(O(K^2\log n)\) tiempo y \(O(K)\) memoria. Como solo 11 coeficientes de la recurrencia son no nulos, el factor constante es pequeño.
第 984 题 Knights and Horses 最终要求的是：求某个整数序列在巨大下标 \(n=10^{18}\) 处的值，并对 \(10^9+7\) 取模。实现中把这个序列具体化为前若干项 \(1,4,9,92,903,4411,14959,41083,98200,212418,425756,803074,1441065,2479669\)。
关键点在于，计算并不是在 \(10^{18}\) 这个规模上直接做组合枚举。代码实际上把原问题压缩成了两个完全精确的代数描述：一个适用于序列尾部、带有奇偶性结构的闭式；以及一个通用的线性递推求值器，用来覆盖其余情况并在模素数 \(10^9+7\) 下工作。
三种语言的实现透露出同一个核心结构：除了开头几个例外下标以外，Knights and Horses 对应的这个序列在 \(n\) 上其实是一个周期为 2 的拟多项式。递推求值器和显式的偶数闭式，并不是两套互不相关的方法，而是同一数学对象的两种写法。
从程序保存的初值，以及用于精确校验的带符号递推，可以直接抽出序列尾部满足的关系：
$$ f_n=7f_{n-1}-19f_{n-2}+21f_{n-3}+6f_{n-4}-42f_{n-5}+42f_{n-6}-6f_{n-7}-21f_{n-8}+19f_{n-9}-7f_{n-10}+f_{n-11}, \qquad n\ge 15. $$
这就是实现真正使用的代数规律。最后的 Project Euler 答案，本质上只是把这个序列在一个非常大的偶数下标上求值。
通用求值器保留了 14 个基值，因此对应的转移多项式是
$$ \chi(x)=x^{14}-7x^{13}+19x^{12}-21x^{11}-6x^{10}+42x^9-42x^8+6x^7+21x^6-19x^5+7x^4-x^3. $$
把它分解后得到
$$ \chi(x)=x^3(x-1)^9(x+1)^2. $$
\(x^3\) 这一因子解释了为什么最小的几个下标要单独处理。越过这段短暂的前缀以后，序列的行为只由根 \(1\) 和 \(-1\) 控制：根 \(1\) 的重数是 9，根 \(-1\) 的重数是 2。
重数为 9 的根 \(1\) 会贡献一个次数至多为 8 的多项式部分；重数为 2 的根 \(-1\) 会贡献一个 \((-1)^n\) 乘以一次多项式的部分。因此对于 \(n\ge 4\)，序列必然具有下面的形状：
$$ f(n)=A_8(n)+(-1)^nB_1(n), $$
其中 \(\deg A_8\le 8\)，\(\deg B_1\le 1\)。把这个结构与实现中已有的数值对齐，就得到显式公式
$$ f(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{941251}{4480}n-\frac{107261}{256}-(-1)^n\frac{2n+3}{256}, \qquad n\ge 4. $$
这一条公式就解释了为什么实现既可以走多项式捷径，也可以保留通用递推引擎，而两者并不会对应到不同的序列。
题目要求的是 \(n=10^{18}\)，这是一个偶数。于是只要在上式中代入 \((-1)^n=1\)，拟多项式就会收缩为实现直接使用的 8 次多项式：
$$ P(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{29413}{140}n-419, \qquad n>3,\ n\equiv 0\pmod 2. $$
由于模数 \(10^9+7\) 是素数，而且比所有出现的分母都大，所以每一个除法都可以用模逆来实现。
奇偶分解已经足够展示这个方法如何落地。因为 \(16\) 是大于 3 的偶数，所以直接代入闭式多项式：
$$ f(16)=P(16)=6623481. $$
如果走递推分支，从前面的项往后推，同样会得到这个值。也就是说，多项式和递推并不是两套分离的技巧，而是同一段尾部序列的两种精确表达。
C++、Python 和 Java 三个实现都会先判断目标下标 \(10^{18}\) 为偶数。然后它们计算 \(n,n^2,\dots,n^8\) 在模 \(10^9+7\) 下的值，把有理系数里的分母替换成模逆，再逐项累加多项式 \(P(n)\)。对本题的目标输入来说，这一步已经足够给出最终答案。
实现中还保留了一个通用递推求值器。它把 \(x^{n-1}\) 表示为模转移多项式 \(\chi(x)\) 的剩余类，然后在系数向量上做二进制快速幂。每次系数向量相乘后，都会用递推系数把高次项折回低次项，这正是线性递推在商环视角下的标准做法，也就是常说的 Kitamasa 思路。虽然状态向量开了 14 个槽位，但最后 3 个递推系数为 0，因此真正控制尾部的还是上面写出的 11 项递推。
其中一个实现会在最终计算前做明确的正确性检查。它验证了 \(f(3)=9\) 和 \(f(5)=903\) 这样的较小值，还用带符号 128 位递推算术检查了精确整数 \(f(100)=8658918531876\)，并确认模意义下的检查点 \(f(10000)\equiv 377956308\pmod{10^9+7}\)。这些校验可以有效防止下标偏移、符号错误以及模化过程中的失误。
对于题目真正要求的这个 Project Euler 查询，时间复杂度是 \(O(1)\)：因为目标下标是偶数，只需要固定次数的模乘和模逆，就能把 8 次多项式算出来。空间复杂度同样是 \(O(1)\)。
保留下来的通用求值器更强一些。状态规模固定为 \(K=14\) 时，缩减后系数向量上的快速幂需要 \(O(K^2\log n)\) 时间和 \(O(K)\) 空间。由于真正非零的递推系数只有 11 个，所以常数也不大。
Задача 984, Knights and Horses, в конечном счете требует найти значение некоторой целочисленной последовательности при огромном индексе \(n=10^{18}\) по модулю \(10^9+7\). Реализации делают эту последовательность конкретной через ее начальные значения: \(1,4,9,92,903,4411,14959,41083,98200,212418,425756,803074,1441065,2479669\).
Важно, что вычисление не выполняется прямым комбинаторным перебором при размере \(10^{18}\). Вместо этого задача уже сведена к двум точным алгебраическим описаниям: к замкнутой формуле для хвоста последовательности с учетом четности и к универсальному вычислителю линейной рекурсии, который покрывает остальные случаи по модулю простого числа.
Все три реализации показывают одну и ту же структуру: после нескольких исключительных начальных индексов последовательность из Knights and Horses становится квазиполиномом по \(n\) с периодом 2. Рекуррентный вычислитель и явная формула для четных \(n\) являются двумя представлениями одной и той же математики.
Из сохраненных начальных значений и знаковой рекурсии, используемой в точной проверке, следует, что хвост последовательности удовлетворяет соотношению
$$ f_n=7f_{n-1}-19f_{n-2}+21f_{n-3}+6f_{n-4}-42f_{n-5}+42f_{n-6}-6f_{n-7}-21f_{n-8}+19f_{n-9}-7f_{n-10}+f_{n-11}, \qquad n\ge 15. $$
Именно это алгебраическое правило действительно зашито в реализациях. Итоговый ответ Project Euler есть просто значение этой последовательности в очень большом четном индексе.
Универсальный вычислитель хранит четырнадцать базисных значений, поэтому его переходный полином имеет вид
$$ \chi(x)=x^{14}-7x^{13}+19x^{12}-21x^{11}-6x^{10}+42x^9-42x^8+6x^7+21x^6-19x^5+7x^4-x^3. $$
Его факторизация такова:
$$ \chi(x)=x^3(x-1)^9(x+1)^2. $$
Множитель \(x^3\) объясняет, почему самые маленькие индексы обрабатываются отдельно. После этого короткого переходного участка динамику определяют только корни \(1\) и \(-1\): кратность 9 у \(1\) и кратность 2 у \(-1\).
Корень \(1\) кратности 9 дает полиномиальную часть степени не выше 8, а корень \(-1\) кратности 2 дает слагаемое вида \((-1)^n\), умноженное на полином степени не выше 1. Следовательно, при \(n\ge 4\) последовательность обязана иметь форму
$$ f(n)=A_8(n)+(-1)^nB_1(n), $$
где \(\deg A_8\le 8\) и \(\deg B_1\le 1\). Подгонка этой структуры к значениям, закодированным в реализациях, приводит к явной формуле
$$ f(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{941251}{4480}n-\frac{107261}{256}-(-1)^n\frac{2n+3}{256}, \qquad n\ge 4. $$
Именно эта формула объясняет, почему код может свободно переключаться между полиномиальным сокращением и универсальным решателем рекурсии, не меняя саму последовательность.
В задаче нужен индекс \(n=10^{18}\), то есть четный. Если подставить \((-1)^n=1\), квазиполином схлопывается в многочлен восьмой степени, который реализации вычисляют напрямую:
$$ P(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{29413}{140}n-419, \qquad n>3,\ n\equiv 0\pmod 2. $$
Так как модуль \(10^9+7\) прост и больше всех знаменателей в этой формуле, каждое деление реализуется как умножение на модульную обратную.
Разбиение по четности уже показывает метод на конкретном значении. Поскольку \(16\) четно и больше 3, используется замкнутый полином:
$$ f(16)=P(16)=6623481. $$
Рекуррентная ветвь выводит то же самое значение из предыдущих членов. Значит, полином и рекурсия не являются двумя независимыми приемами; это две точные записи одного и того же хвоста последовательности.
Реализации на C++, Python и Java сначала замечают, что требуемый индекс \(10^{18}\) четен. Затем они вычисляют \(n,n^2,\dots,n^8\) по модулю \(10^9+7\), заменяют каждый рациональный знаменатель его модульной обратной и по членам суммируют многочлен \(P(n)\). Для конкретного запроса задачи этого уже достаточно, чтобы получить окончательный ответ.
При этом реализации сохраняют и общий решатель рекурсии. Он представляет \(x^{n-1}\) по модулю переходного полинома \(\chi(x)\) и использует двоичное возведение в степень над векторами коэффициентов. После каждого перемножения векторов старшие степени сворачиваются назад с помощью коэффициентов рекурсии; это в точности фактор-кольцевой взгляд, или подход Китамасы, для линейных рекуррентных последовательностей. Хотя хранятся четырнадцать базисных позиций, последние три коэффициента рекурсии равны нулю, поэтому реальное хвостовое соотношение остается 11-членным, как записано выше.
Одна из реализаций выполняет явные проверки перед финальным вычислением. Проверяются малые значения \(f(3)=9\) и \(f(5)=903\), затем точное целое значение \(f(100)=8658918531876\) с использованием знаковой 128-битной рекуррентной арифметики, а также модульная контрольная точка \(f(10000)\equiv 377956308\pmod{10^9+7}\). Такие проверки защищают от ошибок индексации, ошибок знака и неверного модульного сокращения.
Для реального запроса Project Euler время работы равно \(O(1)\): целевой индекс четен, поэтому для вычисления многочлена восьмой степени требуется лишь фиксированное число модульных умножений и обратных элементов. Память также имеет порядок \(O(1)\).
Сохраненный универсальный вычислитель более общий. При фиксированном размере состояния \(K=14\) двоичное возведение в степень над сокращенными векторами коэффициентов требует \(O(K^2\log n)\) времени и \(O(K)\) памяти. Поскольку ненулевых коэффициентов рекурсии только 11, константа при этой оценке мала.
المسألة 984، Knights and Horses، تطلب في النهاية قيمة متتالية صحيحة معينة عند الفهرس الضخم \(n=10^{18}\) مع أخذ النتيجة modulo \(10^9+7\). وتُظهر التطبيقات هذه المتتالية بشكل صريح عبر حدودها الأولى: \(1,4,9,92,903,4411,14959,41083,98200,212418,425756,803074,1441065,2479669\).
النقطة المهمة أن الحساب لا يتم عبر بحث تركيبي مباشر عند حجم \(10^{18}\). بدلاً من ذلك جرى ضغط المسألة إلى وصفين جبريين دقيقين: صيغة مغلقة لحافة المتتالية تعتمد على الزوجية، ومقيّم علاقة خطية يعالج الحالات الأخرى تحت الموديل الأولي \(10^9+7\).
تكشف التطبيقات الثلاثة البنية نفسها: بعد بضعة فهارس ابتدائية استثنائية، تصبح متتالية Knights and Horses شبه كثيرة حدود في \(n\) ذات دور 2. ومحرّك العلاقة الخطية والصيغة الصريحة للحالات الزوجية ليسا طريقتين منفصلتين، بل صورتين للبنية الرياضية نفسها.
من القيم الابتدائية المخزنة ومن العلاقة ذات الإشارات المستخدمة في نقطة الفحص الدقيقة، نحصل على أن ذيل المتتالية يحقق
$$ f_n=7f_{n-1}-19f_{n-2}+21f_{n-3}+6f_{n-4}-42f_{n-5}+42f_{n-6}-6f_{n-7}-21f_{n-8}+19f_{n-9}-7f_{n-10}+f_{n-11}, \qquad n\ge 15. $$
وهذا هو القانون الجبري الحقيقي المستخرج من التطبيقات. والجواب النهائي في Project Euler ليس إلا قيمة هذه المتتالية عند فهرس زوجي هائل.
المقيّم العام يحتفظ بأربعة عشر قيمة أساس، ولذلك يكون كثير الحدود الانتقالي
$$ \chi(x)=x^{14}-7x^{13}+19x^{12}-21x^{11}-6x^{10}+42x^9-42x^8+6x^7+21x^6-19x^5+7x^4-x^3. $$
وعند تحليله نحصل على
$$ \chi(x)=x^3(x-1)^9(x+1)^2. $$
العامل \(x^3\) يفسر لماذا تُعالج الفهارس الصغيرة جداً بصورة منفصلة. وبعد هذا الجزء الانتقالي القصير يصبح السلوك محكوماً فقط بالجذرين \(1\) و\(-1\): بتكرار 9 عند \(1\)، وبتكرار 2 عند \(-1\).
الجذر \(1\) بتكرار 9 يعطي جزءاً كثير حدود درجته على الأكثر 8، بينما الجذر \(-1\) بتكرار 2 يعطي حداً من الشكل \((-1)^n\) مضروباً في كثير حدود درجته على الأكثر 1. لذلك يجب أن تكون المتتالية، عندما \(n\ge 4\)، من الشكل
$$ f(n)=A_8(n)+(-1)^nB_1(n), $$
حيث \(\deg A_8\le 8\) و\(\deg B_1\le 1\). وبمطابقة هذا الشكل مع القيم المشفرة في التطبيقات نحصل على الصيغة الصريحة
$$ f(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{941251}{4480}n-\frac{107261}{256}-(-1)^n\frac{2n+3}{256}, \qquad n\ge 4. $$
هذه الصيغة الواحدة تفسر لماذا يستطيع الكود أن ينتقل بين اختصار كثير الحدود وبين مقيّم العلاقة الخطية العام من دون أن يغيّر المتتالية الأساسية نفسها.
الاستعلام المطلوب يستعمل \(n=10^{18}\)، وهو عدد زوجي. وعندما نضع \((-1)^n=1\)، ينكمش شبه كثير الحدود إلى كثير الحدود من الدرجة الثامنة الذي تستخدمه التطبيقات مباشرة:
$$ P(n)=\frac{31}{40320}n^8+\frac{31}{3360}n^7+\frac{67}{1440}n^6+\frac{41}{320}n^5+\frac{313}{1440}n^4-\frac{5699}{240}n^3+\frac{16049}{420}n^2+\frac{29413}{140}n-419, \qquad n>3,\ n\equiv 0\pmod 2. $$
وبما أن الموديل \(10^9+7\) أولي وأكبر من جميع المقامات الظاهرة هنا، فإن كل قسمة تُنفذ على هيئة ضرب في معكوس معياري.
تفكيك الزوجية يكفي لإظهار الطريقة على قيمة ملموسة. بما أن \(16\) زوجي وأكبر من 3، فنحن نستخدم كثير الحدود المغلق:
$$ f(16)=P(16)=6623481. $$
فرع العلاقة الخطية ينتج القيمة نفسها انطلاقاً من الحدود السابقة، ولذلك فالصيغة كثيرة الحدود والعلاقة الخطية ليستا حيلتين منفصلتين، بل توصيفين دقيقين لذيل المتتالية نفسه.
تبدأ تطبيقات C++ وPython وJava بملاحظة أن الفهرس المطلوب \(10^{18}\) زوجي. ثم تحسب \(n,n^2,\dots,n^8\) modulo \(10^9+7\)، وتستبدل كل مقام نسبي بمعكوسه المعياري، ثم تجمع حدود كثير الحدود \(P(n)\) واحداً بعد الآخر. وهذا يكفي لإنتاج الجواب النهائي لهذا الإدخال.
تحتفظ التطبيقات أيضاً بحالّ عام للعلاقات الخطية. فهو يمثل \(x^{n-1}\) modulo كثير الحدود الانتقالي \(\chi(x)\)، ويستخدم الرفع الثنائي للأس على متجهات المعاملات. وبعد كل ضرب لمتجهي معاملات تُختزل الدرجات العالية باستعمال معاملات العلاقة، وهذا هو بالضبط منظور حلقة القسمة أو منهج Kitamasa للعلاقات الخطية. وعلى الرغم من تخزين أربعة عشر موضعاً أساسياً، فإن آخر ثلاثة معاملات في العلاقة تساوي صفراً، لذا فالعلاقة الحقيقية في الذيل هي العلاقة ذات الأحد عشر حداً المكتوبة أعلاه.
أحد التطبيقات ينفذ اختبارات صريحة قبل الحساب النهائي. فهو يتحقق من قيم صغيرة مثل \(f(3)=9\) و\(f(5)=903\)، ثم يفحص القيمة الصحيحة تماماً \(f(100)=8658918531876\) باستخدام حساب علاقة خطية signed 128-bit، ويؤكد أيضاً نقطة التحقق المعيارية \(f(10000)\equiv 377956308\pmod{10^9+7}\). هذه الاختبارات تحمي من أخطاء الفهرسة، وأخطاء الإشارات، وأخطاء الاختزال المعياري.
بالنسبة إلى الاستعلام الفعلي في Project Euler، فإن زمن التنفيذ هو \(O(1)\): بما أن الفهرس الهدف زوجي، فالمطلوب فقط عدد ثابت من الضربيات المعيارية والمعكوسات لتقييم كثير الحدود من الدرجة الثامنة. كما أن الذاكرة \(O(1)\) أيضاً.
أما المقيّم العام المحفوظ فهو أوسع نطاقاً. مع حجم حالة ثابت \(K=14\)، فإن الرفع الثنائي على متجهات المعاملات المختزلة يحتاج إلى \(O(K^2\log n)\) زمناً و\(O(K)\) ذاكرة. وبما أن عدد معاملات العلاقة غير الصفرية هو 11 فقط، فإن العامل الثابت يبقى صغيراً.