On each square of an \(n\times n\) board, one centaur is placed at one of the four corners of that square. A centaur attacks as a king or a knight, so a placement is valid only when no two chosen corners are separated by a king move or a knight move. If \(C(n)\) denotes the number of valid boards of size \(n\), the required quantity is
$$\sum_{k=2}^{90} C(F_k) \pmod{100000007},$$
where \(F_1=F_2=1\) and \(F_k=F_{k-1}+F_{k-2}\).
The implementations use a two-level strategy. First, they model the board exactly by row states and a transfer matrix, which gives rigorous small-board checkpoints. Then they use the closed congruence that makes the huge Fibonacci boards feasible.
Scale the board by a factor of \(2\) in both directions. Then the four corners of one square can be written as
$$L_0=(0,0),\qquad L_1=(0,1),\qquad R_0=(1,0),\qquad R_1=(1,1).$$
If the square in column \(c\) and row \(r\) uses the corner \((\xi,\eta)\in\{0,1\}^2\), its centaur sits at
$$\bigl(2c+\xi,\ 2r+\eta\bigr).$$
Two centaurs attack if the coordinate difference is a king move,
$$\max(|\Delta x|,|\Delta y|)=1,$$
or a knight move,
$$\{|\Delta x|,|\Delta y|\}=\{1,2\}.$$
This is exactly the geometric test used by the implementation.
Now inspect two neighboring squares in the same row. Checking the \(16\) ordered pairs of corner choices shows that a legal row can only stay on one fixed left-corner type and then, at most once, switch to one fixed right-corner type. Therefore every valid row has the form
$$\bigl(\underbrace{L_\alpha,\dots,L_\alpha}_{k\text{ entries}},\underbrace{R_\beta,\dots,R_\beta}_{n-k\text{ entries}}\bigr),\qquad \alpha,\beta\in\{0,1\},\ 0\le k\le n.$$
When \(k=0\), the whole row is \(R_\beta\); when \(k=n\), the whole row is \(L_\alpha\). Hence the number of admissible row states is
$$2+4(n-1)+2=4n.$$
This explains why the exact state space is small enough for direct transfer counting on small boards.
Two row states are compatible if no pair of centaurs attacks across consecutive rows. Because the move range is at most a knight move, it is enough to check
$$\text{same-column pairs}\qquad\text{and}\qquad\text{diagonal pairs one column apart}.$$
Let \(T_n\) be the \(4n\times 4n\) matrix whose entry is \(1\) when two row states are compatible and \(0\) otherwise. If \(\mathbf{1}\) is the all-ones vector, then the exact count of legal boards is
$$C(n)=\mathbf{1}^{\mathsf T} T_n^{\,n-1}\mathbf{1}.$$
This is an exact formula for every \(n\). It yields the checkpoint values
$$C(1)=4,\qquad C(2)=25,\qquad C(3)=120,\qquad C(10)=1477721.$$
The Fibonacci boards are far too large for transfer-matrix exponentiation, so the implementations use the closed congruence
$$C(n)\equiv 8\binom{2n}{n}-(3n^2+2n+7)\pmod{p},\qquad p=100000007.$$
Thus the row-transfer combinatorics compresses modulo \(p\) to a central binomial term plus a quadratic correction. Once this congruence is available, the whole problem reduces to evaluating \(\binom{2n}{n}\bmod p\) for very large \(n\).
Because \(p\) is prime, Lucas' theorem applies. Write
$$N=\sum_{t\ge 0} N_t p^t,\qquad K=\sum_{t\ge 0} K_t p^t$$
in base \(p\). Then
$$\binom{N}{K}\equiv \prod_{t\ge 0}\binom{N_t}{K_t}\pmod{p}.$$
For this problem we set
$$N=2n,\qquad K=n.$$
Each digit-level binomial is computed by
$$\binom{a}{b}\equiv a!\,(b!)^{-1}\,((a-b)!)^{-1}\pmod{p},\qquad 0\le b\le a \lt p,$$
and the inverse is obtained from Fermat's little theorem:
$$x^{-1}\equiv x^{p-2}\pmod{p}.$$
The Fibonacci sequence is generated up to \(F_{90}\). For each \(k=2,3,\dots,90\), the implementation evaluates \(C(F_k)\bmod p\) and accumulates the result modulo \(p\):
$$\sum_{k=2}^{90} C(F_k)\pmod{p}.$$
The terms are independent, which is why the C++ implementation can evaluate them in parallel while the Python and Java implementations perform the same arithmetic sequentially.
Since \(2n=20 \lt p\), Lucas' theorem has only one base-\(p\) digit here, so the central binomial coefficient is the ordinary one:
$$\binom{20}{10}=184756.$$
The correction term is
$$3n^2+2n+7=3\cdot 10^2+2\cdot 10+7=327.$$
Therefore
$$C(10)\equiv 8\cdot 184756-327=1477721\pmod{100000007},$$
which matches the checked sample value.
The C++, Python, and Java implementations first prepare modular arithmetic for the prime \(p=100000007\). They precompute factorial values at block boundaries, so a later query for \(n!\bmod p\) starts from the nearest stored block product and multiplies only the short tail inside that block. This keeps repeated small-binomial evaluations efficient.
For large board sizes, the implementation applies Lucas' theorem to \(\binom{2n}{n}\), computes the correction term \(3n^2+2n+7\) modulo \(p\), combines them as \(8\binom{2n}{n}-(3n^2+2n+7)\), and then sums these values over \(F_2,F_3,\dots,F_{90}\).
The C++ implementation also performs self-checks before the final sum: exact transfer-matrix counts for small boards, consistency checks for small binomial coefficients against Pascal's triangle, and the sample values \(C(1)=4\), \(C(2)=25\), and \(C(10)=1477721\). Those checks ensure that the exact model and the modular formula agree on all calibrated cases.
For a board of size \(m\), the exact validation model has \(4m\) row states. Building all row-to-row compatibilities requires \(O(m)\) work per state pair, so the transition construction is \(O(m^3)\), and the dynamic program over \(m\) rows is of the same order. This part is used only for small checkpoints, so its cost is negligible.
The main computation has a one-time preprocessing cost of \(O(p)\) to build factorial products at block boundaries, with memory \(O(p/B)\) when the block size is \(B\). After that, one Lucas digit costs a few tail multiplications of length at most \(B\) plus one modular inverse in \(O(\log p)\). Therefore one evaluation of \(C(n)\) costs
$$O\bigl(\log_p n\cdot (B+\log p)\bigr),$$
and the final Fibonacci sum uses this only \(89\) times.
Auf jedem Feld eines \(n\times n\)-Bretts wird genau ein Zentaur in eine der vier Ecken dieses Feldes gesetzt. Ein Zentaur greift wie ein Koenig und wie ein Springer an. Eine Belegung ist also genau dann gueltig, wenn keine zwei gewaehlten Ecken durch einen Koenigs- oder Springerzug verbunden sind. Bezeichnet \(C(n)\) die Anzahl gueltiger Bretter der Groesse \(n\), so ist gesucht:
$$\sum_{k=2}^{90} C(F_k) \pmod{100000007},$$
wobei \(F_1=F_2=1\) und \(F_k=F_{k-1}+F_{k-2}\) gilt.
Die Implementierungen verwenden zwei Ebenen. Zunaechst wird das Problem exakt durch Zeilenzustaende und eine Transfermatrix modelliert; damit lassen sich kleine Bretter direkt zaehlen und pruefen. Fuer die riesigen Fibonacci-Bretter wird dann die geschlossene Kongruenz benutzt.
Man skaliert das Brett in beide Richtungen mit dem Faktor \(2\). Dann koennen die vier Ecken eines Feldes als
$$L_0=(0,0),\qquad L_1=(0,1),\qquad R_0=(1,0),\qquad R_1=(1,1)$$
geschrieben werden. Verwendet das Feld in Spalte \(c\) und Zeile \(r\) die Ecke \((\xi,\eta)\in\{0,1\}^2\), so liegt der Zentaur am Gitterpunkt
$$\bigl(2c+\xi,\ 2r+\eta\bigr).$$
Zwei Zentauren greifen sich an, wenn der Koordinatenunterschied ein Koenigszug ist, also
$$\max(|\Delta x|,|\Delta y|)=1,$$
oder ein Springerzug, also
$$\{|\Delta x|,|\Delta y|\}=\{1,2\}.$$
Genau diese Geometrie wird in der Implementierung ueberprueft.
Betrachtet man zwei benachbarte Felder in derselben Zeile und testet alle \(16\) geordneten Eckenkombinationen, dann zeigt sich: Eine gueltige Zeile kann nur zunaechst einen festen linken Eckentyp verwenden und dann hoechstens einmal zu einem festen rechten Eckentyp wechseln. Jede gueltige Zeile hat also die Form
$$\bigl(\underbrace{L_\alpha,\dots,L_\alpha}_{k\text{ Eintraege}},\underbrace{R_\beta,\dots,R_\beta}_{n-k\text{ Eintraege}}\bigr),\qquad \alpha,\beta\in\{0,1\},\ 0\le k\le n.$$
Fuer \(k=0\) besteht die ganze Zeile aus \(R_\beta\), fuer \(k=n\) nur aus \(L_\alpha\). Damit gibt es insgesamt
$$2+4(n-1)+2=4n$$
zulaessige Zeilenzustaende. Das erklaert, warum die exakte Zustandsmenge fuer kleine Bretter kompakt bleibt.
Zwei Zeilenzustaende sind kompatibel, wenn sich kein Zentaurenpaar in zwei aufeinanderfolgenden Zeilen angreift. Da die Reichweite hoechstens ein Springerzug ist, genuegt es, Folgendes zu pruefen:
$$\text{Paare in derselben Spalte}\qquad\text{und}\qquad\text{diagonale Paare mit einer Spaltenverschiebung}.$$
Sei \(T_n\) die \(4n\times 4n\)-Matrix, deren Eintrag \(1\) ist, wenn zwei Zeilen kompatibel sind, und sonst \(0\). Mit dem Einsvektor \(\mathbf{1}\) gilt dann exakt
$$C(n)=\mathbf{1}^{\mathsf T} T_n^{\,n-1}\mathbf{1}.$$
Diese Formel ist fuer jedes \(n\) exakt. Sie liefert insbesondere die Kontrollwerte
$$C(1)=4,\qquad C(2)=25,\qquad C(3)=120,\qquad C(10)=1477721.$$
Die Fibonacci-Bretter sind viel zu gross fuer eine Potenzierung der Transfermatrix. Deshalb verwenden die Implementierungen die Kongruenz
$$C(n)\equiv 8\binom{2n}{n}-(3n^2+2n+7)\pmod{p},\qquad p=100000007.$$
Damit verdichtet sich die gesamte Transferstruktur modulo \(p\) zu einem zentralen Binomialkoeffizienten plus einem quadratischen Korrekturterm. Sobald diese Kongruenz vorliegt, muss nur noch \(\binom{2n}{n}\bmod p\) schnell berechnet werden.
Weil \(p\) eine Primzahl ist, kann man den Satz von Lucas anwenden. Schreibe
$$N=\sum_{t\ge 0} N_t p^t,\qquad K=\sum_{t\ge 0} K_t p^t$$
in Basis \(p\). Dann gilt
$$\binom{N}{K}\equiv \prod_{t\ge 0}\binom{N_t}{K_t}\pmod{p}.$$
Hier setzen wir
$$N=2n,\qquad K=n.$$
Jeder Ziffernkoeffizient wird berechnet durch
$$\binom{a}{b}\equiv a!\,(b!)^{-1}\,((a-b)!)^{-1}\pmod{p},\qquad 0\le b\le a \lt p,$$
und die Inversen kommen aus dem kleinen Satz von Fermat:
$$x^{-1}\equiv x^{p-2}\pmod{p}.$$
Die Fibonacci-Folge wird bis \(F_{90}\) erzeugt. Fuer jedes \(k=2,3,\dots,90\) berechnet die Implementierung \(C(F_k)\bmod p\) und summiert diese Werte modulo \(p\):
$$\sum_{k=2}^{90} C(F_k)\pmod{p}.$$
Die Summanden sind unabhaengig voneinander. Deshalb kann die C++-Implementierung die Werte parallel auswerten, waehrend die Python- und Java-Implementierungen dieselbe Arithmetik sequentiell ausfuehren.
Da \(2n=20 \lt p\) gilt, hat Lucas hier nur eine einzige Basis-\(p\)-Ziffer. Der zentrale Binomialkoeffizient ist also der gewoehnliche:
$$\binom{20}{10}=184756.$$
Der Korrekturterm ist
$$3n^2+2n+7=3\cdot 10^2+2\cdot 10+7=327.$$
Also folgt
$$C(10)\equiv 8\cdot 184756-327=1477721\pmod{100000007},$$
genau der kontrollierte Beispielwert.
Die C++-, Python- und Java-Implementierungen bereiten zuerst die modulare Arithmetik fuer die Primzahl \(p=100000007\) vor. Dazu werden Fakultaetswerte an Blockgrenzen vorab gespeichert. Eine spaetere Anfrage nach \(n!\bmod p\) startet dann beim naechsten gespeicherten Blockprodukt und multipliziert nur noch den kurzen Rest innerhalb dieses Blocks. So werden wiederholte kleine Binomialkoeffizienten effizient.
Fuer grosse Brettgroessen wendet die Implementierung Lucas auf \(\binom{2n}{n}\) an, berechnet den Korrekturterm \(3n^2+2n+7\) modulo \(p\), kombiniert beides als \(8\binom{2n}{n}-(3n^2+2n+7)\) und summiert die Ergebnisse fuer \(F_2,F_3,\dots,F_{90}\).
Die C++-Implementierung fuehrt vor der Endsumme zusaetzliche Selbsttests aus: exakte Transfermatrix-Zaehlungen fuer kleine Bretter, Konsistenzpruefungen kleiner Binomialkoeffizienten gegen Pascalsches Dreieck und die Beispielwerte \(C(1)=4\), \(C(2)=25\) und \(C(10)=1477721\). Damit ist abgesichert, dass exaktes Modell und modulare Formel auf allen kalibrierten Faellen uebereinstimmen.
Fuer ein Brett der Groesse \(m\) hat das exakte Validierungsmodell \(4m\) Zeilenzustaende. Das Aufbauen aller Zeilenkompatibilitaeten braucht \(O(m)\) Arbeit pro Zustandspaar, also insgesamt \(O(m^3)\), und das dynamische Programm ueber \(m\) Zeilen hat dieselbe Groessenordnung. Dieser Teil wird nur fuer kleine Kontrollwerte benutzt und ist daher praktisch vernachlaessigbar.
Die Hauptrechnung besitzt einmalige Vorverarbeitungskosten von \(O(p)\) fuer die Fakultaetsprodukte an den Blockgrenzen und Speicher \(O(p/B)\), wenn \(B\) die Blockgroesse ist. Danach kostet eine Lucas-Ziffer einige Restmultiplikationen von Laenge hoechstens \(B\) plus eine modulare Inversion in \(O(\log p)\). Damit kostet eine Auswertung von \(C(n)\)
$$O\bigl(\log_p n\cdot (B+\log p)\bigr),$$
und die abschliessende Fibonacci-Summe benoetigt das nur \(89\)-mal.
Her \(n\times n\) tahtasinda, her kareye o karenin dort kosesinden birine yerlestirilmis tam bir centaur tasini dusunuyoruz. Centaur tasi hem sah hem de at gibi saldirdigi icin, secilen iki kose arasindaki fark bir sah hamlesi ya da bir at hamlesi olursa yerlesim gecersizdir. \(C(n)\), boyutu \(n\) olan tahtalardaki gecerli yerlesim sayisi olsun. Istenen nicelik
$$\sum_{k=2}^{90} C(F_k) \pmod{100000007}$$
ifadesidir; burada \(F_1=F_2=1\) ve \(F_k=F_{k-1}+F_{k-2}\) tanimi kullanilir.
Uygulamalar iki katmanli bir strateji kullanir. Ilk katman problemi satir durumlari ve transfer matrisiyle tam olarak modeller; bu sayede kucuk tahtalar icin kesin kontrol degerleri elde edilir. Ikinci katman ise cok buyuk Fibonacci tahtalarini hesaplanabilir hale getiren kapali kongruansi kullanir.
Tahtayi her iki eksende de \(2\) katsayisiyla olceklendirelim. O zaman bir karenin dort kosesi
$$L_0=(0,0),\qquad L_1=(0,1),\qquad R_0=(1,0),\qquad R_1=(1,1)$$
seklinde yazilabilir. Sutunu \(c\), satiri \(r\) olan karede \((\xi,\eta)\in\{0,1\}^2\) kosesi secildiginde centaur tasinin konumu
$$\bigl(2c+\xi,\ 2r+\eta\bigr)$$
olur. Iki tas, koordinat farklari bir sah hamlesi oldugunda yani
$$\max(|\Delta x|,|\Delta y|)=1,$$
ya da bir at hamlesi oldugunda yani
$$\{|\Delta x|,|\Delta y|\}=\{1,2\}$$
birbirini tehdit eder. Uygulamanin geometrik testi tam olarak budur.
Ayni satirdaki komsu iki kareye bakalim. Kose secimlerinin \(16\) sirali olasiligini tek tek kontrol edince su sonuc cikar: gecerli bir satir, once sabit bir sol-kose tipinde kalir, sonra en fazla bir kez sabit bir sag-kose tipine gecer. Dolayisiyla her gecerli satir
$$\bigl(\underbrace{L_\alpha,\dots,L_\alpha}_{k\text{ giris}},\underbrace{R_\beta,\dots,R_\beta}_{n-k\text{ giris}}\bigr),\qquad \alpha,\beta\in\{0,1\},\ 0\le k\le n$$
biçimindedir. \(k=0\) ise tum satir \(R_\beta\), \(k=n\) ise tum satir \(L_\alpha\) olur. Bu nedenle izin verilen satir durumlarinin sayisi
$$2+4(n-1)+2=4n$$
olur. Kucuk tahtalarda tam aktarim sayiminin yapilabilmesini saglayan kompak durum uzayi budur.
Iki satir durumu, ard arda geldiklerinde hicbir centaur cifti birbirine saldirmiyorsa uyumludur. Saldiri menzili en fazla at hamlesi kadar oldugu icin sadece su ciftleri kontrol etmek yeterlidir:
$$\text{ayni sutundaki ciftler}\qquad\text{ve}\qquad\text{bir sutun kaymis capraz ciftler}.$$
\(T_n\), iki satir uyumluysa girisi \(1\), degilse \(0\) olan \(4n\times 4n\) boyutlu matris olsun. \(\mathbf{1}\) tumu \(1\) olan vektor ise kesin sayim
$$C(n)=\mathbf{1}^{\mathsf T} T_n^{\,n-1}\mathbf{1}$$
seklindedir. Bu ifade her \(n\) icin tamdir ve asagidaki kontrol degerlerini verir:
$$C(1)=4,\qquad C(2)=25,\qquad C(3)=120,\qquad C(10)=1477721.$$
Fibonacci boyutlu tahtalar transfer matrisini kuvvetlendirmek icin cok buyuktur. Bu nedenle uygulamalar
$$C(n)\equiv 8\binom{2n}{n}-(3n^2+2n+7)\pmod{p},\qquad p=100000007$$
kongruansini kullanir. Yani satir-transfer modelinin tum kombinatorigi modulo \(p\) altinda merkezi bir binom katsayisi ve basit bir ikinci derece duzeltme terimine sikisir. Bundan sonra asil zor kisim yalnizca \(\binom{2n}{n}\bmod p\) hesabidir.
\(p\) asal oldugu icin Lucas teoremi uygulanir. Su acilimi yazalim:
$$N=\sum_{t\ge 0} N_t p^t,\qquad K=\sum_{t\ge 0} K_t p^t.$$
O zaman
$$\binom{N}{K}\equiv \prod_{t\ge 0}\binom{N_t}{K_t}\pmod{p}$$
elde edilir. Bu problemde
$$N=2n,\qquad K=n$$
alinir. Her basamak seviyesindeki binom
$$\binom{a}{b}\equiv a!\,(b!)^{-1}\,((a-b)!)^{-1}\pmod{p},\qquad 0\le b\le a \lt p$$
formuluyla bulunur; tersler de Fermat kucuk teoremi ile hesaplanir:
$$x^{-1}\equiv x^{p-2}\pmod{p}.$$
Fibonacci dizisi \(F_{90}\)'a kadar uretilir. Her \(k=2,3,\dots,90\) icin uygulama \(C(F_k)\bmod p\) degerini hesaplar ve bunlari modulo \(p\) toplar:
$$\sum_{k=2}^{90} C(F_k)\pmod{p}.$$
Terimler birbirinden bagimsizdir. Bu yuzden C++ uygulamasi bu degerleri paralel hesaplayabilir; Python ve Java uygulamalari ise ayni aritmetigi sirali bicimde uygular.
Burada \(2n=20 \lt p\) oldugundan Lucas ayrisimi tek bir taban-\(p\) basamagindan ibarettir. Dolayisiyla merkezi binom katsayisi siradan degerdir:
$$\binom{20}{10}=184756.$$
Duzeltme terimi ise
$$3n^2+2n+7=3\cdot 10^2+2\cdot 10+7=327$$
olur. O halde
$$C(10)\equiv 8\cdot 184756-327=1477721\pmod{100000007},$$
ki bu deger kontrol edilen ornekle aynidir.
C++, Python ve Java uygulamalari once asal \(p=100000007\) icin moduler aritmetigi hazirlar. Bunun icin blok sinirlarinda faktoriyel carpimlari onceden saklanir. Daha sonra \(n!\bmod p\) istendiginde, en yakin kayitli blok urununden baslanir ve sadece o blok icindeki kisa kuyruk carpilir. Boylece tekrar tekrar gereken kucuk binom hesaplari hizlanir.
Buyuk tahta boyutlarinda uygulama Lucas teoremini \(\binom{2n}{n}\) uzerine uygular, \(3n^2+2n+7\) duzeltmesini modulo \(p\) hesaplar, bunlari \(8\binom{2n}{n}-(3n^2+2n+7)\) olarak birlestirir ve bu degerleri \(F_2,F_3,\dots,F_{90}\) uzerinde toplar.
C++ uygulamasi son toplamdan once ek oz-denetimler de yapar: kucuk tahtalar icin tam transfer-matrisi sayimlari, kucuk binom degerlerinin Pascal ucgeniyle tutarliligi ve \(C(1)=4\), \(C(2)=25\), \(C(10)=1477721\) kontrol noktalari. Boylece tam model ile moduler formulin ayni davranisi verdigi dogrulanmis olur.
Boyutu \(m\) olan bir tahta icin tam dogrulama modeli \(4m\) adet satir durumuna sahiptir. Tum satir-cifti uyumluluklarini kurmak, her durum cifti basina \(O(m)\) is gerektirdiginden toplam \(O(m^3)\) zaman alir; \(m\) satirlik dinamik program da ayni mertebededir. Bu kisim yalnizca kucuk kontrol degerleri icin kullanildigi icin pratikte ihmal edilebilir.
Ana hesaplamada blok sinirlarindaki faktoriyel urunlerini hazirlamak icin tek seferlik \(O(p)\) onislem ve blok boyutu \(B\) icin \(O(p/B)\) bellek gerekir. Bundan sonra bir Lucas basamagi, uzunlugu en fazla \(B\) olan birkac kuyruk carpimi ve \(O(\log p)\) maliyetli bir moduler ters alma gerektirir. Bu nedenle bir \(C(n)\) degeri
$$O\bigl(\log_p n\cdot (B+\log p)\bigr)$$
zamanda hesaplanir; nihai Fibonacci toplami bunu yalnizca \(89\) kez yapar.
En cada casilla de un tablero \(n\times n\) se coloca exactamente un centauro en una de las cuatro esquinas de esa casilla. El centauro ataca como rey y como caballo, de modo que una configuracion es valida solo si ninguna pareja de esquinas elegidas esta separada por un movimiento de rey o de caballo. Si \(C(n)\) denota el numero de tableros validos de tamano \(n\), la cantidad pedida es
$$\sum_{k=2}^{90} C(F_k) \pmod{100000007},$$
donde \(F_1=F_2=1\) y \(F_k=F_{k-1}+F_{k-2}\).
Las implementaciones usan una estrategia de dos niveles. Primero modelan el problema exactamente con estados de fila y una matriz de transferencia, lo que proporciona puntos de control exactos en tableros pequenos. Despues usan la congruencia cerrada que hace posible tratar los enormes tableros de tamano Fibonacci.
Escalamos el tablero por un factor \(2\) en ambas direcciones. Entonces las cuatro esquinas de una casilla se representan como
$$L_0=(0,0),\qquad L_1=(0,1),\qquad R_0=(1,0),\qquad R_1=(1,1).$$
Si la casilla de columna \(c\) y fila \(r\) usa la esquina \((\xi,\eta)\in\{0,1\}^2\), el centauro queda en
$$\bigl(2c+\xi,\ 2r+\eta\bigr).$$
Dos centauros se atacan si la diferencia de coordenadas es un movimiento de rey, es decir
$$\max(|\Delta x|,|\Delta y|)=1,$$
o un movimiento de caballo, es decir
$$\{|\Delta x|,|\Delta y|\}=\{1,2\}.$$
Esta es exactamente la geometria que comprueba la implementacion.
Ahora miramos dos casillas vecinas de una misma fila. Al revisar los \(16\) pares ordenados posibles de esquinas se obtiene que una fila legal solo puede mantenerse en un tipo fijo de esquina izquierda y, como mucho una vez, cambiar a un tipo fijo de esquina derecha. Por tanto, toda fila valida tiene la forma
$$\bigl(\underbrace{L_\alpha,\dots,L_\alpha}_{k\text{ entradas}},\underbrace{R_\beta,\dots,R_\beta}_{n-k\text{ entradas}}\bigr),\qquad \alpha,\beta\in\{0,1\},\ 0\le k\le n.$$
Cuando \(k=0\), toda la fila es \(R_\beta\); cuando \(k=n\), toda la fila es \(L_\alpha\). Por eso el numero de estados admisibles de fila es
$$2+4(n-1)+2=4n.$$
Asi se explica el espacio de estados compacto usado por el conteo exacto en tableros pequenos.
Dos estados de fila son compatibles si ninguna pareja de centauros se ataca entre dos filas consecutivas. Como el alcance del ataque no supera un movimiento de caballo, basta comprobar
$$\text{pares en la misma columna}\qquad\text{y}\qquad\text{pares diagonales separados por una columna}.$$
Sea \(T_n\) la matriz \(4n\times 4n\) cuya entrada vale \(1\) cuando dos filas son compatibles y \(0\) en caso contrario. Si \(\mathbf{1}\) es el vector de unos, entonces el conteo exacto es
$$C(n)=\mathbf{1}^{\mathsf T} T_n^{\,n-1}\mathbf{1}.$$
La formula es exacta para todo \(n\). Produce, por ejemplo, los valores de control
$$C(1)=4,\qquad C(2)=25,\qquad C(3)=120,\qquad C(10)=1477721.$$
Los tableros de tamano Fibonacci son demasiado grandes para elevar una matriz de transferencia. Por eso las implementaciones usan la congruencia
$$C(n)\equiv 8\binom{2n}{n}-(3n^2+2n+7)\pmod{p},\qquad p=100000007.$$
En otras palabras, toda la combinatoria del modelo por filas se condensa modulo \(p\) en un coeficiente binomial central y una correccion cuadratica. A partir de ahi, el problema se reduce a calcular \(\binom{2n}{n}\bmod p\) para \(n\) muy grandes.
Como \(p\) es primo, se aplica el teorema de Lucas. Escribimos
$$N=\sum_{t\ge 0} N_t p^t,\qquad K=\sum_{t\ge 0} K_t p^t$$
en base \(p\). Entonces
$$\binom{N}{K}\equiv \prod_{t\ge 0}\binom{N_t}{K_t}\pmod{p}.$$
En este problema tomamos
$$N=2n,\qquad K=n.$$
Cada binomio de un solo digito se calcula mediante
$$\binom{a}{b}\equiv a!\,(b!)^{-1}\,((a-b)!)^{-1}\pmod{p},\qquad 0\le b\le a \lt p,$$
y las inversas se obtienen con el pequeno teorema de Fermat:
$$x^{-1}\equiv x^{p-2}\pmod{p}.$$
Se genera la sucesion de Fibonacci hasta \(F_{90}\). Para cada \(k=2,3,\dots,90\), la implementacion evalua \(C(F_k)\bmod p\) y acumula el resultado modulo \(p\):
$$\sum_{k=2}^{90} C(F_k)\pmod{p}.$$
Los terminos son independientes. Por eso la implementacion en C++ puede evaluarlos en paralelo, mientras que las versiones en Python y Java hacen la misma aritmetica de forma secuencial.
Como \(2n=20 \lt p\), aqui Lucas solo tiene un digito en base \(p\), de modo que el binomial central es el ordinario:
$$\binom{20}{10}=184756.$$
El termino de correccion vale
$$3n^2+2n+7=3\cdot 10^2+2\cdot 10+7=327.$$
Por lo tanto
$$C(10)\equiv 8\cdot 184756-327=1477721\pmod{100000007},$$
que coincide con el valor de control verificado.
Las implementaciones en C++, Python y Java preparan primero la aritmetica modular para el primo \(p=100000007\). Precalculan productos factoriales en los limites de bloques; asi, una consulta posterior de \(n!\bmod p\) parte del producto almacenado mas cercano y solo multiplica el pequeno tramo final dentro del bloque. Eso abarata las muchas evaluaciones repetidas de binomios pequenos.
Para tableros grandes, la implementacion aplica Lucas a \(\binom{2n}{n}\), calcula la correccion \(3n^2+2n+7\) modulo \(p\), combina ambos terminos como \(8\binom{2n}{n}-(3n^2+2n+7)\) y luego suma esos valores para \(F_2,F_3,\dots,F_{90}\).
La implementacion en C++ tambien ejecuta autocontroles antes de la suma final: conteos exactos por matriz de transferencia en tableros pequenos, comprobaciones de binomios pequenos frente al triangulo de Pascal y los valores \(C(1)=4\), \(C(2)=25\) y \(C(10)=1477721\). Con eso se confirma que el modelo exacto y la formula modular coinciden en todos los casos calibrados.
Para un tablero de tamano \(m\), el modelo exacto de validacion tiene \(4m\) estados de fila. Construir todas las compatibilidades entre filas requiere \(O(m)\) trabajo por cada par de estados, asi que la construccion de transiciones cuesta \(O(m^3)\), y el programa dinamico sobre \(m\) filas tiene el mismo orden. Como esta parte solo se usa en puntos de control pequenos, su coste es despreciable.
La computacion principal tiene un preprocesamiento unico de coste \(O(p)\) para construir productos factoriales en fronteras de bloque y memoria \(O(p/B)\), donde \(B\) es el tamano del bloque. Despues, cada digito de Lucas necesita unas pocas multiplicaciones finales de longitud a lo sumo \(B\) mas una inversion modular en \(O(\log p)\). Por tanto, una evaluacion de \(C(n)\) cuesta
$$O\bigl(\log_p n\cdot (B+\log p)\bigr),$$
y la suma final de Fibonacci solo usa esto \(89\) veces.
在一个 \(n\times n\) 的棋盘上，每个方格里都放置一枚半人马棋子，并且这枚棋子只能放在该方格的四个角之一。半人马棋子的走法是“国王 + 骑士”，因此如果两个被选中的角之间相差一个国王步或一个骑士步，这种摆法就是非法的。设 \(C(n)\) 表示边长为 \(n\) 的棋盘上的合法摆放总数，那么题目要求计算
$$\sum_{k=2}^{90} C(F_k) \pmod{100000007},$$
其中 Fibonacci 数列满足 \(F_1=F_2=1\)，且 \(F_k=F_{k-1}+F_{k-2}\)。
实现采用两层思路。第一层用“行状态 + 转移矩阵”对问题进行精确建模，因此可以在小棋盘上得到完全准确的校验值。第二层使用大规模计算真正依赖的闭式同余，从而把 Fibonacci 规模的大棋盘降到可计算的范围。
先把棋盘在横向和纵向都放大 \(2\) 倍。这样，一个方格的四个角可以写成
$$L_0=(0,0),\qquad L_1=(0,1),\qquad R_0=(1,0),\qquad R_1=(1,1).$$
如果第 \(r\) 行、第 \(c\) 列的方格选择了角 \((\xi,\eta)\in\{0,1\}^2\)，那么对应棋子的坐标就是
$$\bigl(2c+\xi,\ 2r+\eta\bigr).$$
两枚棋子互相攻击，当且仅当它们的坐标差是一个国王步，也就是
$$\max(|\Delta x|,|\Delta y|)=1,$$
或者是一个骑士步，也就是
$$\{|\Delta x|,|\Delta y|\}=\{1,2\}.$$
这与实现中使用的几何判定完全一致。
接着只看同一行中相邻的两个方格。把四个角的 \(16\) 个有序组合逐一检查后，可以发现：一行中的选择只能先一直停留在某一种“左角”类型，然后最多发生一次切换，改为某一种固定的“右角”类型。于是任何一行合法状态都必然形如
$$\bigl(\underbrace{L_\alpha,\dots,L_\alpha}_{k\text{ 个}},\underbrace{R_\beta,\dots,R_\beta}_{n-k\text{ 个}}\bigr),\qquad \alpha,\beta\in\{0,1\},\ 0\le k\le n.$$
当 \(k=0\) 时，整行都是 \(R_\beta\)；当 \(k=n\) 时，整行都是 \(L_\alpha\)。因此一行可行状态的总数为
$$2+4(n-1)+2=4n.$$
这正是小规模精确转移计数之所以可行的关键压缩。
如果两行相邻摆放时，没有任何一对棋子彼此攻击，就称这两个行状态兼容。由于攻击范围最多只到骑士步，所以跨两行时只需要检查两类局部关系：
$$\text{同一列中的成对格子}\qquad\text{以及}\qquad\text{横向相差一列的对角格子。}$$
令 \(T_n\) 为一个 \(4n\times 4n\) 的矩阵：如果两种行状态兼容，则对应元素为 \(1\)，否则为 \(0\)。再记 \(\mathbf{1}\) 为全 1 向量，则合法棋盘总数满足精确公式
$$C(n)=\mathbf{1}^{\mathsf T} T_n^{\,n-1}\mathbf{1}.$$
这个公式对每个 \(n\) 都是严格成立的。它给出了实现中用作校验的一组数值：
$$C(1)=4,\qquad C(2)=25,\qquad C(3)=120,\qquad C(10)=1477721.$$
真正要处理的 Fibonacci 棋盘远远大于转移矩阵直接幂乘所能承受的范围，因此实现转而使用闭式同余
$$C(n)\equiv 8\binom{2n}{n}-(3n^2+2n+7)\pmod{p},\qquad p=100000007.$$
也就是说，行转移模型里复杂的组合结构在模 \(p\) 的意义下，被压缩成了一个中心二项式系数和一个简单的二次修正项。只要接受这个同余结论，剩下的核心任务就变成了高效计算 \(\binom{2n}{n}\bmod p\)。
因为 \(p\) 是素数，所以可以应用 Lucas 定理。把
$$N=\sum_{t\ge 0} N_t p^t,\qquad K=\sum_{t\ge 0} K_t p^t$$
写成 \(p\) 进制展开，则有
$$\binom{N}{K}\equiv \prod_{t\ge 0}\binom{N_t}{K_t}\pmod{p}.$$
在本题中取
$$N=2n,\qquad K=n.$$
每一个“单个数位上的二项式系数”都通过
$$\binom{a}{b}\equiv a!\,(b!)^{-1}\,((a-b)!)^{-1}\pmod{p},\qquad 0\le b\le a \lt p$$
来计算，而逆元由 Fermat 小定理给出：
$$x^{-1}\equiv x^{p-2}\pmod{p}.$$
先生成 Fibonacci 数列直到 \(F_{90}\)。对于每个 \(k=2,3,\dots,90\)，实现都会计算 \(C(F_k)\bmod p\)，然后把这些值模 \(p\) 累加：
$$\sum_{k=2}^{90} C(F_k)\pmod{p}.$$
这些项彼此独立，所以 C++ 实现可以把它们分发到多个线程并行计算，而 Python 与 Java 实现则顺序执行同样的模运算流程。
这里 \(2n=20 \lt p\)，因此 Lucas 定理只涉及一个 \(p\) 进制数位，中心二项式系数就是通常意义下的
$$\binom{20}{10}=184756.$$
修正项为
$$3n^2+2n+7=3\cdot 10^2+2\cdot 10+7=327.$$
所以
$$C(10)\equiv 8\cdot 184756-327=1477721\pmod{100000007},$$
这与程序中校验过的示例值完全一致。
C++、Python 和 Java 实现首先为素数 \(p=100000007\) 准备模运算基础。它们会预先保存若干“块边界”上的阶乘乘积，因此以后查询 \(n!\bmod p\) 时，只需要从最近的已保存块开始，再把该块内剩余的一小段尾部乘上去即可。这使得反复出现的小规模二项式系数计算变得高效。
在大棋盘部分，实现对 \(\binom{2n}{n}\) 应用 Lucas 定理，计算修正项 \(3n^2+2n+7\) 在模 \(p\) 下的值，再按 \(8\binom{2n}{n}-(3n^2+2n+7)\) 合成出 \(C(n)\bmod p\)，最后对 \(F_2,F_3,\dots,F_{90}\) 的所有结果求和。
C++ 实现还会在最终求和前做显式自检：对小棋盘执行精确转移计数，用 Pascal 三角形核对小范围二项式系数，并验证 \(C(1)=4\)、\(C(2)=25\)、\(C(10)=1477721\) 这些样例值。这样可以确认精确模型和模公式在所有已校准案例上彼此一致。
对于边长为 \(m\) 的棋盘，精确校验模型有 \(4m\) 个行状态。构造所有行之间的兼容关系时，每个状态对需要 \(O(m)\) 的检查，因此转移构造是 \(O(m^3)\)，随后在 \(m\) 行上的动态规划也具有同阶复杂度。由于这部分只用于很小的校验规模，所以总成本很低。
主计算部分需要一次性的 \(O(p)\) 预处理来建立块边界处的阶乘乘积；若块大小为 \(B\)，内存开销为 \(O(p/B)\)。此后，Lucas 展开中的每个数位需要若干段长度不超过 \(B\) 的尾部乘法，以及一次 \(O(\log p)\) 的模逆计算。因此一次 \(C(n)\) 的求值复杂度为
$$O\bigl(\log_p n\cdot (B+\log p)\bigr),$$
而最终的 Fibonacci 求和只会执行这种计算 \(89\) 次。
На каждой клетке доски \(n\times n\) размещается ровно один кентавр, причем его можно поставить в один из четырех углов этой клетки. Кентавр бьет как король и как конь, поэтому расстановка допустима только тогда, когда никакие две выбранные вершины не находятся друг от друга на расстоянии хода короля или хода коня. Пусть \(C(n)\) обозначает число допустимых досок размера \(n\). Требуется вычислить
$$\sum_{k=2}^{90} C(F_k) \pmod{100000007},$$
где \(F_1=F_2=1\) и \(F_k=F_{k-1}+F_{k-2}\).
Реализации используют двухуровневую схему. Сначала задача описывается точно через состояния строк и матрицу переходов, что дает надежные контрольные значения на малых досках. Затем применяется замкнутая конгруэнция, которая и делает вычисление для огромных фибоначчиевых размеров практически возможным.
Удобно растянуть доску в обеих координатах в \(2\) раза. Тогда четыре угла клетки можно записать как
$$L_0=(0,0),\qquad L_1=(0,1),\qquad R_0=(1,0),\qquad R_1=(1,1).$$
Если клетка в столбце \(c\) и строке \(r\) использует угол \((\xi,\eta)\in\{0,1\}^2\), то кентавр находится в точке
$$\bigl(2c+\xi,\ 2r+\eta\bigr).$$
Два кентавра атакуют друг друга, если разность координат задает ход короля, то есть
$$\max(|\Delta x|,|\Delta y|)=1,$$
или ход коня, то есть
$$\{|\Delta x|,|\Delta y|\}=\{1,2\}.$$
Именно такую геометрическую проверку выполняет реализация.
Рассмотрим две соседние клетки в одной строке. Проверка всех \(16\) упорядоченных пар углов показывает, что допустимая строка может сначала идти только по одному фиксированному типу левого угла, а затем не более одного раза переключиться на один фиксированный тип правого угла. Поэтому любая допустимая строка имеет вид
$$\bigl(\underbrace{L_\alpha,\dots,L_\alpha}_{k\text{ элементов}},\underbrace{R_\beta,\dots,R_\beta}_{n-k\text{ элементов}}\bigr),\qquad \alpha,\beta\in\{0,1\},\ 0\le k\le n.$$
При \(k=0\) вся строка состоит из \(R_\beta\), а при \(k=n\) вся строка состоит из \(L_\alpha\). Поэтому число допустимых состояний строки равно
$$2+4(n-1)+2=4n.$$
Этим и объясняется компактность точного пространства состояний на малых досках.
Два состояния строк совместимы, если никакая пара кентавров не бьет друг друга в двух соседних строках. Так как дальность удара не превосходит хода коня, достаточно проверять только
$$\text{пары в одном столбце}\qquad\text{и}\qquad\text{диагональные пары со сдвигом на один столбец}.$$
Пусть \(T_n\) обозначает матрицу размера \(4n\times 4n\), в которой стоит \(1\), если две строки совместимы, и \(0\) в противном случае. Тогда точное число допустимых досок задается формулой
$$C(n)=\mathbf{1}^{\mathsf T} T_n^{\,n-1}\mathbf{1}.$$
Эта формула точна для любого \(n\). В частности, она дает контрольные значения
$$C(1)=4,\qquad C(2)=25,\qquad C(3)=120,\qquad C(10)=1477721.$$
Фибоначчиевы размеры слишком велики для прямого возведения матрицы переходов в степень, поэтому реализации используют конгруэнцию
$$C(n)\equiv 8\binom{2n}{n}-(3n^2+2n+7)\pmod{p},\qquad p=100000007.$$
Тем самым вся сложная комбинаторика модели по строкам сжимается по модулю \(p\) до центрального биномиального коэффициента и простого квадратичного поправочного члена. После этого остается быстро вычислять \(\binom{2n}{n}\bmod p\).
Поскольку \(p\) простое, применима теорема Лукаса. Запишем
$$N=\sum_{t\ge 0} N_t p^t,\qquad K=\sum_{t\ge 0} K_t p^t$$
в системе счисления по основанию \(p\). Тогда
$$\binom{N}{K}\equiv \prod_{t\ge 0}\binom{N_t}{K_t}\pmod{p}.$$
В нашей задаче берется
$$N=2n,\qquad K=n.$$
Каждый цифровой биномиальный коэффициент вычисляется по формуле
$$\binom{a}{b}\equiv a!\,(b!)^{-1}\,((a-b)!)^{-1}\pmod{p},\qquad 0\le b\le a \lt p,$$
а обратный элемент находится с помощью малой теоремы Ферма:
$$x^{-1}\equiv x^{p-2}\pmod{p}.$$
Последовательность Фибоначчи строится до \(F_{90}\). Для каждого \(k=2,3,\dots,90\) реализация вычисляет \(C(F_k)\bmod p\) и добавляет это значение к сумме по модулю \(p\):
$$\sum_{k=2}^{90} C(F_k)\pmod{p}.$$
Все слагаемые независимы, поэтому реализация на C++ может считать их параллельно, а версии на Python и Java выполняют ту же арифметику последовательно.
Так как \(2n=20 \lt p\), разложение Лукаса здесь состоит только из одной цифры по основанию \(p\). Значит, центральный биномиальный коэффициент равен обычному
$$\binom{20}{10}=184756.$$
Поправочный член равен
$$3n^2+2n+7=3\cdot 10^2+2\cdot 10+7=327.$$
Следовательно,
$$C(10)\equiv 8\cdot 184756-327=1477721\pmod{100000007},$$
что совпадает с проверяемым образцом.
Реализации на C++, Python и Java сначала подготавливают модульную арифметику для простого числа \(p=100000007\). Для этого заранее сохраняются произведения факториалов на границах блоков. Позже запрос \(n!\bmod p\) начинается с ближайшего сохраненного произведения блока и домножает только короткий хвост внутри этого блока. Благодаря этому многократные вычисления малых биномиальных коэффициентов становятся дешевле.
Для больших размеров доски реализация применяет теорему Лукаса к \(\binom{2n}{n}\), вычисляет поправку \(3n^2+2n+7\) по модулю \(p\), объединяет оба слагаемых в выражение \(8\binom{2n}{n}-(3n^2+2n+7)\) и затем суммирует результаты для \(F_2,F_3,\dots,F_{90}\).
Реализация на C++ также выполняет самопроверки перед финальной суммой: точные подсчеты через матрицу переходов для малых досок, сверку малых биномиальных коэффициентов с треугольником Паскаля и проверку значений \(C(1)=4\), \(C(2)=25\), \(C(10)=1477721\). Это подтверждает согласованность точной модели и модульной формулы на всех калибровочных случаях.
Для доски размера \(m\) точная проверочная модель имеет \(4m\) состояний строки. Построение всех совместимостей между строками требует \(O(m)\) работы на пару состояний, поэтому построение переходов занимает \(O(m^3)\), а динамическое программирование по \(m\) строкам имеет тот же порядок. Поскольку эта часть используется только для малых контрольных значений, ее стоимость практически несущественна.
Основной расчет имеет одноразовую предобработку стоимости \(O(p)\) для построения факториальных произведений на границах блоков и требует памяти \(O(p/B)\), если \(B\) - размер блока. После этого один цифровой шаг Лукаса состоит из нескольких хвостовых умножений длины не более \(B\) и одного модульного обратного элемента стоимости \(O(\log p)\). Поэтому вычисление одного значения \(C(n)\) занимает
$$O\bigl(\log_p n\cdot (B+\log p)\bigr),$$
а в итоговой сумме Фибоначчи такая операция выполняется только \(89\) раз.
على كل مربع من لوحة \(n\times n\) نضع قطعة سنتاور واحدة في واحد من الزوايا الأربع لذلك المربع. قطعة السنتاور تضرب كأنها ملك وفارس معا، لذلك تكون الوضعية صالحة فقط إذا لم تكن اي زاويتين مختارتين على بعد حركة ملك او حركة فارس من بعضهما. اذا رمزنا بعدد الترتيبات الصالحة على لوحة ضلعها \(n\) بالرمز \(C(n)\)، فالمطلوب هو حساب
$$\sum_{k=2}^{90} C(F_k) \pmod{100000007},$$
حيث \(F_1=F_2=1\) و \(F_k=F_{k-1}+F_{k-2}\).
التنفيذات تعتمد على مستويين. اولا يتم بناء نموذج دقيق للمسألة باستخدام حالات الصفوف ومصفوفة انتقال، وهذا يعطي قيما تحقق دقيقة على اللوحات الصغيرة. ثم يتم الانتقال الى علاقة توافقية مغلقة هي التي تسمح فعلا بالتعامل مع احجام فيبوناتشي الكبيرة جدا.
من المفيد تكبير اللوحة بمعامل \(2\) في الاتجاهين. عندئذ يمكن كتابة زوايا المربع الواحد على الصورة
$$L_0=(0,0),\qquad L_1=(0,1),\qquad R_0=(1,0),\qquad R_1=(1,1).$$
اذا كانت الخانة في العمود \(c\) والصف \(r\) تستخدم الزاوية \((\xi,\eta)\in\{0,1\}^2\)، فان موضع السنتاور يصبح
$$\bigl(2c+\xi,\ 2r+\eta\bigr).$$
وتتبادل قطعتان الهجوم اذا كان فرق الاحداثيين يمثل حركة ملك، اي
$$\max(|\Delta x|,|\Delta y|)=1,$$
او حركة فارس، اي
$$\{|\Delta x|,|\Delta y|\}=\{1,2\}.$$
وهذا هو بالضبط الاختبار الهندسي الذي تستخدمه التنفيذات.
لننظر الى مربعين متجاورين في الصف نفسه. عند فحص جميع الازواج المرتبة الممكنة وعددها \(16\)، يتبين ان الصف الصالح لا يمكنه الا ان يبقى اولا على نوع ثابت من الزوايا اليسرى، ثم ينتقل مرة واحدة على الاكثر الى نوع ثابت من الزوايا اليمنى. لذلك فان كل صف صالح يكتب على الصورة
$$\bigl(\underbrace{L_\alpha,\dots,L_\alpha}_{k},\underbrace{R_\beta,\dots,R_\beta}_{n-k}\bigr),\qquad \alpha,\beta\in\{0,1\},\ 0\le k\le n.$$
عندما يكون \(k=0\) يكون الصف كله من النوع \(R_\beta\)، وعندما يكون \(k=n\) يكون الصف كله من النوع \(L_\alpha\). ومن ثم يكون عدد حالات الصف المسموح بها
$$2+4(n-1)+2=4n.$$
وهذا يفسر لماذا يبقى فضاء الحالات الدقيق صغيرا بما يكفي للتحقق المباشر على الاحجام الصغيرة.
حالان لصفين متتاليين يكونان متوافقين اذا لم توجد اي قطعتين متقابلتين تهاجم احداهما الاخرى عبر الصفين. وبما ان مدى الهجوم لا يتجاوز حركة فارس، فيكفي فحص
اي يجب فحص الازواج الواقعة في العمود نفسه، وكذلك الازواج القطرية التي يختلف عموداها بمقدار واحد.
لنرمز ب \(T_n\) الى المصفوفة ذات الحجم \(4n\times 4n\) التي تكون قيمتها \(1\) اذا كان الصفان متوافقين و \(0\) خلاف ذلك. اذا كانت \(\mathbf{1}\) هي متجه جميع عناصره \(1\)، فان العدد الدقيق للوحات الصالحة يساوي
$$C(n)=\mathbf{1}^{\mathsf T} T_n^{\,n-1}\mathbf{1}.$$
هذه صيغة دقيقة لكل \(n\)، وتعطي قيم التحقق
$$C(1)=4,\qquad C(2)=25,\qquad C(3)=120,\qquad C(10)=1477721.$$
اللوحات ذات الاحجام الفيبوناتشية اكبر بكثير من ان تحسب مباشرة برفع مصفوفة انتقال، لذلك تعتمد التنفيذات على العلاقة
$$C(n)\equiv 8\binom{2n}{n}-(3n^2+2n+7)\pmod{p},\qquad p=100000007.$$
بمعنى ان كل البنية التوافقية لنموذج الصفوف تنضغط modulo \(p\) الى حد ثنائي مركزي مع حد تصحيح تربيعي بسيط. وبعد امتلاك هذه العلاقة يصبح العبء الحقيقي هو حساب \(\binom{2n}{n}\bmod p\) بسرعة حتى عندما يكون \(n\) ضخما جدا.
لان \(p\) عدد اولي، يمكن تطبيق مبرهنة Lucas. نكتب
$$N=\sum_{t\ge 0} N_t p^t,\qquad K=\sum_{t\ge 0} K_t p^t$$
في الاساس \(p\). عندئذ نحصل على
$$\binom{N}{K}\equiv \prod_{t\ge 0}\binom{N_t}{K_t}\pmod{p}.$$
في هذه المسألة نأخذ
$$N=2n,\qquad K=n.$$
ويحسب كل معامل ثنائي على مستوى الرقم الواحد من خلال
$$\binom{a}{b}\equiv a!\,(b!)^{-1}\,((a-b)!)^{-1}\pmod{p},\qquad 0\le b\le a \lt p,$$
بينما يستخرج المعكوس من مبرهنة Fermat الصغرى:
$$x^{-1}\equiv x^{p-2}\pmod{p}.$$
يولد تسلسل فيبوناتشي حتى \(F_{90}\). ولكل \(k=2,3,\dots,90\) تحسب التنفيذات القيمة \(C(F_k)\bmod p\) ثم تجمعها modulo \(p\):
$$\sum_{k=2}^{90} C(F_k)\pmod{p}.$$
الحدود مستقلة بعضها عن بعض، ولذلك تستطيع نسخة C++ حسابها بالتوازي، بينما تنفذ نسختا Python و Java العمليات نفسها على التوالي.
بما ان \(2n=20 \lt p\)، فان مبرهنة Lucas هنا لا تحتاج الا الى رقم واحد في الاساس \(p\)، ولذلك يكون المعامل الثنائي المركزي هو المعامل العادي
$$\binom{20}{10}=184756.$$
اما حد التصحيح فيساوي
$$3n^2+2n+7=3\cdot 10^2+2\cdot 10+7=327.$$
ومن ثم
$$C(10)\equiv 8\cdot 184756-327=1477721\pmod{100000007},$$
وهو نفس المقدار الذي تستخدمه التنفيذات كقيمة تحقق.
تنفيذات C++ و Python و Java تجهز اولا الحسابات المعيارية بالنسبة الى العدد الاولي \(p=100000007\). وهي تحفظ جداءات عامليات عند حدود كتل ثابتة، ولذلك عندما نحتاج الى \(n!\bmod p\) نبدأ من اقرب حد كتلي محفوظ ثم نضرب فقط الذيل القصير داخل تلك الكتلة. هذا يقلل تكلفة الحسابات المتكررة للمعاملات الثنائية الصغيرة.
بالنسبة الى الاحجام الكبيرة، يطبق التنفيذ مبرهنة Lucas على \(\binom{2n}{n}\)، ثم يحسب حد التصحيح \(3n^2+2n+7\) modulo \(p\)، ويجمع الحدين في الصيغة \(8\binom{2n}{n}-(3n^2+2n+7)\)، وبعد ذلك يجمع القيم الناتجة على \(F_2,F_3,\dots,F_{90}\).
نسخة C++ تحتوي ايضا على اختبارات ذاتية قبل المجموع النهائي: عد دقيق بطريقة مصفوفة الانتقال للوحات الصغيرة، ومقارنة للمعاملات الثنائية الصغيرة مع مثلث Pascal، والتحقق من القيم \(C(1)=4\) و \(C(2)=25\) و \(C(10)=1477721\). بهذه الطريقة يتم التأكد من ان النموذج الدقيق والصيغة المعيارية متفقان على كل الحالات المعايرة.
للوحة ذات الحجم \(m\)، يملك نموذج التحقق الدقيق \(4m\) حالة صف. بناء جميع التوافقات بين الصفوف يحتاج \(O(m)\) عملا لكل زوج من الحالات، ولذلك يكلف بناء الانتقالات \(O(m^3)\)، كما ان البرمجة الديناميكية عبر \(m\) صفوف تكون من الرتبة نفسها. وبما ان هذا الجزء يستخدم فقط لقيم تحقق صغيرة، فان كلفته العملية ضئيلة.
اما الحساب الرئيسي فيحتاج الى تمهيد وحيد بكلفة \(O(p)\) لبناء جداءات العامليات عند حدود الكتل، مع ذاكرة \(O(p/B)\) اذا كان حجم الكتلة هو \(B\). بعد ذلك، كل رقم في تفكيك Lucas يحتاج الى عدة ضربات ذيلية طول كل منها لا يتجاوز \(B\)، اضافة الى معكوس معياري كلفته \(O(\log p)\). لذلك فان حساب قيمة واحدة من \(C(n)\) يساوي
$$O\bigl(\log_p n\cdot (B+\log p)\bigr),$$
والمجموع النهائي على اعداد فيبوناتشي يكرر ذلك \(89\) مرة فقط.