Let \(G_{R,C}\) be the \(R\times C\) grid graph, and let \(F(R,C,q)\) denote its chromatic polynomial, meaning the number of proper colorings of the grid with \(q\) available colors. The target quantity is
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)\pmod{10^9+7}.$$
In the actual problem one has \(R=9\), \(C=10\), and a very large upper limit \(N=1112131415\). Brute-force coloring is hopeless, and even evaluating the chromatic polynomial separately for every \(x\le N\) is impossible. The successful strategy is therefore split into two layers: first compute the full polynomial \(F(R,C,q)\), then sum that polynomial over \(q=1,2,\dots,N\) by turning the result into a short list of power sums.
Write \(D=RC\). Since the grid has \(D\) vertices, \(F(R,C,q)\) is a polynomial in \(q\) of degree at most \(D\). The implementation constructs this polynomial by sweeping a narrow frontier through the grid and storing only the equality pattern among colors that are still relevant to future cells.
The grid is processed one cell at a time. At any moment, only a small set of boundary vertices can still interact with unprocessed cells; these vertices form the frontier. If \(w=\min(R,C)\), then the frontier never contains more than \(w\) vertices, so the exponential part of the search depends on the smaller dimension instead of the full \(RC\).
A frontier state does not remember actual color numbers. It remembers only which frontier positions are forced to carry the same color. In other words, a state is a set partition of the active frontier positions. Two labelings that differ only by renaming the blocks describe the same coloring constraints, so they are canonically relabeled and merged into a single state.
Whenever the sweep reaches a new adjacency, the chromatic polynomial satisfies the standard identity
$$P_{G+e}(q)=P_G(q)-P_{G/e}(q).$$
The first term counts all colorings before the new restriction is enforced. The second term removes the colorings in which the two endpoints receive the same color. Inside the frontier representation, “the endpoints receive the same color” means that their two frontier blocks are identified. Therefore every edge update contributes one positive copy of the current state and one negative copy of the state obtained by merging the two relevant blocks.
If the endpoints are already in the same block, the two terms cancel completely. That is exactly right: a partial coloring in which adjacent vertices are already equal cannot survive after the edge is inserted.
After a frontier vertex has received all edges that can still affect future cells, it may leave the frontier. At that point there are two cases.
If its color class appears nowhere else on the frontier, then that abstract class will never interact with the future again. It can therefore be assigned any of the \(q\) concrete colors, contributing a multiplicative factor \(q\).
If the same class still appears elsewhere on the frontier, then the choice of that concrete color is not free yet; the remaining representative still carries the constraint forward. In that case the state is simply shrunk and canonically relabeled, with no extra factor.
The process starts from the empty frontier with coefficient \(1\). As the sweep advances, it repeatedly performs three local actions: introduce a new frontier vertex, add the horizontal and vertical edges that now become known, and retire frontier vertices that can no longer interact with the unseen part of the grid.
Each state carries a polynomial in \(q\), and coefficients of identical canonical states are added modulo \(10^9+7\). After the entire grid has been swept and the last frontier vertices have been removed, only the empty state remains. Its coefficient array is exactly
$$F(R,C,q)=\sum_{d=0}^{D} a_d q^d.$$
Once the coefficients \(a_d\) are known, the required quantity becomes
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)=\sum_{d=0}^{D} a_d\sum_{x=1}^{N}x^d \pmod{10^9+7}.$$
So the remaining task is to evaluate the power sums \(\sum_{x=1}^{N}x^d\) for \(0\le d\le D\). For fixed \(d\), Faulhaber's theorem tells us that this is a polynomial in \(N\) of degree \(d+1\). Therefore it is enough to know its values at \(N=0,1,\dots,d+1\), compute those small prefix sums directly, and then recover the value at the huge target \(N\) by Lagrange interpolation modulo the prime \(10^9+7\).
The \(2\times 2\) grid is a 4-cycle, so its chromatic polynomial is
$$F(2,2,q)=q(q-1)^2(q-2)=q^4-4q^3+6q^2-3q.$$
This matches the small checkpoints used by the implementation:
$$F(2,2,3)=18,\qquad F(2,2,20)=130340.$$
The summation stage then becomes
$$S(2,2,N)=\sum_{x=1}^{N}\left(x^4-4x^3+6x^2-3x\right),$$
which is exactly a linear combination of the power sums for degrees \(1,2,3,4\). The full \(9\times 10\) problem uses the same idea, only with degree up to \(90\) instead of \(4\).
The C++, Python, and Java implementations follow the same computational pipeline. They first orient the sweep so that the frontier width is as small as possible. They then maintain a dictionary from canonical frontier partitions to coefficient arrays of length \(RC+1\). Introducing a new cell appends a new singleton block to the frontier, inserting a grid edge applies the positive-minus-merged transition dictated by deletion-contraction, and retiring a frontier vertex either multiplies the polynomial by \(q\) or simply removes that position, depending on whether its color class is still present elsewhere on the frontier.
After the empty-state coefficients \((a_0,a_1,\dots,a_D)\) have been obtained, the implementation computes the final answer degree by degree. For each \(d\), it builds the short table of prefix values of \(\sum_{x=1}^{n}x^d\), precomputes factorials and inverse factorials modulo the prime modulus, and evaluates the corresponding degree-\((d+1)\) polynomial at \(N\) using Lagrange interpolation. The last step is the modular accumulation of \(a_d\) times that power sum.
Let \(w=\min(R,C)\), let \(D=RC\), and let \(T_w\) denote the number of reachable canonical frontier states during the sweep. Every transition updates a coefficient array of length \(D+1\), so the dynamic program costs roughly \(O(RC\cdot T_w\cdot D)\) modular arithmetic, with the real constant determined by how many states are created and merged at each sweep position. Memory usage is \(O(T_w\cdot D)\).
The post-processing phase is much smaller. Evaluating all power sums by interpolation takes \(O(D^2)\) time and \(O(D)\) extra memory. Here \(D=90\), so this final stage is cheap; the true bottleneck is the frontier state space, not the interpolation.
Sei \(G_{R,C}\) der Gittergraph der Größe \(R\times C\), und sei \(F(R,C,q)\) sein chromatisches Polynom, also die Anzahl aller zulässigen Färbungen mit \(q\) Farben. Gesucht ist
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)\pmod{10^9+7}.$$
Im eigentlichen Problem gilt \(R=9\), \(C=10\) und \(N=1112131415\). Weder eine direkte Färbungszählung noch eine getrennte Auswertung für jedes \(x\le N\) ist praktikabel. Deshalb zerfällt die Lösung in zwei Teile: Zuerst wird das vollständige chromatische Polynom des Gitters bestimmt, danach wird die Summe über \(x=1,\dots,N\) als Linearkombination von Potenzsummen ausgewertet.
Setze \(D=RC\). Da der Graph \(D\) Knoten besitzt, ist \(F(R,C,q)\) ein Polynom in \(q\) vom Grad höchstens \(D\). Die Implementierung baut dieses Polynom durch einen Sweep mit schmaler Front auf und speichert dabei nur das Gleichheitsmuster der Farben an den aktuell noch relevanten Randknoten.
Das Gitter wird Zelle für Zelle verarbeitet. Zu jedem Zeitpunkt können nur wenige Randknoten noch mit dem unverarbeiteten Teil des Gitters wechselwirken; genau diese Knoten bilden die Front. Mit \(w=\min(R,C)\) enthält die Front niemals mehr als \(w\) Knoten. Der exponentielle Anteil hängt also von der kleineren Gitterdimension ab und nicht von allen \(RC\) Knoten zugleich.
Ein Frontzustand speichert keine konkreten Farbnummern. Er speichert nur, welche Frontpositionen dieselbe Farbe tragen müssen. Formal ist ein Zustand also eine Mengenpartition der aktiven Frontpositionen. Zwei Beschriftungen, die sich nur durch Umbenennung der Blöcke unterscheiden, beschreiben dieselbe Situation und werden kanonisch vereinheitlicht.
Immer wenn während des Sweeps eine neue Nachbarschaft feststeht, gilt für das chromatische Polynom
$$P_{G+e}(q)=P_G(q)-P_{G/e}(q).$$
Der erste Term zählt alle bisherigen Färbungen, der zweite entfernt genau jene Fälle, in denen die beiden Endpunkte dieselbe Farbe erhalten. In der Frontdarstellung bedeutet „gleiche Farbe“, dass die beiden betreffenden Blöcke verschmolzen werden. Ein Kantenupdate erzeugt daher eine positive Kopie des aktuellen Zustands und eine negative Kopie des Zustands mit identifizierten Blöcken.
Liegen beide Endpunkte bereits im selben Block, heben sich beide Beiträge vollständig auf. Genau das ist korrekt, denn eine Teilfärbung mit gleichen Farben an benachbarten Knoten ist nach dem Einfügen der Kante unzulässig.
Sobald ein Frontknoten alle Kanten erhalten hat, die den noch unverarbeiteten Teil betreffen können, darf er die Front verlassen. Dann gibt es zwei Fälle.
Kommt seine Farbklasse sonst nirgends mehr in der Front vor, dann wird diese abstrakte Klasse später nie wieder gesehen. Sie kann also mit beliebiger der \(q\) konkreten Farben belegt werden, was einen Faktor \(q\) liefert.
Kommt dieselbe Klasse noch an einer anderen Frontposition vor, dann ist die Farbwahl noch nicht frei; die verbliebene Repräsentation trägt die Information weiter. In diesem Fall wird der Zustand nur verkleinert und neu kanonisiert.
Begonnen wird mit leerer Front und Koeffizient \(1\). Der Sweep wiederholt dann drei lokale Operationen: einen neuen Frontknoten einführen, die nun bekannten horizontalen und vertikalen Kanten hinzufügen und nicht mehr benötigte Frontknoten entfernen.
Jeder Zustand trägt ein Polynom in \(q\), und identische kanonische Zustände werden modulo \(10^9+7\) zusammengefasst. Nach dem vollständigen Durchlauf des Gitters und dem Entfernen der letzten Frontknoten bleibt nur noch der leere Zustand übrig. Dessen Koeffizienten sind genau
$$F(R,C,q)=\sum_{d=0}^{D} a_d q^d.$$
Sind die Koeffizienten \(a_d\) bekannt, so wird die Zielgröße zu
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)=\sum_{d=0}^{D} a_d\sum_{x=1}^{N}x^d \pmod{10^9+7}.$$
Übrig bleibt also die Auswertung der Potenzsummen \(\sum_{x=1}^{N}x^d\) für \(0\le d\le D\). Nach dem Satz von Faulhaber ist dies für festes \(d\) ein Polynom in \(N\) vom Grad \(d+1\). Deshalb genügen die Werte an den kleinen Stellen \(N=0,1,\dots,d+1\): Diese Präfixsummen werden direkt berechnet und anschließend per Lagrange-Interpolation modulo der Primzahl \(10^9+7\) auf das große Ziel-\(N\) fortgesetzt.
Das \(2\times 2\)-Gitter ist ein 4-Zyklus. Sein chromatisches Polynom lautet daher
$$F(2,2,q)=q(q-1)^2(q-2)=q^4-4q^3+6q^2-3q.$$
Damit stimmen auch die kleinen Kontrollwerte der Implementierung überein:
$$F(2,2,3)=18,\qquad F(2,2,20)=130340.$$
Die Summationsphase lautet dann
$$S(2,2,N)=\sum_{x=1}^{N}\left(x^4-4x^3+6x^2-3x\right),$$
also genau eine Linearkombination der Potenzsummen in den Graden \(1,2,3,4\). Beim eigentlichen \(9\times 10\)-Problem geschieht dasselbe, nur bis zum Grad \(90\).
Die C++-, Python- und Java-Implementierungen folgen derselben Rechenkette. Zuerst wird der Sweep so ausgerichtet, dass die Front möglichst schmal bleibt. Danach verwalten die Programme eine Hashtabelle von kanonischen Frontpartitionen auf Koeffizientenfelder der Länge \(RC+1\). Beim Einführen einer neuen Zelle wird ein neuer Einzelblock an die Front angehängt, beim Einfügen einer Gitterkante wird die positive-minus-verschmolzene Transition aus der Lösch-Kontraktions-Formel ausgeführt, und beim Entfernen eines Frontknotens wird entweder mit \(q\) multipliziert oder nur die Position gestrichen, je nachdem ob seine Farbklasse noch an anderer Stelle vorkommt.
Sobald die Koeffizienten \((a_0,a_1,\dots,a_D)\) des leeren Zustands vorliegen, wird die Endsumme Grad für Grad berechnet. Für jedes \(d\) erzeugt die Implementierung die kurze Wertetabelle der Präfixsummen \(\sum_{x=1}^{n}x^d\), berechnet Fakultäten und inverse Fakultäten modulo der Primzahl und wertet das zugehörige Polynom vom Grad \(d+1\) per Lagrange-Interpolation an der großen Zahl \(N\) aus. Danach werden die Produkte \(a_d\) mal Potenzsumme modular aufsummiert.
Sei \(w=\min(R,C)\), \(D=RC\), und bezeichne \(T_w\) die Anzahl der tatsächlich erreichbaren kanonischen Frontzustände während des Sweeps. Jede Transition aktualisiert ein Koeffizientenfeld der Länge \(D+1\), daher liegt der Aufwand der dynamischen Programmierung grob bei \(O(RC\cdot T_w\cdot D)\) modularen Operationen. Der Speicherbedarf beträgt \(O(T_w\cdot D)\).
Die Nachbearbeitung ist deutlich kleiner. Alle Potenzsummen per Interpolation zu bestimmen kostet \(O(D^2)\) Zeit und \(O(D)\) Zusatzspeicher. Da hier \(D=90\) gilt, ist dieser Teil leichtgewichtig; der eigentliche Engpass ist der Zustandsraum der Front.
\(G_{R,C}\), \(R\times C\) boyutlu ızgara grafı olsun. \(F(R,C,q)\), bu grafın \(q\) renkle yapılan uygun boyamalarının sayısını veren kromatik polinomudur. Hesaplanması istenen büyüklük
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)\pmod{10^9+7}$$
ifadesidir. Gerçek soruda \(R=9\), \(C=10\) ve \(N=1112131415\) olduğundan, ne doğrudan boyama sayımı ne de her \(x\) için polinomu tek tek değerlendirmek mümkündür. Bu yüzden çözüm iki katmanlıdır: önce tüm kromatik polinom elde edilir, sonra bu polinom \(x=1,2,\dots,N\) üzerinde toplanırken işlem kuvvet toplamlarına ayrılır.
\(D=RC\) yazalım. Grafın \(D\) tepe noktası olduğundan \(F(R,C,q)\), derecesi en çok \(D\) olan bir \(q\) polinomudur. Uygulama bu polinomu, ızgara üzerinde dar bir aktif sınır ilerleterek ve yalnızca gelecekte hâlâ önemli olan renk eşitliği bilgisini saklayarak kurar.
Izgara hücre hücre işlenir. Her anda yalnızca işlenmemiş kısımla hâlâ etkileşebilecek birkaç sınır tepesi vardır; bunlar aktif sınırı oluşturur. \(w=\min(R,C)\) alınırsa aktif sınır hiçbir zaman \(w\) tepeyi aşmaz. Böylece üstel patlama tüm \(RC\) yerine küçük olan boyuta bağlı kalır.
Bir sınır durumu gerçek renk numaralarını tutmaz. Sadece hangi sınır konumlarının aynı rengi almak zorunda olduğunu tutar. Yani durum, aktif sınır konumlarının bir bölümlenmesidir. Etiket isimleri farklı olsa da aynı eşitlik düzenini anlatan durumlar kanonik biçime çevrilip tek duruma birleştirilir.
Tarama sırasında yeni bir komşuluk kesinleştiğinde kromatik polinom şu özdeşliği sağlar:
$$P_{G+e}(q)=P_G(q)-P_{G/e}(q).$$
İlk terim, yeni kısıt gelmeden önceki tüm boyamaları sayar. İkinci terim ise iki ucun aynı rengi aldığı durumları çıkarır. Sınır gösteriminde “iki uç aynı renk” demek, ilgili iki bloğun birleştirilmesi demektir. Bu yüzden her kenar güncellemesi mevcut durumun bir pozitif kopyasını ve iki bloğu birleştirilmiş durumun bir negatif kopyasını üretir.
Eğer iki uç zaten aynı bloktaysa iki katkı tamamen birbirini götürür. Bu tam olarak doğrudur; çünkü komşu iki tepe aynı renkteyse, o kısmi boyama kenar eklendikten sonra artık geçerli değildir.
Bir sınır tepesine, gelecekteki hücreleri etkileyebilecek tüm kenarlar bağlandıktan sonra o tepe sınırdan çıkarılabilir. Bu noktada iki olasılık vardır.
Eğer o tepenin renk sınıfı sınırın başka hiçbir yerinde görünmüyorsa, bu soyut renk sınıfı gelecekle artık etkileşmeyecektir. Dolayısıyla \(q\) somut renkten herhangi biri seçilebilir ve bu da çarpan olarak \(q\) getirir.
Eğer aynı sınıf sınırın başka bir konumunda hâlâ varsa, renk seçimi henüz serbest değildir; kalan temsilci bu bilgiyi taşımaya devam eder. O durumda yalnızca durum küçültülür ve yeniden kanonikleştirilir.
Süreç, katsayısı \(1\) olan boş sınır durumundan başlar. Tarama ilerledikçe üç yerel işlem tekrar eder: yeni bir sınır tepesi eklemek, artık bilinen yatay ve düşey kenarları koymak ve görülmemiş bölgeyle artık etkileşmeyecek tepeleri sınırdan çıkarmak.
Her durum bir \(q\) polinomu taşır ve aynı kanonik durumların katsayıları \(10^9+7\) modunda toplanır. Tüm ızgara işlendiğinde ve son sınır tepeleri de kaldırıldığında yalnızca boş durum kalır. O durumun katsayı dizisi tam olarak
$$F(R,C,q)=\sum_{d=0}^{D} a_d q^d$$
polinomudur.
\(a_d\) katsayıları bilindikten sonra hedef büyüklük
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)=\sum_{d=0}^{D} a_d\sum_{x=1}^{N}x^d \pmod{10^9+7}$$
şekline gelir. Geriye \(0\le d\le D\) için \(\sum_{x=1}^{N}x^d\) kuvvet toplamlarını hesaplamak kalır. Faulhaber teoremine göre sabit \(d\) için bu ifade, derecesi \(d+1\) olan bir \(N\) polinomudur. Bu yüzden \(N=0,1,\dots,d+1\) noktalarındaki küçük ön toplamları bilmek yeterlidir; sonra çok büyük hedef \(N\) değeri mod asal \(10^9+7\) üzerinde Lagrange enterpolasyonu ile elde edilir.
\(2\times 2\) ızgara bir 4-çevrimdir. Bu nedenle kromatik polinomu
$$F(2,2,q)=q(q-1)^2(q-2)=q^4-4q^3+6q^2-3q$$
olur. Bu, uygulamanın kullandığı küçük denetim değerleriyle uyumludur:
$$F(2,2,3)=18,\qquad F(2,2,20)=130340.$$
Toplama aşaması da
$$S(2,2,N)=\sum_{x=1}^{N}\left(x^4-4x^3+6x^2-3x\right)$$
şeklini alır. Yani işlem, dereceleri \(1,2,3,4\) olan kuvvet toplamlarının doğrusal birleşimidir. Asıl \(9\times 10\) örneğinde de aynı fikir kullanılır; yalnızca en yüksek derece \(90\) olur.
C++, Python ve Java uygulamaları aynı hesap zincirini izler. Önce tarama yönü, aktif sınır mümkün olduğunca dar olacak biçimde seçilir. Ardından kanonik sınır bölümlenmelerinden uzunluğu \(RC+1\) olan katsayı dizilerine giden bir sözlük tutulur. Yeni hücre eklenirken sınıra yeni bir tekil blok eklenir, bir ızgara kenarı eklenirken silme-büzmeden gelen pozitif eksi birleştirilmiş geçiş uygulanır, sınırdan bir tepe çıkarılırken de renk sınıfı başka yerde görünüyorsa sadece konum silinir, görünmüyorsa polinom \(q\) ile çarpılır.
Boş durumun katsayıları \((a_0,a_1,\dots,a_D)\) elde edildikten sonra son cevap derece derece hesaplanır. Her \(d\) için uygulama \(\sum_{x=1}^{n}x^d\) ön toplamlarının kısa tablosunu üretir, mod asal altında faktöriyel ve ters faktöriyel değerlerini hazırlar ve derece-\((d+1)\) polinomunu büyük \(N\) üzerinde Lagrange enterpolasyonu ile değerlendirir. Son adımda her \(a_d\), ilgili kuvvet toplamı ile çarpılıp mod altında toplanır.
\(w=\min(R,C)\), \(D=RC\) olsun ve tarama sırasında erişilebilen kanonik sınır durumu sayısını \(T_w\) ile gösterelim. Her geçiş uzunluğu \(D+1\) olan bir katsayı dizisini güncellediği için dinamik programın maliyeti yaklaşık \(O(RC\cdot T_w\cdot D)\) modüler aritmetik işlemdir. Bellek kullanımı \(O(T_w\cdot D)\) düzeyindedir.
Son işleme aşaması çok daha küçüktür. Tüm kuvvet toplamlarını enterpolasyonla hesaplamak \(O(D^2)\) zaman ve \(O(D)\) ek bellek ister. Burada \(D=90\) olduğundan bu bölüm hafiftir; asıl darboğaz frontier durum uzayıdır.
Sea \(G_{R,C}\) el grafo de la rejilla \(R\times C\), y sea \(F(R,C,q)\) su polinomio cromático, es decir, el número de coloraciones propias con \(q\) colores disponibles. La cantidad pedida es
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)\pmod{10^9+7}.$$
En el problema real se tiene \(R=9\), \(C=10\) y un límite enorme \(N=1112131415\). No es viable enumerar coloraciones, ni tampoco evaluar el polinomio por separado para cada \(x\le N\). Por eso la solución se divide en dos fases: primero se construye el polinomio cromático completo del tablero, y luego esa información se suma desde \(x=1\) hasta \(x=N\) reescribiendo el resultado como combinación lineal de sumas de potencias.
Escribamos \(D=RC\). Como la rejilla tiene \(D\) vértices, \(F(R,C,q)\) es un polinomio en \(q\) de grado a lo sumo \(D\). La implementación construye ese polinomio desplazando una frontera estrecha por la rejilla y almacenando solo el patrón de igualdades entre colores que todavía puede influir en las celdas futuras.
La rejilla se procesa celda por celda. En cada instante solo un pequeño conjunto de vértices de la frontera puede seguir interactuando con la parte no procesada; esos vértices forman la frontera activa. Si \(w=\min(R,C)\), entonces la frontera nunca tiene más de \(w\) vértices. Así, la parte exponencial depende de la dimensión menor y no de los \(RC\) vértices a la vez.
Un estado de frontera no guarda números reales de color. Solo guarda qué posiciones de la frontera están obligadas a compartir color. En otras palabras, el estado es una partición del conjunto de posiciones activas. Dos etiquetados que solo difieren por renombrar los bloques representan exactamente la misma situación y se reducen a una forma canónica común.
Cuando el barrido descubre una nueva adyacencia, el polinomio cromático satisface la identidad
$$P_{G+e}(q)=P_G(q)-P_{G/e}(q).$$
El primer término cuenta las coloraciones antes de imponer la nueva restricción. El segundo elimina aquellas en las que ambos extremos reciben el mismo color. En la representación por frontera, “recibir el mismo color” significa fusionar los dos bloques correspondientes. Por tanto, cada actualización por arista produce una copia positiva del estado actual y una copia negativa del estado donde esos dos bloques han sido identificados.
Si ambos extremos ya estaban en el mismo bloque, las dos contribuciones se cancelan por completo. Eso es exactamente lo correcto, porque una coloración parcial con vértices adyacentes iguales deja de ser válida cuando la arista existe.
Cuando un vértice de frontera ya ha recibido todas las aristas que podían conectarlo con la parte futura de la rejilla, puede salir de la frontera. Entonces hay dos posibilidades.
Si su clase de color no aparece en ningún otro lugar de la frontera, esa clase abstracta ya no volverá a intervenir. Por lo tanto puede asignarse cualquiera de los \(q\) colores concretos, lo que introduce un factor multiplicativo \(q\).
Si la misma clase sigue apareciendo en otra posición de la frontera, la elección de color todavía no es libre; el representante restante sigue transportando la restricción. En ese caso solo se reduce el estado y se vuelve a canonizar.
El proceso comienza con la frontera vacía y coeficiente \(1\). A medida que avanza el barrido se repiten tres operaciones locales: introducir un nuevo vértice en la frontera, añadir las aristas horizontales y verticales que ya han quedado determinadas y retirar los vértices de frontera que ya no pueden interactuar con la parte no vista.
Cada estado lleva asociado un polinomio en \(q\), y los coeficientes de los estados canónicos idénticos se suman módulo \(10^9+7\). Cuando toda la rejilla ha sido procesada y la frontera final desaparece, solo queda el estado vacío. Su arreglo de coeficientes es exactamente
$$F(R,C,q)=\sum_{d=0}^{D} a_d q^d.$$
Una vez conocidos los coeficientes \(a_d\), la cantidad buscada se transforma en
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)=\sum_{d=0}^{D} a_d\sum_{x=1}^{N}x^d \pmod{10^9+7}.$$
Así, todo se reduce a evaluar \(\sum_{x=1}^{N}x^d\) para \(0\le d\le D\). Para \(d\) fijo, el teorema de Faulhaber afirma que esa suma es un polinomio en \(N\) de grado \(d+1\). Por ello basta conocer sus valores en \(N=0,1,\dots,d+1\), calcular directamente esas sumas prefijas pequeñas y después recuperar el valor en el enorme \(N\) objetivo mediante interpolación de Lagrange módulo la prima \(10^9+7\).
La rejilla \(2\times 2\) es un ciclo de longitud 4, así que su polinomio cromático es
$$F(2,2,q)=q(q-1)^2(q-2)=q^4-4q^3+6q^2-3q.$$
Esto coincide con los pequeños puntos de control usados por la implementación:
$$F(2,2,3)=18,\qquad F(2,2,20)=130340.$$
La fase de suma se convierte entonces en
$$S(2,2,N)=\sum_{x=1}^{N}\left(x^4-4x^3+6x^2-3x\right),$$
que no es más que una combinación lineal de las sumas de potencias de grados \(1,2,3,4\). El caso completo \(9\times 10\) sigue exactamente el mismo patrón, solo que con grado máximo \(90\).
Las implementaciones en C++, Python y Java siguen la misma tubería matemática. Primero orientan el barrido para que la anchura de la frontera sea mínima. Después mantienen un diccionario que asocia cada partición canónica de la frontera con un arreglo de coeficientes de longitud \(RC+1\). Introducir una celda nueva añade un bloque singleton, insertar una arista de la rejilla aplica la transición positiva menos fusionada impuesta por borrado-contracción, y retirar un vértice de la frontera o bien multiplica por \(q\) o bien solo elimina esa posición, según si su clase de color sigue presente en otra parte de la frontera.
Cuando ya se han obtenido los coeficientes vacíos \((a_0,a_1,\dots,a_D)\), la implementación calcula la suma final grado por grado. Para cada \(d\), construye la tabla corta de valores prefijos de \(\sum_{x=1}^{n}x^d\), precalcula factoriales e inversos factoriales módulo la prima y evalúa el correspondiente polinomio de grado \(d+1\) en \(N\) mediante interpolación de Lagrange. El último paso es acumular módulo \(10^9+7\) cada producto \(a_d\) por su suma de potencias.
Sea \(w=\min(R,C)\), sea \(D=RC\), y sea \(T_w\) el número de estados canónicos de frontera que realmente aparecen durante el barrido. Como cada transición actualiza un arreglo de coeficientes de longitud \(D+1\), el coste principal del programa dinámico es aproximadamente \(O(RC\cdot T_w\cdot D)\) operaciones modulares. La memoria requerida es \(O(T_w\cdot D)\).
La fase final es mucho más pequeña. Calcular todas las sumas de potencias por interpolación cuesta \(O(D^2)\) tiempo y \(O(D)\) memoria auxiliar. Aquí \(D=90\), así que esta parte es barata; el cuello de botella real está en el espacio de estados de frontera.
设 \(G_{R,C}\) 是一个 \(R\times C\) 的网格图，\(F(R,C,q)\) 表示它的色多项式，也就是用 \(q\) 种颜色对该图进行合法染色的方案数。题目要求计算
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)\pmod{10^9+7}.$$
在实际参数中，\(R=9\)、\(C=10\)、\(N=1112131415\)。无论是直接枚举染色，还是对每个 \(x\le N\) 单独求一次色多项式值，都完全不可行。因此正确做法分成两层：先把整个网格图的色多项式 \(F(R,C,q)\) 建出来，再把最后的大求和转写成少量幂和的组合。
记 \(D=RC\)。由于网格图一共有 \(D\) 个顶点，所以 \(F(R,C,q)\) 是关于 \(q\) 的一个次数不超过 \(D\) 的多项式。实现采用的是前沿状态动态规划：用一条很窄的“活动边界”在网格上推进，只记录那些未来还会影响未处理区域的颜色等价关系。
算法按单元格顺序处理整个网格。在任意时刻，只有一小部分边界顶点还可能与尚未处理的区域相连，这些顶点组成前沿。若设 \(w=\min(R,C)\)，则前沿大小始终不超过 \(w\)，因此指数型复杂度只和较小的维度有关，而不是和全部 \(RC\) 个顶点一起爆炸。
前沿状态并不保存具体用了哪几种颜色，它只保存“哪些前沿位置必须同色”这一结构信息。换句话说，一个状态本质上是前沿位置集合的一个划分。只要两个标号方案表达的是同样的等价关系，它们在数学上就是同一个状态，因此可以重新规范化编号后合并。
当扫描过程遇到一条新的邻接边时，色多项式满足经典恒等式
$$P_{G+e}(q)=P_G(q)-P_{G/e}(q).$$
第一项表示在加入这条边之前的所有着色方式；第二项删去的是“两个端点颜色相同”的那些情况。在前沿状态表示中，“两个端点颜色相同”就意味着这两个位置属于同一个颜色块，因此需要把对应的两个块合并。于是，一次加边更新等价于：保留当前状态的正贡献，再减去把这两个块合并之后的状态。
如果两个端点原本就在同一个块里，那么正项和负项会完全抵消。这正是色多项式应有的行为，因为一旦这两个相邻顶点已经被迫同色，这部分局部染色就立刻非法。
某个前沿顶点一旦已经接收了所有可能通向未来区域的边，它就可以从前沿中移除。这里需要分两种情况。
如果它所在的颜色类在前沿中已经没有其他代表，那么这个抽象颜色类以后再也不会与未处理部分发生关系。此时它可以自由选择 \(q\) 个具体颜色中的任意一个，因此多项式需要额外乘上一个因子 \(q\)。
如果这个颜色类在前沿的其他位置还出现着，那么颜色选择还不能最终确定；剩下的代表会继续携带这条颜色约束。因此这种情况下只需要把该位置从状态里删掉，并重新做规范化编号，不必额外乘 \(q\)。
整个过程从“空前沿、系数为 \(1\)”的状态开始。随着扫描推进，算法反复执行三类局部操作：引入一个新的前沿顶点、加入此刻已经确定的横向和纵向边、移除那些再也不会与未处理区域相连的旧前沿顶点。
每个状态都携带一个关于 \(q\) 的多项式，所有规范化后相同的状态会把系数在模 \(10^9+7\) 下相加。等到整张网格都处理完，最后的前沿也被清空，只剩下空状态本身。这个空状态对应的系数数组正好就是
$$F(R,C,q)=\sum_{d=0}^{D} a_d q^d.$$
一旦系数 \(a_d\) 已知，目标量就可写成
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)=\sum_{d=0}^{D} a_d\sum_{x=1}^{N}x^d \pmod{10^9+7}.$$
这样问题就变成了计算 \(\sum_{x=1}^{N}x^d\) 这些幂和，其中 \(0\le d\le D\)。对固定的 \(d\)，Faulhaber 公式告诉我们这个量本身是关于 \(N\) 的一个次数为 \(d+1\) 的多项式。因此只要先计算它在 \(N=0,1,\dots,d+1\) 这些小点上的值，再利用模素数 \(10^9+7\) 下的拉格朗日插值，就能把它在巨大 \(N\) 处的值恢复出来。
\(2\times 2\) 网格图其实就是一个长度为 4 的环，因此它的色多项式为
$$F(2,2,q)=q(q-1)^2(q-2)=q^4-4q^3+6q^2-3q.$$
这和实现中的小规模校验值完全一致：
$$F(2,2,3)=18,\qquad F(2,2,20)=130340.$$
于是最终求和阶段就变成
$$S(2,2,N)=\sum_{x=1}^{N}\left(x^4-4x^3+6x^2-3x\right),$$
也就是把四种低次数幂和按系数组合起来。真正的 \(9\times 10\) 情形完全同理，只不过最高次数从 \(4\) 变成了 \(90\)。
C++、Python 和 Java 的实现遵循同一条计算主线。首先，它们会选择一个扫描方向，使得前沿宽度尽量小。随后，用一个映射结构把“规范化前沿划分”关联到长度为 \(RC+1\) 的系数数组。引入新单元格时，会在前沿末端加入一个新的单元素颜色块；加入网格边时，会执行删缩公式对应的“当前状态正贡献减去合并状态负贡献”；移出旧前沿顶点时，如果该颜色类已经不再出现在前沿中，就给对应多项式乘上 \(q\)，否则只做位置删除和重新规范化。
当空状态的系数 \((a_0,a_1,\dots,a_D)\) 全部得到之后，程序再按次数逐项计算最终答案。对每一个 \(d\)，它先建立 \(\sum_{x=1}^{n}x^d\) 在小点 \(n=0,1,\dots,d+1\) 处的前缀值表，再预处理模素数下的阶乘和逆阶乘，最后使用拉格朗日插值求出这个次数为 \(d+1\) 的多项式在目标 \(N\) 处的值。把所有 \(a_d\) 与相应幂和相乘并累加后，就得到最终结果。
设 \(w=\min(R,C)\)、\(D=RC\)，并记扫描过程中实际可达到的规范化前沿状态数为 \(T_w\)。每次状态转移都要更新一个长度为 \(D+1\) 的系数数组，因此前沿动态规划的主要代价大约是 \(O(RC\cdot T_w\cdot D)\) 次模运算。空间复杂度为 \(O(T_w\cdot D)\)。
最后的幂和阶段要轻得多。把所有次数的幂和都通过插值求出来，只需要 \(O(D^2)\) 时间和 \(O(D)\) 额外空间。在本题中 \(D=90\)，所以后处理基本不是瓶颈；真正的难点在于前沿状态空间本身。
Пусть \(G_{R,C}\) обозначает решёточный граф размера \(R\times C\), а \(F(R,C,q)\) его хроматический полином, то есть число правильных раскрасок в \(q\) цветов. Требуется вычислить величину
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)\pmod{10^9+7}.$$
В реальной постановке используются \(R=9\), \(C=10\) и очень большое \(N=1112131415\). Прямой перебор раскрасок невозможен, а вычислять \(F(R,C,x)\) отдельно для каждого \(x\le N\) тоже бессмысленно. Поэтому решение разбивается на два этапа: сначала строится весь хроматический полином решётки, а затем суммирование по \(x\) сводится к небольшому числу сумм степеней.
Обозначим \(D=RC\). Поскольку у решётки \(D\) вершин, \(F(R,C,q)\) является полиномом по \(q\) степени не выше \(D\). Реализация строит этот полином с помощью динамики по фронту: по сетке проходит узкая активная граница, а в состоянии хранится только та информация о совпадении цветов, которая ещё может повлиять на необработанную часть графа.
Решётка обрабатывается по одной клетке. В каждый момент времени только небольшой набор граничных вершин ещё может соединяться с нерассмотренной областью; эти вершины образуют фронт. Если положить \(w=\min(R,C)\), то размер фронта никогда не превышает \(w\), и экспоненциальная часть сложности зависит от меньшего измерения, а не от всех \(RC\) вершин сразу.
Состояние фронта не хранит конкретные номера цветов. Оно хранит только информацию о том, какие позиции фронта обязаны иметь один и тот же цвет. Иными словами, состояние есть разбиение множества активных позиций фронта. Две маркировки, отличающиеся лишь переименованием блоков, математически эквивалентны, поэтому приводятся к канонической форме и сливаются.
Когда в процессе прохода появляется новое ребро, хроматический полином подчиняется тождеству
$$P_{G+e}(q)=P_G(q)-P_{G/e}(q).$$
Первый член считает все раскраски до добавления нового ограничения. Второй вычитает те случаи, в которых оба конца ребра имеют одинаковый цвет. В представлении через фронт это означает, что соответствующие два блока должны быть слиты. Поэтому обновление по ребру создаёт положительную копию текущего состояния и отрицательную копию состояния, где две нужные метки объединены.
Если оба конца уже находятся в одном и том же блоке, положительный и отрицательный вклад полностью сокращаются. Это именно то, что должно происходить: частичная раскраска, где соседние вершины уже равны по цвету, становится недопустимой после появления ребра.
Как только вершина фронта получила все рёбра, которые ещё могут связывать её с будущей частью графа, она может покинуть фронт. Здесь возможны два случая.
Если её цветовой класс больше нигде на фронте не встречается, то этот абстрактный класс никогда больше не будет участвовать во взаимодействии с будущими вершинами. Значит, ему можно выбрать любой из \(q\) конкретных цветов, и это даёт множитель \(q\).
Если тот же класс ещё присутствует в другой позиции фронта, то выбор цвета пока не свободен: оставшийся представитель продолжает нести это ограничение. Тогда состояние просто уменьшается и снова канонизируется, без дополнительного множителя.
Алгоритм стартует с пустого фронта и коэффициента \(1\). Далее он многократно выполняет три локальные операции: вводит новую вершину на фронт, добавляет горизонтальные и вертикальные рёбра, которые к данному моменту уже определены, и удаляет те фронтовые вершины, которые больше не могут влиять на необработанную часть сетки.
Каждое состояние несёт полином по \(q\), а коэффициенты одинаковых канонических состояний складываются по модулю \(10^9+7\). После полного прохода по решётке и удаления последних вершин фронта остаётся только пустое состояние. Его коэффициентный массив и есть
$$F(R,C,q)=\sum_{d=0}^{D} a_d q^d.$$
Когда коэффициенты \(a_d\) уже известны, искомая величина переписывается так:
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)=\sum_{d=0}^{D} a_d\sum_{x=1}^{N}x^d \pmod{10^9+7}.$$
Остаётся вычислить суммы степеней \(\sum_{x=1}^{N}x^d\) для \(0\le d\le D\). Для фиксированного \(d\) это, по формуле Фаульхабера, полином от \(N\) степени \(d+1\). Следовательно, достаточно знать его значения в точках \(N=0,1,\dots,d+1\), напрямую посчитать эти короткие префиксные суммы, а затем получить значение в огромной точке \(N\) при помощи интерполяции Лагранжа по модулю простого числа \(10^9+7\).
Решётка \(2\times 2\) является циклом длины 4, поэтому её хроматический полином равен
$$F(2,2,q)=q(q-1)^2(q-2)=q^4-4q^3+6q^2-3q.$$
Это совпадает с малыми контрольными значениями, используемыми в реализации:
$$F(2,2,3)=18,\qquad F(2,2,20)=130340.$$
Финальный этап суммирования тогда имеет вид
$$S(2,2,N)=\sum_{x=1}^{N}\left(x^4-4x^3+6x^2-3x\right),$$
то есть сводится к линейной комбинации сумм степеней степеней \(1,2,3,4\). В полном случае \(9\times 10\) происходит ровно то же самое, только максимальная степень равна \(90\).
Реализации на C++, Python и Java следуют одной и той же вычислительной схеме. Сначала выбирается направление прохода, чтобы ширина фронта была как можно меньше. Затем поддерживается отображение от канонических разбиений фронта к массивам коэффициентов длины \(RC+1\). Ввод новой клетки добавляет новый одноэлементный блок, добавление ребра применяет переход «положительное текущее состояние минус состояние со слитыми блоками», а удаление вершины из фронта либо умножает полином на \(q\), либо просто убирает эту позицию, если соответствующий цветовой класс ещё виден в другом месте фронта.
После того как получены коэффициенты пустого состояния \((a_0,a_1,\dots,a_D)\), программа вычисляет окончательный ответ по степеням. Для каждого \(d\) строится короткая таблица значений \(\sum_{x=1}^{n}x^d\) на малых \(n\), заранее вычисляются факториалы и обратные факториалы по модулю простого числа, а затем значение полинома степени \(d+1\) в точке \(N\) восстанавливается интерполяцией Лагранжа. Последний шаг состоит в суммировании произведений \(a_d\) на соответствующие суммы степеней.
Пусть \(w=\min(R,C)\), \(D=RC\), а \(T_w\) обозначает число достижимых канонических фронтовых состояний в процессе прохода. Каждое обновление изменяет коэффициентный массив длины \(D+1\), поэтому основная динамика требует примерно \(O(RC\cdot T_w\cdot D)\) модульных операций. Память составляет \(O(T_w\cdot D)\).
Заключительная стадия значительно дешевле. Вычисление всех сумм степеней с помощью интерполяции требует \(O(D^2)\) времени и \(O(D)\) дополнительной памяти. Поскольку здесь \(D=90\), эта часть мала; главный источник сложности — именно пространство фронтовых состояний.
ليكن \(G_{R,C}\) هو الرسم الشبكي ذو الأبعاد \(R\times C\)، ولتكن \(F(R,C,q)\) كثير الحدود اللوني له، أي عدد التلوينات الصحيحة باستعمال \(q\) ألوان. المطلوب حساب
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)\pmod{10^9+7}.$$
في الحالة الفعلية للمسألة لدينا \(R=9\) و\(C=10\) و\(N=1112131415\)، ولذلك فالتعداد المباشر للتلوينات مستحيل عمليًا، كما أن تقييم كثير الحدود لكل \(x\le N\) على حدة غير ممكن أيضًا. لهذا تُقسَّم الفكرة إلى مرحلتين: أولًا نبني كثير الحدود اللوني الكامل للشبكة، ثم نحول الجمع النهائي على \(x=1,2,\dots,N\) إلى مجموعة صغيرة من مجاميع القوى.
لنكتب \(D=RC\). بما أن الرسم يحوي \(D\) رؤوسًا، فإن \(F(R,C,q)\) هو كثير حدود في \(q\) درجته لا تتجاوز \(D\). يبني التنفيذ هذا الكثير باستعمال برمجة ديناميكية على حدود نشطة ضيقة، مع الاحتفاظ فقط بمعلومة تساوي الألوان بين الرؤوس التي ما زالت قد تؤثر في الجزء غير المعالج من الشبكة.
تُعالَج الشبكة خليةً بعد خلية. وفي كل لحظة لا يبقى إلا عدد صغير من رؤوس الحد الفاصل قادرًا على الاتصال بالجزء الذي لم يُعالَج بعد؛ وهذه الرؤوس تشكل الحد النشط. إذا وضعنا \(w=\min(R,C)\)، فإن حجم هذا الحد لا يتجاوز \(w\) أبدًا، وبذلك يعتمد الجزء الأسي من التعقيد على البعد الأصغر بدلًا من جميع الرؤوس \(RC\) دفعةً واحدة.
لا تخزن حالة الحد أرقام الألوان الفعلية، بل تخزن فقط أي مواضع على الحد يجب أن تتشارك اللون نفسه. أي إن الحالة هي تجزئة لمواضع الحد النشط إلى كتل تمثل فئات اللون. وإذا اختلف توصيف حالتين بمجرد إعادة تسمية هذه الكتل، فهما تصفان الوضع الرياضي نفسه، ولذلك تُعاد فهرستهما إلى صيغة معيارية واحدة ثم تُدمجان.
كلما ظهرت مجاورة جديدة أثناء المسح، يحقق كثير الحدود اللوني الهوية
$$P_{G+e}(q)=P_G(q)-P_{G/e}(q).$$
الحد الأول يعد جميع التلوينات قبل فرض القيد الجديد، والحد الثاني يطرح الحالات التي يحصل فيها طرفا الحافة على اللون نفسه. وفي تمثيل الحد النشط تعني عبارة “اللون نفسه” أن الكتلتين المقابلتين لهذين الطرفين يجب دمجهما. لذا فكل تحديث ناتج عن حافة يضيف نسخة موجبة من الحالة الحالية ونسخة سالبة من الحالة الناتجة عن دمج الكتلتين المعنيتين.
إذا كان الطرفان من الأصل في الكتلة نفسها فإن الحدين يتلاشيان بالكامل. وهذا صحيح تمامًا، لأن أي تلوين جزئي يجعل رأسين متجاورين باللون نفسه يصبح غير صالح فور وجود تلك الحافة.
متى ما استقبل رأس من رؤوس الحد جميع الحواف التي قد توصله مستقبلًا بالجزء غير المعالج، يمكن إخراجه من الحد. وهنا تظهر حالتان.
إذا لم تعد فئة اللون الخاصة به موجودة في أي موضع آخر على الحد، فهذا يعني أن تلك الفئة المجردة لن تتفاعل مع المستقبل بعد الآن. وعندئذ يمكن إسناد أي واحد من الألوان \(q\) إليها، فينشأ عامل ضربي مقداره \(q\).
أما إذا بقيت الفئة نفسها ممثلة في موضع آخر من الحد، فإن اختيار اللون ما زال غير حر، لأن الممثل الباقي سيحمل هذا القيد إلى الخطوات اللاحقة. في هذه الحالة تُصغَّر الحالة وتُعاد معيارتها فقط، من دون عامل إضافي.
تبدأ العملية من حالة الحد الفارغ ذات المعامل \(1\). ثم يكرر المسح ثلاث عمليات محلية: إدخال رأس جديد إلى الحد، وإضافة الحواف الأفقية والعمودية التي أصبحت معلومة، ثم إخراج الرؤوس التي لم يعد يمكن أن تتصل بالجزء غير المرئي من الشبكة.
كل حالة تحمل كثير حدود في \(q\)، وتُجمع معاملات الحالات المعيارية المتطابقة بترديد \(10^9+7\). وبعد اكتمال المسح وإزالة آخر رؤوس الحد، لا يبقى إلا الحد الفارغ. ومصفوفة معاملاته هي بالضبط
$$F(R,C,q)=\sum_{d=0}^{D} a_d q^d.$$
بعد معرفة المعاملات \(a_d\)، تصبح الكمية المطلوبة
$$S(R,C,N)=\sum_{x=1}^{N}F(R,C,x)=\sum_{d=0}^{D} a_d\sum_{x=1}^{N}x^d \pmod{10^9+7}.$$
وهكذا يتبقى حساب مجاميع القوى \(\sum_{x=1}^{N}x^d\) من أجل \(0\le d\le D\). وبحسب صيغة فاولهابر فإن هذه الكمية، عند تثبيت \(d\)، هي كثير حدود في \(N\) درجته \(d+1\). لذلك يكفي أن نعرف قيمها عند \(N=0,1,\dots,d+1\)، فنحسب تلك المجاميع القصيرة مباشرة، ثم نستخرج القيمة عند \(N\) الكبير بواسطة استيفاء لاغرانج بترديد العدد الأولي \(10^9+7\).
شبكة \(2\times 2\) هي دورة طولها 4، ولذلك فإن كثير حدودها اللوني هو
$$F(2,2,q)=q(q-1)^2(q-2)=q^4-4q^3+6q^2-3q.$$
وهذا يطابق نقاط التحقق الصغيرة المستخدمة في التنفيذ:
$$F(2,2,3)=18,\qquad F(2,2,20)=130340.$$
وعندئذ تصبح مرحلة الجمع
$$S(2,2,N)=\sum_{x=1}^{N}\left(x^4-4x^3+6x^2-3x\right),$$
أي مجرد تركيب خطي لمجاميع القوى من الدرجات \(1,2,3,4\). أما في الحالة الكاملة \(9\times 10\) فالفكرة نفسها تبقى كما هي، مع ارتفاع الدرجة القصوى إلى \(90\).
تتبع تطبيقات C++ وPython وJava المسار الحسابي نفسه. فهي تختار أولًا اتجاه المسح بحيث يكون عرض الحد النشط أصغر ما يمكن. ثم تحفظ قاموسًا يربط كل تجزئة معيارية للحد بمصفوفة معاملات طولها \(RC+1\). وعند إدخال خلية جديدة تُضاف كتلة مفردة جديدة، وعند إضافة حافة تُطبَّق النقلة الناتجة عن صيغة الحذف والانكماش، أي نسخة موجبة من الحالة الحالية ونسخة سالبة من الحالة بعد الدمج، وعند إزالة رأس من الحد يُضرب كثير الحدود في \(q\) إذا كانت فئة لونه قد اختفت من الحد، وإلا فيُحذف الموضع فقط مع إعادة المعيارة.
بعد الحصول على معاملات الحالة الفارغة \((a_0,a_1,\dots,a_D)\)، يحسب التنفيذ الجواب النهائي درجةً بعد درجة. ولكل \(d\) يبني جدولًا قصيرًا لقيم \(\sum_{x=1}^{n}x^d\) عند القيم الصغيرة \(n\)، ويحضّر المضروبات ومقلوباتها بترديد العدد الأولي، ثم يقيّم كثير الحدود ذي الدرجة \(d+1\) عند \(N\) باستيفاء لاغرانج. وفي النهاية تُجمع جميع الحدود \(a_d\) مضروبةً في مجموع القوة الموافق لها.
إذا أخذنا \(w=\min(R,C)\) و\(D=RC\)، وكتبنا \(T_w\) لعدد الحالات المعيارية للحد التي يمكن الوصول إليها فعلًا أثناء المسح، فإن كل انتقال يحدّث مصفوفة معاملات طولها \(D+1\). لذا فإن كلفة البرمجة الديناميكية تقارب \(O(RC\cdot T_w\cdot D)\) من العمليات المعيارية، بينما يساوي استهلاك الذاكرة \(O(T_w\cdot D)\).
أما مرحلة ما بعد بناء كثير الحدود فهي أصغر كثيرًا. فحساب جميع مجاميع القوى بالاستيفاء يحتاج إلى \(O(D^2)\) زمنًا و\(O(D)\) ذاكرة إضافية. وهنا \(D=90\)، ولذلك فإن هذه المرحلة ليست هي الاختناق الحقيقي؛ الاختناق يأتي من فضاء حالات الحد النشط نفسه.