For each \(n\), the solution evaluates a quantity \(M(n)\) and then forms
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
The counting argument is encoded by cyclic words of length \(2n\) over the alphabet \(\{0,1,2\}\). Symbol \(0\) means that no special local structure is forced at that place, while \(1\) and \(2\) are the two oriented marker types used by the inclusion-exclusion step. The hard part is therefore to count which cyclic marker patterns are legal, and then attach the multiplicative weight that each legal pattern contributes.
Let \(C_{L,k}\) denote the number of cyclic words \(a_1,\dots,a_L\in\{0,1,2\}\) with exactly \(k\) nonzero symbols, where indices are read modulo \(L\), and which satisfy the local restrictions
$$a_{i-1}\neq 0 \Rightarrow a_i=0,$$
$$a_{i-2}=2 \Rightarrow a_i\neq 1.$$
Only even lengths \(L=2n\) are used in the final answer.
The implementation rewrites the original counting problem as a signed sum over sets of forced local structures. Each chosen structure is recorded by placing a nonzero marker in one position of a cyclic word. There are two oriented types, represented by \(1\) and \(2\), so a configuration with \(k\) chosen structures becomes a cyclic word with exactly \(k\) nonzero symbols.
The two local rules above say exactly which selections can coexist. The first rule forbids two neighboring nonzero markers, so chosen structures cannot overlap immediately. The second rule removes one more forbidden interaction at distance two: a marker of type \(2\) cannot be followed two steps later by a marker of type \(1\).
Because the legality of a new symbol depends only on the previous two symbols, a transfer-state dynamic program is enough. Fix the first two symbols \((a_1,a_2)\), and let
$$D(\ell,s,t,k)$$
be the number of length-\(\ell\) prefixes whose first two symbols are fixed, whose last two symbols are \((s,t)\), which already satisfy every internal local rule, and which contain exactly \(k\) nonzero entries.
If a new symbol \(u\in\{0,1,2\}\) is appended, the transition is legal precisely when
$$t\neq 0 \Rightarrow u=0,$$
$$s=2 \Rightarrow u\neq 1.$$
When \(u\neq 0\), the counter \(k\) increases by \(1\). This is why the implementations only need a tiny state space for the last two symbols and a second dimension for the number of nonzero markers.
A path counted by the DP is not yet a valid cycle. When the current last two symbols are \((x,y)\) and the fixed initial pair is \((a,b)\), the wrap-around conditions are
$$y\neq 0 \Rightarrow a=0,$$
$$x=2 \Rightarrow a\neq 1,$$
$$y=2 \Rightarrow b\neq 1.$$
These are exactly the same local restrictions, but applied across the end of the cycle. Summing all DP states that satisfy these three boundary checks gives \(C_{L,k}\).
Once a valid cyclic marker pattern of length \(2n\) with \(k\) nonzero positions is fixed, the formula used by the implementation factors into four independent pieces.
First, the pattern itself contributes \(C_{2n,k}\).
Second, the \(k\) chosen local structures must be matched injectively with \(k\) distinct labeled objects among \(n\), which gives the falling factorial
$$ (n)_k=\frac{n!}{(n-k)!}. $$
Third, each chosen position has \(4\) concrete realizations, so there is a factor \(4^k\).
Fourth, after those \(k\) forced structures are removed, there remain \(2n-2k\) free items in each of two independent orders, contributing
$$((2n-2k)!)^2.$$
Inclusion-exclusion supplies the sign \((-1)^k\), and a final global factor \(2\) remains. Therefore
$$M(n)=2\sum_{k=0}^{n}(-1)^k C_{2n,k}(n)_k 4^k ((2n-2k)!)^2 \pmod{10^9+7}.$$
After \(M(n)\) has been evaluated for every \(2\le n\le N\), the required result is simply
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
The implementations therefore precompute the pattern counts once, precompute the needed factorial data once, and then sweep through \(n=2,3,\dots,N\).
For \(n=2\) we need length \(4\) cyclic words. The legal counts are easy to derive directly.
For \(k=0\), only \(0000\) is possible, so \(C_{4,0}=1\).
For \(k=1\), choose one of the \(4\) positions and choose symbol \(1\) or \(2\), so \(C_{4,1}=8\).
For \(k=2\), the two nonzero symbols must occupy alternating positions, either \(\{1,3\}\) or \(\{2,4\}\). On each alternating pair, the distance-two rule forbids \((2,1)\) in either direction, so only \((1,1)\) and \((2,2)\) survive. Hence \(C_{4,2}=4\).
Substituting into the formula gives
$$M(2)=2\left(1\cdot 1\cdot 1\cdot (4!)^2 - 8\cdot 2\cdot 4\cdot (2!)^2 + 4\cdot 2\cdot 16\cdot (0!)^2\right).$$
That is
$$M(2)=2(576-256+128)=896,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations follow the same pipeline. They first build the full table \(C_{L,k}\) for every \(L\le 2N\) and \(k\le N\) by running the last-two-symbol DP for each admissible starting pair. They then precompute factorials, inverse factorials, and powers of \(4\) modulo \(10^9+7\).
For each \(n\), the implementation reads the already computed row \(C_{2n,k}\), evaluates the alternating sum for \(M(n)\), multiplies by the outer factor \(2\), and adds the result into the running total for \(S(N)\). The checkpoints embedded in the implementation include
$$M(2)=896,\qquad M(3)=890880,\qquad M(10)=170717180,$$
and
$$S(10)=399291975.$$
Let the final limit be \(N\). The pattern-count DP considers \(O(N)\) lengths, a constant number of last-two-symbol states, and up to \(O(N)\) values of \(k\), so building all \(C_{L,k}\) costs \(O(N^2)\) time. The factorial, inverse-factorial, and power tables cost \(O(N)\) time and memory. Evaluating all alternating sums for \(M(2),\dots,M(N)\) is another \(O(N^2)\) pass. Therefore the overall complexity is
$$O(N^2)\text{ time and }O(N^2)\text{ memory}.$$
Für jedes \(n\) wird zunächst eine Größe \(M(n)\) berechnet und anschließend
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
Das Zählproblem wird durch zyklische Wörter der Länge \(2n\) über dem Alphabet \(\{0,1,2\}\) kodiert. Das Symbol \(0\) bedeutet, dass an dieser Stelle keine lokale Struktur erzwungen wird, während \(1\) und \(2\) die beiden orientierten Markertypen des Inklusions-Exklusions-Schritts darstellen. Die eigentliche Arbeit besteht also darin, die zulässigen zyklischen Markermuster zu zählen und danach ihr jeweiliges Gewicht anzuhängen.
Sei \(C_{L,k}\) die Anzahl zyklischer Wörter \(a_1,\dots,a_L\in\{0,1,2\}\) mit genau \(k\) von Null verschiedenen Symbolen. Die Indizes werden modulo \(L\) gelesen, und es gelten die lokalen Bedingungen
$$a_{i-1}\neq 0 \Rightarrow a_i=0,$$
$$a_{i-2}=2 \Rightarrow a_i\neq 1.$$
In der Endformel werden nur gerade Längen \(L=2n\) verwendet.
Die Implementierung schreibt das ursprüngliche Problem als vorzeichenbehaftete Summe über Mengen erzwungener lokaler Strukturen um. Jede gewählte Struktur wird durch einen von Null verschiedenen Marker an einer Position des Zyklus dargestellt. Da es zwei Orientierungen gibt, werden die Werte \(1\) und \(2\) verwendet. Eine Konfiguration mit \(k\) gewählten Strukturen entspricht also einem zyklischen Wort mit genau \(k\) von Null verschiedenen Einträgen.
Die beiden lokalen Regeln beschreiben exakt, welche Auswahlen gleichzeitig möglich sind. Die erste Regel verbietet benachbarte Marker und verhindert damit unmittelbare Überlappung. Die zweite Regel streicht zusätzlich eine verbotene Wechselwirkung im Abstand zwei: Auf ein Symbol \(2\) darf zwei Schritte später kein Symbol \(1\) folgen.
Da die Gültigkeit eines neuen Symbols nur von den beiden vorherigen Symbolen abhängt, genügt eine kleine Zustands-DP. Fixiere das Anfangspaar \((a_1,a_2)\) und definiere
$$D(\ell,s,t,k)$$
als die Anzahl der Präfixe der Länge \(\ell\), deren erste beiden Symbole fest vorgegeben sind, deren letzte beiden Symbole \((s,t)\) sind, die alle inneren lokalen Regeln bereits erfüllen und genau \(k\) von Null verschiedene Einträge enthalten.
Wird ein neues Symbol \(u\in\{0,1,2\}\) angehängt, dann ist der Übergang genau dann erlaubt, wenn
$$t\neq 0 \Rightarrow u=0,$$
$$s=2 \Rightarrow u\neq 1.$$
Für \(u\neq 0\) erhöht sich der Zähler \(k\) um \(1\). Deshalb benötigen die Implementierungen nur einen sehr kleinen Zustandsraum für die letzten beiden Symbole und eine zweite Dimension für die Anzahl der Marker.
Ein von der DP gezählter Pfad ist noch kein gültiger Zyklus. Wenn die letzten beiden aktuellen Symbole \((x,y)\) sind und das feste Anfangspaar \((a,b)\) lautet, dann müssen über den Rand hinweg noch
$$y\neq 0 \Rightarrow a=0,$$
$$x=2 \Rightarrow a\neq 1,$$
$$y=2 \Rightarrow b\neq 1$$
gelten. Das sind genau dieselben lokalen Regeln, nur auf die Verknüpfung zwischen Ende und Anfang angewendet. Die Summe über alle DP-Endzustände, die diese drei Prüfungen bestehen, ergibt \(C_{L,k}\).
Ist ein gültiges zyklisches Markermuster der Länge \(2n\) mit \(k\) Nichtnull-Positionen festgelegt, zerfällt sein Beitrag in vier unabhängige Faktoren.
Der erste Faktor ist das Muster selbst, also \(C_{2n,k}\).
Der zweite Faktor ist die injektive Zuordnung der \(k\) gewählten lokalen Strukturen zu \(k\) verschiedenen markierten Objekten unter den \(n\) verfügbaren. Das liefert die fallende Fakultät
$$ (n)_k=\frac{n!}{(n-k)!}. $$
Der dritte Faktor ist \(4^k\), weil jede gewählte Position vier konkrete Realisierungen besitzt.
Der vierte Faktor stammt von den übrigen freien Elementen. Nach dem Entfernen der \(k\) erzwungenen Strukturen bleiben in zwei unabhängigen Ordnungen jeweils \(2n-2k\) Elemente übrig, also
$$((2n-2k)!)^2.$$
Dazu kommt das Vorzeichen \((-1)^k\) aus der Inklusions-Exklusion und ein globaler Faktor \(2\). Damit ergibt sich
$$M(n)=2\sum_{k=0}^{n}(-1)^k C_{2n,k}(n)_k 4^k ((2n-2k)!)^2 \pmod{10^9+7}.$$
Sobald \(M(n)\) für alle \(2\le n\le N\) berechnet ist, erhält man das gesuchte Ergebnis durch
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
Die Implementierungen berechnen daher die Mustertabelle einmal vollständig vor, berechnen die Fakultätsdaten einmal vor und laufen dann nur noch über \(n=2,3,\dots,N\).
Für \(n=2\) benötigen wir zyklische Wörter der Länge \(4\). Die Werte \(C_{4,k}\) lassen sich noch direkt bestimmen.
Für \(k=0\) gibt es nur \(0000\), also \(C_{4,0}=1\).
Für \(k=1\) wählen wir eine der \(4\) Positionen und dann das Symbol \(1\) oder \(2\). Daher ist \(C_{4,1}=8\).
Für \(k=2\) müssen die beiden Nichtnull-Symbole auf alternierenden Positionen liegen, also entweder \(\{1,3\}\) oder \(\{2,4\}\). Auf jedem solchen Paar verbietet die Distanz-zwei-Regel die Belegung \((2,1)\) in beiden Richtungen, sodass nur \((1,1)\) und \((2,2)\) übrig bleiben. Also ist \(C_{4,2}=4\).
Einsetzen in die Formel ergibt
$$M(2)=2\left(1\cdot 1\cdot 1\cdot (4!)^2 - 8\cdot 2\cdot 4\cdot (2!)^2 + 4\cdot 2\cdot 16\cdot (0!)^2\right).$$
Damit folgt
$$M(2)=2(576-256+128)=896,$$
genau wie im Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Pipeline. Zuerst bauen sie für alle \(L\le 2N\) und \(k\le N\) die vollständige Tabelle \(C_{L,k}\) auf, indem sie die DP über die letzten beiden Symbole für jedes zulässige Anfangspaar ausführen. Danach werden Fakultäten, inverse Fakultäten und Potenzen von \(4\) modulo \(10^9+7\) vorab berechnet.
Für jedes \(n\) liest die Implementierung die bereits berechnete Zeile \(C_{2n,k}\) aus, wertet die alternierende Summe für \(M(n)\) aus, multipliziert mit dem äußeren Faktor \(2\) und addiert das Ergebnis zum laufenden Wert von \(S(N)\). Die eingebetteten Kontrollwerte lauten unter anderem
$$M(2)=896,\qquad M(3)=890880,\qquad M(10)=170717180,$$
sowie
$$S(10)=399291975.$$
Sei \(N\) die gesuchte Obergrenze. Die Muster-DP betrachtet \(O(N)\) Längen, eine konstante Anzahl von Zuständen für die letzten beiden Symbole und bis zu \(O(N)\) Werte von \(k\). Das Vorberechnen aller \(C_{L,k}\) kostet daher \(O(N^2)\) Zeit. Die Tabellen für Fakultäten, inverse Fakultäten und Potenzen benötigen \(O(N)\) Zeit und Speicher. Die Auswertung aller Summen für \(M(2),\dots,M(N)\) ist ein weiterer \(O(N^2)\)-Durchlauf. Insgesamt ergibt sich also
$$O(N^2)\text{ Zeit und }O(N^2)\text{ Speicher}.$$
Her \(n\) için önce bir \(M(n)\) değeri hesaplanıyor, ardından
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
Sayım argümanı, \(\{0,1,2\}\) alfabesi üzerinde uzunluğu \(2n\) olan döngüsel dizilerle kodlanıyor. \(0\), o konumda zorlanan özel bir yerel yapı olmadığını; \(1\) ve \(2\) ise dahil et-çıkar adımında kullanılan iki yönlü işaret türünü gösteriyor. Bu yüzden asıl zor kısım, hangi döngüsel işaret desenlerinin geçerli olduğunu saymak ve sonra her geçerli desene karşılık gelen çarpanı eklemek.
\(C_{L,k}\), tam olarak \(k\) tane sıfır olmayan sembol içeren ve \(a_1,\dots,a_L\in\{0,1,2\}\) olan döngüsel dizilerin sayısı olsun. İndisler modulo \(L\) okunur ve şu yerel kurallar uygulanır:
$$a_{i-1}\neq 0 \Rightarrow a_i=0,$$
$$a_{i-2}=2 \Rightarrow a_i\neq 1.$$
Son formülde yalnızca çift uzunluklar, yani \(L=2n\), kullanılır.
Uygulama, asıl sayım problemini zorlanmış yerel yapı kümeleri üzerinden alınan işaretli bir toplam olarak yeniden yazar. Seçilen her yapı, döngü üzerinde bir konuma yerleştirilen sıfır olmayan bir işaretle temsil edilir. İki yön bulunduğu için \(1\) ve \(2\) değerleri kullanılır. Böylece \(k\) tane seçilmiş yapıya sahip bir konfigürasyon, tam olarak \(k\) sıfır olmayan sembol içeren bir döngüsel diziye dönüşür.
Yukarıdaki iki yerel kural, hangi seçimlerin birlikte bulunabileceğini tam olarak belirler. İlk kural, yan yana iki sıfır olmayan işareti yasaklar; yani iki zorlanmış yapı hemen üst üste gelemez. İkinci kural ise iki adım uzaklıktaki ek bir çakışmayı kaldırır: türü \(2\) olan bir işaretin iki adım sonrasında türü \(1\) olan bir işaret bulunamaz.
Yeni bir sembolün geçerli olup olmadığı sadece önceki iki sembole bağlı olduğu için küçük bir durum uzayına sahip bir DP yeterlidir. Başlangıç çifti \((a_1,a_2)\) sabitlenir ve
$$D(\ell,s,t,k)$$
uzunluğu \(\ell\) olan, ilk iki sembolü sabit, son iki sembolü \((s,t)\) olan, içerideki tüm yerel kuralları şimdiden sağlayan ve tam olarak \(k\) tane sıfır olmayan giriş içeren önek sayısını göstersin.
Yeni eklenen sembol \(u\in\{0,1,2\}\) olduğunda geçiş ancak şu durumda mümkündür:
$$t\neq 0 \Rightarrow u=0,$$
$$s=2 \Rightarrow u\neq 1.$$
\(u\neq 0\) ise sayaç \(k\) bir artar. Bu nedenle uygulamalar yalnızca son iki sembolü tutan küçük bir durum tablosuna ve işaret sayısını izleyen ikinci bir boyuta ihtiyaç duyar.
DP'nin saydığı bir yol henüz tam bir döngü değildir. Son iki sembol \((x,y)\), başlangıç çifti de \((a,b)\) ise, sınırı kapatırken ayrıca
$$y\neq 0 \Rightarrow a=0,$$
$$x=2 \Rightarrow a\neq 1,$$
$$y=2 \Rightarrow b\neq 1$$
koşulları sağlanmalıdır. Bunlar aynı yerel kuralların, bu kez dizinin sonu ile başı arasında uygulanmış halidir. Bu üç sınır testini geçen tüm DP bitiş durumlarının toplamı \(C_{L,k}\) değerini verir.
Uzunluğu \(2n\) olan ve \(k\) adet sıfır olmayan konuma sahip geçerli bir döngüsel işaret deseni sabitlendiğinde katkı dört bağımsız çarpana ayrılır.
Birinci çarpan desenin kendisidir: \(C_{2n,k}\).
İkinci çarpan, seçilmiş \(k\) yerel yapının \(n\) etiketli nesne içinden farklı \(k\) tanesiyle çakışmasız biçimde eşleştirilmesidir. Bu da düşen faktöriyeli verir:
$$ (n)_k=\frac{n!}{(n-k)!}. $$
Üçüncü çarpan \(4^k\)'dir; çünkü her seçilmiş konumun \(4\) somut gerçekleşme biçimi vardır.
Dördüncü çarpan serbest kalan elemanlardan gelir. Zorlanmış \(k\) yapı kaldırıldığında iki bağımsız sıralamada da \(2n-2k\) eleman kalır ve bu
$$((2n-2k)!)^2$$
katkısını doğurur. İşaret \((-1)^k\) dahil et-çıkar ilkesinden gelir ve en dışta bir de \(2\) katsayısı vardır. Böylece
$$M(n)=2\sum_{k=0}^{n}(-1)^k C_{2n,k}(n)_k 4^k ((2n-2k)!)^2 \pmod{10^9+7}$$
elde edilir.
\(2\le n\le N\) için tüm \(M(n)\) değerleri hesaplandıktan sonra istenen sonuç doğrudan
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}$$
olur. Bu nedenle uygulamalar desen sayımlarını bir kez, faktöriyel verilerini bir kez hazırlar ve sonra \(n=2,3,\dots,N\) boyunca tek bir tarama yapar.
\(n=2\) için uzunluğu \(4\) olan döngüsel diziler gerekir. Bu durumda \(C_{4,k}\) değerleri elle bulunabilir.
\(k=0\) için yalnızca \(0000\) vardır, dolayısıyla \(C_{4,0}=1\).
\(k=1\) için \(4\) konumdan biri seçilir ve sembol olarak \(1\) ya da \(2\) konur; yani \(C_{4,1}=8\).
\(k=2\) için iki sıfır olmayan sembol yalnızca dönüşümlü konumlarda olabilir: \(\{1,3\}\) ya da \(\{2,4\}\). Her dönüşümlü çiftte iki adım kuralı, her iki yönde de \((2,1)\) yerleşimini yasaklar; geriye yalnızca \((1,1)\) ve \((2,2)\) kalır. Bu yüzden \(C_{4,2}=4\).
Formüle koyarsak
$$M(2)=2\left(1\cdot 1\cdot 1\cdot (4!)^2 - 8\cdot 2\cdot 4\cdot (2!)^2 + 4\cdot 2\cdot 16\cdot (0!)^2\right).$$
Buradan
$$M(2)=2(576-256+128)=896$$
çıkar; bu da uygulamadaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı akışı izler. Önce, izin verilen her başlangıç çifti için son iki sembole dayalı DP çalıştırılarak tüm \(L\le 2N\) ve \(k\le N\) değerleri için \(C_{L,k}\) tablosu oluşturulur. Ardından \(10^9+7\) modunda faktöriyeller, ters faktöriyeller ve \(4\)'ün kuvvetleri önceden hesaplanır.
Her \(n\) için uygulama doğrudan \(C_{2n,k}\) satırını kullanır, \(M(n)\) için işaretli toplamı hesaplar, dıştaki \(2\) katsayısını uygular ve sonucu \(S(N)\) toplamına ekler. Uygulamadaki kontrol noktaları arasında
$$M(2)=896,\qquad M(3)=890880,\qquad M(10)=170717180,$$
ve
$$S(10)=399291975$$
bulunur.
Üst sınır \(N\) olsun. Desen sayımı için kullanılan DP, \(O(N)\) farklı uzunluğu, son iki sembol için sabit sayıda durumu ve \(O(N)\) kadar \(k\) değerini tarar; bu nedenle tüm \(C_{L,k}\) tablosunu hazırlamanın maliyeti \(O(N^2)\) zamandır. Faktöriyel, ters faktöriyel ve kuvvet tabloları \(O(N)\) zaman ve bellek ister. Tüm \(M(2),\dots,M(N)\) toplamlarını değerlendirmek de ek bir \(O(N^2)\) geçiştir. Sonuç olarak toplam karmaşıklık
$$O(N^2)\text{ zaman ve }O(N^2)\text{ bellek}$$
olur.
Para cada \(n\), la solución evalúa primero una cantidad \(M(n)\) y después forma
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
El argumento combinatorio se codifica mediante palabras cíclicas de longitud \(2n\) sobre el alfabeto \(\{0,1,2\}\). El símbolo \(0\) indica que en esa posición no se fuerza ninguna estructura local especial, mientras que \(1\) y \(2\) representan los dos tipos orientados de marcador que aparecen en el paso de inclusión-exclusión. Por tanto, la dificultad real consiste en contar qué patrones cíclicos de marcadores son válidos y luego adjuntar el peso multiplicativo de cada patrón válido.
Sea \(C_{L,k}\) el número de palabras cíclicas \(a_1,\dots,a_L\in\{0,1,2\}\) con exactamente \(k\) símbolos no nulos. Los índices se interpretan módulo \(L\), y las restricciones locales son
$$a_{i-1}\neq 0 \Rightarrow a_i=0,$$
$$a_{i-2}=2 \Rightarrow a_i\neq 1.$$
En la respuesta final solo se usan longitudes pares \(L=2n\).
La implementación reescribe el problema original como una suma con signo sobre conjuntos de estructuras locales forzadas. Cada estructura elegida se registra colocando un marcador no nulo en una posición del ciclo. Como existen dos orientaciones, se usan los valores \(1\) y \(2\). Así, una configuración con \(k\) estructuras elegidas se convierte en una palabra cíclica con exactamente \(k\) símbolos no nulos.
Las dos reglas locales anteriores describen exactamente qué elecciones pueden coexistir. La primera regla prohíbe marcadores no nulos adyacentes, evitando superposiciones inmediatas. La segunda elimina una colisión adicional a distancia dos: un marcador de tipo \(2\) no puede ir seguido dos pasos más tarde por un marcador de tipo \(1\).
Como la validez de un nuevo símbolo depende solo de los dos símbolos anteriores, basta un DP de transferencia con un estado pequeño. Se fija el par inicial \((a_1,a_2)\) y se define
$$D(\ell,s,t,k)$$
como el número de prefijos de longitud \(\ell\) cuyos dos primeros símbolos están fijados, cuyos dos últimos símbolos son \((s,t)\), que ya satisfacen todas las reglas locales internas y que contienen exactamente \(k\) entradas no nulas.
Si se añade un nuevo símbolo \(u\in\{0,1,2\}\), la transición es válida exactamente cuando
$$t\neq 0 \Rightarrow u=0,$$
$$s=2 \Rightarrow u\neq 1.$$
Cuando \(u\neq 0\), el contador \(k\) aumenta en \(1\). Por eso las implementaciones solo necesitan un espacio de estados muy pequeño para los dos últimos símbolos y una segunda dimensión para el número de marcadores.
Un camino contado por el DP todavía no es un ciclo válido. Si los dos últimos símbolos actuales son \((x,y)\) y el par inicial fijado es \((a,b)\), entonces al cerrar el ciclo también deben cumplirse
$$y\neq 0 \Rightarrow a=0,$$
$$x=2 \Rightarrow a\neq 1,$$
$$y=2 \Rightarrow b\neq 1.$$
Estas son exactamente las mismas restricciones locales, pero aplicadas a través de la frontera entre el final y el comienzo. La suma de todos los estados finales del DP que superan estas tres comprobaciones da \(C_{L,k}\).
Una vez fijado un patrón cíclico válido de longitud \(2n\) con \(k\) posiciones no nulas, la contribución se descompone en cuatro factores independientes.
El primero es el propio patrón, es decir, \(C_{2n,k}\).
El segundo es la asignación inyectiva de las \(k\) estructuras locales elegidas a \(k\) objetos etiquetados distintos entre los \(n\) disponibles, lo que produce el factorial descendente
$$ (n)_k=\frac{n!}{(n-k)!}. $$
El tercer factor es \(4^k\), porque cada posición elegida tiene \(4\) realizaciones concretas.
El cuarto factor viene de los elementos libres restantes. Tras retirar las \(k\) estructuras forzadas, quedan \(2n-2k\) elementos en cada uno de dos órdenes independientes, lo que aporta
$$((2n-2k)!)^2.$$
La inclusión-exclusión añade el signo \((-1)^k\), y además aparece un factor global \(2\). Por tanto,
$$M(n)=2\sum_{k=0}^{n}(-1)^k C_{2n,k}(n)_k 4^k ((2n-2k)!)^2 \pmod{10^9+7}.$$
Después de calcular \(M(n)\) para todo \(2\le n\le N\), el resultado pedido es simplemente
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
Por eso las implementaciones precalculan una vez la tabla de patrones, una vez los datos factoriales y luego recorren \(n=2,3,\dots,N\).
Para \(n=2\) necesitamos palabras cíclicas de longitud \(4\). Los valores \(C_{4,k}\) se pueden obtener a mano.
Para \(k=0\), solo existe \(0000\), así que \(C_{4,0}=1\).
Para \(k=1\), elegimos una de las \(4\) posiciones y luego el símbolo \(1\) o \(2\), de modo que \(C_{4,1}=8\).
Para \(k=2\), los dos símbolos no nulos tienen que ocupar posiciones alternadas, es decir, \(\{1,3\}\) o \(\{2,4\}\). En cada pareja alternada, la regla de distancia dos prohíbe \((2,1)\) en cualquiera de los dos sentidos, así que solo sobreviven \((1,1)\) y \((2,2)\). En consecuencia, \(C_{4,2}=4\).
Al sustituir en la fórmula, obtenemos
$$M(2)=2\left(1\cdot 1\cdot 1\cdot (4!)^2 - 8\cdot 2\cdot 4\cdot (2!)^2 + 4\cdot 2\cdot 16\cdot (0!)^2\right).$$
Esto da
$$M(2)=2(576-256+128)=896,$$
que coincide con el punto de control usado por la implementación.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero construyen la tabla completa \(C_{L,k}\) para todos los \(L\le 2N\) y \(k\le N\) ejecutando el DP sobre los dos últimos símbolos para cada par inicial permitido. Después precalculan factoriales, factoriales inversos y potencias de \(4\) módulo \(10^9+7\).
Para cada \(n\), la implementación toma la fila ya calculada \(C_{2n,k}\), evalúa la suma alternante de \(M(n)\), multiplica por el factor exterior \(2\) y añade el resultado al acumulado de \(S(N)\). Los puntos de control incorporados incluyen
$$M(2)=896,\qquad M(3)=890880,\qquad M(10)=170717180,$$
y
$$S(10)=399291975.$$
Sea \(N\) el límite final. El DP de conteo de patrones recorre \(O(N)\) longitudes, un número constante de estados para los dos últimos símbolos y hasta \(O(N)\) valores de \(k\), de modo que construir toda la tabla \(C_{L,k}\) cuesta \(O(N^2)\) tiempo. Las tablas de factoriales, factoriales inversos y potencias requieren \(O(N)\) tiempo y memoria. Evaluar todas las sumas alternantes para \(M(2),\dots,M(N)\) es otra pasada de \(O(N^2)\). Por tanto, la complejidad total es
$$O(N^2)\text{ en tiempo y }O(N^2)\text{ en memoria}.$$
对每个 \(n\)，解法先计算一个量 \(M(n)\)，然后再求
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
整个计数过程被编码成长度为 \(2n\) 的循环词，字母表是 \(\{0,1,2\}\)。符号 \(0\) 表示这个位置没有被强制放入特殊的局部结构，而 \(1\) 和 \(2\) 表示在包含-排除中出现的两种有方向的标记类型。于是问题的核心就变成：先数出哪些循环标记模式是合法的，再把每个合法模式对应的乘法权重加上去。
记 \(C_{L,k}\) 为满足下面条件的循环词 \(a_1,\dots,a_L\in\{0,1,2\}\) 的个数：恰好有 \(k\) 个非零符号，且下标按模 \(L\) 理解，并满足局部限制
$$a_{i-1}\neq 0 \Rightarrow a_i=0,$$
$$a_{i-2}=2 \Rightarrow a_i\neq 1.$$
最终公式里只会用到偶数长度 \(L=2n\)。
实现把原问题改写成一个带符号的求和，求和对象是“被强制出现的局部结构”的集合。每选中一个局部结构，就在循环词的某个位置放一个非零标记。因为这种局部结构有两个方向，所以用 \(1\) 和 \(2\) 来区分。于是，一个包含 \(k\) 个被选结构的配置，就对应成一个恰有 \(k\) 个非零符号的循环词。
上面的两条局部规则精确描述了哪些选择可以同时出现。第一条规则禁止相邻位置同时出现非零标记，因此相邻的强制结构不能立刻重叠。第二条规则再排除一种相距两步的冲突：如果某个位置是类型 \(2\)，那么两步之后不能出现类型 \(1\)。
由于新加入的一个符号是否合法，只取决于前两个符号，所以只需要一个很小的转移状态。固定开头两个符号 \((a_1,a_2)\)，定义
$$D(\ell,s,t,k)$$
表示长度为 \(\ell\) 的前缀数量：前两个符号已经固定，最后两个符号是 \((s,t)\)，内部所有局部规则都已经满足，而且非零符号总数正好是 \(k\)。
如果在末尾追加一个新符号 \(u\in\{0,1,2\}\)，那么转移合法当且仅当
$$t\neq 0 \Rightarrow u=0,$$
$$s=2 \Rightarrow u\neq 1.$$
当 \(u\neq 0\) 时，计数参数 \(k\) 增加 \(1\)。这就是为什么实现只需要记录“最后两个符号是什么”和“目前已经用了多少个非零标记”。
DP 统计出的只是线性前缀，不一定已经形成合法的环。如果当前最后两个符号是 \((x,y)\)，而固定的开头两个符号是 \((a,b)\)，那么跨越末尾和开头的边界时，还必须满足
$$y\neq 0 \Rightarrow a=0,$$
$$x=2 \Rightarrow a\neq 1,$$
$$y=2 \Rightarrow b\neq 1.$$
这三条其实就是同样的局部规则，只不过现在它们作用在“序列结尾”和“序列开头”的连接处。把所有通过这三项检查的 DP 末状态加起来，就得到 \(C_{L,k}\)。
一旦一个长度为 \(2n\)、恰有 \(k\) 个非零位置的合法循环标记模式被固定下来，它对 \(M(n)\) 的贡献就分解成四个彼此独立的因子。
第一部分就是模式本身的个数，也就是 \(C_{2n,k}\)。
第二部分是把这 \(k\) 个被选中的局部结构，单射地对应到 \(n\) 个带标签对象中的 \(k\) 个不同对象上，因此得到下降阶乘
$$ (n)_k=\frac{n!}{(n-k)!}. $$
第三部分是 \(4^k\)，因为每个被选位置都有 \(4\) 种具体实现方式。
第四部分来自剩余的自由元素。去掉这 \(k\) 个被强制的局部结构后，两条彼此独立的排列中各自还剩下 \(2n-2k\) 个元素，因此贡献
$$((2n-2k)!)^2.$$
包含-排除给出符号 \((-1)^k\)，最外层还有一个整体因子 \(2\)。于是
$$M(n)=2\sum_{k=0}^{n}(-1)^k C_{2n,k}(n)_k 4^k ((2n-2k)!)^2 \pmod{10^9+7}.$$
当所有 \(2\le n\le N\) 的 \(M(n)\) 都算出来以后，最终答案就是
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
因此，实现会先一次性预处理好模式计数表，再一次性预处理好阶乘和相关数据，最后顺序扫过 \(n=2,3,\dots,N\)。
当 \(n=2\) 时，我们需要长度为 \(4\) 的循环词。此时 \(C_{4,k}\) 可以直接手算。
当 \(k=0\) 时，唯一可能是 \(0000\)，所以 \(C_{4,0}=1\)。
当 \(k=1\) 时，先从 \(4\) 个位置里选一个，再决定符号是 \(1\) 还是 \(2\)，因此 \(C_{4,1}=8\)。
当 \(k=2\) 时，两个非零符号只能放在交错位置上，也就是 \(\{1,3\}\) 或 \(\{2,4\}\)。对于每一组交错位置，距离为二的限制会在两个方向上都排除 \((2,1)\)，所以只剩下 \((1,1)\) 和 \((2,2)\) 两种情况。于是 \(C_{4,2}=4\)。
代入公式得到
$$M(2)=2\left(1\cdot 1\cdot 1\cdot (4!)^2 - 8\cdot 2\cdot 4\cdot (2!)^2 + 4\cdot 2\cdot 16\cdot (0!)^2\right).$$
也就是
$$M(2)=2(576-256+128)=896,$$
这与实现中的校验值一致。
C++、Python 和 Java 的实现流程完全一致。第一步，针对每一个允许的起始二元组，运行“只记最后两个符号”的 DP，从而构造所有 \(L\le 2N\)、\(k\le N\) 的整张 \(C_{L,k}\) 表。第二步，在模 \(10^9+7\) 下预处理阶乘、逆阶乘以及 \(4\) 的幂。
随后对每个 \(n\)，实现直接读取已经算好的 \(C_{2n,k}\)，代入交替求和公式得到 \(M(n)\)，乘上外层因子 \(2\)，再加进总和 \(S(N)\)。实现里内置的校验点包括
$$M(2)=896,\qquad M(3)=890880,\qquad M(10)=170717180,$$
以及
$$S(10)=399291975.$$
设上界为 \(N\)。模式计数 DP 需要遍历 \(O(N)\) 个长度、常数个“最后两个符号”的状态，以及最多 \(O(N)\) 个 \(k\) 值，因此构造整张 \(C_{L,k}\) 表的时间是 \(O(N^2)\)。阶乘、逆阶乘和幂表的预处理只需要 \(O(N)\) 时间和空间。之后对所有 \(M(2),\dots,M(N)\) 做交替求和，又是一次 \(O(N^2)\) 的扫描。所以总复杂度为
$$O(N^2)\text{ 时间，}O(N^2)\text{ 内存}.$$
Для каждого \(n\) решение сначала вычисляет величину \(M(n)\), а затем суммирует
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
Комбинаторика кодируется циклическими словами длины \(2n\) над алфавитом \(\{0,1,2\}\). Символ \(0\) означает, что в этой позиции не фиксируется специальная локальная структура, а символы \(1\) и \(2\) соответствуют двум ориентированным типам маркеров, которые появляются в схеме включения-исключения. Поэтому главная задача состоит в том, чтобы посчитать допустимые циклические шаблоны маркеров, а затем присоединить вес каждого такого шаблона.
Обозначим через \(C_{L,k}\) число циклических слов \(a_1,\dots,a_L\in\{0,1,2\}\) ровно с \(k\) ненулевыми символами. Индексы понимаются по модулю \(L\), и должны выполняться локальные ограничения
$$a_{i-1}\neq 0 \Rightarrow a_i=0,$$
$$a_{i-2}=2 \Rightarrow a_i\neq 1.$$
В итоговой формуле используются только четные длины \(L=2n\).
Реализация переписывает исходную задачу в виде знакопеременной суммы по множествам принудительных локальных структур. Каждая выбранная структура записывается как ненулевой маркер в некоторой позиции цикла. Поскольку существует две ориентации, используются значения \(1\) и \(2\). Значит, конфигурация с \(k\) выбранными структурами превращается в циклическое слово ровно с \(k\) ненулевыми символами.
Два локальных правила выше точно описывают, какие выборы могут сосуществовать. Первое правило запрещает соседние ненулевые маркеры, то есть немедленное перекрытие. Второе правило убирает еще одно запрещенное взаимодействие на расстоянии два: после символа типа \(2\) через два шага не может стоять символ типа \(1\).
Так как допустимость нового символа зависит только от двух предыдущих символов, достаточно динамики по маленькому состоянию. Зафиксируем начальную пару \((a_1,a_2)\) и определим
$$D(\ell,s,t,k)$$
как число префиксов длины \(\ell\), у которых первые два символа уже зафиксированы, последние два символа равны \((s,t)\), все внутренние локальные правила выполнены, и имеется ровно \(k\) ненулевых позиций.
Если приписывается новый символ \(u\in\{0,1,2\}\), то переход допустим тогда и только тогда, когда
$$t\neq 0 \Rightarrow u=0,$$
$$s=2 \Rightarrow u\neq 1.$$
Если \(u\neq 0\), счетчик \(k\) увеличивается на \(1\). Именно поэтому реализации достаточно помнить только два последних символа и текущее число ненулевых маркеров.
Путь, посчитанный в DP, еще не обязательно образует корректный цикл. Если текущие два последних символа равны \((x,y)\), а фиксированная начальная пара равна \((a,b)\), то при замыкании по границе должны дополнительно выполняться условия
$$y\neq 0 \Rightarrow a=0,$$
$$x=2 \Rightarrow a\neq 1,$$
$$y=2 \Rightarrow b\neq 1.$$
Это те же самые локальные правила, но примененные через границу между концом и началом цикла. Сумма по всем конечным состояниям DP, которые проходят эти три проверки, и дает \(C_{L,k}\).
После фиксации корректного циклического шаблона длины \(2n\) с \(k\) ненулевыми позициями его вклад распадается на четыре независимых множителя.
Первый множитель - это сам шаблон, то есть \(C_{2n,k}\).
Второй множитель - инъективное сопоставление \(k\) выбранных локальных структур с \(k\) различными помеченными объектами из \(n\), что дает падающую факториальную степень
$$ (n)_k=\frac{n!}{(n-k)!}. $$
Третий множитель равен \(4^k\), потому что у каждой выбранной позиции есть \(4\) конкретные реализации.
Четвертый множитель приходит от оставшихся свободных элементов. После удаления \(k\) принудительных структур в каждом из двух независимых порядков остается по \(2n-2k\) элементов, что дает
$$((2n-2k)!)^2.$$
Принцип включения-исключения добавляет знак \((-1)^k\), а снаружи остается общий множитель \(2\). Поэтому
$$M(n)=2\sum_{k=0}^{n}(-1)^k C_{2n,k}(n)_k 4^k ((2n-2k)!)^2 \pmod{10^9+7}.$$
После того как вычислены все \(M(n)\) для \(2\le n\le N\), искомый ответ равен
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
Поэтому реализации один раз строят таблицу шаблонов, один раз предварительно считают факториальные данные, а затем проходят по \(n=2,3,\dots,N\).
При \(n=2\) нужны циклические слова длины \(4\). Здесь значения \(C_{4,k}\) можно вывести вручную.
Для \(k=0\) существует только слово \(0000\), значит \(C_{4,0}=1\).
Для \(k=1\) выбирается одна из \(4\) позиций и затем символ \(1\) или \(2\), поэтому \(C_{4,1}=8\).
Для \(k=2\) два ненулевых символа обязаны стоять в чередующихся позициях, то есть либо \(\{1,3\}\), либо \(\{2,4\}\). На каждой такой паре правило расстояния два запрещает конфигурацию \((2,1)\) в обоих направлениях, так что остаются только \((1,1)\) и \((2,2)\). Следовательно, \(C_{4,2}=4\).
Подставляя в формулу, получаем
$$M(2)=2\left(1\cdot 1\cdot 1\cdot (4!)^2 - 8\cdot 2\cdot 4\cdot (2!)^2 + 4\cdot 2\cdot 16\cdot (0!)^2\right).$$
Отсюда
$$M(2)=2(576-256+128)=896,$$
что совпадает с контрольным значением в реализации.
Реализации на C++, Python и Java используют одинаковый конвейер. Сначала они строят полную таблицу \(C_{L,k}\) для всех \(L\le 2N\) и \(k\le N\), запуская DP по двум последним символам для каждой допустимой стартовой пары. Затем заранее вычисляются факториалы, обратные факториалы и степени числа \(4\) по модулю \(10^9+7\).
Для каждого \(n\) реализация берет уже готовую строку \(C_{2n,k}\), вычисляет знакопеременную сумму для \(M(n)\), умножает на внешний множитель \(2\) и добавляет результат к текущему значению \(S(N)\). Встроенные контрольные точки включают
$$M(2)=896,\qquad M(3)=890880,\qquad M(10)=170717180,$$
а также
$$S(10)=399291975.$$
Пусть верхняя граница равна \(N\). DP для подсчета шаблонов перебирает \(O(N)\) длин, константное число состояний для двух последних символов и до \(O(N)\) значений \(k\), поэтому построение всей таблицы \(C_{L,k}\) занимает \(O(N^2)\) времени. Таблицы факториалов, обратных факториалов и степеней требуют \(O(N)\) времени и памяти. Вычисление всех сумм для \(M(2),\dots,M(N)\) - это еще один проход за \(O(N^2)\). Итак, общая сложность равна
$$O(N^2)\text{ по времени и }O(N^2)\text{ по памяти}.$$
لكل \(n\)، تحسب الخوارزمية أولا كمية اسمها \(M(n)\)، ثم تجمع
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
فكرة العد كلها تترجم إلى كلمات دورية طولها \(2n\) على الأبجدية \(\{0,1,2\}\). الرمز \(0\) يعني أن هذا الموضع لا يفرض بنية محلية خاصة، أما الرمزان \(1\) و\(2\) فيمثلان نوعين موجّهين من العلامات المستخدمة داخل مبدأ الشمول والاستبعاد. لذلك يصبح لب المسألة هو عدّ الأنماط الدورية الصالحة لهذه العلامات، ثم إلحاق الوزن الضربي الذي يساهم به كل نمط صالح.
لنرمز بـ \(C_{L,k}\) إلى عدد الكلمات الدورية \(a_1,\dots,a_L\in\{0,1,2\}\) التي تحتوي بالضبط على \(k\) رموز غير صفرية. وتفهم الفهارس بترديد \(L\)، مع تحقق القيود المحلية
$$a_{i-1}\neq 0 \Rightarrow a_i=0,$$
$$a_{i-2}=2 \Rightarrow a_i\neq 1.$$
في الصيغة النهائية لا نستخدم إلا الأطوال الزوجية \(L=2n\).
تعيد الشيفرة كتابة مسألة العد الأصلية على شكل مجموع ذي إشارات على مجموعات من البنى المحلية المفروضة. كل بنية مختارة تسجل بوضع علامة غير صفرية في موضع من الدورة. وبما أن هناك اتجاهين ممكنين، فنستعمل القيمتين \(1\) و\(2\). وهكذا فإن التهيئة التي تحتوي على \(k\) بنى مختارة تتحول إلى كلمة دورية فيها بالضبط \(k\) رموز غير صفرية.
القيدان المحليان السابقان يصفان بدقة أي الاختيارات يمكن أن تتعايش. القيد الأول يمنع علامتين غير صفريتين متجاورتين، أي يمنع التداخل الفوري. والقيد الثاني يزيل تصادما إضافيا على بعد خطوتين: إذا ظهر رمز من النوع \(2\)، فلا يجوز أن يظهر بعد خطوتين رمز من النوع \(1\).
بما أن صلاحية الرمز الجديد تعتمد فقط على الرمزين السابقين، فإن برمجة ديناميكية ذات حالة صغيرة تكفي. نثبت الزوج الابتدائي \((a_1,a_2)\)، ثم نعرف
$$D(\ell,s,t,k)$$
على أنه عدد البادئات ذات الطول \(\ell\) التي يكون أول رمزين فيها ثابتين، وآخر رمزين فيها هما \((s,t)\)، وتكون جميع القيود المحلية الداخلية قد تحققت بالفعل، ويكون عدد الرموز غير الصفرية فيها مساويا تماما لـ \(k\).
إذا أضفنا رمزا جديدا \(u\in\{0,1,2\}\)، فإن الانتقال يكون صالحا إذا وفقط إذا تحقق
$$t\neq 0 \Rightarrow u=0,$$
$$s=2 \Rightarrow u\neq 1.$$
وعندما يكون \(u\neq 0\)، فإن العداد \(k\) يزداد بمقدار \(1\). لهذا السبب لا تحتاج الشيفرة إلا إلى تتبع آخر رمزين وعدد العلامات غير الصفرية حتى اللحظة الحالية.
المسار الذي تعده البرمجة الديناميكية ليس بالضرورة دورة صالحة بعد. إذا كان آخر رمزين حاليين هما \((x,y)\)، وكان الزوج الابتدائي المثبت هو \((a,b)\)، فعند إغلاق الدورة عبر الحد بين النهاية والبداية يجب أيضا أن تتحقق الشروط
$$y\neq 0 \Rightarrow a=0,$$
$$x=2 \Rightarrow a\neq 1,$$
$$y=2 \Rightarrow b\neq 1.$$
هذه هي القيود المحلية نفسها، ولكن بعد تطبيقها عبر الوصلة بين آخر السلسلة وأولها. وجمع جميع حالات النهاية في البرمجة الديناميكية التي تنجح في هذه الاختبارات الثلاثة يعطينا \(C_{L,k}\).
بعد تثبيت نمط دوري صالح طوله \(2n\) وله \(k\) مواضع غير صفرية، تنقسم مساهمته إلى أربعة عوامل مستقلة.
العامل الأول هو عدد الأنماط نفسه، أي \(C_{2n,k}\).
العامل الثاني هو المطابقة الحقنية بين البنى المحلية المختارة وعددها \(k\) وبين \(k\) عناصر مميزة مختلفة من بين \(n\) عنصرا، وهذا يعطي العامل الهابط
$$ (n)_k=\frac{n!}{(n-k)!}. $$
العامل الثالث هو \(4^k\)، لأن كل موضع مختار يملك \(4\) تجسدات ملموسة.
أما العامل الرابع فيأتي من العناصر الحرة المتبقية. بعد إزالة \(k\) من البنى المفروضة، يبقى \(2n-2k\) عنصر في كل واحد من ترتيبين مستقلين، ومن ثم نحصل على
$$((2n-2k)!)^2.$$
ويضيف مبدأ الشمول والاستبعاد الإشارة \((-1)^k\)، ويبقى خارج المجموع عامل عام يساوي \(2\). لذلك
$$M(n)=2\sum_{k=0}^{n}(-1)^k C_{2n,k}(n)_k 4^k ((2n-2k)!)^2 \pmod{10^9+7}.$$
بعد حساب \(M(n)\) لكل \(2\le n\le N\)، تكون النتيجة المطلوبة ببساطة
$$S(N)=\sum_{n=2}^{N} M(n)\pmod{10^9+7}.$$
ولهذا السبب تبني الشيفرة جدول أنماط العد مرة واحدة، وتحضر بيانات المضروبات مرة واحدة، ثم تمر على \(n=2,3,\dots,N\).
عندما يكون \(n=2\)، نحتاج إلى كلمات دورية طولها \(4\). في هذه الحالة يمكن اشتقاق القيم \(C_{4,k}\) مباشرة.
عند \(k=0\)، لا يوجد إلا النمط \(0000\)، ولذلك \(C_{4,0}=1\).
عند \(k=1\)، نختار واحدا من المواضع الأربعة ثم نختار الرمز \(1\) أو \(2\)، ومن ثم \(C_{4,1}=8\).
عند \(k=2\)، يجب أن يشغل الرمزان غير الصفريين موضعين متناوبين، أي \(\{1,3\}\) أو \(\{2,4\}\). وعلى كل زوج متناوب تمنع قاعدة المسافة-اثنين النمط \((2,1)\) في كلا الاتجاهين، فلا يبقى إلا \((1,1)\) و\((2,2)\). إذن \(C_{4,2}=4\).
بالتعويض في الصيغة نحصل على
$$M(2)=2\left(1\cdot 1\cdot 1\cdot (4!)^2 - 8\cdot 2\cdot 4\cdot (2!)^2 + 4\cdot 2\cdot 16\cdot (0!)^2\right).$$
أي
$$M(2)=2(576-256+128)=896,$$
وهو تماما مقدار التحقق الموجود داخل التنفيذ.
تتبع تطبيقات C++ وPython وJava المسار نفسه. أولا تبني الجدول الكامل \(C_{L,k}\) لكل \(L\le 2N\) و\(k\le N\) عن طريق تشغيل البرمجة الديناميكية المعتمدة على آخر رمزين لكل زوج ابتدائي مسموح. ثم تجهز مسبقا المضروبات، والمضروبات العكسية، وقوى العدد \(4\) بترديد \(10^9+7\).
بعد ذلك، لكل \(n\)، يقرأ التنفيذ السطر المحسوب سلفا \(C_{2n,k}\)، ويقيّم المجموع المتناوب الذي يعطي \(M(n)\)، ويضرب في العامل الخارجي \(2\)، ثم يضيف الناتج إلى المجموع الجاري \(S(N)\). ومن نقاط التحقق المضمّنة في التنفيذ
$$M(2)=896,\qquad M(3)=890880,\qquad M(10)=170717180,$$
وكذلك
$$S(10)=399291975.$$
إذا كان الحد الأعلى هو \(N\)، فإن برمجة عدّ الأنماط تمر على \(O(N)\) أطوال مختلفة، وعدد ثابت من الحالات الخاصة بآخر رمزين، وما يصل إلى \(O(N)\) قيمة لـ \(k\)، ولذلك فإن بناء الجدول الكامل \(C_{L,k}\) يحتاج إلى \(O(N^2)\) زمنا. أما جداول المضروبات والمضروبات العكسية والقوى فتحتاج إلى \(O(N)\) زمنا وذاكرة. وتقييم جميع المجاميع الخاصة بـ \(M(2),\dots,M(N)\) هو مرور آخر بتكلفة \(O(N^2)\). وعليه فالتعقيد الكلي هو
وبذلك يكون التعقيد الكلي \(O(N^2)\) زمنيا و\(O(N^2)\) من حيث الذاكرة.