Problem 892, Zebra Circles, asks for the cumulative total of a sequence \(D(n)\) modulo
$$p=1{,}234{,}567{,}891,$$
with initial values \(D(1)=0\) and \(D(2)=2\). The required output is
$$S(N)=\sum_{k=1}^{N} D(k)\pmod p,\qquad N=10^7.$$
The difficulty is that \(N\) is very large and the defining update is a rational recurrence. The successful approach is to keep everything in modular arithmetic, turn each division into multiplication by a precomputed modular inverse, and stream the sequence in one forward pass.
The sequence is generated from the three-term recurrence
$$D_{n+2}=\frac{16n^2(n+1)(2n+3)D_n+4(n+1)(2n^2+4n+3)D_{n+1}}{n(n+2)(n+3)(2n+1)}\qquad (n\ge 1).$$
So the problem is not to discover \(D(n)\) term by term with exact rational arithmetic, but to evaluate this recurrence efficiently modulo \(p\) and accumulate the total sum.
Write
$$A_n=16n^2(n+1)(2n+3),\qquad B_n=4(n+1)(2n^2+4n+3),$$
$$C_n=n(n+2)(n+3)(2n+1).$$
Then the recurrence becomes
$$D_{n+2}=\frac{A_nD_n+B_nD_{n+1}}{C_n}.$$
This rewriting makes the structure clear: each new term depends only on the previous two terms and on explicit polynomials in \(n\). That immediately suggests a constant-state iteration rather than a large dynamic-programming table.
Over arithmetic modulo \(p\), division by an invertible value \(x\) is multiplication by its inverse:
$$\frac{u}{x}\equiv u\,x^{-1}\pmod p.$$
Therefore the recurrence can be evaluated as
$$D_{n+2}\equiv \left(A_nD_n+B_nD_{n+1}\right)\cdot C_n^{-1}\pmod p.$$
Because the denominator factors as \(n\), \(n+2\), \(n+3\), and \(2n+1\), the implementation only needs inverses for ordinary integers appearing in that range. A safe upper bound is \(2N+3\), which covers every denominator factor used during the loop.
Let \(I(i)\) denote the modular inverse of \(i\) modulo \(p\). The implementation uses
$$I(1)=1,$$
$$I(i)\equiv \left(p-\left\lfloor\frac{p}{i}\right\rfloor\right)I(p\bmod i)\pmod p,\qquad i\ge 2.$$
This comes from the Euclidean identity
$$p=\left\lfloor\frac{p}{i}\right\rfloor i+(p\bmod i),$$
which implies
$$(p\bmod i)\equiv -\left\lfloor\frac{p}{i}\right\rfloor i\pmod p.$$
After multiplying by the relevant inverses, one gets a recurrence for \(I(i)\) in terms of a smaller argument \(p\bmod i\). This avoids expensive repeated inverse computations inside the main loop.
Once the inverse table exists, each new term requires only a fixed number of modular multiplications and additions. The running state consists of the current pair \((D_n,D_{n+1})\) and the partial sum
$$S_m=\sum_{k=1}^{m} D(k)\pmod p.$$
After computing \(D_{n+2}\), the implementation immediately updates
$$S_{n+2}=S_{n+1}+D_{n+2}\pmod p.$$
No old term is needed again after it has been shifted out of the two-term window, so the recurrence itself uses constant live state.
The first few terms show how the rational formula collapses to ordinary integers before reduction modulo \(p\).
For \(n=1\), using \(D_1=0\) and \(D_2=2\),
$$D_3=\frac{16\cdot 1^2\cdot 2\cdot 5\cdot D_1+4\cdot 2\cdot 9\cdot D_2}{1\cdot 3\cdot 4\cdot 3} =\frac{0+144}{36}=4.$$
For \(n=2\),
$$D_4=\frac{16\cdot 2^2\cdot 3\cdot 7\cdot D_2+4\cdot 3\cdot 19\cdot D_3}{2\cdot 4\cdot 5\cdot 5} =\frac{2688+912}{200}=18.$$
For \(n=3\),
$$D_5=\frac{16\cdot 3^2\cdot 4\cdot 9\cdot D_3+4\cdot 4\cdot 33\cdot D_4}{3\cdot 5\cdot 6\cdot 7} =\frac{20736+9504}{630}=48.$$
So the sequence begins
$$0,\ 2,\ 4,\ 18,\ 48,\dots$$
and the partial sums begin
$$0,\ 2,\ 6,\ 24,\ 72,\dots$$
The C++, Python, and Java implementations all follow the same plan. They fix the modulus \(p\), the target \(N\), and an inverse-table limit of \(2N+3\). Then they build a table of modular inverses for every integer in that range. After that they initialize the recurrence with the two known starting terms and the initial running sum.
Inside the loop, the implementation evaluates the two polynomial coefficients in the numerator, combines them with the previous two sequence values, multiplies by the product of the four denominator inverses, and reduces modulo \(p\). The new term is added to the running total immediately, and the two-term state window is shifted forward. This design avoids floating-point arithmetic, avoids per-step inverse recomputation, and keeps the recurrence state independent of \(N\).
The inverse table has size \(2N+3\), so building it costs \(O(N)\) time and \(O(N)\) memory. The recurrence loop then performs \(N-2\) iterations, each doing only a constant amount of modular arithmetic, so the loop is also \(O(N)\). The full method is therefore linear in \(N\), with \(O(N)\) memory dominated by the inverse table and only \(O(1)\) additional state for the recurrence and the running sum.
Problem 892, Zebra Circles, verlangt die kumulierte Summe einer Folge \(D(n)\) modulo
$$p=1{,}234{,}567{,}891,$$
mit den Anfangswerten \(D(1)=0\) und \(D(2)=2\). Gesucht ist
$$S(N)=\sum_{k=1}^{N} D(k)\pmod p,\qquad N=10^7.$$
Die Schwierigkeit liegt darin, dass \(N\) sehr groß ist und die Aktualisierung der Folge als rationale Rekurrenz gegeben ist. Die Lösung führt daher alle Rechnungen direkt modulo \(p\) aus, ersetzt jede Division durch Multiplikation mit einem modularen Inversen und verarbeitet die Folge in genau einem Vorwärtsdurchlauf.
Die Folge wird durch die Rekurrenz
$$D_{n+2}=\frac{16n^2(n+1)(2n+3)D_n+4(n+1)(2n^2+4n+3)D_{n+1}}{n(n+2)(n+3)(2n+1)}\qquad (n\ge 1)$$
erzeugt. Damit besteht die Aufgabe nicht darin, rationale Werte exakt zu speichern, sondern diese Vorschrift effizient modulo \(p\) auszuwerten und gleichzeitig die Gesamtsumme mitzuführen.
Setze
$$A_n=16n^2(n+1)(2n+3),\qquad B_n=4(n+1)(2n^2+4n+3),$$
$$C_n=n(n+2)(n+3)(2n+1).$$
Dann schreibt sich die Rekurrenz als
$$D_{n+2}=\frac{A_nD_n+B_nD_{n+1}}{C_n}.$$
Diese Form zeigt sofort, dass jeder neue Folgewert nur von den beiden vorherigen Werten und von expliziten Polynomen in \(n\) abhängt. Ein großes Array aller bisherigen Werte ist also unnötig.
In der Arithmetik modulo \(p\) ist Division durch eine invertierbare Zahl \(x\) dasselbe wie Multiplikation mit \(x^{-1}\):
$$\frac{u}{x}\equiv u\,x^{-1}\pmod p.$$
Damit erhält man
$$D_{n+2}\equiv \left(A_nD_n+B_nD_{n+1}\right)\cdot C_n^{-1}\pmod p.$$
Da der Nenner in die Faktoren \(n\), \(n+2\), \(n+3\) und \(2n+1\) zerfällt, werden nur Inverse gewöhnlicher ganzer Zahlen aus diesem Bereich benötigt. Die Implementierung reserviert dafür sicherheitshalber alle Werte bis \(2N+3\).
Sei \(I(i)\) das modulare Inverse von \(i\) modulo \(p\). Verwendet wird
$$I(1)=1,$$
$$I(i)\equiv \left(p-\left\lfloor\frac{p}{i}\right\rfloor\right)I(p\bmod i)\pmod p,\qquad i\ge 2.$$
Die Grundlage ist die euklidische Identität
$$p=\left\lfloor\frac{p}{i}\right\rfloor i+(p\bmod i),$$
also
$$(p\bmod i)\equiv -\left\lfloor\frac{p}{i}\right\rfloor i\pmod p.$$
Nach Multiplikation mit den passenden Inversen entsteht eine Rekurrenz für \(I(i)\) mit kleinerem Argument \(p\bmod i\). Dadurch entfallen teure Einzelberechnungen von Inversen innerhalb der Hauptschleife.
Sobald die Inversentabelle vorhanden ist, benötigt jeder neue Term nur noch eine feste Anzahl modularer Multiplikationen und Additionen. Der laufende Zustand besteht aus dem Paar \((D_n,D_{n+1})\) und der Teilsumme
$$S_m=\sum_{k=1}^{m} D(k)\pmod p.$$
Nach der Berechnung von \(D_{n+2}\) wird sofort
$$S_{n+2}=S_{n+1}+D_{n+2}\pmod p$$
aktualisiert. Sobald ein alter Wert aus dem Zweierfenster herausfällt, wird er nie wieder gebraucht.
Die ersten Terme zeigen, dass die rationale Vorschrift sauber auf ganze Werte führt.
Für \(n=1\) mit \(D_1=0\) und \(D_2=2\) gilt
$$D_3=\frac{16\cdot 1^2\cdot 2\cdot 5\cdot D_1+4\cdot 2\cdot 9\cdot D_2}{1\cdot 3\cdot 4\cdot 3} =\frac{0+144}{36}=4.$$
Für \(n=2\) erhält man
$$D_4=\frac{16\cdot 2^2\cdot 3\cdot 7\cdot D_2+4\cdot 3\cdot 19\cdot D_3}{2\cdot 4\cdot 5\cdot 5} =\frac{2688+912}{200}=18.$$
Für \(n=3\) folgt
$$D_5=\frac{16\cdot 3^2\cdot 4\cdot 9\cdot D_3+4\cdot 4\cdot 33\cdot D_4}{3\cdot 5\cdot 6\cdot 7} =\frac{20736+9504}{630}=48.$$
Die Folge beginnt also mit
$$0,\ 2,\ 4,\ 18,\ 48,\dots$$
und die Partialsummen beginnen mit
$$0,\ 2,\ 6,\ 24,\ 72,\dots$$
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Zuerst werden der Modulus \(p\), das Ziel \(N\) und die Obergrenze \(2N+3\) für die Inversentabelle festgelegt. Danach werden die modularen Inversen aller ganzen Zahlen in diesem Bereich vorab berechnet. Anschließend startet die Rekurrenz mit den beiden bekannten Anfangswerten und der anfänglichen Laufsumme.
In jeder Schleifeniteration berechnet die Implementierung die beiden Polynomkoeffizienten im Zähler, kombiniert sie mit den zwei zuletzt bekannten Folgewerten, multipliziert mit dem Produkt der vier vorberechneten Nennerinverse und reduziert modulo \(p\). Der neue Wert wird sofort zur Gesamtsumme addiert, danach wird das Zweierfenster um einen Schritt weitergeschoben. So vermeidet der Ansatz Gleitkommaarithmetik, vermeidet wiederholte Inversenberechnung und hält den aktiven Rekurrenzzustand konstant klein.
Die Inversentabelle hat Größe \(2N+3\), daher kostet ihr Aufbau \(O(N)\) Zeit und \(O(N)\) Speicher. Die Rekurrenzschleife besitzt \(N-2\) Durchläufe und führt pro Durchlauf nur konstant viele modulare Operationen aus, also ebenfalls \(O(N)\) Zeit. Insgesamt ist das Verfahren linear in \(N\); der Speicherverbrauch ist \(O(N)\), dominiert von der Inversentabelle, während die Rekurrenz selbst nur \(O(1)\) Zusatzspeicher benötigt.
Problem 892, Zebra Circles, şu dizinin kümülatif toplamını
$$p=1{,}234{,}567{,}891$$
modunda istemektedir. Başlangıç değerleri \(D(1)=0\) ve \(D(2)=2\) olup aranan çıktı
$$S(N)=\sum_{k=1}^{N} D(k)\pmod p,\qquad N=10^7$$
şeklindedir. Zorluk, \(N\) çok büyük olduğu için ve tanım rasyonel bir yineleme ile verildiği için doğrudan kesirli hesap yapmanın pratik olmamasıdır. Çözüm, tüm bölmeleri modüler terslere çevirip diziyi tek bir ileri taramada üretir.
Dizi şu üç terimli bağıntıyla üretilir:
$$D_{n+2}=\frac{16n^2(n+1)(2n+3)D_n+4(n+1)(2n^2+4n+3)D_{n+1}}{n(n+2)(n+3)(2n+1)}\qquad (n\ge 1).$$
Dolayısıyla esas mesele, bu bağıntıyı rasyonel sayı aritmetiğiyle yavaş yavaş çözmek değil; mod \(p\) altında hızlıca değerlendirip toplamı eşzamanlı bir şekilde biriktirmektir.
Şöyle tanımlayalım:
$$A_n=16n^2(n+1)(2n+3),\qquad B_n=4(n+1)(2n^2+4n+3),$$
$$C_n=n(n+2)(n+3)(2n+1).$$
O zaman yineleme
$$D_{n+2}=\frac{A_nD_n+B_nD_{n+1}}{C_n}$$
haline gelir. Bu yazım, her yeni terimin yalnızca önceki iki terime ve \(n\)'in açık polinomlarına bağlı olduğunu gösterir. Böylece tüm geçmişi tutan büyük bir tabloya ihtiyaç kalmaz.
Modüler aritmetikte terslenebilir bir \(x\) için
$$\frac{u}{x}\equiv u\,x^{-1}\pmod p$$
olur. Bu nedenle bağıntı
$$D_{n+2}\equiv \left(A_nD_n+B_nD_{n+1}\right)\cdot C_n^{-1}\pmod p$$
şeklinde hesaplanabilir. Payda \(n\), \(n+2\), \(n+3\) ve \(2n+1\) çarpanlarına ayrıldığı için, döngü boyunca gereken tüm tersler sıradan tamsayı tersleridir. Uygulama bunların hepsini güvenli bir üst sınır olarak \(2N+3\)'e kadar hazırlar.
\(I(i)\), \(i\)'nin mod \(p\)'deki tersi olsun. Kullanılan bağıntı
$$I(1)=1,$$
$$I(i)\equiv \left(p-\left\lfloor\frac{p}{i}\right\rfloor\right)I(p\bmod i)\pmod p,\qquad i\ge 2$$
şeklindedir. Bunun temeli Öklid özdeşliğidir:
$$p=\left\lfloor\frac{p}{i}\right\rfloor i+(p\bmod i).$$
Buradan
$$(p\bmod i)\equiv -\left\lfloor\frac{p}{i}\right\rfloor i\pmod p$$
elde edilir. Uygun terslerle çarpınca \(I(i)\) için daha küçük argümana bağlı bir yineleme çıkar. Böylece ana döngü içinde tekrar tekrar ters hesaplamaya gerek kalmaz.
Ters tablosu hazır olduktan sonra her yeni terim, sabit sayıda modüler çarpma ve toplama ile bulunur. Canlı durumda yalnızca \((D_n,D_{n+1})\) çifti ile
$$S_m=\sum_{k=1}^{m} D(k)\pmod p$$
kısmi toplamı tutulur. \(D_{n+2}\) bulunduğu anda
$$S_{n+2}=S_{n+1}+D_{n+2}\pmod p$$
güncellenir. Pencereden çıkan eski terim bir daha kullanılmadığı için yineleme durumu sabit boyutta kalır.
İlk birkaç terim, rasyonel görünen formülün gerçekte düzgün tamsayı değerleri ürettiğini gösterir.
\(n=1\) için, \(D_1=0\) ve \(D_2=2\) kullanılırsa
$$D_3=\frac{16\cdot 1^2\cdot 2\cdot 5\cdot D_1+4\cdot 2\cdot 9\cdot D_2}{1\cdot 3\cdot 4\cdot 3} =\frac{0+144}{36}=4.$$
\(n=2\) için
$$D_4=\frac{16\cdot 2^2\cdot 3\cdot 7\cdot D_2+4\cdot 3\cdot 19\cdot D_3}{2\cdot 4\cdot 5\cdot 5} =\frac{2688+912}{200}=18.$$
\(n=3\) için
$$D_5=\frac{16\cdot 3^2\cdot 4\cdot 9\cdot D_3+4\cdot 4\cdot 33\cdot D_4}{3\cdot 5\cdot 6\cdot 7} =\frac{20736+9504}{630}=48.$$
Böylece dizi
$$0,\ 2,\ 4,\ 18,\ 48,\dots$$
diye başlar; kısmi toplamlar da
$$0,\ 2,\ 6,\ 24,\ 72,\dots$$
olur.
C++, Python ve Java implementasyonlarının yapısı aynıdır. Önce modül \(p\), hedef \(N\) ve ters tablosu için \(2N+3\) üst sınırı belirlenir. Ardından bu aralıktaki her tamsayının modüler tersi önceden hesaplanır. Sonra yineleme, bilinen iki başlangıç terimi ve başlangıç toplamı ile başlatılır.
Döngünün her adımında implementasyon, paydaki iki polinom katsayısını hesaplar, bunları önceki iki dizi değeriyle birleştirir, paydadaki dört çarpanın hazır terslerini çarpar ve sonucu mod \(p\)'ye indirger. Yeni terim anında toplam değişkenine eklenir, sonra iki terimlik pencere bir adım ileri kaydırılır. Bu tasarım kayan nokta aritmetiğinden kaçınır, döngü içinde ters hesaplamaz ve aktif durumu \(N\)'den bağımsız tutar.
Ters tablosunun boyutu \(2N+3\) olduğu için bu tabloyu kurmak \(O(N)\) zaman ve \(O(N)\) bellek ister. Yineleme döngüsü \(N-2\) kez çalışır ve her adımda yalnızca sabit sayıda modüler işlem yapar; dolayısıyla o da \(O(N)\) zamandadır. Sonuçta yöntem toplamda lineer zamana sahiptir. Bellek kullanımı \(O(N)\) olup baskın terim ters tablosudur; yinelemenin kendisi ve kısmi toplam için yalnızca \(O(1)\) ek durum tutulur.
El problema 892, Zebra Circles, pide la suma acumulada de una sucesión \(D(n)\) módulo
$$p=1{,}234{,}567{,}891,$$
con valores iniciales \(D(1)=0\) y \(D(2)=2\). La salida buscada es
$$S(N)=\sum_{k=1}^{N} D(k)\pmod p,\qquad N=10^7.$$
La dificultad es que \(N\) es enorme y la actualización de la sucesión está dada por una recurrencia racional. La idea correcta es trabajar siempre en aritmética modular, convertir cada división en una multiplicación por un inverso modular precomputado y recorrer la sucesión una sola vez.
La sucesión viene dada por la recurrencia
$$D_{n+2}=\frac{16n^2(n+1)(2n+3)D_n+4(n+1)(2n^2+4n+3)D_{n+1}}{n(n+2)(n+3)(2n+1)}\qquad (n\ge 1).$$
Por tanto, el objetivo no es manipular fracciones exactas durante millones de pasos, sino evaluar esta fórmula eficientemente módulo \(p\) y acumular la suma total al mismo tiempo.
Definimos
$$A_n=16n^2(n+1)(2n+3),\qquad B_n=4(n+1)(2n^2+4n+3),$$
$$C_n=n(n+2)(n+3)(2n+1).$$
Entonces la recurrencia se escribe como
$$D_{n+2}=\frac{A_nD_n+B_nD_{n+1}}{C_n}.$$
Esta forma deja claro que cada término nuevo depende solo de los dos anteriores y de polinomios explícitos en \(n\). Por eso no hace falta guardar toda la historia de la sucesión.
En aritmética módulo \(p\), dividir por un valor invertible \(x\) equivale a multiplicar por \(x^{-1}\):
$$\frac{u}{x}\equiv u\,x^{-1}\pmod p.$$
Así, la actualización puede evaluarse como
$$D_{n+2}\equiv \left(A_nD_n+B_nD_{n+1}\right)\cdot C_n^{-1}\pmod p.$$
Como el denominador se factoriza en \(n\), \(n+2\), \(n+3\) y \(2n+1\), solo hacen falta inversos de enteros ordinarios en ese rango. La implementación reserva de forma segura todos los valores hasta \(2N+3\).
Sea \(I(i)\) el inverso modular de \(i\) módulo \(p\). Se usa la relación
$$I(1)=1,$$
$$I(i)\equiv \left(p-\left\lfloor\frac{p}{i}\right\rfloor\right)I(p\bmod i)\pmod p,\qquad i\ge 2.$$
Esto proviene de la identidad euclídea
$$p=\left\lfloor\frac{p}{i}\right\rfloor i+(p\bmod i),$$
que implica
$$(p\bmod i)\equiv -\left\lfloor\frac{p}{i}\right\rfloor i\pmod p.$$
Al multiplicar por los inversos adecuados se obtiene una recurrencia para \(I(i)\) en términos de un argumento más pequeño. Con eso se evita recalcular inversos costosos dentro del bucle principal.
Una vez construida la tabla de inversos, cada término nuevo requiere solo un número fijo de multiplicaciones y sumas modulares. El estado activo consiste en el par \((D_n,D_{n+1})\) y en la suma parcial
$$S_m=\sum_{k=1}^{m} D(k)\pmod p.$$
Después de calcular \(D_{n+2}\), la implementación actualiza enseguida
$$S_{n+2}=S_{n+1}+D_{n+2}\pmod p.$$
Como un término viejo deja de ser necesario en cuanto sale de la ventana de dos elementos, la recurrencia usa memoria constante para su estado vivo.
Los primeros términos muestran que la fórmula racional produce enteros limpios antes de aplicar el módulo.
Para \(n=1\), con \(D_1=0\) y \(D_2=2\),
$$D_3=\frac{16\cdot 1^2\cdot 2\cdot 5\cdot D_1+4\cdot 2\cdot 9\cdot D_2}{1\cdot 3\cdot 4\cdot 3} =\frac{0+144}{36}=4.$$
Para \(n=2\),
$$D_4=\frac{16\cdot 2^2\cdot 3\cdot 7\cdot D_2+4\cdot 3\cdot 19\cdot D_3}{2\cdot 4\cdot 5\cdot 5} =\frac{2688+912}{200}=18.$$
Para \(n=3\),
$$D_5=\frac{16\cdot 3^2\cdot 4\cdot 9\cdot D_3+4\cdot 4\cdot 33\cdot D_4}{3\cdot 5\cdot 6\cdot 7} =\frac{20736+9504}{630}=48.$$
Así, la sucesión comienza como
$$0,\ 2,\ 4,\ 18,\ 48,\dots$$
y las sumas parciales comienzan como
$$0,\ 2,\ 6,\ 24,\ 72,\dots$$
Las implementaciones en C++, Python y Java siguen la misma estrategia. Primero fijan el módulo \(p\), el objetivo \(N\) y el límite \(2N+3\) para la tabla de inversos. Después precalculan el inverso modular de cada entero en ese intervalo. Luego inicializan la recurrencia con los dos términos conocidos y con la suma acumulada inicial.
En cada iteración, la implementación evalúa los dos coeficientes polinómicos del numerador, los combina con los dos términos anteriores de la sucesión, multiplica por el producto de los cuatro inversos del denominador y reduce el resultado módulo \(p\). El término recién obtenido se añade de inmediato al total, y la ventana de dos términos se desplaza hacia delante. De esta manera se evita la aritmética de punto flotante, se evita recomputar inversos y se mantiene el estado activo independiente de \(N\).
La tabla de inversos tiene tamaño \(2N+3\), así que construirla cuesta \(O(N)\) tiempo y \(O(N)\) memoria. El bucle de la recurrencia realiza \(N-2\) iteraciones y cada una usa solo una cantidad constante de operaciones modulares, por lo que también cuesta \(O(N)\) tiempo. En conjunto, el método completo es lineal en \(N\). La memoria total es \(O(N)\), dominada por la tabla de inversos, mientras que la recurrencia y la suma acumulada usan solo \(O(1)\) memoria adicional.
第 892 题 Zebra Circles 要求计算一个序列 \(D(n)\) 的前缀和，并对
$$p=1{,}234{,}567{,}891$$
取模。已知初值为 \(D(1)=0\)、\(D(2)=2\)，目标是求
$$S(N)=\sum_{k=1}^{N} D(k)\pmod p,\qquad N=10^7.$$
难点在于 \(N\) 非常大，而且序列更新公式是带分母的有理递推。如果直接做精确分数运算，速度和内存都不合适。正确做法是从头到尾都在模 \(p\) 下计算，把每一次除法改写成乘以预处理好的模逆元，然后用一次线性扫描完成整个求和。
实现所使用的递推关系是
$$D_{n+2}=\frac{16n^2(n+1)(2n+3)D_n+4(n+1)(2n^2+4n+3)D_{n+1}}{n(n+2)(n+3)(2n+1)}\qquad (n\ge 1).$$
因此问题的核心不是把每一步都当成普通有理数来展开，而是要把这条递推式高效地转写为模运算，并且在生成新项的同时维护总和。
定义
$$A_n=16n^2(n+1)(2n+3),\qquad B_n=4(n+1)(2n^2+4n+3),$$
$$C_n=n(n+2)(n+3)(2n+1).$$
那么递推式可写成
$$D_{n+2}=\frac{A_nD_n+B_nD_{n+1}}{C_n}.$$
这样写的好处是结构一目了然：每个新项只依赖前两项 \(D_n\)、\(D_{n+1}\)，以及关于 \(n\) 的显式多项式系数。这说明没有必要保存整段历史序列，只要保留最近两项即可。
在模 \(p\) 的算术中，只要 \(x\) 在模 \(p\) 下可逆，就有
$$\frac{u}{x}\equiv u\,x^{-1}\pmod p.$$
于是递推可以改写为
$$D_{n+2}\equiv \left(A_nD_n+B_nD_{n+1}\right)\cdot C_n^{-1}\pmod p.$$
这里 \(C_n\) 又分解成四个简单因子：
$$C_n=n(n+2)(n+3)(2n+1).$$
因此程序不需要处理复杂的“整体分母”，只要事先准备好这些整数因子的逆元即可。因为循环中最大的因子不会超过一个简单的线性上界，所以实现把所有需要的逆元一次性预处理到 \(2N+3\)。
记 \(I(i)\) 为 \(i\) 在模 \(p\) 下的逆元。实现使用
$$I(1)=1,$$
$$I(i)\equiv \left(p-\left\lfloor\frac{p}{i}\right\rfloor\right)I(p\bmod i)\pmod p,\qquad i\ge 2.$$
它来自欧几里得除法恒等式
$$p=\left\lfloor\frac{p}{i}\right\rfloor i+(p\bmod i),$$
因此
$$(p\bmod i)\equiv -\left\lfloor\frac{p}{i}\right\rfloor i\pmod p.$$
再乘上相应的逆元，就得到 \(I(i)\) 可以由更小的参数 \(p\bmod i\) 推出来。这个技巧的价值非常大，因为它把“为很多整数分别求逆”改成了“线性时间表填充”，避免了在主循环中重复做昂贵的逆元运算。
逆元表建立以后，每一步只剩下固定次数的模乘和模加。程序维护的活动状态只有最近两项 \((D_n,D_{n+1})\) 以及前缀和
$$S_m=\sum_{k=1}^{m} D(k)\pmod p.$$
算出新项 \(D_{n+2}\) 之后，立刻更新
$$S_{n+2}=S_{n+1}+D_{n+2}\pmod p.$$
一旦最旧的那一项从两项窗口中移出，它就再也不会被访问。也就是说，真正随 \(N\) 增长的只有逆元表，而递推本身始终只占常数级状态。
前几项可以直接验证递推确实运作正常，而且分母会整齐地约出整数值。
当 \(n=1\) 时，代入 \(D_1=0\)、\(D_2=2\)，得到
$$D_3=\frac{16\cdot 1^2\cdot 2\cdot 5\cdot D_1+4\cdot 2\cdot 9\cdot D_2}{1\cdot 3\cdot 4\cdot 3} =\frac{0+144}{36}=4.$$
当 \(n=2\) 时，
$$D_4=\frac{16\cdot 2^2\cdot 3\cdot 7\cdot D_2+4\cdot 3\cdot 19\cdot D_3}{2\cdot 4\cdot 5\cdot 5} =\frac{2688+912}{200}=18.$$
当 \(n=3\) 时，
$$D_5=\frac{16\cdot 3^2\cdot 4\cdot 9\cdot D_3+4\cdot 4\cdot 33\cdot D_4}{3\cdot 5\cdot 6\cdot 7} =\frac{20736+9504}{630}=48.$$
因此序列开头是
$$0,\ 2,\ 4,\ 18,\ 48,\dots$$
对应的前缀和开头是
$$0,\ 2,\ 6,\ 24,\ 72,\dots$$
这个例子也解释了为什么实现只要保留最近两项就够了：每个新值只会引用这两项，不会回头读取更早的数据。
C++、Python 和 Java 三个实现采用的是同一套流程。首先固定模数 \(p\)、目标 \(N\) 和逆元表上界 \(2N+3\)。然后预处理这个范围内每个整数的模逆元。接着用两个已知初值启动递推，并把初始前缀和设置为前两项之和。
在循环内部，实现先计算分子中的两个多项式系数，再与当前保存的两项序列值相乘相加，然后乘上分母四个因子的逆元乘积，最后对 \(p\) 取模。新得到的项会立刻加入运行总和，随后把“两项窗口”整体向前推进一格。这样做完全避免了浮点数，也避免了在每一步重新求逆元，同时让递推状态保持为常数大小。
逆元表大小为 \(2N+3\)，因此预处理它需要 \(O(N)\) 时间和 \(O(N)\) 空间。主递推循环运行 \(N-2\) 次，而每次只做固定数量的模乘与模加，所以循环本身也是 \(O(N)\) 时间。总体而言，整个算法对 \(N\) 呈线性复杂度。内存消耗同样是 \(O(N)\)，主要来自逆元表；除它之外，递推窗口和累计和都只需要 \(O(1)\) 额外空间。
В задаче 892, Zebra Circles, требуется найти накопленную сумму последовательности \(D(n)\) по модулю
$$p=1{,}234{,}567{,}891,$$
если заданы начальные значения \(D(1)=0\) и \(D(2)=2\). Требуемый ответ равен
$$S(N)=\sum_{k=1}^{N} D(k)\pmod p,\qquad N=10^7.$$
Главная сложность в том, что \(N\) очень велико, а переход к следующему члену задается рациональной рекуррентной формулой. Поэтому решение полностью работает в модульной арифметике, заменяет каждое деление умножением на заранее вычисленный обратный элемент и проходит по последовательности один раз слева направо.
Последовательность задается рекуррентным соотношением
$$D_{n+2}=\frac{16n^2(n+1)(2n+3)D_n+4(n+1)(2n^2+4n+3)D_{n+1}}{n(n+2)(n+3)(2n+1)}\qquad (n\ge 1).$$
Значит, задача состоит не в том, чтобы хранить огромные рациональные числа, а в том, чтобы эффективно вычислять это соотношение по модулю \(p\) и одновременно накапливать сумму.
Обозначим
$$A_n=16n^2(n+1)(2n+3),\qquad B_n=4(n+1)(2n^2+4n+3),$$
$$C_n=n(n+2)(n+3)(2n+1).$$
Тогда рекурсия принимает вид
$$D_{n+2}=\frac{A_nD_n+B_nD_{n+1}}{C_n}.$$
Такое разбиение сразу показывает структуру вычисления: новый член зависит только от двух предыдущих членов и от явных полиномиальных коэффициентов по \(n\). Следовательно, хранить всю историю последовательности не требуется.
В арифметике по модулю \(p\) деление на обратимый элемент \(x\) эквивалентно умножению на \(x^{-1}\):
$$\frac{u}{x}\equiv u\,x^{-1}\pmod p.$$
Поэтому вычисление можно переписать так:
$$D_{n+2}\equiv \left(A_nD_n+B_nD_{n+1}\right)\cdot C_n^{-1}\pmod p.$$
Поскольку знаменатель раскладывается на факторы \(n\), \(n+2\), \(n+3\) и \(2n+1\), программе нужны только обратные к обычным целым числам из этого диапазона. В качестве удобной безопасной границы берется \(2N+3\).
Пусть \(I(i)\) означает обратный к \(i\) по модулю \(p\). Используется формула
$$I(1)=1,$$
$$I(i)\equiv \left(p-\left\lfloor\frac{p}{i}\right\rfloor\right)I(p\bmod i)\pmod p,\qquad i\ge 2.$$
Она следует из евклидова тождества
$$p=\left\lfloor\frac{p}{i}\right\rfloor i+(p\bmod i),$$
откуда
$$(p\bmod i)\equiv -\left\lfloor\frac{p}{i}\right\rfloor i\pmod p.$$
После умножения на подходящие обратные элементы получается рекурсия для \(I(i)\) через меньшее значение \(p\bmod i\). Это позволяет заполнить всю таблицу обратных один раз и не тратить время на отдельные вычисления внутри основного цикла.
Когда таблица обратных уже готова, каждый новый член требует лишь фиксированного числа модульных умножений и сложений. В памяти хранятся только пара \((D_n,D_{n+1})\) и частичная сумма
$$S_m=\sum_{k=1}^{m} D(k)\pmod p.$$
После нахождения \(D_{n+2}\) сразу выполняется обновление
$$S_{n+2}=S_{n+1}+D_{n+2}\pmod p.$$
Как только самый старый элемент выходит из двухэлементного окна, он больше не нужен. Поэтому сама рекурсия использует только постоянный объем оперативного состояния.
Первые несколько членов удобно посчитать вручную, чтобы увидеть, как рациональная формула превращается в обычные целые значения.
Для \(n=1\), при \(D_1=0\) и \(D_2=2\), получаем
$$D_3=\frac{16\cdot 1^2\cdot 2\cdot 5\cdot D_1+4\cdot 2\cdot 9\cdot D_2}{1\cdot 3\cdot 4\cdot 3} =\frac{0+144}{36}=4.$$
Для \(n=2\) имеем
$$D_4=\frac{16\cdot 2^2\cdot 3\cdot 7\cdot D_2+4\cdot 3\cdot 19\cdot D_3}{2\cdot 4\cdot 5\cdot 5} =\frac{2688+912}{200}=18.$$
Для \(n=3\) получаем
$$D_5=\frac{16\cdot 3^2\cdot 4\cdot 9\cdot D_3+4\cdot 4\cdot 33\cdot D_4}{3\cdot 5\cdot 6\cdot 7} =\frac{20736+9504}{630}=48.$$
Итак, начало последовательности таково:
$$0,\ 2,\ 4,\ 18,\ 48,\dots$$
а начало последовательности частичных сумм таково:
$$0,\ 2,\ 6,\ 24,\ 72,\dots$$
Реализации на C++, Python и Java устроены одинаково. Сначала фиксируются модуль \(p\), целевое значение \(N\) и предел \(2N+3\) для таблицы обратных. Затем заранее вычисляются обратные ко всем целым числам в этом диапазоне. После этого рекурсия запускается с двумя известными начальными членами и с начальной накопленной суммой.
Внутри цикла реализация вычисляет два полиномиальных коэффициента числителя, комбинирует их с двумя последними значениями последовательности, умножает на произведение четырех обратных к знаменателю и берет результат по модулю \(p\). Новый член сразу прибавляется к общей сумме, после чего двухэлементное окно сдвигается вперед. Такой подход не использует числа с плавающей точкой, не пересчитывает обратные заново на каждом шаге и делает активное состояние независимым от \(N\).
Таблица обратных имеет размер \(2N+3\), поэтому ее построение требует \(O(N)\) времени и \(O(N)\) памяти. Основной цикл рекурсии выполняется \(N-2\) раз и в каждой итерации содержит только константное число модульных операций, так что он тоже работает за \(O(N)\). Следовательно, весь метод линейный по \(N\). Память равна \(O(N)\) и определяется главным образом таблицей обратных; помимо нее, для рекурсии и бегущей суммы нужен только \(O(1)\) дополнительный объем.
في المسألة 892، Zebra Circles، نريد حساب المجموع التراكمي للمتتالية \(D(n)\) بترديد
$$p=1{,}234{,}567{,}891,$$
مع القيم الابتدائية \(D(1)=0\) و\(D(2)=2\). والكمية المطلوبة هي
$$S(N)=\sum_{k=1}^{N} D(k)\pmod p,\qquad N=10^7.$$
التحدي أن \(N\) كبير جدا، وأن التحديث معطى بعلاقة تكرارية كسرية. لذلك لا يصلح الحساب الكسري المباشر. الفكرة الصحيحة هي البقاء بالكامل داخل الحساب المعياري، وتحويل كل قسمة إلى ضرب في مقلوب معياري محسوب مسبقا، ثم توليد الحدود وجمعها في مرور واحد.
المتتالية تولد بالعلاقة
$$D_{n+2}=\frac{16n^2(n+1)(2n+3)D_n+4(n+1)(2n^2+4n+3)D_{n+1}}{n(n+2)(n+3)(2n+1)}\qquad (n\ge 1).$$
إذن المطلوب ليس التعامل مع كسور دقيقة عبر ملايين الخطوات، بل إعادة صياغة هذه العلاقة بحيث تقيم بكفاءة بترديد \(p\) مع تحديث المجموع الكلي في الوقت نفسه.
لنكتب
$$A_n=16n^2(n+1)(2n+3),\qquad B_n=4(n+1)(2n^2+4n+3),$$
$$C_n=n(n+2)(n+3)(2n+1).$$
فتصبح العلاقة
$$D_{n+2}=\frac{A_nD_n+B_nD_{n+1}}{C_n}.$$
هذه الصياغة توضح أن كل حد جديد يعتمد فقط على الحدين السابقين وعلى معاملات كثيرة حدود ظاهرة في \(n\). لذلك لا حاجة إلى تخزين التاريخ الكامل للمتتالية.
في الحساب بترديد \(p\)، القسمة على قيمة قابلة للعكس \(x\) تكافئ الضرب في \(x^{-1}\):
$$\frac{u}{x}\equiv u\,x^{-1}\pmod p.$$
وبذلك يمكن تقييم التحديث على الصورة
$$D_{n+2}\equiv \left(A_nD_n+B_nD_{n+1}\right)\cdot C_n^{-1}\pmod p.$$
ولأن المقام يتحلل إلى العوامل \(n\) و\(n+2\) و\(n+3\) و\(2n+1\)، فإن المطلوب عمليا هو مقلوبات معيارية لأعداد صحيحة عادية ضمن هذا المجال. لذلك يحضر التنفيذ جميع هذه المقلوبات حتى حد آمن هو \(2N+3\).
ليكن \(I(i)\) هو المقلوب المعياري للعدد \(i\) بترديد \(p\). تستعمل العلاقة
$$I(1)=1,$$
$$I(i)\equiv \left(p-\left\lfloor\frac{p}{i}\right\rfloor\right)I(p\bmod i)\pmod p,\qquad i\ge 2.$$
وهذه تأتي من هوية القسمة الإقليدية
$$p=\left\lfloor\frac{p}{i}\right\rfloor i+(p\bmod i),$$
ومنها
$$(p\bmod i)\equiv -\left\lfloor\frac{p}{i}\right\rfloor i\pmod p.$$
بعد الضرب في المقلوبات المناسبة نحصل على علاقة تعاودية للمقلوب \(I(i)\) بدلالة وسيط أصغر هو \(p\bmod i\). فائدة ذلك أنه يملأ الجدول كله مرة واحدة، بدل إعادة حساب مقلوب جديد داخل الحلقة الرئيسية في كل خطوة.
بعد تجهيز جدول المقلوبات، يحتاج كل حد جديد إلى عدد ثابت من عمليات الضرب والجمع المعيارية. والحالة الحية في الذاكرة هي فقط الزوج \((D_n,D_{n+1})\) والمجموع الجزئي
$$S_m=\sum_{k=1}^{m} D(k)\pmod p.$$
وبمجرد حساب \(D_{n+2}\) يحدث التنفيذ مباشرة
$$S_{n+2}=S_{n+1}+D_{n+2}\pmod p.$$
وعندما يخرج الحد الأقدم من نافذة الحدين، لا يعود هناك أي احتياج إليه. لهذا تبقى حالة التكرار نفسها ثابتة الحجم، بينما الزيادة في الذاكرة تأتي فقط من جدول المقلوبات.
حساب أول عدة حدود يوضح كيف تتحول العلاقة الكسرية إلى قيم صحيحة نظيفة.
عند \(n=1\)، ومع \(D_1=0\) و\(D_2=2\)، نحصل على
$$D_3=\frac{16\cdot 1^2\cdot 2\cdot 5\cdot D_1+4\cdot 2\cdot 9\cdot D_2}{1\cdot 3\cdot 4\cdot 3} =\frac{0+144}{36}=4.$$
وعند \(n=2\)،
$$D_4=\frac{16\cdot 2^2\cdot 3\cdot 7\cdot D_2+4\cdot 3\cdot 19\cdot D_3}{2\cdot 4\cdot 5\cdot 5} =\frac{2688+912}{200}=18.$$
وعند \(n=3\)،
$$D_5=\frac{16\cdot 3^2\cdot 4\cdot 9\cdot D_3+4\cdot 4\cdot 33\cdot D_4}{3\cdot 5\cdot 6\cdot 7} =\frac{20736+9504}{630}=48.$$
إذن بداية المتتالية هي
$$0,\ 2,\ 4,\ 18,\ 48,\dots$$
وبداية المجاميع الجزئية هي
$$0,\ 2,\ 6,\ 24,\ 72,\dots$$
تتبع تطبيقات C++ وPython وJava الخطة نفسها. أولا تثبت قيمة \(p\) والهدف \(N\) والحد \(2N+3\) اللازم لجدول المقلوبات. ثم تحسب مسبقا مقلوب كل عدد صحيح في هذا المجال. بعد ذلك تبدأ العلاقة التكرارية من الحدين الابتدائيين المعروفين، ويجهز المجموع التراكمي الأولي.
داخل الحلقة تحسب الشيفرة معاملي كثيرات الحدود في البسط، وتجمع مساهمتهما من الحدين السابقين، ثم تضرب في حاصل ضرب المقلوبات الأربعة الخاصة بعوامل المقام، وأخيرا تختزل النتيجة بترديد \(p\). ويضاف الحد الجديد مباشرة إلى المجموع الكلي، ثم تتحرك نافذة الحدين خطوة إلى الأمام. هذه البنية تتجنب الحسابات العشرية، وتتجنب إعادة حساب المقلوبات في كل مرة، وتحافظ على حجم الحالة النشطة ثابتا.
حجم جدول المقلوبات هو \(2N+3\)، لذا فإن بناؤه يكلف \(O(N)\) زمنا و\(O(N)\) ذاكرة. أما حلقة التكرار فتعمل \(N-2\) مرة، وكل مرة تستخدم عددا ثابتا من العمليات المعيارية، ولذلك فهي أيضا \(O(N)\) زمنيا. النتيجة أن الخوارزمية كاملة خطية في \(N\). استهلاك الذاكرة الكلي هو \(O(N)\) ويهيمن عليه جدول المقلوبات، بينما لا تحتاج حالة التكرار والمجموع الجاري إلا إلى \(O(1)\) ذاكرة إضافية.