There are three vertical lines and two allowed adjacent swaps. Operation \(A\) swaps the first and second lines, and operation \(B\) swaps the second and third lines. Among all words that contain exactly \(m\) copies of \(A\) and exactly \(n\) copies of \(B\), we must count those whose total permutation is the identity.
The required answer is taken modulo \(M=1234567891\). A direct dynamic program over all prefixes and all six permutations is useful only for tiny checks. For the real input sizes, the key is to compress the word into consecutive pairs and count those pairs analytically.
Work in the symmetric group \(S_3\):
$$A=(12),\qquad B=(23).$$
Both generators are transpositions, so they are odd permutations. The identity permutation is even. Therefore, if \(m+n\) is odd, then no word can evaluate to the identity and
$$F(m,n)=0.$$
From now on, assume \(m+n\) is even and write
$$m+n=2t,\qquad t=\frac{m+n}{2}.$$
Split any word of length \(2t\) into \(t\) adjacent blocks:
$$\bigl(x_1x_2\bigr)\bigl(x_3x_4\bigr)\cdots\bigl(x_{2t-1}x_{2t}\bigr),\qquad x_i\in\{A,B\}.$$
Now set
$$e=\text{identity},\qquad r=AB=(123),\qquad r^2=BA=(132).$$
Each pair belongs to the cyclic subgroup \(\{e,r,r^2\}\), because
$$AA=e,\qquad BB=e,\qquad AB=r,\qquad BA=r^2.$$
Suppose exactly \(k\) of the \(t\) pairs are mixed, meaning they are either \(AB\) or \(BA\). Then the remaining pairs must be neutral pairs \(AA\) and \(BB\). Their counts are forced:
$$u=\frac{m-k}{2},\qquad v=\frac{n-k}{2}.$$
So \(k\) is admissible exactly when
$$0\le k\le \min(m,n),\qquad k\equiv m\pmod 2.$$
Once \(k\) is fixed, the number of ways to choose which of the \(t\) pair positions are \(AA\), which are \(BB\), and which are mixed is the multinomial coefficient
$$T_k=\frac{t!}{u!\,v!\,k!}=\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}.$$
This counts the block layout, but it does not yet distinguish whether a mixed block is \(AB\) or \(BA\).
Inside the \(k\) mixed positions, let exactly \(j\) blocks be \(AB=r\) and the remaining \(k-j\) blocks be \(BA=r^2\). Their product is
$$r^j(r^2)^{k-j}=r^{j+2(k-j)}=r^{2j-k}.$$
This equals the identity exactly when
$$2j-k\equiv 0\pmod 3.$$
Therefore the number of valid orientations of the \(k\) mixed blocks is
$$R_k=\sum_{\substack{0\le j\le k\\2j-k\equiv 0\pmod 3}}\binom{k}{j}.$$
This sum has a clean closed form. Let \(\omega\neq 1\) be a complex cube root of unity, so \(\omega^3=1\). A roots-of-unity filter gives
$$R_k=\frac{1}{3}\sum_{q=0}^{2}\omega^{-2kq}(1+\omega^q)^k.$$
Evaluating the three terms yields
$$R_k=\frac{2^k+2(-1)^k}{3}.$$
For each admissible \(k\), the choices of block layout and the choices of mixed-block orientations are independent. Hence
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}} T_k\,R_k \pmod{M}.$$
Substituting the explicit formulas gives
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}}\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}\cdot\frac{2^k+2(-1)^k}{3}\pmod{M}.$$
This is the closed summation used by the implementations.
Let \(k_0=m\bmod 2\), the smallest admissible value of \(k\). The initial combinatorial factor is
$$T_{k_0}= \begin{cases} \binom{t}{m/2}, & k_0=0,\\ t\binom{t-1}{(m-1)/2}, & k_0=1. \end{cases}$$
For later terms, taking the ratio of consecutive admissible values gives
$$\frac{T_{k+2}}{T_k}=\frac{(m-k)(n-k)}{4(k+1)(k+2)}.$$
So once one term is known, the next one is obtained with constant-time modular arithmetic. Also, when \(k\) increases by \(2\), the factor \(2^k\) is multiplied by \(4\), while \((-1)^k\) stays unchanged because the parity of \(k\) never changes inside the loop.
Here \(m+n=6\), so \(t=3\), and admissible values of \(k\) are \(1\) and \(3\).
For \(k=1\), we have
$$T_1=\frac{3!}{1!\,1!\,1!}=6,\qquad R_1=\frac{2^1+2(-1)^1}{3}=0.$$
So all layouts with exactly one mixed pair contribute nothing, because a single nontrivial element of order \(3\) cannot be the identity.
For \(k=3\), we get
$$T_3=\frac{3!}{0!\,0!\,3!}=1,\qquad R_3=\frac{2^3+2(-1)^3}{3}=2.$$
Thus
$$F(3,3)=1\cdot 2=2.$$
The two words are the fully alternating ones:
$$ABABAB,\qquad BABABA.$$
The C++, Python, and Java implementations all evaluate the same formula modulo \(1234567891\). They first handle the parity test \(m+n\) odd \(\Rightarrow 0\), then set \(t=(m+n)/2\) and start from the smallest admissible \(k\).
The initial factor \(T_{k_0}\) is computed through a binomial coefficient modulo \(M\). Since modular division is needed, the implementation uses modular inverses under the prime modulus, obtained by fast exponentiation. To avoid computing one inverse at a time, it builds inverses for long consecutive ranges in batches and reuses them inside the product.
After that, the program walks through \(k,k+2,k+4,\dots\). At each step it updates the current multinomial factor with the ratio
$$\frac{(m-k)(n-k)}{4(k+1)(k+2)}$$
updates the power \(2^k\) by multiplying by \(4\), multiplies by the modular inverse of \(3\), and adds the current contribution to the running answer. The whole computation therefore uses the closed form directly and never builds a large \(O(mn)\) dynamic-programming table over the six states of \(S_3\).
The number of admissible values of \(k\) is \(1+\left\lfloor\frac{\min(m,n)-k_0}{2}\right\rfloor\), so the main summation is linear in \(\min(m,n)\). Computing the starting binomial factor is also linear in the smaller half-count, so the total running time is \(O(\min(m,n))\) modular multiplications.
The implementations store only a few scalar values plus a temporary batch of modular inverses. If the batch size is denoted by \(B\), the extra memory is \(O(B)\); with the batch size treated as a fixed engineering constant, the working memory is effectively constant with respect to \(m\) and \(n\).
Es gibt drei vertikale Linien und zwei erlaubte Nachbarvertauschungen. Die Operation \(A\) vertauscht die erste mit der zweiten Linie, \(B\) vertauscht die zweite mit der dritten. Unter allen Wörtern mit genau \(m\) Symbolen \(A\) und genau \(n\) Symbolen \(B\) sollen diejenigen gezählt werden, deren Gesamtpermutation die Identität ist.
Gesucht ist das Ergebnis modulo \(M=1234567891\). Ein direktes dynamisches Programm über Präfixe und alle sechs Permutationen ist nur für winzige Beispiele brauchbar. Für die echten Größenordnungen wird das Wort stattdessen in benachbarte Paare zerlegt und diese Paarstruktur direkt gezählt.
Wir arbeiten in der symmetrischen Gruppe \(S_3\):
$$A=(12),\qquad B=(23).$$
Beide Erzeuger sind Transpositionen und damit ungerade Permutationen. Die Identität ist gerade. Also gilt bei ungeradem \(m+n\) sofort
$$F(m,n)=0.$$
Im Folgenden nehmen wir daher an, dass \(m+n\) gerade ist, und schreiben
$$m+n=2t,\qquad t=\frac{m+n}{2}.$$
Ein Wort der Länge \(2t\) wird in \(t\) benachbarte Blöcke der Länge \(2\) aufgeteilt:
$$\bigl(x_1x_2\bigr)\bigl(x_3x_4\bigr)\cdots\bigl(x_{2t-1}x_{2t}\bigr),\qquad x_i\in\{A,B\}.$$
Setze nun
$$e=\text{Identität},\qquad r=AB=(123),\qquad r^2=BA=(132).$$
Jedes Paar liegt dann in der zyklischen Untergruppe \(\{e,r,r^2\}\), denn
$$AA=e,\qquad BB=e,\qquad AB=r,\qquad BA=r^2.$$
Seien genau \(k\) der \(t\) Paare gemischt, also entweder \(AB\) oder \(BA\). Dann bleiben nur neutrale Paare \(AA\) und \(BB\) übrig. Deren Anzahl ist fest vorgegeben:
$$u=\frac{m-k}{2},\qquad v=\frac{n-k}{2}.$$
Damit ist \(k\) genau dann zulässig, wenn
$$0\le k\le \min(m,n),\qquad k\equiv m\pmod 2.$$
Für festes \(k\) ist die Zahl der Anordnungen der \(t\) Paarpositionen als \(AA\), \(BB\) oder gemischt gleich dem multinomialen Koeffizienten
$$T_k=\frac{t!}{u!\,v!\,k!}=\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}.$$
Dieser Faktor zählt die Blockstruktur, unterscheidet aber innerhalb eines gemischten Blocks noch nicht zwischen \(AB\) und \(BA\).
Unter den \(k\) gemischten Positionen seien genau \(j\) Blöcke vom Typ \(AB=r\) und die übrigen \(k-j\) vom Typ \(BA=r^2\). Ihr Produkt ist
$$r^j(r^2)^{k-j}=r^{j+2(k-j)}=r^{2j-k}.$$
Dies ist genau dann die Identität, wenn
$$2j-k\equiv 0\pmod 3.$$
Also ist die Zahl gültiger Orientierungen der \(k\) gemischten Blöcke
$$R_k=\sum_{\substack{0\le j\le k\\2j-k\equiv 0\pmod 3}}\binom{k}{j}.$$
Diese Summe hat eine kompakte geschlossene Form. Sei \(\omega\neq 1\) eine komplexe dritte Einheitswurzel mit \(\omega^3=1\). Dann liefert ein Roots-of-unity-Filter
$$R_k=\frac{1}{3}\sum_{q=0}^{2}\omega^{-2kq}(1+\omega^q)^k.$$
Nach Auswertung der drei Terme folgt
$$R_k=\frac{2^k+2(-1)^k}{3}.$$
Für jedes zulässige \(k\) sind die Wahl der Blockstruktur und die Wahl der Orientierungen unabhängig. Daher gilt
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}} T_k\,R_k \pmod{M}.$$
Mit den expliziten Formeln wird daraus
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}}\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}\cdot\frac{2^k+2(-1)^k}{3}\pmod{M}.$$
Genau diese Summenform werten die Implementierungen aus.
Sei \(k_0=m\bmod 2\) der kleinste zulässige Wert von \(k\). Dann ist der Anfangsfaktor
$$T_{k_0}= \begin{cases} \binom{t}{m/2}, & k_0=0,\\ t\binom{t-1}{(m-1)/2}, & k_0=1. \end{cases}$$
Für die Folgeterme ergibt das Quotientenbild
$$\frac{T_{k+2}}{T_k}=\frac{(m-k)(n-k)}{4(k+1)(k+2)}.$$
Sobald also ein Summand bekannt ist, lässt sich der nächste mit konstanter modularer Arithmetik berechnen. Gleichzeitig wird \(2^k\) bei jedem Schritt \(k\to k+2\) mit \(4\) multipliziert, während \((-1)^k\) wegen der festen Parität unverändert bleibt.
Hier ist \(m+n=6\), also \(t=3\), und die zulässigen Werte von \(k\) sind \(1\) und \(3\).
Für \(k=1\) gilt
$$T_1=\frac{3!}{1!\,1!\,1!}=6,\qquad R_1=\frac{2^1+2(-1)^1}{3}=0.$$
Alle Anordnungen mit genau einem gemischten Paar tragen also nichts bei, weil ein einzelnes nichttriviales Element der Ordnung \(3\) nicht die Identität sein kann.
Für \(k=3\) erhält man
$$T_3=\frac{3!}{0!\,0!\,3!}=1,\qquad R_3=\frac{2^3+2(-1)^3}{3}=2.$$
Somit folgt
$$F(3,3)=1\cdot 2=2.$$
Die beiden Wörter sind die vollständig alternierenden:
$$ABABAB,\qquad BABABA.$$
Die C++-, Python- und Java-Implementierungen werten alle dieselbe Formel modulo \(1234567891\) aus. Zuerst wird der Paritätstest durchgeführt: Ist \(m+n\) ungerade, so ist die Antwort sofort \(0\). Andernfalls setzt die Implementierung \(t=(m+n)/2\) und beginnt beim kleinsten zulässigen \(k\).
Der Anfangsfaktor \(T_{k_0}\) wird über einen Binomialkoeffizienten modulo \(M\) berechnet. Weil dabei Divisionen auftreten, verwendet die Implementierung modulare Inversen unter dem Primmodul, gewonnen durch schnelle Potenzierung. Um nicht für jeden Nenner separat ein Inverses zu berechnen, werden Inverse ganzer aufeinanderfolgender Bereiche blockweise vorbereitet und im Produkt wiederverwendet.
Danach läuft das Programm über \(k,k+2,k+4,\dots\). In jedem Schritt aktualisiert es den aktuellen multinomialen Faktor mit dem Quotienten
$$\frac{(m-k)(n-k)}{4(k+1)(k+2)}$$
aktualisiert die Potenz \(2^k\) durch Multiplikation mit \(4\), multipliziert mit dem modularen Inversen von \(3\) und addiert den aktuellen Beitrag zur laufenden Summe. So wird die geschlossene Formel direkt ausgewertet, ohne jemals eine große \(O(mn)\)-Tabelle über die sechs Zustände von \(S_3\) aufzubauen.
Die Anzahl zulässiger \(k\)-Werte ist \(1+\left\lfloor\frac{\min(m,n)-k_0}{2}\right\rfloor\); die Hauptsumme ist also linear in \(\min(m,n)\). Auch die Berechnung des anfänglichen Binomialfaktors ist linear in der kleineren Halbanzahl. Insgesamt ergibt sich somit eine Laufzeit von \(O(\min(m,n))\) modularen Multiplikationen.
Gespeichert werden nur wenige Skalare sowie ein temporärer Block modularer Inversen. Bezeichnet \(B\) die Blockgröße, dann ist der zusätzliche Speicher \(O(B)\). Wird \(B\) als feste technische Konstante betrachtet, ist der Arbeitspeicher bezüglich \(m\) und \(n\) effektiv konstant.
Üç dikey çizgi ve iki komşu takası vardır. \(A\) işlemi birinci ve ikinci çizgiyi, \(B\) işlemi ise ikinci ve üçüncü çizgiyi yer değiştirir. Tam olarak \(m\) tane \(A\) ve tam olarak \(n\) tane \(B\) içeren tüm sözcükler arasında, toplam permütasyonu birim dönüşüm olanları saymamız gerekir.
Cevap \(M=1234567891\) modunda istenir. Önekler ve altı permütasyon durumu üzerinde doğrudan bir dinamik program ancak çok küçük örneklerde işe yarar. Büyük girdilerde asıl fikir, sözcüğü ardışık ikililere bölmek ve bu ikili yapıyı kapalı biçimde saymaktır.
\(S_3\) simetrik grubunda çalışıyoruz:
$$A=(12),\qquad B=(23).$$
Her iki üreteç de transpozisyon olduğu için tek permütasyondur. Birim permütasyon ise çifttir. Bu yüzden \(m+n\) tekse hiçbir sözcük birime eşit olamaz ve
$$F(m,n)=0$$
olur. Bundan sonra \(m+n\)'nin çift olduğunu varsayalım ve
$$m+n=2t,\qquad t=\frac{m+n}{2}$$
yazalım.
Uzunluğu \(2t\) olan her sözcüğü \(t\) adet komşu blok halinde yazabiliriz:
$$\bigl(x_1x_2\bigr)\bigl(x_3x_4\bigr)\cdots\bigl(x_{2t-1}x_{2t}\bigr),\qquad x_i\in\{A,B\}.$$
Şimdi
$$e=\text{birim},\qquad r=AB=(123),\qquad r^2=BA=(132)$$
tanımlarını yapalım. O zaman her ikili blok \(\{e,r,r^2\}\) çevrimsel alt grubunda kalır; çünkü
$$AA=e,\qquad BB=e,\qquad AB=r,\qquad BA=r^2.$$
\(t\) bloktan tam \(k\) tanesi karışık, yani \(AB\) veya \(BA\) olsun. Geri kalanlar zorunlu olarak nötr bloklar \(AA\) ve \(BB\) olur. Sayıları
$$u=\frac{m-k}{2},\qquad v=\frac{n-k}{2}$$
şeklinde belirlenir. Böylece \(k\) için geçerli koşullar
$$0\le k\le \min(m,n),\qquad k\equiv m\pmod 2$$
olur. Sabit bir \(k\) için, \(t\) blok konumundan hangilerinin \(AA\), hangilerinin \(BB\), hangilerinin karışık olduğunu seçme sayısı şu multinom katsayısıdır:
$$T_k=\frac{t!}{u!\,v!\,k!}=\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}.$$
Bu katsayı blok yerleşimini sayar; fakat karışık blokların kendi içindeki \(AB\) ve \(BA\) yönlerini henüz ayırmaz.
\(k\) karışık konumun tam \(j\) tanesi \(AB=r\), kalan \(k-j\) tanesi \(BA=r^2\) olsun. Bu karışık blokların çarpımı
$$r^j(r^2)^{k-j}=r^{j+2(k-j)}=r^{2j-k}$$
olur. Bunun birim olması için
$$2j-k\equiv 0\pmod 3$$
gerekir. Dolayısıyla \(k\) karışık bloğun geçerli yön sayısı
$$R_k=\sum_{\substack{0\le j\le k\\2j-k\equiv 0\pmod 3}}\binom{k}{j}$$
şeklindedir. Bu toplam kök-birlik filtresiyle kapalı forma indirgenir. \(\omega\neq 1\) ve \(\omega^3=1\) olacak şekilde bir karmaşık küpkök alırsak,
$$R_k=\frac{1}{3}\sum_{q=0}^{2}\omega^{-2kq}(1+\omega^q)^k$$
ve buradan
$$R_k=\frac{2^k+2(-1)^k}{3}$$
elde edilir.
Her geçerli \(k\) için blok yerleşimi ile karışık blokların yön seçimleri birbirinden bağımsızdır. Bu nedenle
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}} T_k\,R_k \pmod{M}$$
olur. Açık form yazılırsa
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}}\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}\cdot\frac{2^k+2(-1)^k}{3}\pmod{M}.$$
Uygulamaların değerlendirdiği kapalı toplam tam olarak budur.
\(k_0=m\bmod 2\), yani izin verilen en küçük \(k\) olsun. Başlangıçtaki kombinatoryal katsayı
$$T_{k_0}= \begin{cases} \binom{t}{m/2}, & k_0=0,\\ t\binom{t-1}{(m-1)/2}, & k_0=1 \end{cases}$$
şeklindedir. Sonraki terimler için oran
$$\frac{T_{k+2}}{T_k}=\frac{(m-k)(n-k)}{4(k+1)(k+2)}$$
olur. Yani bir terim biliniyorsa sonraki terim sabit sayıda modüler işlemle bulunur. Ayrıca \(k\) her adımda \(2\) arttığı için \(2^k\) her defasında \(4\) ile çarpılır; buna karşılık \((-1)^k\) parite değişmediği için sabit kalır.
Burada \(m+n=6\) olduğundan \(t=3\) ve geçerli \(k\) değerleri \(1\) ile \(3\)'tür.
\(k=1\) için
$$T_1=\frac{3!}{1!\,1!\,1!}=6,\qquad R_1=\frac{2^1+2(-1)^1}{3}=0.$$
Demek ki tam bir karışık blok içeren bütün yerleşimler sıfır katkı verir; çünkü mertebesi \(3\) olan tek bir gayri trivial eleman birim olamaz.
\(k=3\) için ise
$$T_3=\frac{3!}{0!\,0!\,3!}=1,\qquad R_3=\frac{2^3+2(-1)^3}{3}=2.$$
Dolayısıyla
$$F(3,3)=1\cdot 2=2$$
olur. Bu iki sözcük tamamen alternanslı olanlardır:
$$ABABAB,\qquad BABABA.$$
C++, Python ve Java uygulamaları aynı formülü \(1234567891\) modunda hesaplar. Önce parite testi yapılır; \(m+n\) tekse cevap doğrudan \(0\) döner. Çift durumda \(t=(m+n)/2\) alınır ve en küçük geçerli \(k\) değerinden başlanır.
Başlangıç katsayısı \(T_{k_0}\), \(M\) modunda bir binom katsayısı olarak hesaplanır. Bölme gerektiği için uygulama asal mod altında modüler tersler kullanır ve bunları hızlı üs alma ile elde eder. Her payda için ayrı ters hesaplamamak adına, ardışık uzun aralıkların tersleri bloklar halinde hazırlanır ve çarpım sırasında tekrar kullanılır.
Daha sonra program \(k,k+2,k+4,\dots\) boyunca ilerler. Her adımda güncel multinom katsayısını
$$\frac{(m-k)(n-k)}{4(k+1)(k+2)}$$
oranıyla günceller, \(2^k\) çarpanını \(4\) ile ilerletir, \(3\)'ün modüler tersini uygular ve o adımdaki katkıyı toplam cevaba ekler. Böylece altı durumlu büyük bir \(O(mn)\) dinamik program tablosu kurmadan kapalı toplam doğrudan hesaplanmış olur.
Geçerli \(k\) sayısı \(1+\left\lfloor\frac{\min(m,n)-k_0}{2}\right\rfloor\) kadardır; dolayısıyla ana toplam \(\min(m,n)\) cinsinden lineerdir. Başlangıç binom katsayısının hesaplanması da daha küçük yarı-sayım kadar lineer maliyetlidir. Toplam çalışma süresi bu nedenle \(O(\min(m,n))\) modüler çarpma düzeyindedir.
Uygulama yalnızca birkaç skaler değer ve geçici bir modüler ters bloğu saklar. Blok boyutuna \(B\) dersek ek bellek \(O(B)\) olur. \(B\) sabit bir mühendislik parametresi kabul edilirse, çalışma belleği \(m\) ve \(n\)'ye göre pratikte sabittir.
Hay tres líneas verticales y dos intercambios adyacentes permitidos. La operación \(A\) intercambia la primera y la segunda línea, mientras que \(B\) intercambia la segunda y la tercera. Entre todas las palabras con exactamente \(m\) letras \(A\) y exactamente \(n\) letras \(B\), debemos contar las que producen la permutación identidad.
La respuesta se pide módulo \(M=1234567891\). Una programación dinámica directa sobre prefijos y las seis permutaciones sólo sirve para comprobar casos diminutos. Para los tamaños reales, la idea clave es agrupar la palabra en pares consecutivos y contar esa estructura de pares de forma cerrada.
Trabajamos en el grupo simétrico \(S_3\):
$$A=(12),\qquad B=(23).$$
Ambos generadores son transposiciones, así que son permutaciones impares. La identidad es par. Por tanto, si \(m+n\) es impar, ningún producto puede ser la identidad y
$$F(m,n)=0.$$
Desde ahora supongamos que \(m+n\) es par y escribamos
$$m+n=2t,\qquad t=\frac{m+n}{2}.$$
Cualquier palabra de longitud \(2t\) puede partirse en \(t\) bloques adyacentes:
$$\bigl(x_1x_2\bigr)\bigl(x_3x_4\bigr)\cdots\bigl(x_{2t-1}x_{2t}\bigr),\qquad x_i\in\{A,B\}.$$
Definimos
$$e=\text{identidad},\qquad r=AB=(123),\qquad r^2=BA=(132).$$
Cada par cae en el subgrupo cíclico \(\{e,r,r^2\}\), porque
$$AA=e,\qquad BB=e,\qquad AB=r,\qquad BA=r^2.$$
Supongamos que exactamente \(k\) de los \(t\) pares son mixtos, es decir, del tipo \(AB\) o \(BA\). Los demás deben ser pares neutros \(AA\) y \(BB\). Sus cantidades quedan determinadas por
$$u=\frac{m-k}{2},\qquad v=\frac{n-k}{2}.$$
Así, \(k\) es admisible exactamente cuando
$$0\le k\le \min(m,n),\qquad k\equiv m\pmod 2.$$
Una vez fijado \(k\), el número de maneras de decidir qué posiciones de los \(t\) pares son \(AA\), cuáles son \(BB\) y cuáles son mixtas es el coeficiente multinomial
$$T_k=\frac{t!}{u!\,v!\,k!}=\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}.$$
Este factor cuenta la disposición de bloques, pero todavía no distingue entre \(AB\) y \(BA\) dentro de cada bloque mixto.
Entre las \(k\) posiciones mixtas, supongamos que exactamente \(j\) son \(AB=r\) y las restantes \(k-j\) son \(BA=r^2\). El producto de esos bloques es
$$r^j(r^2)^{k-j}=r^{j+2(k-j)}=r^{2j-k}.$$
Esto es la identidad exactamente cuando
$$2j-k\equiv 0\pmod 3.$$
Por lo tanto, el número de orientaciones válidas de los \(k\) bloques mixtos es
$$R_k=\sum_{\substack{0\le j\le k\\2j-k\equiv 0\pmod 3}}\binom{k}{j}.$$
Esta suma admite una forma cerrada elegante. Si \(\omega\neq 1\) es una raíz cúbica compleja de la unidad con \(\omega^3=1\), entonces un filtro de raíces de la unidad da
$$R_k=\frac{1}{3}\sum_{q=0}^{2}\omega^{-2kq}(1+\omega^q)^k.$$
Al evaluar los tres términos obtenemos
$$R_k=\frac{2^k+2(-1)^k}{3}.$$
Para cada \(k\) admisible, la elección del tipo de bloque y la elección de las orientaciones mixtas son independientes. En consecuencia,
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}} T_k\,R_k \pmod{M}.$$
Sustituyendo las fórmulas explícitas,
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}}\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}\cdot\frac{2^k+2(-1)^k}{3}\pmod{M}.$$
Ésta es exactamente la suma cerrada que evalúan las implementaciones.
Sea \(k_0=m\bmod 2\), el menor valor admisible de \(k\). El factor combinatorio inicial es
$$T_{k_0}= \begin{cases} \binom{t}{m/2}, & k_0=0,\\ t\binom{t-1}{(m-1)/2}, & k_0=1. \end{cases}$$
Para los términos siguientes, el cociente entre dos valores admisibles consecutivos es
$$\frac{T_{k+2}}{T_k}=\frac{(m-k)(n-k)}{4(k+1)(k+2)}.$$
Así, una vez conocido un sumando, el siguiente se obtiene con aritmética modular de costo constante. Además, al aumentar \(k\) en \(2\), el factor \(2^k\) se multiplica por \(4\), mientras que \((-1)^k\) no cambia porque la paridad de \(k\) permanece fija.
Aquí \(m+n=6\), así que \(t=3\), y los valores admisibles de \(k\) son \(1\) y \(3\).
Para \(k=1\),
$$T_1=\frac{3!}{1!\,1!\,1!}=6,\qquad R_1=\frac{2^1+2(-1)^1}{3}=0.$$
Por tanto, todas las disposiciones con exactamente un par mixto aportan cero, porque un único elemento no trivial de orden \(3\) nunca puede ser la identidad.
Para \(k=3\),
$$T_3=\frac{3!}{0!\,0!\,3!}=1,\qquad R_3=\frac{2^3+2(-1)^3}{3}=2.$$
Luego
$$F(3,3)=1\cdot 2=2.$$
Las dos palabras son las completamente alternantes:
$$ABABAB,\qquad BABABA.$$
Las implementaciones en C++, Python y Java evalúan la misma fórmula módulo \(1234567891\). Primero realizan la prueba de paridad: si \(m+n\) es impar, la respuesta es \(0\). En el caso par fijan \(t=(m+n)/2\) y comienzan con el menor valor admisible de \(k\).
El factor inicial \(T_{k_0}\) se calcula mediante un coeficiente binomial módulo \(M\). Como aparecen divisiones, la implementación usa inversos modulares bajo el módulo primo y los obtiene por exponenciación rápida. Para evitar calcular un inverso separado para cada denominador, prepara por bloques los inversos de rangos consecutivos largos y los reutiliza en el producto.
Después el programa recorre \(k,k+2,k+4,\dots\). En cada paso actualiza el factor multinomial actual con la razón
$$\frac{(m-k)(n-k)}{4(k+1)(k+2)}$$
actualiza la potencia \(2^k\) multiplicando por \(4\), aplica el inverso modular de \(3\) y suma la contribución actual al acumulado. De este modo evalúa la fórmula cerrada de forma directa y evita construir una tabla grande \(O(mn)\) sobre los seis estados de \(S_3\).
El número de valores admisibles de \(k\) es \(1+\left\lfloor\frac{\min(m,n)-k_0}{2}\right\rfloor\), así que la suma principal es lineal en \(\min(m,n)\). El cálculo del binomial inicial también es lineal en la mitad menor correspondiente. En conjunto, el tiempo total es \(O(\min(m,n))\) multiplicaciones modulares.
Las implementaciones guardan sólo unos pocos escalares y un bloque temporal de inversos modulares. Si el tamaño del bloque es \(B\), la memoria extra es \(O(B)\). Si \(B\) se considera una constante de ingeniería fija, la memoria de trabajo es esencialmente constante respecto de \(m\) y \(n\).
题目中有三条竖线，以及两种相邻交换操作。操作 \(A\) 交换第一条和第二条线，操作 \(B\) 交换第二条和第三条线。在所有恰好包含 \(m\) 个 \(A\) 与 \(n\) 个 \(B\) 的操作序列中，我们要统计最终总置换仍然是恒等置换的序列个数。
答案按 \(M=1234567891\) 取模。若直接对前缀长度和六个置换状态做动态规划，只能处理很小的检验样例。真正有效的方法是把整个序列按相邻两个字符一组压缩成长度为 \(2\) 的块，然后直接对这些块做组合计数。
在对称群 \(S_3\) 中记
$$A=(12),\qquad B=(23).$$
\(A\) 和 \(B\) 都是换位，因此都是奇置换，而恒等置换是偶置换。所以如果 \(m+n\) 是奇数，那么任何这样的乘积都不可能等于恒等置换，于是
$$F(m,n)=0.$$
下面只讨论 \(m+n\) 为偶数的情形，并记
$$m+n=2t,\qquad t=\frac{m+n}{2}.$$
长度为 \(2t\) 的任意序列都可以拆成 \(t\) 个相邻块：
$$\bigl(x_1x_2\bigr)\bigl(x_3x_4\bigr)\cdots\bigl(x_{2t-1}x_{2t}\bigr),\qquad x_i\in\{A,B\}.$$
再定义
$$e=\text{恒等元},\qquad r=AB=(123),\qquad r^2=BA=(132).$$
这样每一个长度为 \(2\) 的块都会落在循环子群 \(\{e,r,r^2\}\) 中，因为
$$AA=e,\qquad BB=e,\qquad AB=r,\qquad BA=r^2.$$
设这 \(t\) 个块中恰好有 \(k\) 个是混合块，也就是类型为 \(AB\) 或 \(BA\)。那么剩下的块只能是中性块 \(AA\) 与 \(BB\)，而它们的数量已经被 \(m,n,k\) 唯一确定：
$$u=\frac{m-k}{2},\qquad v=\frac{n-k}{2}.$$
因此 \(k\) 合法的充要条件是
$$0\le k\le \min(m,n),\qquad k\equiv m\pmod 2.$$
当 \(k\) 固定后，从 \(t\) 个位置中决定哪些是 \(AA\)、哪些是 \(BB\)、哪些是混合块的方案数就是多项式系数
$$T_k=\frac{t!}{u!\,v!\,k!}=\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}.$$
这个因子只统计块类型的分布，还没有区分混合块内部到底是 \(AB\) 还是 \(BA\)。
在这 \(k\) 个混合块中，设有恰好 \(j\) 个是 \(AB=r\)，其余 \(k-j\) 个是 \(BA=r^2\)。这些混合块的乘积为
$$r^j(r^2)^{k-j}=r^{j+2(k-j)}=r^{2j-k}.$$
它等于恒等元当且仅当
$$2j-k\equiv 0\pmod 3.$$
于是，固定 \(k\) 时，混合块方向的有效选择数为
$$R_k=\sum_{\substack{0\le j\le k\\2j-k\equiv 0\pmod 3}}\binom{k}{j}.$$
这个和式可以用单位根筛化简。取 \(\omega\neq 1\) 且 \(\omega^3=1\) 的复立方单位根，则
$$R_k=\frac{1}{3}\sum_{q=0}^{2}\omega^{-2kq}(1+\omega^q)^k.$$
把三个项分别化简后得到非常整洁的结果
$$R_k=\frac{2^k+2(-1)^k}{3}.$$
这一步正是公式中看起来最神秘的那一项的来源：它不是凭空猜出的，而是混合块在三阶循环群里乘积为单位元的计数。
对每个合法的 \(k\)，块类型的排列与混合块内部方向的选择彼此独立，因此总数就是两部分相乘再求和：
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}} T_k\,R_k \pmod{M}.$$
代入显式表达式后，得到
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}}\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}\cdot\frac{2^k+2(-1)^k}{3}\pmod{M}.$$
这就是程序实际计算的闭式求和。整个问题已经从“枚举所有长度为 \(m+n\) 的字”转化为“枚举合法的混合块数 \(k\)”这一维求和。
令 \(k_0=m\bmod 2\)，也就是最小的合法 \(k\)。此时初始组合因子为
$$T_{k_0}= \begin{cases} \binom{t}{m/2}, & k_0=0,\\ t\binom{t-1}{(m-1)/2}, & k_0=1. \end{cases}$$
接下来不必每次都重新计算阶乘，只要利用相邻合法项之间的比值：
$$\frac{T_{k+2}}{T_k}=\frac{(m-k)(n-k)}{4(k+1)(k+2)}.$$
因此一旦知道某个 \(k\) 的项，就能用常数次模运算得到下一个 \(k+2\) 的项。另外，当 \(k\) 每次增加 \(2\) 时，\(2^k\) 只需再乘一个 \(4\)，而 \((-1)^k\) 因为奇偶性不变所以始终保持同号。这就是实现能够顺序扫描全部合法 \(k\) 的原因。
此时 \(m+n=6\)，所以 \(t=3\)，合法的 \(k\) 只有 \(1\) 和 \(3\)。
当 \(k=1\) 时，
$$T_1=\frac{3!}{1!\,1!\,1!}=6,\qquad R_1=\frac{2^1+2(-1)^1}{3}=0.$$
也就是说，虽然块的排法有 \(6\) 种，但只要只有一个混合块，它在三阶循环群中不可能乘成恒等元，所以贡献为零。
当 \(k=3\) 时，
$$T_3=\frac{3!}{0!\,0!\,3!}=1,\qquad R_3=\frac{2^3+2(-1)^3}{3}=2.$$
于是
$$F(3,3)=1\cdot 2=2.$$
对应的两个序列正好是完全交替的两个：
$$ABABAB,\qquad BABABA.$$
C++、Python 和 Java 实现都在模 \(1234567891\) 下计算同一个求和公式。程序先判断 \(m+n\) 的奇偶性；如果总长度为奇数，答案立刻就是 \(0\)。否则先算出 \(t=(m+n)/2\)，并从最小合法的 \(k\) 开始。
初始项 \(T_{k_0}\) 通过模 \(M\) 下的二项式系数得到。由于其中涉及除法，实现采用素数模下的模逆元，并通过快速幂求出。为了避免对每个分母都单独做一次求逆，程序会按连续区间成批预处理逆元，然后在乘积过程中复用这些结果。
随后程序依次遍历 \(k,k+2,k+4,\dots\)。每一步都利用
$$\frac{(m-k)(n-k)}{4(k+1)(k+2)}$$
更新当前的组合因子，把 \(2^k\) 乘上 \(4\)，再乘以 \(3\) 的模逆，并把当前贡献加入答案。整个过程只保留当前项和少量辅助数据，因此完全不需要构造一个规模为 \(O(mn)\) 的六状态动态规划表。
合法的 \(k\) 个数为 \(1+\left\lfloor\frac{\min(m,n)-k_0}{2}\right\rfloor\)，所以主循环对 \(\min(m,n)\) 是线性的。初始二项式因子的计算也只需要与较小半计数同阶的模乘次数，因此总时间复杂度为 \(O(\min(m,n))\)。
实现中只保存少量标量以及一块临时逆元缓冲区。若块大小记为 \(B\)，额外空间为 \(O(B)\)；若把 \(B\) 看成固定的工程参数，那么相对于 \(m\) 与 \(n\) 的增长，工作内存可视为常数级。
Есть три вертикальные линии и две допустимые соседние перестановки. Операция \(A\) меняет местами первую и вторую линии, а операция \(B\) меняет местами вторую и третью. Среди всех слов, содержащих ровно \(m\) букв \(A\) и ровно \(n\) букв \(B\), нужно посчитать те, чья итоговая перестановка равна тождественной.
Ответ требуется по модулю \(M=1234567891\). Прямая динамика по префиксам и шести состояниям группы подходит только для очень маленьких проверок. Для больших входов нужно сгруппировать слово в соседние пары и посчитать уже эти пары в явном виде.
Работаем в симметрической группе \(S_3\):
$$A=(12),\qquad B=(23).$$
Оба генератора являются транспозициями, то есть нечётными перестановками. Тождественная перестановка чётная. Значит, если \(m+n\) нечётно, то никакое слово не может дать тождество, и
$$F(m,n)=0.$$
Далее предполагаем, что \(m+n\) чётно, и пишем
$$m+n=2t,\qquad t=\frac{m+n}{2}.$$
Любое слово длины \(2t\) разбивается на \(t\) соседних блоков длины \(2\):
$$\bigl(x_1x_2\bigr)\bigl(x_3x_4\bigr)\cdots\bigl(x_{2t-1}x_{2t}\bigr),\qquad x_i\in\{A,B\}.$$
Обозначим
$$e=\text{тождество},\qquad r=AB=(123),\qquad r^2=BA=(132).$$
Каждая пара лежит в циклической подгруппе \(\{e,r,r^2\}\), потому что
$$AA=e,\qquad BB=e,\qquad AB=r,\qquad BA=r^2.$$
Пусть ровно \(k\) из \(t\) пар являются смешанными, то есть имеют вид \(AB\) или \(BA\). Тогда оставшиеся пары обязаны быть нейтральными \(AA\) и \(BB\), а их количества равны
$$u=\frac{m-k}{2},\qquad v=\frac{n-k}{2}.$$
Следовательно, допустимые значения \(k\) задаются условиями
$$0\le k\le \min(m,n),\qquad k\equiv m\pmod 2.$$
Для фиксированного \(k\) число способов выбрать, какие позиции среди \(t\) пар являются \(AA\), какие \(BB\), а какие смешанными, равно мультиномиальному коэффициенту
$$T_k=\frac{t!}{u!\,v!\,k!}=\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}.$$
Этот множитель считает только расположение типов блоков и ещё не различает ориентации \(AB\) и \(BA\) внутри смешанных пар.
Пусть среди \(k\) смешанных позиций ровно \(j\) блоков равны \(AB=r\), а остальные \(k-j\) равны \(BA=r^2\). Тогда произведение этих блоков равно
$$r^j(r^2)^{k-j}=r^{j+2(k-j)}=r^{2j-k}.$$
Оно совпадает с тождеством тогда и только тогда, когда
$$2j-k\equiv 0\pmod 3.$$
Поэтому число допустимых ориентаций для \(k\) смешанных блоков равно
$$R_k=\sum_{\substack{0\le j\le k\\2j-k\equiv 0\pmod 3}}\binom{k}{j}.$$
У этой суммы есть компактная замкнутая форма. Пусть \(\omega\neq 1\) и \(\omega^3=1\), то есть \(\omega\) является комплексным кубическим корнем из единицы. Тогда фильтр корней из единицы даёт
$$R_k=\frac{1}{3}\sum_{q=0}^{2}\omega^{-2kq}(1+\omega^q)^k.$$
После вычисления трёх слагаемых получаем
$$R_k=\frac{2^k+2(-1)^k}{3}.$$
Для каждого допустимого \(k\) выбор расположения блоков и выбор ориентаций смешанных блоков независимы. Значит,
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}} T_k\,R_k \pmod{M}.$$
Подставляя явные выражения, получаем
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}}\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}\cdot\frac{2^k+2(-1)^k}{3}\pmod{M}.$$
Именно эту замкнутую сумму вычисляют реализации.
Пусть \(k_0=m\bmod 2\) — минимальное допустимое значение \(k\). Тогда начальный комбинаторный множитель имеет вид
$$T_{k_0}= \begin{cases} \binom{t}{m/2}, & k_0=0,\\ t\binom{t-1}{(m-1)/2}, & k_0=1. \end{cases}$$
Для следующих допустимых значений отношение соседних членов равно
$$\frac{T_{k+2}}{T_k}=\frac{(m-k)(n-k)}{4(k+1)(k+2)}.$$
Значит, зная один член суммы, следующий можно получить за константное число модульных операций. Кроме того, при переходе \(k\to k+2\) множитель \(2^k\) просто умножается на \(4\), а знак \((-1)^k\) не меняется, потому что чётность \(k\) во всём цикле фиксирована.
Здесь \(m+n=6\), следовательно \(t=3\), а допустимые значения \(k\) равны \(1\) и \(3\).
Для \(k=1\) имеем
$$T_1=\frac{3!}{1!\,1!\,1!}=6,\qquad R_1=\frac{2^1+2(-1)^1}{3}=0.$$
То есть все раскладки с одной смешанной парой дают нулевой вклад, потому что одиночный нетривиальный элемент порядка \(3\) не может совпасть с тождеством.
Для \(k=3\) получаем
$$T_3=\frac{3!}{0!\,0!\,3!}=1,\qquad R_3=\frac{2^3+2(-1)^3}{3}=2.$$
Следовательно,
$$F(3,3)=1\cdot 2=2.$$
Этими двумя словами являются полностью чередующиеся варианты
$$ABABAB,\qquad BABABA.$$
Реализации на C++, Python и Java вычисляют одну и ту же формулу по модулю \(1234567891\). Сначала выполняется проверка чётности: если \(m+n\) нечётно, ответ немедленно равен \(0\). В чётном случае программа вычисляет \(t=(m+n)/2\) и начинает с минимального допустимого \(k\).
Начальный множитель \(T_{k_0}\) находится через биномиальный коэффициент по модулю \(M\). Поскольку требуется деление, реализация использует обратные элементы по простому модулю и получает их быстрым возведением в степень. Чтобы не вычислять обратный элемент отдельно для каждого знаменателя, программа заранее строит обратные значения для длинных последовательных диапазонов и переиспользует их в произведении.
Затем цикл проходит по \(k,k+2,k+4,\dots\). На каждом шаге текущий мультиномиальный множитель обновляется по формуле
$$\frac{(m-k)(n-k)}{4(k+1)(k+2)}$$
степень \(2^k\) умножается на \(4\), применяется обратный элемент к \(3\), и вклад текущего члена прибавляется к накопленному ответу. Поэтому вычисление идёт напрямую по закрытой формуле и не строит большую таблицу \(O(mn)\) по шести состояниям группы \(S_3\).
Число допустимых значений \(k\) равно \(1+\left\lfloor\frac{\min(m,n)-k_0}{2}\right\rfloor\), так что основная сумма линейна по \(\min(m,n)\). Вычисление стартового биномиального множителя тоже линейно по меньшей половинной величине. В итоге общее время работы составляет \(O(\min(m,n))\) модульных умножений.
Реализации хранят лишь несколько скалярных переменных и временный блок обратных элементов. Если обозначить размер блока через \(B\), дополнительная память равна \(O(B)\). При фиксированном инженерном выборе \(B\) рабочая память фактически является константной относительно \(m\) и \(n\).
لدينا ثلاثة خطوط عمودية وعمليتا تبديل متجاورتان فقط. العملية \(A\) تبدّل بين الخطين الأول والثاني، أما العملية \(B\) فتبدّل بين الخطين الثاني والثالث. من بين جميع الكلمات التي تحتوي بالضبط على \(m\) من \(A\) و\(n\) من \(B\)، نريد عدّ الكلمات التي يكون حاصلها الكلي هو تبديل الهوية.
المطلوب هو الجواب بترديد \(M=1234567891\). البرمجة الديناميكية المباشرة على البوادئ وعلى الحالات الست للمجموعة تصلح فقط لاختبارات صغيرة جدًا. أما للحجوم الحقيقية فالفكرة الأساسية هي ضغط الكلمة إلى أزواج متجاورة ثم عدّ هذه الأزواج عدًا تحليليًا.
نعمل داخل المجموعة التناظرية \(S_3\):
$$A=(12),\qquad B=(23).$$
كل من \(A\) و\(B\) تبديل فردي لأنه تبديل ثنائي، بينما الهوية تبديل زوجي. لذلك إذا كان \(m+n\) فرديًا فلا يمكن أن نحصل على الهوية، ومن ثم
$$F(m,n)=0.$$
من الآن فصاعدًا نفترض أن \(m+n\) زوجي، ونكتب
$$m+n=2t,\qquad t=\frac{m+n}{2}.$$
أي كلمة طولها \(2t\) يمكن تقسيمها إلى \(t\) كتل متتابعة:
$$\bigl(x_1x_2\bigr)\bigl(x_3x_4\bigr)\cdots\bigl(x_{2t-1}x_{2t}\bigr),\qquad x_i\in\{A,B\}.$$
لنرمز إلى عنصر الهوية بالحرف \(e\)، ونعرّف أيضًا
$$r=AB=(123),\qquad r^2=BA=(132).$$
كل زوج من الحرفين يقع داخل الزمرة الدورية \(\{e,r,r^2\}\)، لأن
$$AA=e,\qquad BB=e,\qquad AB=r,\qquad BA=r^2.$$
افترض أن بين هذه الكتل \(t\) توجد بالضبط \(k\) كتل مختلطة، أي من النوع \(AB\) أو \(BA\). أما الكتل الباقية فلا بد أن تكون من النوعين المحايدين \(AA\) و\(BB\)، وعددها محدد تمامًا بـ
$$u=\frac{m-k}{2},\qquad v=\frac{n-k}{2}.$$
إذًا يكون \(k\) مقبولًا إذا وفقط إذا تحقق
$$0\le k\le \min(m,n),\qquad k\equiv m\pmod 2.$$
وعند تثبيت \(k\)، فإن عدد الطرق لاختيار مواضع الكتل \(AA\) و\(BB\) والكتل المختلطة بين المواقع \(t\) يساوي المعامل متعدد الحدود
$$T_k=\frac{t!}{u!\,v!\,k!}=\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}.$$
هذا العامل يعدّ ترتيب أنواع الكتل، لكنه لا يميز بعدُ ما إذا كانت الكتلة المختلطة هي \(AB\) أم \(BA\).
داخل المواضع المختلطة \(k\)، لنفترض أن \(j\) منها من النوع \(AB=r\)، والباقي \(k-j\) من النوع \(BA=r^2\). حاصل ضرب هذه الكتل هو
$$r^j(r^2)^{k-j}=r^{j+2(k-j)}=r^{2j-k}.$$
ويكون هذا مساويًا للهوية إذا وفقط إذا
$$2j-k\equiv 0\pmod 3.$$
لذلك فإن عدد الاتجاهات الصحيحة للكتل المختلطة يساوي
$$R_k=\sum_{\substack{0\le j\le k\\2j-k\equiv 0\pmod 3}}\binom{k}{j}.$$
ولهذا المجموع صيغة مغلقة جميلة. إذا كانت \(\omega\neq 1\) جذرًا تكعيبيًا مركبًا للوحدة بحيث \(\omega^3=1\)، فإن مرشح جذور الوحدة يعطي
$$R_k=\frac{1}{3}\sum_{q=0}^{2}\omega^{-2kq}(1+\omega^q)^k.$$
وبتبسيط الحدود الثلاثة نحصل على
$$R_k=\frac{2^k+2(-1)^k}{3}.$$
لكل قيمة مقبولة من \(k\)، يكون اختيار توزيع أنواع الكتل مستقلًا عن اختيار اتجاهات الكتل المختلطة. لذلك
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}} T_k\,R_k \pmod{M}.$$
وبالتعويض عن الصيغ الصريحة نحصل على
$$F(m,n)=\sum_{\substack{0\le k\le \min(m,n)\\k\equiv m\pmod 2}}\frac{t!}{\left(\frac{m-k}{2}\right)!\left(\frac{n-k}{2}\right)!k!}\cdot\frac{2^k+2(-1)^k}{3}\pmod{M}.$$
هذه هي الصيغة المغلقة التي تنفذها التطبيقات مباشرة.
ليكن \(k_0=m\bmod 2\)، أي أصغر قيمة مقبولة لـ \(k\). عندها يكون العامل التركيبي الابتدائي
$$T_{k_0}= \begin{cases} \binom{t}{m/2}, & k_0=0,\\ t\binom{t-1}{(m-1)/2}, & k_0=1. \end{cases}$$
أما للعناصر اللاحقة فإن نسبة حدين متتاليين مقبولين تساوي
$$\frac{T_{k+2}}{T_k}=\frac{(m-k)(n-k)}{4(k+1)(k+2)}.$$
هذا يعني أن معرفة حد واحد تكفي للحصول على الحد التالي بعدد ثابت من العمليات المعيارية. كذلك، عند الانتقال من \(k\) إلى \(k+2\)، فإن العامل \(2^k\) يُحدَّث بالضرب في \(4\)، بينما تبقى \((-1)^k\) ثابتة لأن زوجية \(k\) لا تتغير داخل الحلقة.
هنا لدينا \(m+n=6\)، ولذلك \(t=3\)، والقيم المقبولة لـ \(k\) هي \(1\) و\(3\).
عندما \(k=1\)، نجد
$$T_1=\frac{3!}{1!\,1!\,1!}=6,\qquad R_1=\frac{2^1+2(-1)^1}{3}=0.$$
إذن جميع الترتيبات التي تحتوي على كتلة مختلطة واحدة فقط تعطي مساهمة صفرية، لأن عنصرًا واحدًا غير بديهي من رتبة \(3\) لا يمكن أن يكون هوية.
وعندما \(k=3\)، نحصل على
$$T_3=\frac{3!}{0!\,0!\,3!}=1,\qquad R_3=\frac{2^3+2(-1)^3}{3}=2.$$
ومن ثم
$$F(3,3)=1\cdot 2=2.$$
والكلمتان هما النمطان المتناوبان بالكامل:
$$ABABAB,\qquad BABABA.$$
تقيّم تطبيقات C++ وPython وJava الصيغة نفسها بترديد \(1234567891\). تبدأ الشيفرة بفحص زوجية \(m+n\)؛ فإذا كان المجموع فرديًا كان الجواب \(0\) مباشرة. وإذا كان زوجيًا تُحسب القيمة \(t=(m+n)/2\) ثم يبدأ المسح من أصغر \(k\) مقبول.
يُحسب العامل الابتدائي \(T_{k_0}\) على هيئة معامل ثنائي بترديد \(M\). وبما أن ذلك يتطلب قسمة معيارية، فإن التنفيذ يستخدم المعكوسات المعيارية تحت هذا الترديد الأولي ويحسبها بالرفع السريع للأس. ولتفادي حساب معكوس مستقل لكل مقام، تُبنى معكوسات مقاطع متتالية طويلة على شكل دفعات ثم يُعاد استخدامها داخل الضرب التراكمي.
بعد ذلك تتحرك الشيفرة عبر القيم \(k,k+2,k+4,\dots\). في كل خطوة تُحدِّث العامل متعدد الحدود الحالي بالنسبة
$$\frac{(m-k)(n-k)}{4(k+1)(k+2)}$$
وتحدّث \(2^k\) بالضرب في \(4\)، ثم تطبق المعكوس المعياري للعدد \(3\)، وتضيف مساهمة الحد الحالي إلى الجواب النهائي. وبذلك تُحسب الصيغة المغلقة مباشرة من غير بناء جدول برمجة ديناميكية ضخم من رتبة \(O(mn)\) على الحالات الست للمجموعة \(S_3\).
عدد قيم \(k\) المقبولة يساوي \(1+\left\lfloor\frac{\min(m,n)-k_0}{2}\right\rfloor\)، ولذلك فإن حلقة الجمع الرئيسية خطية في \(\min(m,n)\). كما أن حساب المعامل الثنائي الابتدائي خطي هو الآخر في النصف الأصغر الموافق. لذا يكون الزمن الكلي \(O(\min(m,n))\) من الضربات المعيارية.
لا تحتفظ التطبيقات إلا بعدد قليل من القيم العددية ودفعة مؤقتة من المعكوسات المعيارية. إذا رمزنا إلى حجم الدفعة بـ \(B\)، فإن الذاكرة الإضافية هي \(O(B)\). وإذا عومل \(B\) على أنه ثابت هندسي اختير مسبقًا، فإن الذاكرة العملية تكون شبه ثابتة بالنسبة إلى \(m\) و\(n\).