The sequence is defined by
$$G_0=G_1=\cdots=G_{1999}=1,$$
and for every \(n\ge 2000\),
$$G_n=G_{n-2000}+G_{n-1999}\pmod M,$$
where in the Project Euler problem
$$M=20092010.$$
The challenge is to compute \(G_N\) for an enormous index such as
$$N=10^{18}.$$
A direct simulation is impossible. Even storing all terms up to \(10^{18}\) is absurd, and even an \(O(N)\) recurrence loop is far too slow. The code therefore converts the recurrence into polynomial arithmetic and uses binary exponentiation.
Introduce a formal shift symbol \(x\). In a linear recurrence, multiplying by \(x\) means “move one step forward in the sequence”. So \(x^k\) corresponds to shifting by \(k\) positions.
The recurrence
$$G_n=G_{n-2000}+G_{n-1999}$$
can be rewritten as
$$G_{n+2000}=G_n+G_{n+1}.$$
If \(x\) is the shift operator, then “shift by 2000” is the same as “shift by 0 plus shift by 1”, so formally
$$x^{2000}=1+x.$$
This is the key algebraic identity behind the whole solution.
Move everything to one side:
$$x^{2000}-x-1=0.$$
So the natural modulus polynomial is
$$P(x)=x^{2000}-x-1.$$
The solver works in the quotient ring
$$\mathbb Z_M[x]\big/\bigl(P(x)\bigr),$$
which means that inside computations we are always allowed to replace
$$x^{2000}\equiv x+1\pmod{P(x)}.$$
Any higher power \(x^n\) can therefore be reduced to a polynomial of degree at most 1999.
Because the recurrence has order 2000, every term \(G_N\) is a linear combination of the first 2000 values.
Concretely, there exist coefficients \(c_0,\dots,c_{1999}\) such that
$$G_N\equiv \sum_{i=0}^{1999} c_i\,G_i \pmod M.$$
Those coefficients are exactly the remainder of \(x^N\) modulo \(P(x)\):
$$x^N \equiv \sum_{i=0}^{1999} c_i x^i \pmod{P(x)}.$$
This statement is the polynomial version of companion-matrix exponentiation. Instead of exponentiating a \(2000\times 2000\) matrix, the code exponentiates the indeterminate \(x\) in the quotient ring.
Normally we would still need to evaluate
$$\sum_{i=0}^{1999} c_i\,G_i.$$
But here the initial block is especially simple:
$$G_0=G_1=\cdots=G_{1999}=1.$$
Therefore
$$G_N\equiv \sum_{i=0}^{1999} c_i \pmod M.$$
This is why the implementation can finish by simply summing the coefficients of the reduced polynomial.
From the reduction rule,
$$x^{2000}\equiv x+1.$$
So the coefficient vector has only two nonzero entries, both equal to 1.
Hence
$$G_{2000}\equiv 1+1=2 \pmod M.$$
This matches the recurrence directly:
$$G_{2000}=G_0+G_1=1+1=2.$$
Multiply the previous identity by \(x\):
$$x^{2001}\equiv x(x+1)=x^2+x.$$
Therefore
$$G_{2001}\equiv G_1+G_2=1+1=2.$$
Again this agrees with the recurrence:
$$G_{2001}=G_1+G_2=2.$$
Reduce
$$x^{4000}=(x^{2000})^2\equiv (x+1)^2=x^2+2x+1.$$
So the reduced polynomial is
$$x^{4000}\equiv 1+2x+x^2.$$
Hence
$$G_{4000}\equiv G_0+2G_1+G_2=1+2+1=4 \pmod M.$$
And indeed the direct recurrence produces
$$G_{3999}=3,\qquad G_{4000}=G_{2000}+G_{2001}=2+2=4.$$
This example shows very clearly what the coefficient vector means: it tells us how \(G_N\) depends on the first 2000 terms.
Suppose we already have two reduced polynomials
$$A(x)=\sum_{i=0}^{1999} a_i x^i,\qquad B(x)=\sum_{j=0}^{1999} b_j x^j.$$
Their ordinary product has degree at most 3998:
$$A(x)B(x)=\sum_{t=0}^{3998} d_t x^t.$$
Whenever a term \(x^t\) has \(t\ge 2000\), the reduction rule says
$$x^t=x^{t-2000}x^{2000}\equiv x^{t-2000}(x+1)=x^{t-1999}+x^{t-2000}.$$
So each high-degree coefficient \(d_t\) is pushed into exactly two lower positions:
$$d_t x^t \longmapsto d_t x^{t-2000}+d_t x^{t-1999}.$$
This is exactly what the function multiply_mod does in the C++ code. It first computes the raw convolution, then scans degrees from high to low and folds each coefficient back with the rule above.
We need \(x^N\) modulo \(P(x)\), and exponentiation by squaring works in any associative multiplication structure. The quotient ring is associative, so we can use the standard binary method:
1. Start with the multiplicative identity \(1\).
2. Let the current base be \(x\).
3. Read the binary expansion of \(N\).
4. When a bit is 1, multiply the accumulator by the current base.
5. Square the base at every step.
6. Reduce after every multiplication.
Thus the number of polynomial multiplications is only
$$O(\log N),$$
not \(O(N)\).
A standard method for linear recurrences is to build the \(2000\times 2000\) companion matrix and raise it to the \(N\)-th power.
The present approach is mathematically equivalent, but much lighter. Instead of matrix-vector multiplication, we work with one degree-1999 polynomial. Since the recurrence only contains two nonzero coefficients, the reduction rule \(x^{2000}\equiv x+1\) is extremely simple, and the polynomial method becomes especially attractive.
The implementation contains several checks:
$$G_0=1,\qquad G_{1999}=1,$$
$$G_{2000}=2,\qquad G_{2001}=2.$$
Then it cross-checks the fast solver against a direct sliding-window recurrence at
$$N=25000.$$
That shared value is
$$G_{25000}=4096 \pmod{20092010}.$$
This validates both the quotient-ring interpretation and the binary-exponentiation implementation.
The code fixes
$$K=2000$$
and represents every reduced polynomial as an array of length 2000. Entry \(i\) is the coefficient of \(x^i\).
The function multiply_mod first performs an ordinary quadratic convolution into a temporary array of length \(2K\). It then reduces every coefficient of degree at least \(K\) by sending it to positions \(i-K\) and \(i-K+1\), which is the array form of
$$x^K\equiv x+1.$$
The function solve initializes
$$\text{acc}=1,\qquad \text{base}=x,$$
raises \(x\) to the target power by binary exponentiation, and finally returns the sum of all coefficients in the resulting remainder polynomial.
Let
$$K=2000.$$
One polynomial multiplication with reduction costs
$$O(K^2),$$
because the raw convolution is quadratic. Binary exponentiation uses
$$O(\log N)$$
such multiplications, so the total time is
$$O(K^2\log N).$$
The working memory is only
$$O(K),$$
since we store a few arrays of length about \(K\) or \(2K\), not a huge matrix.
Die Folge ist definiert durch
$$G_0=G_1=\cdots=G_{1999}=1,$$
und für jedes \(n\ge 2000\) gilt
$$G_n=G_{n-2000}+G_{n-1999}\pmod M.$$
Im Euler-Problem ist
$$M=20092010.$$
Gesucht ist \(G_N\) für einen riesigen Index wie
$$N=10^{18}.$$
Eine direkte Simulation ist völlig unrealistisch. Deshalb übersetzt der Code die Rekurrenz in Polynomrechnung und verwendet binäre Exponentiation.
Führe ein formales Symbol \(x\) als Shift-Operator ein. Multiplikation mit \(x\) bedeutet: einen Schritt in der Folge weitergehen.
Aus
$$G_n=G_{n-2000}+G_{n-1999}$$
folgt äquivalent
$$G_{n+2000}=G_n+G_{n+1}.$$
Formal heißt das für den Shift:
$$x^{2000}=1+x.$$
Genau diese Identität ist das Herzstück der Lösung.
Man schreibt
$$x^{2000}-x-1=0,$$
also arbeitet der Solver modulo
$$P(x)=x^{2000}-x-1.$$
Alle Rechnungen finden in
$$\mathbb Z_M[x]/(P(x))$$
statt. Dort darf man jederzeit
$$x^{2000}\equiv x+1$$
ersetzen. Dadurch wird jede hohe Potenz auf Grad höchstens 1999 reduziert.
Da die Rekurrenz Ordnung 2000 hat, ist jedes \(G_N\) eine lineare Kombination der ersten 2000 Werte:
$$G_N\equiv \sum_{i=0}^{1999} c_i G_i \pmod M.$$
Diese Koeffizienten sind genau die Restkoeffizienten von
$$x^N\equiv \sum_{i=0}^{1999} c_i x^i \pmod{P(x)}.$$
Das ist dieselbe Mathematik wie bei einer Companion-Matrix, nur in kompakterer Form.
Hier sind die Startwerte besonders einfach:
$$G_0=G_1=\cdots=G_{1999}=1.$$
Deshalb reduziert sich
$$G_N\equiv \sum_{i=0}^{1999} c_i G_i$$
sofort zu
$$G_N\equiv \sum_{i=0}^{1999} c_i \pmod M.$$
Genau deswegen summiert die Implementierung am Ende einfach alle Koeffizienten des Restpolynoms.
Aus der Reduktionsregel folgt direkt
$$x^{2000}\equiv x+1.$$
Also ist
$$G_{2000}\equiv 1+1=2 \pmod M.$$
Das stimmt genau mit der Rekurrenz überein:
$$G_{2000}=G_0+G_1=2.$$
Multipliziert man mit \(x\), erhält man
$$x^{2001}\equiv x^2+x.$$
Daher
$$G_{2001}\equiv G_1+G_2=2.$$
Man reduziert
$$x^{4000}=(x^{2000})^2\equiv (x+1)^2=x^2+2x+1.$$
Also
$$x^{4000}\equiv 1+2x+x^2,$$
und damit
$$G_{4000}\equiv G_0+2G_1+G_2=4 \pmod M.$$
Seien
$$A(x)=\sum_{i=0}^{1999} a_i x^i,\qquad B(x)=\sum_{j=0}^{1999} b_j x^j.$$
Ihr gewöhnliches Produkt hat Grad höchstens 3998. Für jeden Term \(x^t\) mit \(t\ge 2000\) benutzt man
$$x^t=x^{t-2000}x^{2000}\equiv x^{t-2000}+x^{t-1999}.$$
Ein Hochgradterm wird also auf genau zwei niedrigere Grade verteilt. Genau das macht multiply_mod: erst Faltung, dann sukzessive Rückfaltung mit der Regel \(x^{2000}\equiv x+1\).
Gesucht ist \(x^N\) modulo \(P(x)\). Da die Multiplikation im Quotientenring assoziativ ist, kann man ganz normal Exponentiation by Squaring anwenden:
1. Starte mit dem Akkumulator \(1\).
2. Die Basis ist zunächst \(x\).
3. Lies die Bits von \(N\).
4. Bei einem Eins-Bit multipliziere den Akkumulator mit der Basis.
5. Quadriere die Basis in jedem Schritt.
6. Reduziere nach jeder Multiplikation.
Eine Standardlösung wäre die \(2000\times 2000\)-Companion-Matrix. Die hier verwendete Methode ist mathematisch äquivalent, aber deutlich leichter: statt einer großen Matrix exponentiert man nur ein Polynom vom Grad 1999.
Der Code prüft
$$G_0=1,\qquad G_{1999}=1,$$
$$G_{2000}=2,\qquad G_{2001}=2.$$
Außerdem wird der schnelle Solver bei
$$N=25000$$
gegen eine direkte Sliding-Window-Simulation geprüft. Der gemeinsame Wert ist
$$G_{25000}=4096 \pmod{20092010}.$$
Der Code setzt
$$K=2000$$
und speichert jedes reduzierte Polynom als Array der Länge 2000. Die Funktion multiply_mod bildet zunächst die quadratische Faltung in ein temporäres Array der Länge \(2K\) und reduziert dann alle Grade \(\ge K\) mit der Regel
$$x^K\equiv x+1.$$
solve startet mit
$$\text{acc}=1,\qquad \text{base}=x,$$
führt die binäre Exponentiation aus und summiert am Ende alle Koeffizienten.
Mit
$$K=2000$$
kostet eine Polynom-Multiplikation mit Reduktion
$$O(K^2).$$
Da nur
$$O(\log N)$$
Multiplikationen nötig sind, ergibt sich insgesamt
$$O(K^2\log N)$$
Zeit und
$$O(K)$$
Speicher.
Dizi şu şekilde tanımlanır:
$$G_0=G_1=\cdots=G_{1999}=1,$$
ve her \(n\ge 2000\) için
$$G_n=G_{n-2000}+G_{n-1999}\pmod M.$$
Project Euler probleminde
$$M=20092010$$
alınır. Amaç,
$$N=10^{18}$$
gibi dev bir indis için \(G_N\) değerini bulmaktır. Doğrudan yineleme imkansızdır; bu yüzden kod problemi polinom aritmetiğine çevirir ve ikili üs alma kullanır.
Biçimsel bir \(x\) sembolü tanıtalım. Bu sembol “bir adım ileri kaydırma” anlamına gelsin. O zaman \(x^k\), dizide \(k\) adım ileri gitmeyi temsil eder.
Yineleme
$$G_n=G_{n-2000}+G_{n-1999}$$
eşdeğer olarak
$$G_{n+2000}=G_n+G_{n+1}$$
şeklinde yazılabilir. Bu da operatör düzeyinde
$$x^{2000}=1+x$$
demektir. Çözümün merkezi fikri tam olarak budur.
Tüm terimleri bir tarafa atarsak
$$x^{2000}-x-1=0$$
elde ederiz. Dolayısıyla mod polinomumuz
$$P(x)=x^{2000}-x-1$$
olur. Kod,
$$\mathbb Z_M[x]/(P(x))$$
bölüm halkasında çalışır. Yani her hesapta
$$x^{2000}\equiv x+1$$
yerine koyması yapılabilir. Bu sayede her yüksek kuvvet en fazla 1999 dereceli bir polinoma indirgenir.
Yineleme mertebesi 2000 olduğu için, her \(G_N\) ilk 2000 terimin lineer birleşimidir:
$$G_N\equiv \sum_{i=0}^{1999} c_i G_i \pmod M.$$
Bu katsayılar tam olarak şu kalan polinomun katsayılarıdır:
$$x^N\equiv \sum_{i=0}^{1999} c_i x^i \pmod{P(x)}.$$
Bu bakış açısı, companion matrix üslemesinin polinom halkası versiyonudur. Yani \(2000\times 2000\) matris yerine tek bir polinom üslenir.
Normalde
$$G_N\equiv \sum_{i=0}^{1999} c_i G_i$$
ifadesini ayrıca değerlendirmemiz gerekirdi. Ama burada başlangıç bloğu çok özeldir:
$$G_0=G_1=\cdots=G_{1999}=1.$$
Bu nedenle ifade doğrudan
$$G_N\equiv \sum_{i=0}^{1999} c_i \pmod M$$
biçimine düşer. Kodun en sonda yalnızca katsayıları toplamasının nedeni budur.
İndirgeme kuralından
$$x^{2000}\equiv x+1$$
gelir. Dolayısıyla katsayı vektöründe yalnızca iki tane 1 vardır ve
$$G_{2000}\equiv 1+1=2 \pmod M$$
olur. Bu, yineleme ile de aynıdır:
$$G_{2000}=G_0+G_1=2.$$
Bir önceki bağıntıyı \(x\) ile çarparsak
$$x^{2001}\equiv x^2+x$$
elde edilir. O halde
$$G_{2001}\equiv G_1+G_2=2.$$
Şunu indirgeriz:
$$x^{4000}=(x^{2000})^2\equiv (x+1)^2=x^2+2x+1.$$
Yani
$$x^{4000}\equiv 1+2x+x^2$$
olur. Bu yüzden
$$G_{4000}\equiv G_0+2G_1+G_2=4 \pmod M.$$
Gerçekten doğrudan yineleme de
$$G_{4000}=G_{2000}+G_{2001}=2+2=4$$
sonucunu verir. Bu örnek, katsayı vektörünün \(G_N\)'yi ilk 2000 terim üzerinden nasıl ifade ettiğini açıkça gösterir.
İki indirgenmiş polinom düşünelim:
$$A(x)=\sum_{i=0}^{1999} a_i x^i,\qquad B(x)=\sum_{j=0}^{1999} b_j x^j.$$
Normal çarpımları en fazla 3998 derecelidir:
$$A(x)B(x)=\sum_{t=0}^{3998} d_t x^t.$$
Eğer \(t\ge 2000\) ise,
$$x^t=x^{t-2000}x^{2000}\equiv x^{t-2000}(x+1)=x^{t-1999}+x^{t-2000}$$
kullanılır. Yani her yüksek dereceli terim iki alt dereceye geri katlanır:
$$d_t x^t \longmapsto d_t x^{t-2000}+d_t x^{t-1999}.$$
C++ içindeki multiply_mod fonksiyonu tam olarak bunu yapar: önce ham konvolüsyon, sonra yüksek dereceleri yukarıdaki kuralla alta dağıtma.
Amacımız \(x^N\) kuvvetini modulo \(P(x)\) hesaplamaktır. Bölüm halkasındaki çarpım birleşmelidir, dolayısıyla standart ikili üs alma burada da geçerlidir:
1. Başlangıç akümülatörü \(1\) alınır.
2. Taban \(x\) olarak başlatılır.
3. \(N\)'nin ikilik açılımı okunur.
4. Bit 1 ise akümülatör tabanla çarpılır.
5. Her adımda taban karesine yükseltilir.
6. Her çarpımdan sonra indirgeme yapılır.
Böylece gerekli çarpım sayısı yalnızca
$$O(\log N)$$
olur.
Lineer yinelemeler için klasik yöntem, \(2000\times 2000\) companion matrix kurup onu üslemektir. Buradaki yöntem matematiksel olarak eşdeğerdir ama daha hafiftir. Büyük bir matris yerine 1999 dereceli bir polinomla çalışırız. Bu yinelemede yalnızca iki katsayı sıfır olmadığı için \(x^{2000}\equiv x+1\) indirgemesi olağanüstü basittir.
Kod şu denetimleri içerir:
$$G_0=1,\qquad G_{1999}=1,$$
$$G_{2000}=2,\qquad G_{2001}=2.$$
Daha sonra hızlı çözücü,
$$N=25000$$
noktasında doğrudan kayan pencere yinelemesiyle karşılaştırılır. Ortak değer
$$G_{25000}=4096 \pmod{20092010}$$
çıkar. Bu da hem bölüm halkası yorumunu hem de ikili üs alma kodunu doğrular.
Kod
$$K=2000$$
sabitini kullanır ve her indirgenmiş polinomu uzunluğu 2000 olan bir dizi olarak saklar. \(i\). hücre \(x^i\)'nin katsayısıdır.
multiply_mod önce uzunluğu \(2K\) olan geçici dizide normal kuadratik konvolüsyon yapar. Sonra derecesi \(K\) veya daha büyük olan her terimi
$$x^K\equiv x+1$$
kuralıyla \(i-K\) ve \(i-K+1\) konumlarına geri dağıtır.
solve fonksiyonu
$$\text{acc}=1,\qquad \text{base}=x$$
ile başlar, \(x^N\)'yi ikili üs alma ile hesaplar ve sonunda elde edilen kalanın tüm katsayılarını toplayıp cevabı döndürür.
$$K=2000$$
olsun. Bir polinom çarpımı ve indirgeme işlemi
$$O(K^2)$$
zaman alır; çünkü temel maliyet ham konvolüsyondur. İkili üs alma
$$O(\log N)$$
adet böyle adım kullandığından toplam süre
$$O(K^2\log N)$$
olur. Bellek ise yalnızca birkaç \(K\) ve \(2K\) uzunluklu dizi tuttuğumuz için
$$O(K)$$
seviyesindedir.
La sucesion esta definida por
$$G_0=G_1=\cdots=G_{1999}=1,$$
y para todo \(n\ge 2000\),
$$G_n=G_{n-2000}+G_{n-1999}\pmod M.$$
En el problema de Euler se toma
$$M=20092010.$$
Se pide calcular \(G_N\) para un indice gigantesco como
$$N=10^{18}.$$
La simulacion directa es imposible, asi que el codigo traduce la recurrencia a aritmetica de polinomios y usa exponenciacion binaria.
Introducimos un simbolo formal \(x\) que representa “avanzar un paso” en la sucesion. Entonces \(x^k\) representa avanzar \(k\) posiciones.
La recurrencia
$$G_n=G_{n-2000}+G_{n-1999}$$
equivale a
$$G_{n+2000}=G_n+G_{n+1}.$$
En lenguaje operador eso significa
$$x^{2000}=1+x.$$
Llevando todo a un lado, obtenemos
$$x^{2000}-x-1=0.$$
Por tanto trabajamos modulo
$$P(x)=x^{2000}-x-1.$$
Es decir, dentro del anillo cociente
$$\mathbb Z_M[x]/(P(x)),$$
siempre podemos reemplazar
$$x^{2000}\equiv x+1.$$
Como la recurrencia tiene orden 2000, cualquier termino \(G_N\) es una combinacion lineal de los primeros 2000 valores:
$$G_N\equiv \sum_{i=0}^{1999} c_i G_i \pmod M.$$
Los coeficientes \(c_i\) son precisamente los del resto
$$x^N\equiv \sum_{i=0}^{1999} c_i x^i \pmod{P(x)}.$$
Esta es la version polinomica de la exponenciacion de la matriz companera.
Aqui los valores iniciales son especialmente simples:
$$G_0=G_1=\cdots=G_{1999}=1.$$
Por eso
$$G_N\equiv \sum_{i=0}^{1999} c_i \pmod M.$$
Esa es exactamente la razon por la que el codigo acaba sumando todos los coeficientes.
La regla de reduccion da
$$x^{2000}\equiv x+1.$$
Asi,
$$G_{2000}\equiv 1+1=2 \pmod M.$$
y eso coincide con la recurrencia directa:
$$G_{2000}=G_0+G_1=2.$$
Multiplicando por \(x\),
$$x^{2001}\equiv x^2+x,$$
luego
$$G_{2001}\equiv G_1+G_2=2.$$
Reducimos
$$x^{4000}=(x^{2000})^2\equiv (x+1)^2=x^2+2x+1.$$
Por tanto
$$x^{4000}\equiv 1+2x+x^2,$$
y entonces
$$G_{4000}\equiv G_0+2G_1+G_2=4 \pmod M.$$
Sean
$$A(x)=\sum_{i=0}^{1999} a_i x^i,\qquad B(x)=\sum_{j=0}^{1999} b_j x^j.$$
Su producto ordinario llega hasta grado 3998. Cuando aparece un termino \(x^t\) con \(t\ge 2000\), usamos
$$x^t=x^{t-2000}x^{2000}\equiv x^{t-2000}+x^{t-1999}.$$
Asi cada coeficiente alto se reparte en dos posiciones mas bajas. Eso es exactamente lo que implementa multiply_mod.
Queremos \(x^N\) modulo \(P(x)\). Como la multiplicacion en el anillo cociente es asociativa, se puede aplicar la exponenciacion por cuadrados:
1. Se empieza con el acumulador \(1\).
2. La base inicial es \(x\).
3. Se recorren los bits de \(N\).
4. Si un bit vale 1, se multiplica el acumulador por la base.
5. La base se eleva al cuadrado en cada paso.
6. Tras cada multiplicacion se reduce modulo \(P(x)\).
Una solucion clasica construiria la matriz companera \(2000\times 2000\). Este metodo es equivalente, pero mucho mas ligero: en lugar de una gran matriz, se trabaja con un unico polinomio de grado 1999.
El codigo comprueba
$$G_0=1,\qquad G_{1999}=1,$$
$$G_{2000}=2,\qquad G_{2001}=2.$$
Luego compara el solucionador rapido con una simulacion directa en
$$N=25000,$$
donde ambos dan
$$G_{25000}=4096 \pmod{20092010}.$$
El programa fija
$$K=2000$$
y representa cada polinomio reducido como un arreglo de longitud 2000. La funcion multiply_mod hace primero la convolucion cuadratica ordinaria en un arreglo temporal de longitud \(2K\), y luego reduce todos los grados grandes con la regla
$$x^K\equiv x+1.$$
La funcion solve arranca con
$$\text{acc}=1,\qquad \text{base}=x,$$
eleva \(x\) a la potencia deseada y finalmente suma los coeficientes del resto.
Con
$$K=2000,$$
una multiplicacion con reduccion cuesta
$$O(K^2).$$
La exponenciacion binaria usa
$$O(\log N)$$
multiplicaciones, asi que el tiempo total es
$$O(K^2\log N),$$
mientras que la memoria es
$$O(K).$$
数列定义为
$$G_0=G_1=\cdots=G_{1999}=1,$$
并且对所有 \(n\ge 2000\)，有
$$G_n=G_{n-2000}+G_{n-1999}\pmod M.$$
在题目中
$$M=20092010.$$
目标是求超大下标
$$N=10^{18}$$
处的 \(G_N\)。直接递推显然不可行，因此代码把问题转成多项式运算，再用二进制快速幂。
引入形式符号 \(x\)，表示“向前推进一项”。于是 \(x^k\) 就表示向前推进 \(k\) 步。
递推式
$$G_n=G_{n-2000}+G_{n-1999}$$
等价于
$$G_{n+2000}=G_n+G_{n+1}.$$
在算子语言里，这就是
$$x^{2000}=1+x.$$
移项可得
$$x^{2000}-x-1=0.$$
因此模多项式是
$$P(x)=x^{2000}-x-1.$$
代码实际上在商环
$$\mathbb Z_M[x]/(P(x))$$
中运算，也就是始终可以使用
$$x^{2000}\equiv x+1$$
来降幂。
由于递推阶数是 2000，每个 \(G_N\) 都能写成前 2000 项的线性组合：
$$G_N\equiv \sum_{i=0}^{1999} c_i G_i \pmod M.$$
这些系数 \(c_i\) 正是余式多项式中的系数：
$$x^N\equiv \sum_{i=0}^{1999} c_i x^i \pmod{P(x)}.$$
这就是 companion matrix 方法的多项式版本。
这里初始块非常特殊：
$$G_0=G_1=\cdots=G_{1999}=1.$$
所以
$$G_N\equiv \sum_{i=0}^{1999} c_i \pmod M.$$
也就是说，答案就是余式多项式全部系数之和。
由降幂规则直接得到
$$x^{2000}\equiv x+1.$$
于是
$$G_{2000}\equiv 1+1=2 \pmod M.$$
这和原递推完全一致：
$$G_{2000}=G_0+G_1=2.$$
把上式乘以 \(x\)，得到
$$x^{2001}\equiv x^2+x,$$
因此
$$G_{2001}\equiv G_1+G_2=2.$$
有
$$x^{4000}=(x^{2000})^2\equiv (x+1)^2=x^2+2x+1.$$
所以
$$x^{4000}\equiv 1+2x+x^2,$$
进而
$$G_{4000}\equiv G_0+2G_1+G_2=4 \pmod M.$$
设
$$A(x)=\sum_{i=0}^{1999} a_i x^i,\qquad B(x)=\sum_{j=0}^{1999} b_j x^j.$$
它们的普通乘积最高到 3998 次。只要出现 \(x^t\) 且 \(t\ge 2000\)，就用
$$x^t=x^{t-2000}x^{2000}\equiv x^{t-2000}+x^{t-1999}$$
把高次项折回去。于是每个高次系数都会分摊到两个低次位置。这正是 multiply_mod 所做的事情。
我们要求的是 \(x^N\) 在商环中的值。由于乘法满足结合律，完全可以像普通整数幂那样做二进制快速幂：
1. 累积器初始为 \(1\)。
2. 基底初始为 \(x\)。
3. 按 \(N\) 的二进制位处理。
4. 某位为 1 时，把累积器乘上当前基底。
5. 每一步都把基底平方。
6. 每次乘法后都进行模多项式降幂。
线性递推的经典方法是构造 \(2000\times 2000\) 的 companion matrix 再做快速幂。这里的方法在数学上等价，但更轻：不用大矩阵，只需处理一个 1999 次以内的多项式。
代码检查
$$G_0=1,\qquad G_{1999}=1,$$
$$G_{2000}=2,\qquad G_{2001}=2.$$
随后又在
$$N=25000$$
处把快速算法与直接滑动窗口递推进行对比，它们共同得到
$$G_{25000}=4096 \pmod{20092010}.$$
程序固定
$$K=2000$$
并把每个降幂后的多项式表示成长度为 2000 的数组，第 \(i\) 个位置就是 \(x^i\) 的系数。
multiply_mod 先在长度 \(2K\) 的临时数组里做普通卷积，再把所有次数 \(\ge K\) 的项按
$$x^K\equiv x+1$$
折回到低次数位置。
solve 用
$$\text{acc}=1,\qquad \text{base}=x$$
开始做二进制快速幂，最后把余式数组中的所有系数相加作为答案。
设
$$K=2000.$$
一次多项式乘法加降幂的成本是
$$O(K^2),$$
而快速幂需要
$$O(\log N)$$
次这样的乘法，因此总时间复杂度是
$$O(K^2\log N).$$
额外空间只需几个长度约为 \(K\) 或 \(2K\) 的数组，所以是
$$O(K).$$
Последовательность задается так:
$$G_0=G_1=\cdots=G_{1999}=1,$$
а для всех \(n\ge 2000\)
$$G_n=G_{n-2000}+G_{n-1999}\pmod M.$$
В задаче Euler берется
$$M=20092010.$$
Нужно найти \(G_N\) для огромного индекса, например
$$N=10^{18}.$$
Прямой перебор невозможен, поэтому код переводит рекуррентность в арифметику полиномов и использует бинарное возведение в степень.
Введем формальный символ \(x\), означающий переход на один шаг вперед по последовательности. Тогда \(x^k\) означает сдвиг на \(k\) позиций.
Рекуррентность
$$G_n=G_{n-2000}+G_{n-1999}$$
эквивалентна записи
$$G_{n+2000}=G_n+G_{n+1}.$$
На языке оператора это означает
$$x^{2000}=1+x.$$
Переносим все в одну сторону:
$$x^{2000}-x-1=0.$$
Поэтому работаем по модулю полинома
$$P(x)=x^{2000}-x-1.$$
То есть вычисления ведутся в кольце
$$\mathbb Z_M[x]/(P(x)),$$
где всегда можно заменять
$$x^{2000}\equiv x+1.$$
Поскольку рекуррентность имеет порядок 2000, любой член \(G_N\) выражается через первые 2000 значений:
$$G_N\equiv \sum_{i=0}^{1999} c_i G_i \pmod M.$$
Коэффициенты \(c_i\) - это именно коэффициенты остатка
$$x^N\equiv \sum_{i=0}^{1999} c_i x^i \pmod{P(x)}.$$
Это та же математика, что и у companion matrix, только записанная через полиномы.
Начальные значения одинаковы:
$$G_0=G_1=\cdots=G_{1999}=1.$$
Поэтому выражение
$$G_N\equiv \sum_{i=0}^{1999} c_i G_i$$
сразу превращается в
$$G_N\equiv \sum_{i=0}^{1999} c_i \pmod M.$$
По правилу редукции
$$x^{2000}\equiv x+1.$$
Значит,
$$G_{2000}\equiv 1+1=2 \pmod M.$$
Это в точности совпадает с прямой рекуррентностью:
$$G_{2000}=G_0+G_1=2.$$
Умножая на \(x\), получаем
$$x^{2001}\equiv x^2+x,$$
откуда
$$G_{2001}\equiv G_1+G_2=2.$$
Имеем
$$x^{4000}=(x^{2000})^2\equiv (x+1)^2=x^2+2x+1.$$
То есть
$$x^{4000}\equiv 1+2x+x^2,$$
и потому
$$G_{4000}\equiv G_0+2G_1+G_2=4 \pmod M.$$
Пусть
$$A(x)=\sum_{i=0}^{1999} a_i x^i,\qquad B(x)=\sum_{j=0}^{1999} b_j x^j.$$
Их обычное произведение имеет степень до 3998. Для каждого члена \(x^t\) с \(t\ge 2000\) используем
$$x^t=x^{t-2000}x^{2000}\equiv x^{t-2000}+x^{t-1999}.$$
Так каждый высокий коэффициент переносится в две более низкие позиции. Именно это делает функция multiply_mod.
Нужно найти \(x^N\) в кольце вычетов по \(P(x)\). Так как умножение ассоциативно, можно применять обычное exponentiation by squaring:
1. аккумулятор начинается с \(1\);
2. база начинается с \(x\);
3. биты числа \(N\) обрабатываются по очереди;
4. если бит равен 1, аккумулятор умножается на базу;
5. база каждый раз возводится в квадрат;
6. после каждого умножения выполняется редукция.
Классический подход к линейной рекуррентности - возведение в степень companion matrix размера \(2000\times 2000\). Здесь используется эквивалентная, но более компактная версия: вместо матрицы возводится в степень полином степени 1999.
Код проверяет
$$G_0=1,\qquad G_{1999}=1,$$
$$G_{2000}=2,\qquad G_{2001}=2.$$
Затем быстрый решатель сверяется с прямой симуляцией при
$$N=25000,$$
и общее значение равно
$$G_{25000}=4096 \pmod{20092010}.$$
Программа фиксирует
$$K=2000$$
и хранит каждый редуцированный полином как массив длины 2000. Функция multiply_mod сначала строит обычную свертку в массиве длины \(2K\), а затем сворачивает все степени \(\ge K\) по правилу
$$x^K\equiv x+1.$$
Функция solve начинает с
$$\text{acc}=1,\qquad \text{base}=x,$$
выполняет бинарное возведение в степень и в конце суммирует коэффициенты остатка.
При
$$K=2000$$
одно умножение с редукцией стоит
$$O(K^2).$$
Таких умножений требуется
$$O(\log N),$$
поэтому итоговая сложность равна
$$O(K^2\log N)$$
по времени и
$$O(K)$$
по памяти.
تُعرَّف المتتالية كما يلي:
$$G_0=G_1=\cdots=G_{1999}=1,$$
ولكل \(n\ge 2000\) لدينا
$$G_n=G_{n-2000}+G_{n-1999}\pmod M.$$
وفي مسألة Euler يكون
$$M=20092010.$$
المطلوب هو حساب \(G_N\) عندما يكون
$$N=10^{18}$$
مثلًا. التوليد المباشر مستحيل عمليًا، لذلك يحول الكود المسألة إلى حسابات على كثيرات حدود ثم يستخدم الرفع الثنائي للأس.
نعرّف رمزًا شكليًا \(x\) ليمثل الانتقال خطوة واحدة إلى الأمام في المتتالية. وعندئذ فإن \(x^k\) يمثل الإزاحة بمقدار \(k\) خطوات.
العلاقة
$$G_n=G_{n-2000}+G_{n-1999}$$
تكافئ
$$G_{n+2000}=G_n+G_{n+1}.$$
وهذا يعني على مستوى المؤثرات أن
$$x^{2000}=1+x.$$
بنقل كل شيء إلى طرف واحد نحصل على
$$x^{2000}-x-1=0.$$
إذًا نعمل بترديد كثير الحدود
$$P(x)=x^{2000}-x-1.$$
أي داخل الحلقة
$$\mathbb Z_M[x]/(P(x)),$$
حيث يمكن دائمًا استبدال
$$x^{2000}\equiv x+1.$$
بما أن رتبة العلاقة 2000، فإن أي حد \(G_N\) يكتب على صورة تركيب خطي من أول 2000 حد:
$$G_N\equiv \sum_{i=0}^{1999} c_i G_i \pmod M.$$
وهذه المعاملات \(c_i\) هي بالضبط معاملات باقي
$$x^N\equiv \sum_{i=0}^{1999} c_i x^i \pmod{P(x)}.$$
وهذا هو المنظور كثير الحدود لطريقة companion matrix.
لدينا هنا شرط ابتدائي بسيط جدًا:
$$G_0=G_1=\cdots=G_{1999}=1.$$
وبالتالي
$$G_N\equiv \sum_{i=0}^{1999} c_i \pmod M.$$
ولهذا ينتهي الكود بجمع جميع معاملات كثير الحدود المتبقي.
من قاعدة الاختزال مباشرة نحصل على
$$x^{2000}\equiv x+1.$$
إذًا
$$G_{2000}\equiv 1+1=2 \pmod M.$$
وهذا يوافق العلاقة الأصلية:
$$G_{2000}=G_0+G_1=2.$$
بضرب العلاقة السابقة في \(x\) نحصل على
$$x^{2001}\equiv x^2+x,$$
ومن ثم
$$G_{2001}\equiv G_1+G_2=2.$$
لدينا
$$x^{4000}=(x^{2000})^2\equiv (x+1)^2=x^2+2x+1.$$
أي
$$x^{4000}\equiv 1+2x+x^2,$$
وبالتالي
$$G_{4000}\equiv G_0+2G_1+G_2=4 \pmod M.$$
إذا كان لدينا
$$A(x)=\sum_{i=0}^{1999} a_i x^i,\qquad B(x)=\sum_{j=0}^{1999} b_j x^j,$$
فإن حاصل الضرب العادي يصل إلى درجة 3998. وعندما يظهر حد \(x^t\) مع \(t\ge 2000\)، نستخدم
$$x^t=x^{t-2000}x^{2000}\equiv x^{t-2000}+x^{t-1999}.$$
وبذلك يُعاد توزيع كل معامل مرتفع على موضعين أدنى. وهذا بالضبط ما تنفذه الدالة multiply_mod.
نحن نريد حساب \(x^N\) داخل الحلقة السابقة، والضرب فيها تجميعي، لذا يمكن استخدام الطريقة القياسية:
1. نبدأ بالمراكم \(1\).
2. تكون القاعدة أولًا هي \(x\).
3. نقرأ التمثيل الثنائي للعدد \(N\).
4. إذا كان البت يساوي 1 نضرب المراكم في القاعدة.
5. نربع القاعدة في كل خطوة.
6. نختزل بعد كل ضرب.
الطريقة القياسية في المتتاليات الخطية هي بناء companion matrix بحجم \(2000\times 2000\) ثم رفعها للأس. الطريقة هنا مكافئة رياضيًا لكنها أخف بكثير: بدل مصفوفة ضخمة نعمل على كثير حدود واحد درجته لا تتجاوز 1999.
يتحقق الكود من
$$G_0=1,\qquad G_{1999}=1,$$
$$G_{2000}=2,\qquad G_{2001}=2.$$
ثم يقارن الحل السريع مع المحاكاة المباشرة عند
$$N=25000,$$
وتكون القيمة المشتركة
$$G_{25000}=4096 \pmod{20092010}.$$
يثبت البرنامج
$$K=2000$$
ويمثل كل كثير حدود مختزل بمصفوفة طولها 2000. تمثل الخانة \(i\) معامل \(x^i\).
تقوم multiply_mod أولًا بحساب الالتفاف التربيعي المعتاد في مصفوفة مؤقتة طولها \(2K\)، ثم تختزل كل الدرجات \(\ge K\) بواسطة القاعدة
$$x^K\equiv x+1.$$
أما solve فتبدأ من
$$\text{acc}=1,\qquad \text{base}=x,$$
ثم تجري الرفع الثنائي للأس وفي النهاية تجمع معاملات الباقي.
عند
$$K=2000$$
تكون كلفة عملية ضرب واحدة مع الاختزال
$$O(K^2),$$
ويُستخدم عدد
$$O(\log N)$$
من هذه العمليات، لذلك يكون الزمن الكلي
$$O(K^2\log N),$$
أما الذاكرة فهي
$$O(K).$$