Let \(A(n)\) denote the number of valid colourings of a \(2\times n\) strip using four colours. The implementations work modulo
$$M=10^6+4321=1{,}000{,}004{,}321.$$
The key difficulty is that the legality of a new column is not determined only by the colours visible in that column. The algorithm therefore converts the strip into a finite-state process that remembers just enough local information to decide every future extension.
The counting problem is turned into a transfer-matrix problem. Each state describes the current colours on the top and bottom rows, how many more columns the current horizontal segments must continue, and whether the previous move was a special monochromatic vertical column.
After processing a column, the algorithm stores a state
$$s=(r_{\text{top}},c_{\text{top}},r_{\text{bot}},c_{\text{bot}},\nu),$$
where \(c_{\text{top}},c_{\text{bot}}\in\{1,2,3,4\}\) are the current colours, \(r_{\text{top}},r_{\text{bot}}\in\{0,1,2\}\) are the remaining numbers of columns that the current top and bottom horizontal segments must still occupy, and \(\nu\in\{0,1\}\) is a one-bit memory flag.
If a segment has total length \(1\), its stored remainder is \(0\); if its total length is \(2\), the stored remainder is \(1\); if its total length is \(3\), the stored remainder is \(2\). Thus only segment lengths \(1,2,3\) can occur.
The raw state space is bounded by
$$3\cdot 4\cdot 3\cdot 4\cdot 2=288,$$
and a reachability search later removes the impossible ones.
The first column can begin in two qualitatively different ways.
First, it may be a monochromatic vertical column. In that case top and bottom have the same colour, both stored remainders are \(0\), and the flag is set to \(\nu=1\). There are exactly \(4\) such initial states.
Second, the first column may use different top and bottom colours. Then one chooses ordered colours \(c_{\text{top}}\neq c_{\text{bot}}\) and independent segment lengths \(\ell_{\text{top}},\ell_{\text{bot}}\in\{1,2,3\}\). The stored remainders are \(\ell_{\text{top}}-1\) and \(\ell_{\text{bot}}-1\), and the flag is \(\nu=0\).
This gives the initial row vector \(v_1\), whose entries count all admissible descriptions of a strip of length \(1\).
Suppose the current state is \(s=(r_{\text{top}},c_{\text{top}},r_{\text{bot}},c_{\text{bot}},\nu)\).
If \(r_{\text{top}}>0\), then the next top cell is forced to keep colour \(c_{\text{top}}\), and the new remainder becomes \(r_{\text{top}}-1\). If \(r_{\text{top}}=0\), then a new top segment begins: choose a new colour different from \(c_{\text{top}}\), choose a new length \(\ell\in\{1,2,3\}\), and store the remainder \(\ell-1\). The bottom row behaves symmetrically.
After those local choices are made, the next column must satisfy two filters.
First, an ordinary next column must use different colours on the two rows:
$$c'_{\text{top}}\neq c'_{\text{bot}}.$$
Second, if both current remainders are \(0\) and the flag is \(\nu=0\), then both rows are not allowed to restart simultaneously into an ordinary split column. In other words, a synchronized restart of both rows is permitted only immediately after the special vertical situation.
There is also one extra branch. When both remainders are \(0\), the next column may be a monochromatic vertical column of colour \(v\), provided
$$v\neq c_{\text{top}},\qquad v\neq c_{\text{bot}}.$$
This moves the automaton to the state \((0,v,0,v,1)\).
Starting from all initial states, a breadth-first search enumerates the reachable state set \(\mathcal S\). This is an exact pruning step: unreachable raw states never contribute and are discarded before any matrix algebra is done.
Now define the transfer matrix \(T\) by
$$T_{ij}=\#\{\text{legal one-column extensions from state }s_i\text{ to state }s_j\} \pmod M.$$
For this problem the entries are effectively \(0\) or \(1\), but writing them as counts keeps the formulation clean. If \(v_n\) is the row vector of counts after \(n\) columns, then
$$v_n=v_1T^{\,n-1} \pmod M.$$
Not every state after the \(n\)-th column corresponds to a complete strip of length \(n\). If a remainder is still positive, then some horizontal segment would need extra columns beyond the end of the strip.
Therefore the valid terminal set is
$$\mathcal T=\{\,s\in\mathcal S: r_{\text{top}}=0 \text{ and } r_{\text{bot}}=0\,\}.$$
The final answer is
$$A(n)=\sum_{s\in\mathcal T} v_n(s)\pmod M.$$
Because the target value uses \(n=10^{16}\), the power \(T^{n-1}\) is computed by binary exponentiation.
The implementations include the checkpoint \(A(2)=120\). This can be derived directly from the state model.
If the first column is monochromatic, there are \(4\) choices. The second column can then be another monochromatic vertical column in one of the \(3\) other colours, or an ordinary split column with two different colours chosen from the remaining \(3\) colours, which gives \(3\cdot 2=6\) choices. This contributes
$$4\cdot(3+6)=36.$$
If the first column is split with different top and bottom colours, there are \(12\) ordered colour pairs. Now inspect the possible initial segment lengths.
If the lengths are \((1,1)\), both rows end immediately. Since the flag is then \(0\), the second column cannot restart both rows into another split column, so it must be a monochromatic vertical column using one of the two unused colours. Contribution:
$$12\cdot 2=24.$$
If the lengths are \((2,1)\), the top row continues while the bottom row restarts, and the restarted bottom colour must differ from both the continuing top colour and the old bottom colour. That gives \(2\) choices, hence another \(24\). By symmetry, the pattern \((1,2)\) contributes another \(24\).
If the lengths are \((2,2)\), both rows simply continue and the strip ends exactly after the second column, so the contribution is \(12\).
Any pattern involving a segment of length \(3\) cannot finish within two columns, so it contributes \(0\). Altogether,
$$36+24+24+24+12=120.$$
The C++, Python, and Java implementations follow the same pipeline. They first enumerate all admissible first-column states, then run a reachability search to collect and sort the finite state set. After that, they build the transition matrix by explicitly generating every legal successor of every reachable state.
Once the matrix is ready, the implementation keeps a count vector for the current strip length and raises the matrix to the needed power with exponentiation by squaring. Whenever a binary digit of \(n-1\) is \(1\), the vector is multiplied by the current matrix power. At the end, only states with both remainders equal to \(0\) are summed. One implementation also includes small checkpoints such as \(A(2)=120\), \(A(5)=45876\), and \(A(100)=53275818\).
Let \(S=|\mathcal S|\). The reachability phase is \(O(S)\) up to a small constant branching factor, and the raw state space never exceeds \(288\) states. The dominant cost is matrix exponentiation: dense matrix multiplication is \(O(S^3)\), so the full power computation costs \(O(S^3\log n)\). The vector-matrix multiplications add \(O(S^2\log n)\), and the memory usage is \(O(S^2)\) for the matrix plus \(O(S)\) for the state lists and vectors. The implementations skip zero entries in the inner loops, which improves constants without changing the asymptotic bound.
Sei \(A(n)\) die Anzahl gültiger Färbungen eines \(2\times n\)-Streifens mit vier Farben. Die Implementierungen rechnen modulo
$$M=10^6+4321=1{,}000{,}004{,}321.$$
Die Schwierigkeit besteht darin, dass die Gültigkeit der nächsten Spalte nicht nur von den sichtbaren Farben dieser Spalte abhängt. Deshalb wird das Problem in einen endlichen Zustandsautomaten umformuliert, der genau die nötige lokale Information speichert.
Die Zählung wird als Transfermatrix-Problem formuliert. Jeder Zustand beschreibt die aktuellen Farben oben und unten, wie viele Spalten die laufenden horizontalen Segmente noch weitergehen müssen, und ob der vorherige Schritt eine spezielle monochrome Vertikalspalte war.
Nach Verarbeitung einer Spalte speichert der Algorithmus den Zustand
$$s=(r_{\text{oben}},c_{\text{oben}},r_{\text{unten}},c_{\text{unten}},\nu),$$
wobei \(c_{\text{oben}},c_{\text{unten}}\in\{1,2,3,4\}\) die aktuellen Farben sind, \(r_{\text{oben}},r_{\text{unten}}\in\{0,1,2\}\) die Anzahl noch ausstehender Spalten der aktuellen horizontalen Segmente angeben und \(\nu\in\{0,1\}\) ein Ein-Bit-Gedächtnis ist.
Hat ein Segment Gesamtlänge \(1\), so ist sein gespeicherter Rest \(0\); bei Gesamtlänge \(2\) ist er \(1\); bei Gesamtlänge \(3\) ist er \(2\). Damit können nur Segmentlängen \(1,2,3\) auftreten.
Der rohe Zustandsraum ist nach oben beschränkt durch
$$3\cdot 4\cdot 3\cdot 4\cdot 2=288,$$
und eine Erreichbarkeitssuche entfernt später alle unmöglichen Zustände.
Die erste Spalte kann auf zwei grundsätzlich verschiedene Arten beginnen.
Erstens kann sie eine monochrome Vertikalspalte sein. Dann haben obere und untere Zelle dieselbe Farbe, beide gespeicherten Reste sind \(0\), und das Flag wird auf \(\nu=1\) gesetzt. Davon gibt es genau \(4\) Anfangszustände.
Zweitens kann die erste Spalte oben und unten verschiedene Farben haben. Dann wählt man geordnete Farben \(c_{\text{oben}}\neq c_{\text{unten}}\) sowie unabhängig Segmentlängen \(\ell_{\text{oben}},\ell_{\text{unten}}\in\{1,2,3\}\). Gespeichert werden die Reste \(\ell_{\text{oben}}-1\) und \(\ell_{\text{unten}}-1\), das Flag ist \(\nu=0\).
So entsteht der Anfangsvektor \(v_1\), dessen Einträge alle zulässigen Beschreibungen eines Streifens der Länge \(1\) zählen.
Sei der aktuelle Zustand \(s=(r_{\text{oben}},c_{\text{oben}},r_{\text{unten}},c_{\text{unten}},\nu)\).
Falls \(r_{\text{oben}}>0\), muss die nächste obere Zelle die Farbe \(c_{\text{oben}}\) behalten, und der neue Rest ist \(r_{\text{oben}}-1\). Falls \(r_{\text{oben}}=0\), beginnt ein neues oberes Segment: Man wählt eine neue Farbe ungleich \(c_{\text{oben}}\), eine neue Länge \(\ell\in\{1,2,3\}\) und speichert \(\ell-1\). Unten geschieht exakt das Analoge.
Danach muss die nächste Spalte zwei Filter erfüllen.
Erstens muss eine gewöhnliche nächste Spalte oben und unten verschiedene Farben besitzen:
$$c'_{\text{oben}}\neq c'_{\text{unten}}.$$
Zweitens gilt: Wenn beide aktuellen Reste \(0\) sind und das Flag \(\nu=0\) ist, dürfen nicht beide Zeilen gleichzeitig in eine gewöhnliche geteilte Spalte neu starten. Ein synchroner Neustart beider Zeilen ist also nur direkt nach der speziellen Vertikalsituation erlaubt.
Zusätzlich gibt es einen Sonderzweig. Wenn beide Reste \(0\) sind, darf die nächste Spalte eine monochrome Vertikalspalte der Farbe \(v\) sein, sofern
$$v\neq c_{\text{oben}},\qquad v\neq c_{\text{unten}}.$$
Der Automat geht dann in den Zustand \((0,v,0,v,1)\) über.
Ausgehend von allen Anfangszuständen enumeriert eine Breitensuche die erreichbare Zustandsmenge \(\mathcal S\). Das ist eine exakte Bereinigung: Unerreichbare rohe Zustände tragen nie etwas bei und werden vor der Matrixrechnung entfernt.
Nun definiert man die Transfermatrix \(T\) durch
$$T_{ij}=\#\{\text{legale Erweiterungen um eine Spalte von }s_i\text{ nach }s_j\} \pmod M.$$
Für dieses Problem sind die Einträge praktisch \(0\) oder \(1\), aber als Zählmatrix formuliert ist die Darstellung sauberer. Ist \(v_n\) der Zeilenvektor der Anzahlen nach \(n\) Spalten, dann gilt
$$v_n=v_1T^{\,n-1}\pmod M.$$
Nicht jeder Zustand nach der \(n\)-ten Spalte entspricht einem vollständig abgeschlossenen Streifen der Länge \(n\). Ist ein Rest noch positiv, dann würde ein horizontales Segment über das rechte Ende hinaus weitere Spalten verlangen.
Daher ist die gültige Endmenge
$$\mathcal T=\{\,s\in\mathcal S: r_{\text{oben}}=0 \text{ und } r_{\text{unten}}=0\,\}.$$
Die gesuchte Anzahl lautet also
$$A(n)=\sum_{s\in\mathcal T} v_n(s)\pmod M.$$
Da der Zielwert \(n=10^{16}\) verwendet, wird \(T^{n-1}\) per binärer Exponentiation berechnet.
Die Implementierungen enthalten den Kontrollwert \(A(2)=120\). Er folgt direkt aus dem Zustandsmodell.
Ist die erste Spalte monochrom, gibt es \(4\) Möglichkeiten. Die zweite Spalte kann dann wieder eine monochrome Vertikalspalte in einer der \(3\) anderen Farben sein, oder eine gewöhnliche geteilte Spalte mit zwei verschiedenen Farben aus den verbleibenden \(3\) Farben, also \(3\cdot 2=6\) Möglichkeiten. Beitrag:
$$4\cdot(3+6)=36.$$
Ist die erste Spalte geteilt, gibt es \(12\) geordnete Farbpaare. Nun betrachtet man die möglichen Anfangslängen der Segmente.
Bei Längen \((1,1)\) enden beide Zeilen sofort. Weil dann das Flag \(0\) ist, darf die zweite Spalte nicht beide Zeilen gleichzeitig in eine neue geteilte Spalte starten; also muss sie eine monochrome Vertikalspalte in einer der zwei unbenutzten Farben sein. Beitrag:
$$12\cdot 2=24.$$
Bei Längen \((2,1)\) läuft die obere Zeile weiter, während die untere neu startet. Die neue untere Farbe muss sowohl von der weiterlaufenden oberen Farbe als auch von der alten unteren Farbe verschieden sein. Das gibt \(2\) Möglichkeiten, also nochmals \(24\). Symmetrisch liefert \((1,2)\) weitere \(24\).
Bei \((2,2)\) laufen beide Zeilen einfach weiter, und der Streifen endet genau nach der zweiten Spalte. Beitrag: \(12\).
Jedes Längenmuster mit einer \(3\) kann in zwei Spalten nicht fertig werden und trägt daher \(0\) bei. Insgesamt also
$$36+24+24+24+12=120.$$
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst werden alle zulässigen Zustandsbeschreibungen für die erste Spalte erzeugt, dann wird mit einer Erreichbarkeitssuche die endliche Zustandsmenge gesammelt und sortiert. Anschließend wird die Übergangsmatrix aufgebaut, indem für jeden erreichbaren Zustand alle legalen Nachfolger explizit generiert werden.
Sobald die Matrix feststeht, hält die Implementierung einen Zählvektor für die aktuelle Streifenlänge und berechnet die benötigte Potenz der Matrix mit Exponentiation by Squaring. Immer wenn ein Binärbit von \(n-1\) gleich \(1\) ist, wird der Vektor mit der aktuellen Matrixpotenz multipliziert. Am Ende werden nur die Zustände mit beiden Resten gleich \(0\) aufsummiert. Eine Implementierung enthält außerdem kleine Kontrollwerte wie \(A(2)=120\), \(A(5)=45876\) und \(A(100)=53275818\).
Sei \(S=|\mathcal S|\). Die Erreichbarkeitsphase benötigt \(O(S)\) bis auf einen kleinen Verzweigungsfaktor, und der rohe Zustandsraum hat höchstens \(288\) Zustände. Die dominierenden Kosten entstehen durch die Matrixpotenzierung: Dichte Matrixmultiplikation kostet \(O(S^3)\), also insgesamt \(O(S^3\log n)\). Die Vektor-Matrix-Multiplikationen fügen \(O(S^2\log n)\) hinzu, und der Speicherbedarf beträgt \(O(S^2)\) für die Matrix plus \(O(S)\) für Zustandslisten und Vektoren. Die Implementierungen überspringen Nulleinträge in den inneren Schleifen; das verbessert die Konstanten, ändert aber nicht die asymptotische Ordnung.
\(A(n)\), dört renk kullanılarak boyanan \(2\times n\) şeridin geçerli renklendirme sayısı olsun. Uygulamalar sonucu
$$M=10^6+4321=1{,}000{,}004{,}321$$
modunda hesaplar. Zorluk şudur: bir sonraki sütunun geçerli olup olmadığı sadece o sütunda görünen renklere bağlı değildir. Bu yüzden çözüm, gelecekteki tüm uzatmaları belirlemek için yeterli olan en küçük yerel hafızayı tutan sonlu durum modeline geçer.
Sayım problemi bir transfer matrisi problemine dönüştürülür. Her durum, üst ve alt satırdaki güncel renkleri, mevcut yatay parçaların kaç sütun daha sürmesi gerektiğini ve önceki adımın özel tek renkli bir dikey sütun olup olmadığını saklar.
Bir sütun işlendiğinde algoritma şu durumu saklar:
$$s=(r_{\text{ust}},c_{\text{ust}},r_{\text{alt}},c_{\text{alt}},\nu),$$
burada \(c_{\text{ust}},c_{\text{alt}}\in\{1,2,3,4\}\) mevcut renklerdir, \(r_{\text{ust}},r_{\text{alt}}\in\{0,1,2\}\) üst ve alt yatay parçaların daha kaç sütun sürmek zorunda olduğunu gösterir ve \(\nu\in\{0,1\}\) tek bitlik bir hafıza işaretidir.
Bir parçanın toplam uzunluğu \(1\) ise saklanan kalan değer \(0\), uzunluğu \(2\) ise \(1\), uzunluğu \(3\) ise \(2\) olur. Böylece yalnızca \(1,2,3\) uzunluklu parçalar oluşabilir.
Ham durum uzayı en fazla
$$3\cdot 4\cdot 3\cdot 4\cdot 2=288$$
durum içerir; daha sonra erişilebilirlik taraması bunların imkansız olanlarını eler.
İlk sütun iki temel biçimde başlayabilir.
Birinci olasılık, tek renkli bir dikey sütundur. Bu durumda üst ve alt hücre aynı renge sahiptir, iki kalan değer de \(0\)'dır ve işaret \(\nu=1\) yapılır. Böyle tam olarak \(4\) başlangıç durumu vardır.
İkinci olasılık, üst ve altın farklı renklere sahip olmasıdır. O zaman sıralı olarak \(c_{\text{ust}}\neq c_{\text{alt}}\) renkleri ve bağımsız biçimde \(\ell_{\text{ust}},\ell_{\text{alt}}\in\{1,2,3\}\) parça uzunlukları seçilir. Saklanan kalanlar \(\ell_{\text{ust}}-1\) ve \(\ell_{\text{alt}}-1\), işaret ise \(\nu=0\) olur.
Böylece uzunluğu \(1\) olan şeritlerin tüm geçerli açıklamalarını sayan başlangıç satır vektörü \(v_1\) elde edilir.
Mevcut durum \(s=(r_{\text{ust}},c_{\text{ust}},r_{\text{alt}},c_{\text{alt}},\nu)\) olsun.
Eğer \(r_{\text{ust}}>0\) ise bir sonraki üst hücre zorunlu olarak \(c_{\text{ust}}\) renginde kalır ve yeni kalan \(r_{\text{ust}}-1\) olur. Eğer \(r_{\text{ust}}=0\) ise yeni bir üst parça başlar: \(c_{\text{ust}}\)'tan farklı yeni bir renk seçilir, \(\ell\in\{1,2,3\}\) uzunluğu seçilir ve kalan \(\ell-1\) olarak kaydedilir. Alt satır için kural simetriktir.
Bu yerel seçimlerden sonra bir sonraki sütun iki filtreyi geçmelidir.
İlk olarak, sıradan bir sonraki sütunda üst ve alt renkler farklı olmalıdır:
$$c'_{\text{ust}}\neq c'_{\text{alt}}.$$
İkinci olarak, iki mevcut kalan da \(0\) ve işaret \(\nu=0\) ise iki satırın aynı anda sıradan bir ayrık sütuna yeniden başlamasına izin verilmez. Yani iki satırın senkron yeniden başlaması sadece özel dikey durumun hemen ardından mümkündür.
Bunun dışında bir ek dal daha vardır. Her iki kalan da \(0\) iken, bir sonraki sütun renk \(v\) ile tek renkli dikey sütun olabilir; yeter ki
$$v\neq c_{\text{ust}},\qquad v\neq c_{\text{alt}}.$$
Bu seçim otomatı \((0,v,0,v,1)\) durumuna götürür.
Tüm başlangıç durumlarından başlayarak genişlik öncelikli arama erişilebilir durum kümesi \(\mathcal S\)'yi çıkarır. Bu tam bir budamadır: erişilemeyen ham durumlar hiçbir katkı yapmaz ve matris hesabından önce silinir.
Şimdi transfer matrisi \(T\) şu şekilde tanımlanır:
$$T_{ij}=\#\{\text{bir sütunluk geçerli uzatma ile }s_i\text{ durumundan }s_j\text{ durumuna geçiş}\}\pmod M.$$
Bu problemde girişler pratikte \(0\) ya da \(1\)'dir, ama sayım biçiminde yazmak daha temizdir. \(v_n\), \(n\) sütun sonrasındaki sayım satır vektörü ise
$$v_n=v_1T^{\,n-1}\pmod M$$
olur.
\(n\). sütundan sonraki her durum uzunluğu \(n\) olan tamamlanmış bir şeride karşılık gelmez. Eğer herhangi bir kalan pozitifse ilgili yatay parça şeridin sonunun ötesine taşmak için ek sütun ister.
Bu nedenle geçerli terminal küme
$$\mathcal T=\{\,s\in\mathcal S: r_{\text{ust}}=0 \text{ ve } r_{\text{alt}}=0\,\}$$
olur. Nihai sonuç
$$A(n)=\sum_{s\in\mathcal T} v_n(s)\pmod M$$
şeklindedir. Hedef değer \(n=10^{16}\) olduğu için \(T^{n-1}\) ikili üs alma ile hesaplanır.
Uygulamalarda \(A(2)=120\) kontrol değeri yer alır. Bu değer durum modelinden doğrudan çıkar.
Eğer ilk sütun tek renkliyse \(4\) seçim vardır. İkinci sütun ya kalan \(3\) renkten biriyle yine tek renkli dikey sütun olur ya da kalan \(3\) renk içinden seçilen iki farklı renkle sıradan ayrık sütun olur; bunun sayısı \(3\cdot 2=6\)'dır. Katkı:
$$4\cdot(3+6)=36.$$
Eğer ilk sütun ayrık ise sıralı \(12\) renk çifti vardır. Şimdi başlangıç parça uzunluklarını inceleyelim.
Uzunluklar \((1,1)\) ise iki satır da hemen biter. Bu durumda işaret \(0\) olduğu için ikinci sütun iki satırı birlikte yeni bir ayrık sütuna başlatamaz; dolayısıyla kullanılmayan iki renkten biriyle tek renkli dikey sütun olmak zorundadır. Katkı:
$$12\cdot 2=24.$$
Uzunluklar \((2,1)\) ise üst satır devam eder, alt satır yeniden başlar. Yeni alt renk hem devam eden üst renkten hem de eski alt renkten farklı olmalıdır. Bu \(2\) seçim verir; katkı yine \(24\)'tür. Simetriden \((1,2)\) deseni de \(24\) verir.
\((2,2)\) durumunda iki satır da sadece devam eder ve şerit tam ikinci sütunda biter. Katkı \(12\)'dir.
İçinde \(3\) geçen her uzunluk deseni iki sütunda tamamlanamaz, bu yüzden katkısı \(0\)'dır. Toplam:
$$36+24+24+24+12=120.$$
C++, Python ve Java uygulamaları aynı hattı izler. Önce ilk sütun için tüm geçerli durum açıklamaları üretilir, sonra erişilebilirlik aramasıyla sonlu durum kümesi toplanıp sıralanır. Ardından her erişilebilir durum için tüm geçerli ardıllar açıkça üretilerek geçiş matrisi kurulur.
Matris hazır olduktan sonra uygulama mevcut şerit uzunluğu için bir sayım vektörü tutar ve matrisi üs alma karesi yöntemiyle gerekli kuvvete yükseltir. \(n-1\)'in ikilik yazımında bir bit \(1\) ise vektör o anda eldeki matris kuvvetiyle çarpılır. Son aşamada yalnızca iki kalanı da \(0\) olan durumlar toplanır. Uygulamalardan biri ayrıca \(A(2)=120\), \(A(5)=45876\) ve \(A(100)=53275818\) gibi küçük kontrol değerleri de içerir.
\(S=|\mathcal S|\) olsun. Erişilebilirlik aşaması küçük bir dallanma sabiti dışında \(O(S)\) maliyetlidir ve ham durum uzayı hiçbir zaman \(288\)'i geçmez. Asıl maliyet matris üs almadadır: yoğun matris çarpımı \(O(S^3)\) olduğundan toplam maliyet \(O(S^3\log n)\) olur. Vektör-matris çarpımları buna \(O(S^2\log n)\) ekler. Bellek kullanımı matris için \(O(S^2)\), durum listeleri ve vektörler için \(O(S)\)'dir. İç döngülerde sıfır girişler atlandığından sabitler küçülür ama asimptotik mertebe değişmez.
Sea \(A(n)\) el número de coloraciones válidas de una tira \(2\times n\) usando cuatro colores. Las implementaciones trabajan módulo
$$M=10^6+4321=1{,}000{,}004{,}321.$$
La dificultad central es que la validez de la siguiente columna no depende solo de los colores visibles en esa columna. Por eso el método transforma la tira en un proceso de estados finitos que conserva exactamente la memoria local necesaria para extender la coloración.
El conteo se reformula como un problema de matriz de transferencia. Cada estado describe los colores actuales de la fila superior e inferior, cuántas columnas más deben continuar los segmentos horizontales actuales y si el paso anterior fue una columna vertical monocromática especial.
Después de procesar una columna, el algoritmo guarda el estado
$$s=(r_{\text{sup}},c_{\text{sup}},r_{\text{inf}},c_{\text{inf}},\nu),$$
donde \(c_{\text{sup}},c_{\text{inf}}\in\{1,2,3,4\}\) son los colores actuales, \(r_{\text{sup}},r_{\text{inf}}\in\{0,1,2\}\) son las columnas restantes que deben ocupar los segmentos horizontales actuales y \(\nu\in\{0,1\}\) es un bit de memoria.
Si un segmento tiene longitud total \(1\), su resto almacenado es \(0\); si su longitud total es \(2\), el resto es \(1\); si es \(3\), el resto es \(2\). Por tanto, solo aparecen segmentos de longitudes \(1,2,3\).
El espacio bruto de estados está acotado por
$$3\cdot 4\cdot 3\cdot 4\cdot 2=288,$$
y una búsqueda de alcanzabilidad elimina después los estados imposibles.
La primera columna puede comenzar de dos formas cualitativamente distintas.
La primera posibilidad es una columna vertical monocromática. En ese caso, arriba y abajo tienen el mismo color, ambos restos valen \(0\) y la bandera se fija en \(\nu=1\). Hay exactamente \(4\) estados iniciales de este tipo.
La segunda posibilidad es una columna con colores distintos arriba y abajo. Entonces se eligen colores ordenados \(c_{\text{sup}}\neq c_{\text{inf}}\) y longitudes independientes \(\ell_{\text{sup}},\ell_{\text{inf}}\in\{1,2,3\}\). Los restos almacenados son \(\ell_{\text{sup}}-1\) y \(\ell_{\text{inf}}-1\), y la bandera vale \(\nu=0\).
Así se obtiene el vector fila inicial \(v_1\), cuyas entradas cuentan todas las descripciones admisibles de una tira de longitud \(1\).
Supongamos que el estado actual es \(s=(r_{\text{sup}},c_{\text{sup}},r_{\text{inf}},c_{\text{inf}},\nu)\).
Si \(r_{\text{sup}}>0\), la siguiente celda superior está forzada a mantener el color \(c_{\text{sup}}\) y el nuevo resto pasa a ser \(r_{\text{sup}}-1\). Si \(r_{\text{sup}}=0\), comienza un nuevo segmento superior: se elige un color distinto de \(c_{\text{sup}}\), una longitud \(\ell\in\{1,2,3\}\) y se guarda el resto \(\ell-1\). La fila inferior se trata de forma simétrica.
Una vez hechas esas elecciones locales, la siguiente columna debe pasar dos filtros.
Primero, una columna ordinaria debe usar colores distintos en las dos filas:
$$c'_{\text{sup}}\neq c'_{\text{inf}}.$$
Segundo, si ambos restos actuales son \(0\) y la bandera es \(\nu=0\), no se permite que ambas filas reinicien simultáneamente hacia una columna ordinaria separada. Es decir, un reinicio sincronizado de ambas filas solo está permitido inmediatamente después de la situación vertical especial.
Además existe una rama adicional. Cuando ambos restos son \(0\), la siguiente columna puede ser una columna vertical monocromática de color \(v\), siempre que
$$v\neq c_{\text{sup}},\qquad v\neq c_{\text{inf}}.$$
Entonces el autómata pasa al estado \((0,v,0,v,1)\).
Partiendo de todos los estados iniciales, una búsqueda en anchura enumera el conjunto de estados alcanzables \(\mathcal S\). Es una poda exacta: los estados brutos no alcanzables nunca contribuyen y se eliminan antes de cualquier cálculo matricial.
Ahora se define la matriz de transferencia \(T\) mediante
$$T_{ij}=\#\{\text{extensiones legales de una columna desde }s_i\text{ hasta }s_j\}\pmod M.$$
En este problema las entradas son en la práctica \(0\) o \(1\), pero escribirlas como conteos deja la formulación más clara. Si \(v_n\) es el vector fila de conteos tras \(n\) columnas, entonces
$$v_n=v_1T^{\,n-1}\pmod M.$$
No todo estado alcanzado tras la columna \(n\) representa una tira completa de longitud \(n\). Si queda algún resto positivo, eso significa que algún segmento horizontal necesitaría columnas adicionales más allá del borde derecho.
Por lo tanto, el conjunto terminal válido es
$$\mathcal T=\{\,s\in\mathcal S: r_{\text{sup}}=0 \text{ y } r_{\text{inf}}=0\,\}.$$
La respuesta final es
$$A(n)=\sum_{s\in\mathcal T} v_n(s)\pmod M.$$
Como el valor objetivo usa \(n=10^{16}\), la potencia \(T^{n-1}\) se calcula con exponenciación binaria.
Las implementaciones incluyen la comprobación \(A(2)=120\). Se puede deducir directamente del modelo de estados.
Si la primera columna es monocromática, hay \(4\) opciones. La segunda columna puede ser otra columna vertical monocromática en uno de los \(3\) colores restantes, o una columna ordinaria separada con dos colores distintos elegidos entre esos \(3\) colores restantes, lo que da \(3\cdot 2=6\) opciones. Contribución:
$$4\cdot(3+6)=36.$$
Si la primera columna es separada, hay \(12\) pares ordenados de colores. Ahora se analizan las posibles longitudes iniciales de los segmentos.
Si las longitudes son \((1,1)\), ambas filas terminan inmediatamente. Como la bandera vale entonces \(0\), la segunda columna no puede reiniciar ambas filas a la vez hacia otra columna separada; por tanto debe ser una columna vertical monocromática usando uno de los dos colores no utilizados. Contribución:
$$12\cdot 2=24.$$
Si las longitudes son \((2,1)\), la fila superior continúa mientras la inferior reinicia. El nuevo color inferior debe ser distinto tanto del color superior que continúa como del antiguo color inferior. Eso da \(2\) opciones, es decir, otros \(24\). Por simetría, el patrón \((1,2)\) aporta otros \(24\).
Si las longitudes son \((2,2)\), ambas filas simplemente continúan y la tira termina exactamente al final de la segunda columna. La contribución es \(12\).
Cualquier patrón que incluya una longitud \(3\) no puede completarse en solo dos columnas, así que aporta \(0\). En total,
$$36+24+24+24+12=120.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero enumeran todos los estados admisibles de la primera columna, luego ejecutan una búsqueda de alcanzabilidad para reunir y ordenar el conjunto finito de estados. Después construyen la matriz de transición generando explícitamente todos los sucesores legales de cada estado alcanzable.
Una vez construida la matriz, la implementación mantiene un vector de conteos para la longitud actual de la tira y eleva la matriz a la potencia necesaria mediante exponenciación por cuadrados. Cada vez que un bit de \(n-1\) es igual a \(1\), el vector se multiplica por la potencia actual de la matriz. Al final solo se suman los estados con ambos restos iguales a \(0\). Una de las implementaciones también incluye comprobaciones pequeñas como \(A(2)=120\), \(A(5)=45876\) y \(A(100)=53275818\).
Sea \(S=|\mathcal S|\). La fase de alcanzabilidad cuesta \(O(S)\) salvo por un pequeño factor constante de ramificación, y el espacio bruto de estados nunca supera \(288\). El costo dominante es la exponenciación matricial: la multiplicación densa de matrices cuesta \(O(S^3)\), así que el cálculo completo requiere \(O(S^3\log n)\). Las multiplicaciones vector-matriz añaden \(O(S^2\log n)\), y la memoria usada es \(O(S^2)\) para la matriz más \(O(S)\) para listas de estados y vectores. Las implementaciones omiten entradas nulas en los bucles internos, lo que reduce las constantes sin alterar el orden asintótico.
设 \(A(n)\) 表示用四种颜色给一个 \(2\times n\) 条带进行合法染色的方案数。实现中的所有计算都在模数
$$M=10^6+4321=1{,}000{,}004{,}321$$
下进行。真正的难点在于：下一列是否合法，并不只取决于这一列当前看到的颜色，还取决于当前横向色段是否还必须继续。因此，解法把原问题改写为一个有限状态计数问题，只保留未来转移真正需要的局部信息。
整个计数过程可以写成一个转移矩阵问题。每个状态记录上行和下行的当前颜色、当前横向色段还需要继续多少列，以及前一步是否处于一种特殊的“同色竖列”情形。
处理完某一列后，算法保存状态
$$s=(r_{\text{top}},c_{\text{top}},r_{\text{bot}},c_{\text{bot}},\nu)$$
这里 \(c_{\text{top}},c_{\text{bot}}\in\{1,2,3,4\}\) 是当前上格和下格的颜色，\(r_{\text{top}},r_{\text{bot}}\in\{0,1,2\}\) 表示当前上方和下方横向色段在当前列之后还必须继续的列数，\(\nu\in\{0,1\}\) 是一位记忆标志。
如果某个色段总长度为 \(1\)，那么当前列之后的剩余长度就是 \(0\)；总长度为 \(2\) 时剩余长度为 \(1\)；总长度为 \(3\) 时剩余长度为 \(2\)。因此，这个模型只会出现长度为 \(1,2,3\) 的横向色段。
不考虑可达性时，原始状态总数上界为
$$3\cdot 4\cdot 3\cdot 4\cdot 2=288$$
后续会用一次可达性搜索把永远到不了的状态全部删掉。
第一列有两类本质不同的起始状态。
第一类是“同色竖列”：上格和下格颜色相同，两个剩余长度都为 \(0\)，并且把标志设为 \(\nu=1\)。四种颜色各对应一个这样的初始状态，所以共有 \(4\) 个。
第二类是“上下异色列”：选择一个有序颜色对 \(c_{\text{top}}\neq c_{\text{bot}}\)，再分别选择上方和下方横向色段的长度 \(\ell_{\text{top}},\ell_{\text{bot}}\in\{1,2,3\}\)。状态中保存的是剩余长度 \(\ell_{\text{top}}-1\) 和 \(\ell_{\text{bot}}-1\)，并令 \(\nu=0\)。
这样就得到长度为 \(1\) 时的初始行向量 \(v_1\)。它的每个分量表示一种合法首列描述出现的次数。
设当前状态为 \(s=(r_{\text{top}},c_{\text{top}},r_{\text{bot}},c_{\text{bot}},\nu)\)。
如果 \(r_{\text{top}}>0\)，说明上方当前色段还没结束，那么下一列上格颜色被强制保持为 \(c_{\text{top}}\)，新的剩余长度变成 \(r_{\text{top}}-1\)。如果 \(r_{\text{top}}=0\)，说明上方当前色段已经在这一列结束，下一列必须开启新的上方色段：选择一个不同于 \(c_{\text{top}}\) 的新颜色，再选择新色段长度 \(\ell\in\{1,2,3\}\)，并把新的剩余长度记为 \(\ell-1\)。下方规则完全对称。
完成这些局部选择之后，新的列还必须通过两道过滤。
第一，普通转移产生的新列必须满足上下颜色不同：
$$c'_{\text{top}}\neq c'_{\text{bot}}$$
第二，如果当前上下两个剩余长度都已经是 \(0\)，而且标志 \(\nu=0\)，那么不允许上下两行同时重新开始并形成一个普通的异色列。也就是说，只有紧接在特殊“同色竖列”之后，才允许上下两行同步重启。
另外还有一条额外分支。当上下两个剩余长度都为 \(0\) 时，下一列可以直接放成一个颜色为 \(v\) 的同色竖列，但要求
$$v\neq c_{\text{top}},\qquad v\neq c_{\text{bot}}$$
此时自动机跳转到状态 \((0,v,0,v,1)\)。
从所有初始状态出发，用广度优先搜索枚举所有可达状态，得到有限集合 \(\mathcal S\)。这一步不是近似，而是精确剪枝：任何不可达状态都不可能对答案产生贡献，因此可以在矩阵计算之前彻底丢弃。
然后定义转移矩阵 \(T\)：
$$T_{ij}=\#\{\text{从状态 }s_i\text{ 合法扩展一列后到达 }s_j\}\pmod M$$
在本题里，矩阵元素实际上几乎总是 \(0\) 或 \(1\)，但把它写成“方案数”形式更便于统一理解。若 \(v_n\) 表示长度为 \(n\) 时的计数行向量，则有
$$v_n=v_1T^{\,n-1}\pmod M$$
处理完第 \(n\) 列后，并不是所有状态都代表一个完整的 \(2\times n\) 条带。如果某一行的剩余长度仍然大于 \(0\)，那就意味着该行当前色段还想继续延伸到右边更多列，这显然超出了长度 \(n\) 的边界。
因此，合法终止状态集合必须是
$$\mathcal T=\{\,s\in\mathcal S: r_{\text{top}}=0,\ r_{\text{bot}}=0\,\}$$
最终答案就是
$$A(n)=\sum_{s\in\mathcal T} v_n(s)\pmod M$$
由于目标规模使用的是 \(n=10^{16}\)，所以 \(T^{n-1}\) 必须通过二进制快速幂来计算。
实现里包含一个小校验值 \(A(2)=120\)。这个数可以直接从状态模型中手工推出。
如果第一列是同色竖列，那么有 \(4\) 种颜色选择。第二列此时有两种类型：一种还是同色竖列，但颜色必须换成剩下的 \(3\) 种之一；另一种是普通异色列，此时上下颜色都必须不同于第一列的颜色，且上下彼此不同，所以有 \(3\cdot 2=6\) 种。于是这一类贡献为
$$4\cdot(3+6)=36$$
如果第一列是上下异色列，那么有 \(12\) 个有序颜色对。接下来按两行色段的初始长度分类。
当长度模式是 \((1,1)\) 时，上下两行都在第一列结束。由于此时标志是 \(0\)，第二列不能让上下两行同时重新开始形成普通异色列，因此第二列只能是同色竖列，而且颜色必须取前两种颜色之外的两种之一，所以贡献是
$$12\cdot 2=24$$
当长度模式是 \((2,1)\) 时，上方继续延伸，而下方重新开始。下方的新颜色必须既不同于继续中的上方颜色，也不同于原来的下方颜色，所以恰好有 \(2\) 种选择，总贡献为 \(24\)。由对称性，\((1,2)\) 也再贡献 \(24\)。
当长度模式是 \((2,2)\) 时，两行都只是继续一列，并且恰好在第二列结束，所以贡献是 \(12\)。
任何包含长度 \(3\) 的模式都不可能在两列之内结束，因此贡献为 \(0\)。总和就是
$$36+24+24+24+12=120$$
C++、Python 和 Java 三个实现遵循完全相同的流程。首先枚举所有合法的首列状态，然后运行一次可达性搜索，收集并排序有限状态集合。接着，对每个可达状态显式生成所有合法后继，从而建立转移矩阵。
矩阵建好之后，实现维护一个当前计数向量，并使用平方取幂法计算所需的矩阵幂。当 \(n-1\) 的二进制表示中某一位为 \(1\) 时，就把当前向量乘上对应的矩阵幂。最后只把上下剩余长度都等于 \(0\) 的状态求和。某个实现还包含若干小规模校验值，例如 \(A(2)=120\)、\(A(5)=45876\) 和 \(A(100)=53275818\)。
记 \(S=|\mathcal S|\)。可达性搜索阶段在分支数为常数的前提下可视为 \(O(S)\)，而原始状态空间上界只有 \(288\)。主成本来自矩阵快速幂：若按稠密矩阵相乘，每次乘法是 \(O(S^3)\)，因此总复杂度为 \(O(S^3\log n)\)。向量与矩阵的乘法额外贡献 \(O(S^2\log n)\)。空间方面，矩阵占 \(O(S^2)\)，状态数组和计数向量占 \(O(S)\)。实现中还会跳过内层循环里的零元素，从而降低常数因子，但不改变渐近阶。
Пусть \(A(n)\) обозначает число корректных раскрасок полосы \(2\times n\) четырьмя цветами. Во всех реализациях вычисления ведутся по модулю
$$M=10^6+4321=1{,}000{,}004{,}321.$$
Главная трудность состоит в том, что допустимость следующего столбца определяется не только теми цветами, которые видны в этом столбце. Нужно также помнить, обязаны ли текущие горизонтальные отрезки продолжаться дальше. Поэтому задача переводится в конечный автомат, который хранит только ту локальную информацию, которая действительно влияет на будущие переходы.
Подсчет переписывается как задача о матрице переходов. Каждое состояние описывает текущие цвета верхней и нижней строк, сколько столбцов еще должны продолжаться текущие горизонтальные отрезки, и был ли предыдущий шаг специальным одноцветным вертикальным столбцом.
После обработки очередного столбца алгоритм хранит состояние
$$s=(r_{\text{верх}},c_{\text{верх}},r_{\text{низ}},c_{\text{низ}},\nu),$$
где \(c_{\text{верх}},c_{\text{низ}}\in\{1,2,3,4\}\) - текущие цвета, \(r_{\text{верх}},r_{\text{низ}}\in\{0,1,2\}\) - число столбцов, на которое соответствующий горизонтальный отрезок обязан еще продолжиться, а \(\nu\in\{0,1\}\) - однобитный флаг памяти.
Если полный размер отрезка равен \(1\), то после текущего столбца его остаток равен \(0\); если размер \(2\), остаток равен \(1\); если размер \(3\), остаток равен \(2\). Значит, в модели встречаются только длины \(1,2,3\).
Грубая верхняя оценка на число состояний равна
$$3\cdot 4\cdot 3\cdot 4\cdot 2=288,$$
а позже поиск достижимости удаляет все невозможные состояния.
Первый столбец может начинаться двумя принципиально разными способами.
Первый вариант - одноцветный вертикальный столбец. Тогда верхняя и нижняя клетки имеют один и тот же цвет, оба остатка равны \(0\), а флаг устанавливается в \(\nu=1\). Таких начальных состояний ровно \(4\).
Второй вариант - столбец с разными цветами сверху и снизу. Тогда выбирается упорядоченная пара цветов \(c_{\text{верх}}\neq c_{\text{низ}}\), а также независимо длины \(\ell_{\text{верх}},\ell_{\text{низ}}\in\{1,2,3\}\). В состоянии сохраняются остатки \(\ell_{\text{верх}}-1\) и \(\ell_{\text{низ}}-1\), а флаг равен \(\nu=0\).
Так получается начальный строковый вектор \(v_1\), чьи компоненты считают все допустимые описания полосы длины \(1\).
Пусть текущее состояние равно \(s=(r_{\text{верх}},c_{\text{верх}},r_{\text{низ}},c_{\text{низ}},\nu)\).
Если \(r_{\text{верх}}>0\), то следующая верхняя клетка обязана сохранить цвет \(c_{\text{верх}}\), а новый остаток становится равным \(r_{\text{верх}}-1\). Если \(r_{\text{верх}}=0\), то начинается новый верхний отрезок: выбирается новый цвет, отличный от \(c_{\text{верх}}\), выбирается длина \(\ell\in\{1,2,3\}\), и в состоянии записывается остаток \(\ell-1\). Для нижней строки действует симметричное правило.
После этих локальных выборов новый столбец должен пройти два фильтра.
Во-первых, обычный новый столбец обязан иметь разные цвета сверху и снизу:
$$c'_{\text{верх}}\neq c'_{\text{низ}}.$$
Во-вторых, если оба текущих остатка равны \(0\) и флаг \(\nu=0\), то обе строки не могут одновременно перезапуститься в обычный разделенный столбец. Иначе говоря, синхронный перезапуск двух строк разрешен только сразу после специальной вертикальной ситуации.
Кроме того, существует дополнительная ветвь. Когда оба остатка равны \(0\), следующий столбец может быть одноцветным вертикальным столбцом цвета \(v\), если
$$v\neq c_{\text{верх}},\qquad v\neq c_{\text{низ}}.$$
Тогда автомат переходит в состояние \((0,v,0,v,1)\).
Начиная со всех начальных состояний, поиск в ширину перечисляет достижимое множество состояний \(\mathcal S\). Это точная отсечка: недостижимые состояния никогда не дают вклад и удаляются еще до матричной части решения.
Далее вводится матрица переходов \(T\):
$$T_{ij}=\#\{\text{допустимые продолжения на один столбец из }s_i\text{ в }s_j\}\pmod M.$$
В данной задаче элементы на практике почти всегда равны \(0\) или \(1\), но запись через количества делает формулу естественной. Если \(v_n\) - строковый вектор количеств после \(n\) столбцов, то
$$v_n=v_1T^{\,n-1}\pmod M.$$
Не каждое состояние после \(n\)-го столбца соответствует полностью завершенной полосе длины \(n\). Если хотя бы один остаток положителен, это означает, что некоторый горизонтальный отрезок хотел бы продолжиться за правую границу.
Поэтому множество допустимых терминальных состояний равно
$$\mathcal T=\{\,s\in\mathcal S: r_{\text{верх}}=0 \text{ и } r_{\text{низ}}=0\,\}.$$
Окончательный ответ имеет вид
$$A(n)=\sum_{s\in\mathcal T} v_n(s)\pmod M.$$
Поскольку целевое значение использует \(n=10^{16}\), степень \(T^{n-1}\) вычисляется бинарным возведением в степень.
В реализациях присутствует контрольное значение \(A(2)=120\). Его можно вывести непосредственно из модели состояний.
Если первый столбец одноцветный вертикальный, то есть \(4\) выбора цвета. Тогда второй столбец либо снова одноцветный вертикальный, причем цвет должен быть одним из оставшихся \(3\), либо обычный разделенный столбец с двумя различными цветами, выбранными из этих же \(3\) оставшихся цветов, что дает \(3\cdot 2=6\) вариантов. Вклад:
$$4\cdot(3+6)=36.$$
Если первый столбец разделенный, то существует \(12\) упорядоченных пар цветов. Теперь рассмотрим возможные начальные длины двух отрезков.
Для длин \((1,1)\) обе строки заканчиваются сразу. Так как флаг равен \(0\), второй столбец не может одновременно перезапустить обе строки в новый разделенный столбец; значит, он обязан быть одноцветным вертикальным столбцом, и цвет выбирается из двух еще не использованных цветов. Вклад:
$$12\cdot 2=24.$$
Для длин \((2,1)\) верхняя строка продолжается, а нижняя перезапускается. Новый нижний цвет должен отличаться и от продолжающегося верхнего цвета, и от прежнего нижнего цвета. Это дает \(2\) варианта, то есть еще \(24\). По симметрии случай \((1,2)\) также дает \(24\).
Для \((2,2)\) обе строки просто продолжаются и завершаются ровно на втором столбце. Вклад равен \(12\).
Любой шаблон, содержащий длину \(3\), не может закончиться за два столбца, поэтому его вклад равен \(0\). Итого
$$36+24+24+24+12=120.$$
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала перечисляются все допустимые состояния для первого столбца, затем с помощью поиска достижимости собирается и сортируется конечное множество состояний. После этого строится матрица переходов: для каждого достижимого состояния явно генерируются все допустимые последователи.
Когда матрица готова, реализация хранит вектор количеств для текущей длины полосы и вычисляет нужную степень матрицы методом быстрого возведения в степень. Всякий раз, когда очередной бит числа \(n-1\) равен \(1\), вектор умножается на текущую степень матрицы. В конце суммируются только те состояния, у которых оба остатка равны \(0\). В одной из реализаций также присутствуют небольшие проверки вроде \(A(2)=120\), \(A(5)=45876\) и \(A(100)=53275818\).
Пусть \(S=|\mathcal S|\). Этап поиска достижимости стоит \(O(S)\) с точностью до малого постоянного коэффициента ветвления, а грубый размер пространства состояний никогда не превышает \(288\). Основная стоимость исходит от матричного возведения в степень: плотное умножение матриц занимает \(O(S^3)\), поэтому полная сложность равна \(O(S^3\log n)\). Умножения вектора на матрицу добавляют \(O(S^2\log n)\). По памяти требуется \(O(S^2)\) для матрицы и \(O(S)\) для списков состояний и векторов. Во внутренних циклах нулевые элементы пропускаются, что уменьшает константы, но не меняет асимптотику.
لتكن \(A(n)\) هي عدد التلوينات الصحيحة لشريط بحجم \(2\times n\) باستخدام أربعة ألوان. جميع الحسابات في التنفيذات تتم بترديد
$$M=10^6+4321=1{,}000{,}004{,}321.$$
الصعوبة الحقيقية أن صلاحية العمود التالي لا تعتمد فقط على الألوان الظاهرة في ذلك العمود، بل تعتمد أيضا على ما إذا كانت المقاطع الأفقية الجارية ما زالت ملزمة بالاستمرار. لذلك تعيد الخوارزمية صياغة المسألة كعملية ذات حالات منتهية تحتفظ فقط بالذاكرة المحلية اللازمة لاتخاذ كل انتقال لاحق.
يمكن تحويل العد إلى مسألة مصفوفة انتقال. كل حالة تصف اللون الحالي في الصف العلوي والسفلي، وعدد الأعمدة الإضافية التي يجب أن يستمر فيها كل مقطع أفقي حالي، وهل كانت الخطوة السابقة عمودا رأسيا خاصا ذا لون واحد.
بعد معالجة عمود ما، تحفظ الخوارزمية الحالة
$$s=(r_{\text{top}},c_{\text{top}},r_{\text{bot}},c_{\text{bot}},\nu).$$
هنا \(c_{\text{top}},c_{\text{bot}}\in\{1,2,3,4\}\) هما اللونان الحاليان في الأعلى والأسفل، و\(r_{\text{top}},r_{\text{bot}}\in\{0,1,2\}\) هما عدد الأعمدة المتبقية التي يجب أن يشغلها كل مقطع أفقي جار، و\(\nu\in\{0,1\}\) علم ذاكرة من بت واحد.
إذا كان طول المقطع الكلي \(1\) فإن الباقي المخزن بعد العمود الحالي يساوي \(0\). وإذا كان الطول \(2\) فالباقي \(1\)، وإذا كان \(3\) فالباقي \(2\). لذلك لا تظهر إلا مقاطع أفقية بطول \(1\) أو \(2\) أو \(3\).
الحد الأعلى الخام لعدد الحالات هو
$$3\cdot 4\cdot 3\cdot 4\cdot 2=288,$$
ثم تقوم خطوة بحث عن القابلية للوصول بحذف الحالات التي لا يمكن الوصول إليها فعلا.
يمكن أن يبدأ العمود الأول بطريقتين مختلفتين جوهريا.
الطريقة الأولى أن يكون العمود كله بلون واحد رأسيا. عندها يكون اللون العلوي مساويا للسفلي، ويكون الباقيان مساويين للصفر، وتضبط العلامة على \(\nu=1\). يوجد بالضبط \(4\) حالات ابتدائية من هذا النوع.
الطريقة الثانية أن يكون اللون العلوي مختلفا عن السفلي. عندها نختار زوجا مرتبا من الألوان \(c_{\text{top}}\neq c_{\text{bot}}\)، ونختار بشكل مستقل طولي المقطعين الأفقيين \(\ell_{\text{top}},\ell_{\text{bot}}\in\{1,2,3\}\). الذي يخزن في الحالة هو \(\ell_{\text{top}}-1\) و\(\ell_{\text{bot}}-1\)، وتكون العلامة \(\nu=0\).
بهذا نحصل على متجه البداية \(v_1\) الذي تعد مركباته جميع الأوصاف المسموح بها لشريط طوله \(1\).
افترض أن الحالة الحالية هي \(s=(r_{\text{top}},c_{\text{top}},r_{\text{bot}},c_{\text{bot}},\nu)\).
إذا كان \(r_{\text{top}}>0\)، فهذا يعني أن المقطع العلوي الحالي لم ينته بعد، ولذلك يجب أن تحتفظ الخلية العلوية التالية باللون \(c_{\text{top}}\)، ويصبح الباقي الجديد \(r_{\text{top}}-1\). وإذا كان \(r_{\text{top}}=0\)، فهذا يعني أن المقطع العلوي انتهى في العمود الحالي، ولذلك يبدأ في العمود التالي مقطع علوي جديد: نختار لونا جديدا مختلفا عن \(c_{\text{top}}\)، ونختار طولا جديدا \(\ell\in\{1,2,3\}\)، ثم نخزن الباقي \(\ell-1\). والقاعدة نفسها تنطبق على الصف السفلي.
بعد هذه الاختيارات المحلية، يجب أن يمر العمود الجديد عبر مرشحين.
أولا، إذا كان الانتقال عاديا غير رأسي خاص، فيجب أن يكون اللونان العلوي والسفلي مختلفين:
$$c'_{\text{top}}\neq c'_{\text{bot}}.$$
ثانيا، إذا كان الباقيان الحاليان كلاهما \(0\) وكانت العلامة \(\nu=0\)، فلا يسمح بأن يعيد الصفان البدء معا في عمود عادي ذي لونين مختلفين. بعبارة أخرى، إعادة البدء المتزامنة للصفين مسموحة فقط مباشرة بعد الحالة الرأسية الخاصة.
وهناك أيضا فرع إضافي. عندما يكون الباقيان كلاهما \(0\)، يمكن أن يكون العمود التالي عمودا رأسيا بلون واحد \(v\)، بشرط أن
$$v\neq c_{\text{top}},\qquad v\neq c_{\text{bot}}.$$
وعندها ينتقل النظام إلى الحالة \((0,v,0,v,1)\).
انطلاقا من جميع الحالات الابتدائية، يجري بحث بعرض الشجرة لاستخراج مجموعة الحالات القابلة للوصول \(\mathcal S\). هذه ليست تقريبية بل خطوة تقليم دقيقة: أي حالة غير قابلة للوصول لا يمكن أن تسهم في الجواب، ولذلك تزال قبل أي جبر مصفوفي.
بعد ذلك تعرف مصفوفة الانتقال \(T\) كما يلي، حيث ترمز \(\mathcal E_{ij}\) إلى مجموعة الامتدادات القانونية بطول عمود واحد من \(s_i\) إلى \(s_j\):
$$T_{ij}=\#\mathcal E_{ij}\pmod M.$$
في هذه المسألة تكون العناصر عمليا \(0\) أو \(1\)، لكن كتابتها كأعداد طرق تجعل الصياغة أوضح. إذا كان \(v_n\) هو متجه العد بعد \(n\) أعمدة، فإن
$$v_n=v_1T^{\,n-1}\pmod M.$$
ليست كل حالة بعد العمود \(n\) تمثل شريطا مكتملا بطول \(n\). فإذا بقي أحد الباقيين موجبا، فهذا يعني أن هناك مقطعا أفقيا لا يزال يحتاج إلى أعمدة إضافية بعد نهاية الشريط.
لذلك تكون مجموعة النهايات الصحيحة هي
$$\mathcal T=\{\,s\in\mathcal S: r_{\text{top}}=0,\ r_{\text{bot}}=0\,\}.$$
ومن ثم يكون الجواب النهائي
$$A(n)=\sum_{s\in\mathcal T} v_n(s)\pmod M.$$
ولأن القيمة المطلوبة تستخدم \(n=10^{16}\)، فإن \(T^{n-1}\) يحسب بالرفع السريع للأس باستخدام التربيع.
تحتوي التنفيذات على قيمة فحص صغيرة هي \(A(2)=120\). ويمكن اشتقاقها مباشرة من نموذج الحالات.
إذا كان العمود الأول عمودا رأسيا بلون واحد، فلدينا \(4\) اختيارات. عندئذ يمكن أن يكون العمود الثاني أيضا عمودا رأسيا بلون واحد من بين الألوان الثلاثة الأخرى، أو عمودا عاديا منفصلا بلونين مختلفين مأخوذين من تلك الألوان الثلاثة نفسها، وعدد ذلك \(3\cdot 2=6\). إذن مساهمة هذه الحالة هي
$$4\cdot(3+6)=36.$$
أما إذا كان العمود الأول بلونين مختلفين في الأعلى والأسفل، فلدينا \(12\) زوجا مرتبا من الألوان. والآن ننظر إلى أطوال المقطعين الابتدائيين.
إذا كانت الأطوال \((1,1)\)، فإن الصفين ينتهيان مباشرة. وبما أن العلامة حينها تساوي \(0\)، فلا يجوز للعمود الثاني أن يعيد تشغيل الصفين معا في عمود عادي منفصل، ولذلك يجب أن يكون عمودا رأسيا بلون واحد من أحد اللونين غير المستخدمين. المساهمة هي
$$12\cdot 2=24.$$
إذا كانت الأطوال \((2,1)\)، فإن الصف العلوي يستمر بينما يعيد الصف السفلي البدء. ويجب أن يختلف اللون السفلي الجديد عن اللون العلوي المستمر وعن اللون السفلي القديم، وهذا يعطي \(2\) اختيارين، أي مساهمة مقدارها \(24\). وبالتناظر تعطي الحالة \((1,2)\) مساهمة أخرى مقدارها \(24\).
إذا كانت الأطوال \((2,2)\)، فإن الصفين يواصلان فقط، وينتهي الشريط تماما عند العمود الثاني، فتكون المساهمة \(12\).
وأي نمط يحتوي على طول \(3\) لا يمكن أن يكتمل في عمودين فقط، ولذلك تكون مساهمته \(0\). في النهاية نحصل على
$$36+24+24+24+12=120.$$
تتبع تنفيذات C++ وPython وJava الخطة نفسها تماما. فهي تبدأ بتعداد كل الحالات المسموح بها للعمود الأول، ثم تشغّل بحثا عن الوصول لتجميع مجموعة الحالات المنتهية وترتيبها. بعد ذلك تبني مصفوفة الانتقال عبر توليد جميع الخلفاء القانونيين لكل حالة قابلة للوصول.
بعد بناء المصفوفة، يحتفظ التنفيذ بمتجه للعدادات عند الطول الحالي للشريط، ثم يرفع المصفوفة إلى القوة المطلوبة باستعمال الرفع بالتربيع. وكلما كان أحد بتات \(n-1\) مساويا لـ \(1\)، يضرب المتجه في القوة الحالية للمصفوفة. وفي النهاية تجمع فقط الحالات التي يساوي فيها الباقيان الصفر. كما تتضمن إحدى التنفيذات قيما صغيرة للفحص مثل \(A(2)=120\) و\(A(5)=45876\) و\(A(100)=53275818\).
ليكن \(S=|\mathcal S|\). طور الوصول يكلف \(O(S)\) مع ثابت تفرع صغير، كما أن الفضاء الخام للحالات لا يتجاوز \(288\) حالة. الكلفة المسيطرة تأتي من رفع المصفوفة: ضرب المصفوفات الكثيفة يكلف \(O(S^3)\)، ومن ثم تكون الكلفة الكلية \(O(S^3\log n)\). أما ضربات المتجه بالمصفوفة فتضيف \(O(S^2\log n)\). من حيث الذاكرة، نحتاج إلى \(O(S^2)\) للمصفوفة و\(O(S)\) لقوائم الحالات والمتجهات. وتتجنب التنفيذات العناصر الصفرية داخل الحلقات الداخلية، مما يحسن الثوابت دون أن يغير الرتبة التقاربية.