The configuration is a chain of \(a+b\) colored units. Exactly \(a\) of them are type A and \(b\) are type B. Adjacent units share an ordered boundary pair of vertices, and every edge in the unit graph imposes the usual coloring rule that its endpoints must have different colors. For Project Euler 194 the parameters are \(a=25\), \(b=75\), and \(c=1984\), and the final answer is required modulo \(10^8\).
A direct count of whole-chain colorings would mix together 100 units and an enormous number of color assignments. The implementations avoid that by isolating one local counting problem: how many valid extensions does a single unit have when the two colors on its incoming boundary are already fixed and distinct?
Fix an ordered incoming boundary pair \((x,y)\) with \(x \ne y\). A unit contributes five unfixed vertices: two outgoing boundary vertices and three internal vertices. Because the constraints only say that adjacent vertices must have different colors, the actual names of \(x\) and \(y\) never matter; only the fact that they are distinct matters.
Both unit types start from a distinct ordered pair \((x,y)\) and end at another distinct ordered pair. The outgoing top boundary color must differ from the incoming top one, and the outgoing bottom boundary color must differ from the outgoing top one. The rest of the unit only sees the incoming pair through adjacency constraints.
This is the invariant that makes the chain multiplicative. When one unit is glued to the next, its right boundary becomes the next unit's left boundary, and that shared boundary is again just a distinct ordered pair. So every unit can be counted independently once the local extension count is known.
Let \(A(c)\) be the number of valid colorings of one type-A unit when the incoming boundary colors are fixed and distinct, and let \(B(c)\) be the analogous number for one type-B unit.
The two unit graphs differ in exactly one place. In type A, the outgoing lower boundary vertex is also adjacent to the incoming lower boundary vertex, so it is forbidden to reuse that color. Type B omits that edge, which is why \(B(c)\) is larger.
Since a unit has five unfixed vertices, these local counts are degree-5 coloring polynomials in \(c\). The implementations determine them exactly by brute force for \(c=2,3,4,5,6,7\):
$$\bigl(A(2),A(3),A(4),A(5),A(6),A(7)\bigr)=(0,4,62,372,1396,3980),$$
$$\bigl(B(2),B(3),B(4),B(5),B(6),B(7)\bigr)=(0,6,88,486,1728,4750).$$
Six exact values are enough to recover a degree-5 polynomial uniquely, so Newton forward interpolation gives the closed formulas used implicitly by the implementations:
$$A(c)=c^5-9c^4+34c^3-69c^2+77c-38,$$
$$B(c)=c^5-8c^4+27c^3-50c^2+52c-24=(c-2)^3(c^2-2c+3).$$
Take three colors \(\{x,y,z\}\) and fix the incoming boundary as \((x,y)\). A complete enumeration of one unit gives
$$A(3)=4,\qquad B(3)=6.$$
The difference is already visible at this smallest nontrivial palette size. Type B has two extra extensions because its outgoing lower boundary is allowed to reuse the color \(y\); type A forbids exactly those colorings through its extra lower edge. This tiny example captures the only structural distinction between the two building blocks.
Once the local counts are known, the full answer factorizes. First choose which of the \(a+b\) positions are occupied by type-A units. That contributes
$$\binom{a+b}{a}.$$
Then choose the ordered color pair on the very first boundary. Because the two colors must be distinct, this contributes
$$c(c-1).$$
Every type-A unit contributes a factor \(A(c)\), every type-B unit contributes a factor \(B(c)\), and the location of the unit does not matter because every interface is just a distinct ordered pair and the color names are symmetric. Therefore
$$\boxed{N(a,b,c)=\binom{a+b}{a}\,c(c-1)\,A(c)^a B(c)^b.}$$
For the Euler instance \((a,b,c)=(25,75,1984)\), that exact integer is finally reduced modulo \(10^8\).
The C++, Python, and Java implementations begin by fixing two distinct incoming boundary colors and brute-forcing the five remaining vertices for \(c=2,\dots,7\). That produces the six exact values of \(A(c)\) and \(B(c)\) listed above. The C++ implementation also checks the interpolated values against fresh brute-force counts for a few additional small palette sizes.
Instead of hard-coding symbolic algebra, the implementations evaluate the degree-5 polynomials through Newton forward differences. If \(n=c-2\), then
$$A(c)=\sum_{k=0}^{5}\Delta^kA(2)\binom{n}{k},\qquad B(c)=\sum_{k=0}^{5}\Delta^kB(2)\binom{n}{k}.$$
For these two unit counts, the first entries of the forward-difference tables are
$$A:\ (0,4,54,198,264,120),\qquad B:\ (0,6,76,240,288,120).$$
Because the underlying functions really are degree-5 polynomials, this interpolation is exact rather than approximate.
After obtaining \(A(c)\) and \(B(c)\), the implementations compute \(\binom{a+b}{a}\), multiply by \(c(c-1)\), and raise the two local counts to the powers \(a\) and \(b\) with fast modular exponentiation. The final stage runs modulo \(10^8\), while the small checkpoint calculations may use exact integer arithmetic first and reduce only at the end.
The local brute-force phase is constant-sized: it evaluates only six palette sizes, and each unit has only five unfixed vertices. Building the forward-difference table and evaluating the resulting polynomial are therefore \(O(1)\).
For parameterized inputs, forming \(\binom{a+b}{a}\) by multiplicative accumulation costs \(O(\min(a,b))\) arithmetic steps, and the two modular powers cost \(O(\log a+\log b)\). Extra memory usage is \(O(1)\) beyond a few fixed tables of sample values and differences.
Die gesuchte Konfiguration ist eine Kette aus \(a+b\) gefärbten Bausteinen. Genau \(a\) davon sind vom Typ A und \(b\) vom Typ B. Benachbarte Bausteine teilen sich ein geordnetes Randpaar von Knoten, und jede Kante im zugrunde liegenden Graphen verlangt verschiedene Farben an ihren Endpunkten. Für Project Euler 194 gilt \(a=25\), \(b=75\) und \(c=1984\); das Ergebnis wird modulo \(10^8\) gesucht.
Ein direktes Zählen aller Gesamtfärbungen würde 100 Bausteine gleichzeitig behandeln und wäre unübersichtlich und groß. Die Implementierungen reduzieren deshalb alles auf ein lokales Problem: Wie viele gültige Erweiterungen besitzt genau ein Baustein, wenn die zwei Farben am eingehenden Rand bereits fest und verschieden sind?
Fixiere ein geordnetes eingehendes Randpaar \((x,y)\) mit \(x \ne y\). Ein einzelner Baustein fügt fünf noch ungefärbte Knoten hinzu: zwei ausgehende Randknoten und drei innere Knoten. Da die Bedingungen nur besagen, dass benachbarte Knoten verschieden gefärbt sein müssen, sind die konkreten Namen von \(x\) und \(y\) irrelevant; entscheidend ist nur, dass sie verschieden sind.
Beide Bausteintypen starten mit einem verschiedenen geordneten Paar \((x,y)\) und enden wieder mit einem verschiedenen geordneten Paar. Die ausgehende obere Randfarbe muss sich von der eingehenden oberen unterscheiden, und die ausgehende untere Randfarbe muss sich von der ausgehenden oberen unterscheiden. Alle übrigen Bedingungen sehen das eingehende Paar nur über Adjazenzen.
Genau diese Invariante macht die Kette multiplikativ. Wenn zwei Bausteine zusammengeklebt werden, wird der rechte Rand des ersten zum linken Rand des zweiten, und dieser gemeinsame Rand ist erneut einfach ein verschiedenes geordnetes Paar. Dadurch kann jeder Baustein unabhängig gezählt werden, sobald die lokale Erweiterungszahl bekannt ist.
Sei \(A(c)\) die Anzahl gültiger Färbungen eines einzelnen Typ-A-Bausteins bei festem, verschiedenem eingehendem Randpaar, und \(B(c)\) die entsprechende Zahl für Typ B.
Die beiden Bausteingraphen unterscheiden sich genau an einer Stelle. Bei Typ A ist der ausgehende untere Randknoten zusätzlich mit dem eingehenden unteren Randknoten verbunden und darf dessen Farbe daher nicht wiederverwenden. Diese Kante fehlt bei Typ B, deshalb ist \(B(c)\) größer.
Da ein Baustein fünf freie Knoten besitzt, sind diese lokalen Zählfunktionen Polynome vom Grad 5 in \(c\). Die Implementierungen bestimmen sie exakt durch Brute Force für \(c=2,3,4,5,6,7\):
$$\bigl(A(2),A(3),A(4),A(5),A(6),A(7)\bigr)=(0,4,62,372,1396,3980),$$
$$\bigl(B(2),B(3),B(4),B(5),B(6),B(7)\bigr)=(0,6,88,486,1728,4750).$$
Sechs exakte Stützstellen reichen aus, um ein Polynom vom Grad 5 eindeutig zu bestimmen. Mit der Newtonschen Vorwärtsinterpolation erhält man deshalb exakt die Formeln, die in den Implementierungen implizit ausgewertet werden:
$$A(c)=c^5-9c^4+34c^3-69c^2+77c-38,$$
$$B(c)=c^5-8c^4+27c^3-50c^2+52c-24=(c-2)^3(c^2-2c+3).$$
Nimm drei Farben \(\{x,y,z\}\) und fixiere den eingehenden Rand als \((x,y)\). Eine vollständige Enumeration eines einzelnen Bausteins ergibt
$$A(3)=4,\qquad B(3)=6.$$
Der Unterschied ist bereits bei dieser kleinsten nichttrivialen Farbanzahl sichtbar. Typ B besitzt zwei zusätzliche Erweiterungen, weil der ausgehende untere Rand dort die Farbe \(y\) wiederverwenden darf. Typ A verbietet genau diese beiden Fälle über seine zusätzliche untere Kante. Dieses kleine Beispiel zeigt bereits den einzigen strukturellen Unterschied der beiden Bausteine.
Sobald die lokalen Zahlen bekannt sind, zerfällt die Gesamtlösung sauber in Faktoren. Zuerst wählt man, welche der \(a+b\) Positionen von Typ-A-Bausteinen besetzt werden. Das liefert
$$\binom{a+b}{a}.$$
Dann wählt man das geordnete Farbenpaar am allerersten Rand. Da die beiden Farben verschieden sein müssen, gibt das
$$c(c-1).$$
Jeder Typ-A-Baustein trägt dann einen Faktor \(A(c)\) bei, jeder Typ-B-Baustein einen Faktor \(B(c)\). Die Position spielt keine Rolle, weil jede Schnittstelle nur ein verschiedenes geordnetes Paar ist und die Farbnamen symmetrisch sind. Also gilt
$$\boxed{N(a,b,c)=\binom{a+b}{a}\,c(c-1)\,A(c)^a B(c)^b.}$$
Für die Euler-Parameter \((a,b,c)=(25,75,1984)\) wird diese exakte ganze Zahl am Ende modulo \(10^8\) reduziert.
Die Implementierungen in C++, Python und Java fixieren zunächst zwei verschiedene eingehende Randfarben und brute-forcen dann die fünf verbleibenden Knoten für \(c=2,\dots,7\). So entstehen die sechs exakten Werte von \(A(c)\) und \(B(c)\). Die C++-Implementierung prüft die interpolierten Werte zusätzlich noch gegen frische Brute-Force-Zählungen für einige weitere kleine Farbzahlen.
Statt symbolische Polynome fest zu verdrahten, werten die Implementierungen die Grad-5-Polynome über Newtonsche Vorwärtsdifferenzen aus. Mit \(n=c-2\) gilt
$$A(c)=\sum_{k=0}^{5}\Delta^kA(2)\binom{n}{k},\qquad B(c)=\sum_{k=0}^{5}\Delta^kB(2)\binom{n}{k}.$$
Für diese beiden Zählfunktionen lauten die ersten Einträge der Differenztabellen
$$A:\ (0,4,54,198,264,120),\qquad B:\ (0,6,76,240,288,120).$$
Weil die zugrunde liegenden Funktionen tatsächlich Polynome fünften Grades sind, ist diese Interpolation exakt und keine Näherung.
Nachdem \(A(c)\) und \(B(c)\) vorliegen, berechnen die Implementierungen \(\binom{a+b}{a}\), multiplizieren mit \(c(c-1)\) und heben die beiden lokalen Zahlen per schneller modularer Exponentiation in die Potenzen \(a\) und \(b\). Der Endschritt arbeitet modulo \(10^8\); kleine Kontrollrechnungen können vorher mit exakten Ganzzahlen ausgeführt werden.
Die lokale Brute-Force-Phase ist konstant groß: Es werden nur sechs Farbzahlen ausgewertet, und jeder Baustein besitzt nur fünf freie Knoten. Der Aufbau der Differenztabelle und die Polynom-Auswertung sind daher \(O(1)\).
Für parametrisierte Eingaben kostet die Bildung von \(\binom{a+b}{a}\) über eine multiplikative Schleife \(O(\min(a,b))\) Rechenschritte, und die beiden modularen Potenzen kosten \(O(\log a+\log b)\). Der zusätzliche Speicherbedarf ist \(O(1)\) abgesehen von wenigen festen Tabellen mit Beispielwerten und Differenzen.
Aranan yapı, \(a+b\) adet renkli birimden oluşan bir zincirdir. Bunların tam \(a\) tanesi A tipi, \(b\) tanesi B tipidir. Yan yana duran birimler, sıralı bir sınır düğüm çifti paylaşır ve birim grafındaki her kenar, uçlarındaki renklerin farklı olmasını zorunlu kılar. Project Euler 194 için parametreler \(a=25\), \(b=75\) ve \(c=1984\)'tür; sonuç \(10^8\) modunda istenir.
Bütün zinciri tek seferde saymaya çalışmak, 100 birimi ve çok büyük sayıda renk atamasını aynı anda takip etmek demektir. Uygulamalar bunun yerine tek bir yerel sayım problemini izole eder: Bir birimin giriş sınırındaki iki renk önceden sabit ve farklıysa, o birim kaç farklı şekilde tamamlanabilir?
\(x \ne y\) olacak şekilde sıralı bir giriş sınır çifti \((x,y)\) sabitleyelim. Tek bir birim, beş serbest düğüm içerir: iki çıkış sınır düğümü ve üç iç düğüm. Kısıtların tamamı yalnızca komşu düğümlerin farklı renk almasını söylediği için, \(x\) ve \(y\)'nin hangi renk isimleri olduğunun önemi yoktur; önemli olan tek şey bu iki rengin farklı olmasıdır.
Her iki birim türü de farklı bir sıralı çift \((x,y)\) ile başlar ve yine farklı bir sıralı çift ile biter. Çıkıştaki üst sınır rengi, girişteki üst sınır renginden farklı olmalıdır; çıkıştaki alt sınır rengi de çıkıştaki üst sınır renginden farklı olmalıdır. Birimin geri kalan kısmı giriş çiftini yalnızca komşuluk ilişkileri üzerinden görür.
Zinciri çarpımsal hale getiren temel invariants budur. Bir birimin sağ sınırı, bir sonraki birimin sol sınırı olduğunda, ortaya çıkan ortak sınır yine sadece farklı bir sıralı renkten ibarettir. Dolayısıyla yerel uzatma sayısı bilindiğinde her birim bağımsız biçimde sayılabilir.
Giriş sınırındaki iki renk sabit ve farklıyken, tek bir A tipi birimin geçerli boyamalarının sayısına \(A(c)\), tek bir B tipi birimin geçerli boyamalarının sayısına da \(B(c)\) diyelim.
İki birim grafı yalnızca tek bir yerde ayrılır. A tipinde, çıkıştaki alt sınır düğümü girişteki alt sınır düğümüne de komşudur; bu yüzden onun rengini yeniden kullanamaz. B tipinde bu kenar yoktur; dolayısıyla \(B(c)\), \(A(c)\)'den daha büyüktür.
Bir birimde beş serbest düğüm bulunduğu için bu yerel sayımlar \(c\)'ye göre derece 5 polinomlardır. Uygulamalar bunları \(c=2,3,4,5,6,7\) için brute force ile tam olarak bulur:
$$\bigl(A(2),A(3),A(4),A(5),A(6),A(7)\bigr)=(0,4,62,372,1396,3980),$$
$$\bigl(B(2),B(3),B(4),B(5),B(6),B(7)\bigr)=(0,6,88,486,1728,4750).$$
Derece 5 bir polinomu belirlemek için altı tam örnek nokta yeterlidir. Bu yüzden Newton ileri fark interpolasyonu, uygulamaların fiilen kullandığı kapalı biçimleri tam olarak geri verir:
$$A(c)=c^5-9c^4+34c^3-69c^2+77c-38,$$
$$B(c)=c^5-8c^4+27c^3-50c^2+52c-24=(c-2)^3(c^2-2c+3).$$
\(\{x,y,z\}\) olmak üzere üç renk alalım ve giriş sınırını \((x,y)\) olarak sabitleyelim. Tek bir birimin tam enumerasyonu şu sonucu verir:
$$A(3)=4,\qquad B(3)=6.$$
Fark, en küçük anlamlı palet boyutunda bile görünür. B tipinde iki ek uzatma vardır; çünkü çıkıştaki alt sınır, \(y\) rengini yeniden kullanabilir. A tipinde ise ek alt kenar tam olarak bu iki durumu yasaklar. Böylece iki yapı taşı arasındaki tek yapısal fark çok küçük bir örnekte açıkça görülür.
Yerel sayılar bilindikten sonra toplam sayı temiz biçimde çarpanlara ayrılır. Önce \(a+b\) konumun hangilerinin A tipi olacağını seçeriz. Bu
$$\binom{a+b}{a}$$
çarpanını verir. Sonra ilk sınırdaki sıralı renk çiftini seçeriz. İki renk farklı olmak zorunda olduğundan bunun katkısı
$$c(c-1)$$
olur. Her A tipi birim bir \(A(c)\) çarpanı, her B tipi birim bir \(B(c)\) çarpanı getirir. Birimin zincirdeki yeri önemli değildir; çünkü her arayüz yine sadece farklı bir sıralı renktir ve renk isimleri simetriktir. Sonuç olarak
$$\boxed{N(a,b,c)=\binom{a+b}{a}\,c(c-1)\,A(c)^a B(c)^b.}$$
Euler örneğinde \((a,b,c)=(25,75,1984)\) için elde edilen tam sayı en sonda \(10^8\) modunda alınır.
C++, Python ve Java uygulamaları önce girişteki iki farklı sınır rengini sabitler, ardından \(c=2,\dots,7\) için kalan beş düğümü brute force ile tarar. Böylece yukarıda verilen altı \(A(c)\) ve \(B(c)\) değeri elde edilir. C++ uygulaması ayrıca interpolasyon sonucunu birkaç ek küçük \(c\) değeri için yeniden brute force ile doğrular.
Uygulamalar sembolik polinom yazmak yerine Newton ileri fark biçimini kullanır. \(n=c-2\) olmak üzere
$$A(c)=\sum_{k=0}^{5}\Delta^kA(2)\binom{n}{k},\qquad B(c)=\sum_{k=0}^{5}\Delta^kB(2)\binom{n}{k}.$$
Bu iki yerel sayım için fark tablosunun ilk girişleri
$$A:\ (0,4,54,198,264,120),\qquad B:\ (0,6,76,240,288,120)$$
şeklindedir. Altta gerçekten derece 5 polinomlar bulunduğu için bu yöntem yaklaşık değil, tam sonuç üretir.
\(A(c)\) ve \(B(c)\) elde edildikten sonra uygulamalar \(\binom{a+b}{a}\) değerini hesaplar, \(c(c-1)\) ile çarpar ve iki yerel sayıyı hızlı modüler üs alma ile sırasıyla \(a\) ve \(b\) kuvvetlerine yükseltir. Son aşama \(10^8\) modunda çalışır; küçük doğrulama adımları ise gerekirse önce tam sayılarla yapılabilir.
Yerel brute force aşaması sabit boyutludur: yalnızca altı farklı palet boyutu değerlendirilir ve her birimde sadece beş serbest düğüm vardır. Bu nedenle fark tablosunu oluşturmak ve polinomu değerlendirmek \(O(1)\) maliyetlidir.
Parametreli girişler için \(\binom{a+b}{a}\) değerini çarpımsal birikimle hesaplamak \(O(\min(a,b))\) aritmetik adım gerektirir; iki modüler üs alma da \(O(\log a+\log b)\) sürer. Birkaç sabit örnek tablosu dışında ek bellek kullanımı \(O(1)\)'dir.
La configuración buscada es una cadena de \(a+b\) bloques coloreados. Exactamente \(a\) son de tipo A y \(b\) son de tipo B. Los bloques consecutivos comparten un par ordenado de vértices frontera, y cada arista del grafo del bloque exige que sus extremos tengan colores distintos. En el caso de Project Euler 194 se usan \(a=25\), \(b=75\) y \(c=1984\), y la respuesta final se pide módulo \(10^8\).
Contar directamente todas las coloraciones de la cadena completa mezclaría 100 bloques y una cantidad enorme de asignaciones de color. Las implementaciones evitan eso aislando un único problema local: cuántas extensiones válidas tiene un bloque cuando los dos colores de su frontera de entrada ya están fijados y son distintos.
Fijemos un par ordenado de entrada \((x,y)\) con \(x \ne y\). Un bloque añade cinco vértices no fijados: dos vértices de frontera de salida y tres vértices internos. Como todas las restricciones son simplemente “vértices adyacentes deben tener colores distintos”, los nombres concretos de \(x\) e \(y\) no importan; solo importa que sean diferentes.
Ambos tipos de bloque comienzan con un par ordenado distinto \((x,y)\) y terminan también con otro par ordenado distinto. El color de la frontera superior de salida debe diferir del color superior de entrada, y el color inferior de salida debe diferir del superior de salida. El resto del bloque solo ve el par de entrada a través de restricciones de adyacencia.
Esa es la invariante que vuelve multiplicativa a toda la cadena. Cuando se pegan dos bloques consecutivos, la frontera derecha del primero pasa a ser la frontera izquierda del segundo, y esa frontera compartida vuelve a ser simplemente un par ordenado de colores distintos. Por eso cada bloque puede contarse de manera independiente una vez conocido el número local de extensiones.
Sea \(A(c)\) el número de coloraciones válidas de un solo bloque de tipo A cuando el par de entrada está fijado y es distinto, y sea \(B(c)\) el conteo análogo para un bloque de tipo B.
Los dos grafos solo difieren en una arista. En el tipo A, el vértice inferior de salida también es adyacente al vértice inferior de entrada, así que no puede reutilizar ese color. El tipo B omite esa arista, y por eso \(B(c)\) es mayor.
Como un bloque tiene cinco vértices libres, estos conteos locales son polinomios de grado 5 en \(c\). Las implementaciones los determinan exactamente por fuerza bruta para \(c=2,3,4,5,6,7\):
$$\bigl(A(2),A(3),A(4),A(5),A(6),A(7)\bigr)=(0,4,62,372,1396,3980),$$
$$\bigl(B(2),B(3),B(4),B(5),B(6),B(7)\bigr)=(0,6,88,486,1728,4750).$$
Seis valores exactos bastan para reconstruir de forma única un polinomio de grado 5, así que la interpolación hacia adelante de Newton devuelve exactamente las fórmulas que luego evalúan las implementaciones:
$$A(c)=c^5-9c^4+34c^3-69c^2+77c-38,$$
$$B(c)=c^5-8c^4+27c^3-50c^2+52c-24=(c-2)^3(c^2-2c+3).$$
Tomemos tres colores \(\{x,y,z\}\) y fijemos la frontera de entrada como \((x,y)\). Una enumeración completa de un único bloque da
$$A(3)=4,\qquad B(3)=6.$$
La diferencia ya aparece con el menor tamaño de paleta no trivial. El tipo B tiene dos extensiones adicionales porque su frontera inferior de salida puede reutilizar el color \(y\); el tipo A prohíbe exactamente esas dos configuraciones mediante su arista inferior extra. Este ejemplo pequeño captura toda la diferencia estructural entre ambos bloques.
Una vez conocidos los conteos locales, el número total se factoriza limpiamente. Primero elegimos qué \(a\) de las \(a+b\) posiciones estarán ocupadas por bloques de tipo A. Eso aporta
$$\binom{a+b}{a}.$$
Después elegimos el par ordenado de colores en la primera frontera. Como los dos colores deben ser distintos, eso aporta
$$c(c-1).$$
Cada bloque de tipo A aporta un factor \(A(c)\), cada bloque de tipo B aporta un factor \(B(c)\), y la posición concreta no importa porque cada interfaz es simplemente un par ordenado distinto y los nombres de los colores son simétricos. Por tanto,
$$\boxed{N(a,b,c)=\binom{a+b}{a}\,c(c-1)\,A(c)^a B(c)^b.}$$
Para los parámetros del problema \((a,b,c)=(25,75,1984)\), ese entero exacto se reduce finalmente módulo \(10^8\).
Las implementaciones en C++, Python y Java fijan primero dos colores distintos en la frontera de entrada y luego recorren por fuerza bruta los cinco vértices restantes para \(c=2,\dots,7\). Así obtienen los seis valores exactos de \(A(c)\) y \(B(c)\) mostrados arriba. La implementación en C++ además contrasta la interpolación con nuevos recuentos por fuerza bruta para algunos valores pequeños adicionales.
En lugar de almacenar álgebra simbólica expandida, las implementaciones evalúan los polinomios de grado 5 mediante diferencias hacia adelante de Newton. Si \(n=c-2\), entonces
$$A(c)=\sum_{k=0}^{5}\Delta^kA(2)\binom{n}{k},\qquad B(c)=\sum_{k=0}^{5}\Delta^kB(2)\binom{n}{k}.$$
Para estos dos conteos, las primeras entradas de las tablas de diferencias son
$$A:\ (0,4,54,198,264,120),\qquad B:\ (0,6,76,240,288,120).$$
Como las funciones subyacentes son realmente polinomios de grado 5, esta interpolación es exacta y no aproximada.
Después de obtener \(A(c)\) y \(B(c)\), las implementaciones calculan \(\binom{a+b}{a}\), multiplican por \(c(c-1)\) y elevan los dos conteos locales a las potencias \(a\) y \(b\) con exponenciación modular rápida. La fase final trabaja módulo \(10^8\), aunque las comprobaciones pequeñas pueden hacerse primero con enteros exactos.
La fase local de fuerza bruta tiene tamaño constante: solo se evalúan seis tamaños de paleta y cada bloque tiene únicamente cinco vértices libres. Por ello, construir la tabla de diferencias y evaluar el polinomio cuesta \(O(1)\).
Para entradas parametrizadas, formar \(\binom{a+b}{a}\) por acumulación multiplicativa cuesta \(O(\min(a,b))\) operaciones aritméticas, y las dos potencias modulares cuestan \(O(\log a+\log b)\). El uso extra de memoria es \(O(1)\) aparte de unas pocas tablas fijas de muestras y diferencias.
题目要求统计一条由 \(a+b\) 个着色单元组成的链。其中特定地有 \(a\) 个 A 型单元、\(b\) 个 B 型单元。相邻单元共享一个有序的边界顶点对，而单元图中的每一条边都要求两端颜色不同。对 Project Euler 194 而言，参数是 \(a=25\)、\(b=75\)、\(c=1984\)，最终答案对 \(10^8\) 取模。
如果直接去数整条链的所有合法着色，就必须同时处理 100 个单元和极其庞大的颜色分配空间。实现真正做的事情是把问题压缩成一个局部计数：当某个单元左侧边界上的两种颜色已经固定且彼此不同的时候，这个单元本身有多少种合法延伸方式？
先固定一个有序输入边界 \((x,y)\)，其中 \(x \ne y\)。一个单元会新增五个尚未固定的顶点：两个输出边界顶点和三个内部顶点。因为所有约束都只是“相邻顶点颜色不同”，所以 \(x\) 和 \(y\) 具体是哪两种颜色并不重要，真正重要的只是它们互不相同。
两种单元都从一个互异的有序颜色对 \((x,y)\) 出发，并且结束时也得到另一个互异的有序颜色对。输出端上方顶点的颜色必须不同于输入端上方颜色，输出端下方顶点的颜色又必须不同于输出端上方颜色。除此之外，单元内部只会通过邻接关系“看到”这个输入边界对。
这就是整条链可以拆成乘法结构的关键不变量。当前单元的右边界会成为下一个单元的左边界，而这个共享边界仍然只是一个“互异的有序颜色对”。因此，只要局部延伸数已经知道，每个单元的贡献就可以独立计算，再乘起来即可。
记 \(A(c)\) 为：在输入边界颜色固定且不同的前提下，一个 A 型单元的合法着色数。类似地，记 \(B(c)\) 为一个 B 型单元的合法着色数。
这两类单元的图形只差一条边。A 型中，输出边界的下方顶点还与输入边界的下方顶点相邻，因此不能重用那个颜色；B 型没有这条边，所以 \(B(c)\) 必然比 \(A(c)\) 更大。
由于一个单元只有五个自由顶点，所以这两个局部计数都是关于 \(c\) 的五次多项式。实现先对 \(c=2,3,4,5,6,7\) 做精确暴力枚举：
$$\bigl(A(2),A(3),A(4),A(5),A(6),A(7)\bigr)=(0,4,62,372,1396,3980),$$
$$\bigl(B(2),B(3),B(4),B(5),B(6),B(7)\bigr)=(0,6,88,486,1728,4750).$$
六个精确点已经足以唯一确定一个五次多项式，因此用 Newton 前向插值就能把实现中实际使用的公式完全恢复出来：
$$A(c)=c^5-9c^4+34c^3-69c^2+77c-38,$$
$$B(c)=c^5-8c^4+27c^3-50c^2+52c-24=(c-2)^3(c^2-2c+3).$$
取三种颜色 \(\{x,y,z\}\)，并把输入边界固定为 \((x,y)\)。把一个单元的所有可能情况完整枚举后，可以得到
$$A(3)=4,\qquad B(3)=6.$$
差异在最小的非平凡调色板上就已经出现。B 型比 A 型多出的两种着色，恰好就是“输出下边界重用了颜色 \(y\)”的两种情况；A 型由于多了一条下方边，正好把这两种情况排除掉。这个小例子已经完整体现了 A 与 B 两种单元之间唯一真正的结构差别。
一旦局部计数确定，整体答案就会自然分解。首先，从 \(a+b\) 个位置中选出哪 \(a\) 个放置 A 型单元，这会贡献
$$\binom{a+b}{a}.$$
然后，为最左端的第一个边界选择一个有序颜色对。因为这两个颜色必须不同，所以这一步贡献
$$c(c-1).$$
接下来，每个 A 型单元贡献一个因子 \(A(c)\)，每个 B 型单元贡献一个因子 \(B(c)\)。单元放在哪个位置并不影响贡献，因为每个接口都只是“一个互异的有序颜色对”，而颜色名称本身是对称的。因此总公式为
$$\boxed{N(a,b,c)=\binom{a+b}{a}\,c(c-1)\,A(c)^a B(c)^b.}$$
对于题目的参数 \((a,b,c)=(25,75,1984)\)，最后只需把这个整数对 \(10^8\) 取模即可。
C++、Python 和 Java 三个实现都会先固定两个彼此不同的输入边界颜色，然后在 \(c=2,\dots,7\) 上对其余五个顶点做暴力枚举。这样就得到上面列出的六个 \(A(c)\) 和 \(B(c)\) 的精确值。C++ 实现还会把插值得到的结果与若干额外小 \(c\) 的重新暴力计数进行对照验证。
实现并没有把多项式手工展开后硬编码，而是使用 Newton 前向差分形式进行求值。令 \(n=c-2\)，则
$$A(c)=\sum_{k=0}^{5}\Delta^kA(2)\binom{n}{k},\qquad B(c)=\sum_{k=0}^{5}\Delta^kB(2)\binom{n}{k}.$$
对于这两个局部计数，差分表首列分别是
$$A:\ (0,4,54,198,264,120),\qquad B:\ (0,6,76,240,288,120).$$
由于底层函数本来就真的是五次多项式，所以这里的插值不是近似，而是精确求值。
得到 \(A(c)\) 与 \(B(c)\) 之后，实现再计算 \(\binom{a+b}{a}\)，乘上 \(c(c-1)\)，并用快速模幂把两个局部计数分别提升到 \(a\) 次方和 \(b\) 次方。最终阶段在模 \(10^8\) 下完成；一些小规模校验则可以先用精确整数做完再取模。
局部暴力阶段的规模是常数：只计算六个颜色数值，而且每个单元只有五个自由顶点。因此构造差分表和随后做多项式求值都是 \(O(1)\)。
如果把 \(a\) 和 \(b\) 看成一般参数，则通过乘法累积计算 \(\binom{a+b}{a}\) 需要 \(O(\min(a,b))\) 次算术操作，而两次模幂运算需要 \(O(\log a+\log b)\)。除几张固定大小的样本表和差分表之外，额外空间是 \(O(1)\)。
Искомая конструкция представляет собой цепочку из \(a+b\) раскрашенных блоков. Ровно \(a\) блоков имеют тип A, а \(b\) блоков имеют тип B. Соседние блоки делят упорядоченную пару граничных вершин, и каждое ребро графа блока требует, чтобы цвета на его концах были различны. В задаче Project Euler 194 заданы \(a=25\), \(b=75\) и \(c=1984\), а ответ нужен по модулю \(10^8\).
Прямой подсчет всех раскрасок всей цепочки сразу означал бы необходимость одновременно учитывать 100 блоков и огромное пространство цветовых назначений. Реализации вместо этого выделяют одну локальную задачу: сколько допустимых продолжений имеет один блок, если два цвета на его входной границе уже зафиксированы и различны?
Зафиксируем упорядоченную входную пару \((x,y)\), где \(x \ne y\). Один блок добавляет пять нефиксированных вершин: две вершины выходной границы и три внутренние вершины. Поскольку все ограничения имеют вид «соседние вершины должны иметь разные цвета», конкретные названия цветов \(x\) и \(y\) несущественны; важно лишь то, что они различны.
Оба типа блоков начинают с различной упорядоченной пары \((x,y)\) и заканчивают также различной упорядоченной парой. Цвет верхней выходной границы должен отличаться от цвета верхней входной границы, а цвет нижней выходной границы должен отличаться от цвета верхней выходной границы. Вся остальная часть блока «видит» входную пару только через отношения смежности.
Именно этот инвариант делает всю цепочку мультипликативной. Правая граница текущего блока становится левой границей следующего, и эта общая граница снова представляет собой просто различную упорядоченную пару. Поэтому, как только локальное число продолжений известно, вклад каждого блока можно считать независимо.
Обозначим через \(A(c)\) число допустимых раскрасок одного блока типа A при фиксированной различной входной паре, а через \(B(c)\) — аналогичное число для блока типа B.
Эти два графа отличаются ровно одним ребром. В типе A нижняя вершина выходной границы дополнительно смежна с нижней вершиной входной границы, поэтому она не может повторно использовать тот же цвет. В типе B этого ребра нет, и потому \(B(c)\) больше.
Поскольку в одном блоке пять свободных вершин, эти локальные функции являются полиномами пятой степени по \(c\). Реализации находят их точно полным перебором для \(c=2,3,4,5,6,7\):
$$\bigl(A(2),A(3),A(4),A(5),A(6),A(7)\bigr)=(0,4,62,372,1396,3980),$$
$$\bigl(B(2),B(3),B(4),B(5),B(6),B(7)\bigr)=(0,6,88,486,1728,4750).$$
Шести точных значений достаточно, чтобы однозначно восстановить полином степени 5, поэтому интерполяция Ньютона по прямым разностям дает именно те формулы, которые затем вычисляются в программах:
$$A(c)=c^5-9c^4+34c^3-69c^2+77c-38,$$
$$B(c)=c^5-8c^4+27c^3-50c^2+52c-24=(c-2)^3(c^2-2c+3).$$
Возьмем три цвета \(\{x,y,z\}\) и зафиксируем входную границу как \((x,y)\). Полный перебор раскрасок одного блока дает
$$A(3)=4,\qquad B(3)=6.$$
Разница видна уже при минимальном нетривиальном числе цветов. У типа B есть две дополнительные раскраски, потому что его нижняя выходная граница может повторно использовать цвет \(y\); у типа A ровно эти два случая запрещены дополнительным нижним ребром. Этот маленький пример полностью отражает единственное структурное различие двух строительных блоков.
Как только локальные числа известны, весь ответ раскладывается в произведение. Сначала нужно выбрать, какие из \(a+b\) позиций заняты блоками типа A. Это дает множитель
$$\binom{a+b}{a}.$$
Затем выбирается упорядоченная пара цветов на самой первой границе. Так как цвета должны быть различны, это дает
$$c(c-1).$$
Каждый блок типа A вносит множитель \(A(c)\), каждый блок типа B — множитель \(B(c)\). Конкретное место блока не важно, потому что каждый интерфейс представляет собой всего лишь различную упорядоченную пару, а названия цветов симметричны. Поэтому
$$\boxed{N(a,b,c)=\binom{a+b}{a}\,c(c-1)\,A(c)^a B(c)^b.}$$
Для параметров задачи \((a,b,c)=(25,75,1984)\) это точное целое число затем сокращается по модулю \(10^8\).
Реализации на C++, Python и Java сначала фиксируют две различные входные граничные краски, а затем полным перебором проходят по оставшимся пяти вершинам для \(c=2,\dots,7\). Так получаются шесть точных значений \(A(c)\) и \(B(c)\), приведенных выше. Реализация на C++ дополнительно сравнивает интерполированные значения с новыми brute-force подсчетами для нескольких других малых значений \(c\).
Вместо ручного раскрытия полиномов реализации используют форму Ньютона с прямыми разностями. Если положить \(n=c-2\), то
$$A(c)=\sum_{k=0}^{5}\Delta^kA(2)\binom{n}{k},\qquad B(c)=\sum_{k=0}^{5}\Delta^kB(2)\binom{n}{k}.$$
Для этих двух локальных функций первые элементы таблиц разностей равны
$$A:\ (0,4,54,198,264,120),\qquad B:\ (0,6,76,240,288,120).$$
Так как исходные функции действительно являются полиномами пятой степени, здесь выполняется точное вычисление, а не приближение.
После нахождения \(A(c)\) и \(B(c)\) реализации вычисляют \(\binom{a+b}{a}\), умножают на \(c(c-1)\) и возводят оба локальных значения в степени \(a\) и \(b\) с помощью быстрой модульной экспоненты. Финальный этап работает по модулю \(10^8\), хотя маленькие проверочные примеры могут сначала считаться в точной целочисленной арифметике.
Локальная brute-force фаза имеет постоянный размер: рассматриваются только шесть значений палитры, а в блоке всего пять свободных вершин. Поэтому построение таблицы разностей и вычисление полинома стоят \(O(1)\).
Для параметризованного ввода вычисление \(\binom{a+b}{a}\) мультипликативным накоплением требует \(O(\min(a,b))\) арифметических шагов, а две модульные степени требуют \(O(\log a+\log b)\). Дополнительная память равна \(O(1)\), не считая нескольких фиксированных таблиц со значениями и разностями.
البنية المطلوبة هي سلسلة من \(a+b\) وحدات ملوّنة. يوجد بالضبط \(a\) وحدة من النوع A و\(b\) وحدة من النوع B. الوحدات المتجاورة تشترك في زوج حدّي مرتب من الرؤوس، وكل ضلع في رسم الوحدة يفرض أن يكون لونا طرفيه مختلفين. في مسألة Project Euler 194 تكون القيم \(a=25\)، \(b=75\)، \(c=1984\)، ويُطلب الجواب بترديد \(10^8\).
العدّ المباشر لجميع تلوينات السلسلة كاملة يعني التعامل مع 100 وحدة دفعة واحدة ومع عدد هائل من الإسنادات اللونية. لذلك تختزل التطبيقات المسألة إلى سؤال محلي واحد: إذا كان لونا الحدّ الداخل لوحدة واحدة مثبتين ومختلفين، فكم عدد الطرق الصحيحة لإكمال تلوين هذه الوحدة؟
لنثبت زوجًا حدّيًا داخلاً مرتبًا \((x,y)\) بحيث \(x \ne y\). تضيف كل وحدة خمس رؤوس غير مثبتة: رأسي الحدّ الخارج وثلاثة رؤوس داخلية. وبما أن جميع القيود من النوع «الرأسان المتجاوران يجب أن يحملا لونين مختلفين»، فإن أسماء اللونين \(x\) و\(y\) لا تهم؛ المهم فقط أنهما مختلفان.
كل من النوعين يبدأ من زوج مرتب مختلف \((x,y)\) وينتهي أيضًا بزوج مرتب مختلف. يجب أن يختلف لون الرأس العلوي الخارج عن لون الرأس العلوي الداخل، ويجب أن يختلف لون الرأس السفلي الخارج عن لون الرأس العلوي الخارج. أما بقية الوحدة فلا ترى الزوج الداخل إلا عبر علاقات التجاور.
هذا هو الثابت الذي يجعل السلسلة كلها قابلة للتفكيك إلى حاصل ضرب. فعندما نصل وحدة بأخرى، يصبح الحد الأيمن للأولى هو الحد الأيسر للثانية، وهذا الحد المشترك ما زال مجرد زوج مرتب من لونين مختلفين. لذلك يمكن عدّ مساهمة كل وحدة على حدة بمجرد معرفة عدد التمديدات المحلية.
لنرمز بـ \(A(c)\) إلى عدد التلوينات الصحيحة لوحدة واحدة من النوع A عندما يكون الزوج الداخل مثبتًا ومختلفًا، ولنرمز بـ \(B(c)\) إلى العدد المناظر لوحدة من النوع B.
الفرق بين الرسمين يقع في ضلع واحد فقط. ففي النوع A يكون الرأس السفلي الخارج مجاورًا أيضًا للرأس السفلي الداخل، ولذلك لا يجوز له إعادة استعمال ذلك اللون. أما النوع B فلا يحتوي هذا الضلع، ولهذا يكون \(B(c)\) أكبر.
ولأن الوحدة تحتوي خمس رؤوس حرة، فإن هذين العددين المحليين هما كثيرتا حدود من الدرجة الخامسة في \(c\). وتحسب التطبيقات هاتين الدالتين بدقة بالعدّ الشامل من أجل \(c=2,3,4,5,6,7\):
$$\bigl(A(2),A(3),A(4),A(5),A(6),A(7)\bigr)=(0,4,62,372,1396,3980),$$
$$\bigl(B(2),B(3),B(4),B(5),B(6),B(7)\bigr)=(0,6,88,486,1728,4750).$$
ست نقاط دقيقة تكفي لتحديد كثيرة حدود من الدرجة الخامسة تحديدًا وحيدًا، ولذلك يعيد استيفاء نيوتن بالفروق الأمامية الصيغ المغلقة التي تستعملها التطبيقات فعليًا:
$$A(c)=c^5-9c^4+34c^3-69c^2+77c-38,$$
$$B(c)=c^5-8c^4+27c^3-50c^2+52c-24=(c-2)^3(c^2-2c+3).$$
خذ ثلاثة ألوان \(\{x,y,z\}\)، وثبت الحد الداخل على الصورة \((x,y)\). عند تعداد جميع إمكانات وحدة واحدة نحصل على
$$A(3)=4,\qquad B(3)=6.$$
يظهر الفرق منذ أصغر عدد غير تافه من الألوان. فالوحدة من النوع B تمتلك تمديدين إضافيين لأن الحد السفلي الخارج يمكنه إعادة استعمال اللون \(y\). أما النوع A فيمنع هاتين الحالتين بالضبط بسبب الضلع السفلي الإضافي. وهذا المثال الصغير يوضح الفارق البنيوي الوحيد بين الوحدتين.
بعد معرفة الأعداد المحلية ينفصل الجواب الكلي إلى عوامل واضحة. أولًا نختار أي المواضع من أصل \(a+b\) ستشغلها وحدات النوع A، وهذا يعطي
$$\binom{a+b}{a}.$$
ثم نختار الزوج اللوني المرتب على الحد الأول. وبما أن اللونين يجب أن يكونا مختلفين، فإن هذه الخطوة تعطي
$$c(c-1).$$
بعد ذلك تساهم كل وحدة من النوع A بعامل \(A(c)\)، وتساهم كل وحدة من النوع B بعامل \(B(c)\). ولا يهم موضع الوحدة داخل السلسلة، لأن كل واجهة ما هي إلا زوج مرتب مختلف، كما أن أسماء الألوان متناظرة. ومن ثم نحصل على
$$\boxed{N(a,b,c)=\binom{a+b}{a}\,c(c-1)\,A(c)^a B(c)^b.}$$
ولقِيَم أويلر \((a,b,c)=(25,75,1984)\) يُختزل هذا العدد الصحيح في النهاية بترديد \(10^8\).
تبدأ تطبيقات C++ وPython وJava بتثبيت لونين مختلفين على الحد الداخل، ثم تعدّ بالقوة الغاشمة الحالات الممكنة للرؤوس الخمسة الباقية من أجل \(c=2,\dots,7\). وهكذا تحصل على القيم الست الدقيقة لـ \(A(c)\) و\(B(c)\) المذكورة أعلاه. كما تتحقق نسخة C++ أيضًا من أن نتائج الاستيفاء تطابق عدًّا شاملاً جديدًا لبعض القيم الصغيرة الإضافية.
بدلًا من تخزين كثيرة الحدود موسعةً بصورة رمزية، تستعمل التطبيقات صيغة نيوتن بالفروق الأمامية. إذا وضعنا \(n=c-2\)، فإن
$$A(c)=\sum_{k=0}^{5}\Delta^kA(2)\binom{n}{k},\qquad B(c)=\sum_{k=0}^{5}\Delta^kB(2)\binom{n}{k}.$$
أما أوائل جداول الفروق لهاتين الدالتين المحليتين فهي
$$A:\ (0,4,54,198,264,120),\qquad B:\ (0,6,76,240,288,120).$$
وبما أن الدالتين الأصليتين كثيرتا حدود من الدرجة الخامسة فعلًا، فإن هذا الاستيفاء دقيق تمامًا وليس تقريبًا عدديًا.
بعد إيجاد \(A(c)\) و\(B(c)\)، تحسب التطبيقات \(\binom{a+b}{a}\)، وتضرب في \(c(c-1)\)، ثم ترفع القيمتين المحليتين إلى الأسين \(a\) و\(b\) باستخدام الأس السريع المعياري. تعمل المرحلة النهائية بترديد \(10^8\)، بينما يمكن أن تُجرى اختبارات التحقق الصغيرة أولًا بحسابات صحيحة دقيقة.
مرحلة العد المحلي بالقوة الغاشمة ذات حجم ثابت: فهي تقيم ستة أحجام فقط من لوحات الألوان، وكل وحدة تحتوي على خمسة رؤوس حرة ليس إلا. لذلك فإن بناء جدول الفروق وتقييم كثيرة الحدود كلاهما من رتبة \(O(1)\).
إذا اعتبرنا \(a\) و\(b\) مُدخلين عامّين، فإن تكوين \(\binom{a+b}{a}\) بالضرب التراكمي يحتاج إلى \(O(\min(a,b))\) خطوة حسابية، كما أن رفع القوتين المعياريتين يحتاج إلى \(O(\log a+\log b)\). أما الذاكرة الإضافية فهي \(O(1)\) باستثناء عدد قليل من الجداول الثابتة للقيم والعينات.