We are given \(p\) copies of \(A\), \(q\) copies of \(B\), and \(r\) copies of \(C\). A word is valid if every \(A\) and every \(B\) have at least two \(C\)'s between them. The task is to count all valid words and return the answer modulo \(10^9+7\).
The brute-force space has size \(\binom{p+q+r}{p,q,r}\), so direct enumeration is impossible for the real parameters. The key simplification is that the exact positions of the \(C\)'s matter only through how many times the word switches between \(A\) and \(B\) after all \(C\)'s are removed.
Let \(W(p,q,r)\) denote the number of valid words built from \(p\) letters \(A\), \(q\) letters \(B\), and \(r\) letters \(C\).
Set
$$m=p+q.$$
If we delete every \(C\) from a word, the remaining letters form a binary skeleton
$$s_1s_2\dots s_m,\qquad s_i\in\{A,B\},$$
with exactly \(p\) letters \(A\) and \(q\) letters \(B\). For such a skeleton define its transition count by
$$t(s)=\#\{\,i\in\{1,\dots,m-1\}: s_i\ne s_{i+1}\,\}.$$
This number \(t(s)\) counts how many adjacent boundaries in the skeleton change from \(A\) to \(B\) or from \(B\) to \(A\).
Suppose two consecutive letters of the skeleton are different. In the full word, those two letters become an adjacent \(A/B\) pair once the \(C\)'s between them are ignored, so that boundary must contain at least two \(C\)'s. Otherwise those two letters would violate the rule immediately.
The converse is also true. If every transition boundary of the skeleton receives at least two \(C\)'s, then any \(A\) and any \(B\) in the whole word are separated by at least one such boundary, hence by at least two \(C\)'s in total.
Therefore a skeleton with \(t\) transitions consumes exactly
$$2t$$
mandatory letters \(C\). The whole constraint is reduced to a transition cost.
Let \(N_{p,q}(t)\) be the number of \(A/B\) skeletons with \(p\) letters \(A\), \(q\) letters \(B\), and exactly \(t\) transitions. A skeleton with \(t\) transitions has \(t+1\) runs.
If \(t=2u+1\) is odd, then the word starts and ends with different letters, so it has \(u+1\) runs of \(A\) and \(u+1\) runs of \(B\). Splitting \(p\) into \(u+1\) positive run lengths gives \(\binom{p-1}{u}\) choices, and similarly for \(q\). Since the skeleton may start with either \(A\) or \(B\),
$$N_{p,q}(2u+1)=2\binom{p-1}{u}\binom{q-1}{u}.$$
If \(t=2u\) is even, then the skeleton starts and ends with the same letter. Either \(A\) uses \(u+1\) runs and \(B\) uses \(u\) runs, or the roles are reversed, so
$$N_{p,q}(2u)=\binom{p-1}{u}\binom{q-1}{u-1}+\binom{p-1}{u-1}\binom{q-1}{u}.$$
As usual, we interpret \(\binom{n}{k}=0\) when \(k<0\) or \(k>n\).
Fix a skeleton with \(t\) transitions. After reserving \(2t\) mandatory \(C\)'s, there remain
$$r-2t$$
letters \(C\) to place freely. There are \(m+1\) slots: before the first skeleton letter, after the last one, and one slot between each consecutive pair of skeleton letters.
By the stars-and-bars formula, the number of ways to distribute the remaining \(C\)'s is
$$\binom{(r-2t)+(m+1)-1}{(m+1)-1}=\binom{r-2t+m}{m},$$
provided \(2t\le r\). So every skeleton with the same transition count contributes the same amount.
If one of the letters \(A\) or \(B\) is absent, there is no restriction at all, so
$$W(p,q,r)=\binom{r+m}{m}\qquad\text{when }p=0\text{ or }q=0.$$
Otherwise
$$W(p,q,r)=\sum_{t\ge 1} N_{p,q}(t)\binom{r-2t+m}{m},$$
where terms with \(2t>r\) vanish automatically. Because the count is symmetric in \(p\) and \(q\), the implementation first swaps them so that \(p\le q\). Then the maximum possible transition count is
$$t_{\max}=\min\left(m-1,\left\lfloor\frac{r}{2}\right\rfloor,\begin{cases} 2p-1,& p=q,\\ 2p,& p<q. \end{cases}\right).$$
The last bound is purely combinatorial: the scarcer letter cannot support more alternations than this.
Here \(m=4\). Since both \(A\) and \(B\) are present, we sum over transition counts.
For \(t=1\), the valid skeletons are \(AABB\) and \(BBAA\). Each needs \(2\) mandatory \(C\)'s, leaving \(2\) free \(C\)'s. The number of insertions is
$$\binom{4-2+4}{4}=\binom{6}{4}=15,$$
so the contribution is \(2\cdot 15=30\).
For \(t=2\), the valid skeletons are \(ABBA\) and \(BAAB\). Now all \(4\) letters \(C\) are forced, so the insertion factor is
$$\binom{4-4+4}{4}=\binom{4}{4}=1,$$
and the contribution is \(2\cdot 1=2\).
For \(t=3\), we would need \(6\) letters \(C\), but only \(4\) are available, so this case contributes nothing. Therefore
$$W(2,2,4)=30+2=32,$$
which matches the exact checkpoint used by the implementation.
The C++, Python, and Java implementations all follow the same formula. They first swap the counts so that \(p\le q\), compute \(m=p+q\), and handle the easy case \(p=0\) or \(q=0\) by returning \(\binom{r+m}{m}\) modulo \(10^9+7\).
Instead of building factorial tables up to \(r+m\), the implementation computes
$$\binom{r+m}{m}=\prod_{i=1}^{m}\frac{r+i}{i}\pmod{10^9+7}$$
using modular inverses of \(1,2,\dots,m\). It also builds the short binomial rows \(\binom{p-1}{u}\) and \(\binom{q-1}{u}\) incrementally, which is enough to evaluate the odd and even formulas for \(N_{p,q}(t)\).
The second important recurrence updates the insertion factor without recomputing a fresh binomial coefficient each time:
$$\binom{n-2}{m}=\binom{n}{m}\cdot\frac{(n-m)(n-m-1)}{n(n-1)}.$$
Starting from \(n=r+m\), one loop step moves from transition count \(t-1\) to \(t\). To make the divisions legal modulo \(10^9+7\), the implementation precomputes inverses for the consecutive denominators that appear in this recurrence.
Finally, it loops over \(t=1,\dots,t_{\max}\), evaluates the appropriate run-count formula for \(N_{p,q}(t)\), multiplies by \(\binom{r-2t+m}{m}\), and accumulates the result modulo \(10^9+7\).
After the swap, let \(m=p+q\) and \(t_{\max}\) be the transition limit above. Precomputing inverses up to \(m\) costs \(O(m)\) time and memory. The short binomial tables cost \(O(t_{\max})\), and the final summation over all transition counts also costs \(O(t_{\max})\).
Hence the total complexity is
$$O(m+t_{\max})=O(p+q)$$
time and
$$O(m+t_{\max})=O(p+q)$$
memory. The large value of \(r\) does not create a table of size \(r\); it appears only inside modular products.
Gegeben sind \(p\) Kopien von \(A\), \(q\) Kopien von \(B\) und \(r\) Kopien von \(C\). Ein Wort ist genau dann gültig, wenn zwischen jedem \(A\) und jedem \(B\) mindestens zwei \(C\) liegen. Gesucht ist die Anzahl aller gültigen Wörter modulo \(10^9+7\).
Der brute-force-Raum hat Größe \(\binom{p+q+r}{p,q,r}\) und ist für die echten Parameter unbrauchbar. Entscheidend ist daher, dass nach dem Entfernen aller \(C\) nur noch zählt, wie oft das restliche Wort zwischen \(A\) und \(B\) wechselt.
Bezeichne mit \(W(p,q,r)\) die Anzahl der gültigen Wörter aus \(p\) Buchstaben \(A\), \(q\) Buchstaben \(B\) und \(r\) Buchstaben \(C\).
Setze
$$m=p+q.$$
Wenn man aus einem Wort alle \(C\) löscht, bleibt ein binäres Skelett
$$s_1s_2\dots s_m,\qquad s_i\in\{A,B\},$$
mit genau \(p\) Buchstaben \(A\) und \(q\) Buchstaben \(B\). Dazu definieren wir die Zahl der Übergänge
$$t(s)=\#\{\,i\in\{1,\dots,m-1\}: s_i\ne s_{i+1}\,\}.$$
Diese Größe zählt genau die Stellen, an denen im Skelett von \(A\) nach \(B\) oder von \(B\) nach \(A\) gewechselt wird.
Wenn zwei benachbarte Buchstaben des Skeletts verschieden sind, muss die Lücke zwischen ihnen im vollständigen Wort mindestens zwei \(C\) enthalten. Sonst wäre dieses benachbarte \(A/B\)-Paar selbst schon ein Verstoß gegen die Bedingung.
Umgekehrt reicht diese Bedingung auch aus. Erhält jede Übergangsstelle des Skeletts mindestens zwei \(C\), dann liegt zwischen jedem \(A\) und jedem \(B\) im vollständigen Wort mindestens eine solche Übergangsstelle und damit insgesamt mindestens zwei \(C\).
Ein Skelett mit \(t\) Übergängen verbraucht also genau
$$2t$$
verpflichtende Buchstaben \(C\). Die gesamte Nebenbedingung wird damit zu einer einfachen Übergangskostenregel.
Sei \(N_{p,q}(t)\) die Zahl der \(A/B\)-Skelette mit \(p\) Buchstaben \(A\), \(q\) Buchstaben \(B\) und genau \(t\) Übergängen. Ein Skelett mit \(t\) Übergängen besitzt \(t+1\) Läufe.
Ist \(t=2u+1\) ungerade, dann beginnt und endet das Skelett mit verschiedenen Buchstaben. Es gibt also \(u+1\) Läufe von \(A\) und \(u+1\) Läufe von \(B\). Die Zerlegung von \(p\) in \(u+1\) positive Lauf-Längen liefert \(\binom{p-1}{u}\) Möglichkeiten, und analog für \(q\). Da das Skelett entweder mit \(A\) oder mit \(B\) beginnen kann, gilt
$$N_{p,q}(2u+1)=2\binom{p-1}{u}\binom{q-1}{u}.$$
Ist \(t=2u\) gerade, dann beginnt und endet das Skelett mit demselben Buchstaben. Entweder hat \(A\) genau \(u+1\) Läufe und \(B\) genau \(u\) Läufe, oder umgekehrt. Daher
$$N_{p,q}(2u)=\binom{p-1}{u}\binom{q-1}{u-1}+\binom{p-1}{u-1}\binom{q-1}{u}.$$
Dabei verwenden wir die Konvention \(\binom{n}{k}=0\) für \(k<0\) oder \(k>n\).
Fixiere ein Skelett mit \(t\) Übergängen. Nach Abzug der \(2t\) verpflichtenden \(C\) bleiben
$$r-2t$$
Buchstaben \(C\) frei übrig. Es gibt \(m+1\) Einfügeplätze: vor dem ersten Skelettbuchstaben, nach dem letzten und je einen Platz zwischen zwei aufeinanderfolgenden Skelettbuchstaben.
Mit Stars-and-Bars erhält man für die Zahl der Verteilungen
$$\binom{(r-2t)+(m+1)-1}{(m+1)-1}=\binom{r-2t+m}{m},$$
sofern \(2t\le r\) gilt. Alle Skelette mit gleicher Übergangszahl tragen also denselben Faktor bei.
Falls einer der Buchstaben \(A\) oder \(B\) gar nicht vorkommt, gibt es keine Einschränkung, also
$$W(p,q,r)=\binom{r+m}{m}\qquad\text{für }p=0\text{ oder }q=0.$$
Andernfalls gilt
$$W(p,q,r)=\sum_{t\ge 1} N_{p,q}(t)\binom{r-2t+m}{m}.$$
Da die Anzahl symmetrisch in \(p\) und \(q\) ist, vertauscht die Implementierung die beiden Werte zunächst so, dass \(p\le q\) gilt. Dann ist die maximale mögliche Übergangszahl
$$t_{\max}=\min\left(m-1,\left\lfloor\frac{r}{2}\right\rfloor,\begin{cases} 2p-1,& p=q,\\ 2p,& p<q. \end{cases}\right).$$
Die letzte Schranke ist rein kombinatorisch: Der seltenere Buchstabe kann nur so oft zum Alternieren beitragen.
Hier ist \(m=4\). Weil sowohl \(A\) als auch \(B\) vorkommen, summieren wir über die möglichen Übergangszahlen.
Für \(t=1\) sind die Skelette \(AABB\) und \(BBAA\) möglich. Jedes davon braucht \(2\) verpflichtende \(C\), sodass \(2\) freie \(C\) übrig bleiben. Der Einfügefaktor ist
$$\binom{4-2+4}{4}=\binom{6}{4}=15,$$
also beträgt der Beitrag \(2\cdot 15=30\).
Für \(t=2\) sind die Skelette \(ABBA\) und \(BAAB\) möglich. Jetzt sind alle \(4\) Buchstaben \(C\) schon fest verplant, daher ist der Einfügefaktor
$$\binom{4-4+4}{4}=\binom{4}{4}=1,$$
und der Beitrag ist \(2\cdot 1=2\).
Für \(t=3\) wären \(6\) Buchstaben \(C\) nötig, aber es stehen nur \(4\) zur Verfügung. Dieser Fall trägt also nichts bei. Insgesamt erhält man
$$W(2,2,4)=30+2=32,$$
genau den exakten Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe Formel. Zuerst werden die Häufigkeiten so vertauscht, dass \(p\le q\) gilt, dann wird \(m=p+q\) gesetzt und der einfache Fall \(p=0\) oder \(q=0\) direkt über \(\binom{r+m}{m}\) modulo \(10^9+7\) behandelt.
Anstatt Fakultätstabellen bis \(r+m\) aufzubauen, berechnet die Implementierung
$$\binom{r+m}{m}=\prod_{i=1}^{m}\frac{r+i}{i}\pmod{10^9+7}$$
mit modularen Inversen von \(1,2,\dots,m\). Ebenso werden die kurzen Binomialzeilen \(\binom{p-1}{u}\) und \(\binom{q-1}{u}\) inkrementell aufgebaut; mehr wird für die Formeln von \(N_{p,q}(t)\) nicht benötigt.
Der zweite zentrale Schritt ist eine Rekurrenz für den Einfügefaktor:
$$\binom{n-2}{m}=\binom{n}{m}\cdot\frac{(n-m)(n-m-1)}{n(n-1)}.$$
Beginnend mit \(n=r+m\) führt ein Schleifendurchlauf jeweils von der Übergangszahl \(t-1\) zu \(t\). Damit die Divisionen modulo \(10^9+7\) zulässig sind, werden die Inversen der benötigten aufeinanderfolgenden Nenner vorab berechnet.
Zum Schluss läuft der Code über \(t=1,\dots,t_{\max}\), wertet je nach Parität die passende Formel für \(N_{p,q}(t)\) aus, multipliziert mit \(\binom{r-2t+m}{m}\) und akkumuliert alles modulo \(10^9+7\).
Nach dem Vertauschen sei \(m=p+q\) und \(t_{\max}\) die obige Übergangsschranke. Das Vorberechnen der modularen Inversen bis \(m\) kostet \(O(m)\) Zeit und \(O(m)\) Speicher. Die kurzen Binomialtabellen kosten \(O(t_{\max})\), und ebenso die Summation über alle Übergangszahlen.
Damit ergibt sich insgesamt
$$O(m+t_{\max})=O(p+q)$$
Zeit und
$$O(m+t_{\max})=O(p+q)$$
Speicher. Der sehr große Wert von \(r\) erzeugt also kein Array der Größe \(r\); er taucht nur in modularen Produkten auf.
Elimizde \(p\) adet \(A\), \(q\) adet \(B\) ve \(r\) adet \(C\) vardır. Bir kelime ancak her \(A\) ile her \(B\) arasında en az iki tane \(C\) bulunuyorsa geçerlidir. Amaç, tüm geçerli kelimeleri sayıp sonucu \(10^9+7\) modunda vermektir.
Doğrudan sayım uzayı \(\binom{p+q+r}{p,q,r}\) büyüklüğündedir; gerçek parametrelerde bu yaklaşım imkansızdır. Asıl kilit nokta, bütün \(C\)'ler çıkarıldıktan sonra geriye kalan yapıda yalnızca \(A\) ile \(B\) arasındaki tür değişimlerinin önemli olmasıdır.
\(p\) adet \(A\), \(q\) adet \(B\) ve \(r\) adet \(C\) ile oluşturulabilen geçerli kelime sayısını \(W(p,q,r)\) ile gösterelim.
Önce
$$m=p+q$$
olsun. Bir kelimedeki bütün \(C\)'leri silersek geriye
$$s_1s_2\dots s_m,\qquad s_i\in\{A,B\},$$
şeklinde, tam olarak \(p\) tane \(A\) ve \(q\) tane \(B\) içeren bir ikili iskelet kalır. Bu iskelet için geçiş sayısını
$$t(s)=\#\{\,i\in\{1,\dots,m-1\}: s_i\ne s_{i+1}\,\}$$
diye tanımlayalım. Bu değer, iskelet içinde art arda gelen iki harfin tür değiştirdiği yerlerin sayısıdır.
İskelette yan yana duran iki harf farklıysa, tam kelimede bu sınırın içine en az iki tane \(C\) konmalıdır. Aksi halde o komşu \(A/B\) çifti kuralı anında bozar.
Tersi de doğrudur. İskeletteki her tür değişimi arasına en az iki \(C\) yerleştirilirse, tam kelimedeki herhangi bir \(A\) ile herhangi bir \(B\) arasında mutlaka en az bir böyle sınır bulunur; dolayısıyla aralarında toplamda en az iki \(C\) vardır.
Bu yüzden \(t\) geçişli bir iskelet tam olarak
$$2t$$
adet zorunlu \(C\) tüketir. Problem böylece bir “geçiş maliyeti” problemine dönüşür.
\(N_{p,q}(t)\), \(p\) tane \(A\), \(q\) tane \(B\) ve tam \(t\) geçiş içeren \(A/B\) iskeletlerinin sayısı olsun. \(t\) geçişli bir iskeletin \(t+1\) adet bloğu vardır.
Eğer \(t=2u+1\) tek ise, kelime farklı harfle başlayıp farklı harfle biter. Bu durumda \(u+1\) adet \(A\) bloğu ve \(u+1\) adet \(B\) bloğu vardır. \(p\)'yi \(u+1\) pozitif parçaya ayırma sayısı \(\binom{p-1}{u}\), \(q\) için de aynı şekilde \(\binom{q-1}{u}\) olur. Başlangıç harfi \(A\) da olabilir \(B\) de olabilir, dolayısıyla
$$N_{p,q}(2u+1)=2\binom{p-1}{u}\binom{q-1}{u}.$$
Eğer \(t=2u\) çift ise, kelime aynı harfle başlayıp aynı harfle biter. Ya \(A\) harfi \(u+1\) blok, \(B\) harfi \(u\) blok oluşturur ya da tersi olur. Bu nedenle
$$N_{p,q}(2u)=\binom{p-1}{u}\binom{q-1}{u-1}+\binom{p-1}{u-1}\binom{q-1}{u}.$$
Burada \(\binom{n}{k}=0\) kuralını \(k<0\) veya \(k>n\) için kullanıyoruz.
\(t\) geçişli sabit bir iskelet düşünelim. \(2t\) adet zorunlu \(C\) ayrıldıktan sonra geriye
$$r-2t$$
adet serbest \(C\) kalır. Bunların yerleşebileceği \(m+1\) slot vardır: ilk harften önce, son harften sonra ve iskeletteki her komşu harf çiftinin arası.
Stars and bars sonucu bize
$$\binom{(r-2t)+(m+1)-1}{(m+1)-1}=\binom{r-2t+m}{m}$$
sayısını verir. Elbette bunun anlamlı olması için \(2t\le r\) gerekir. Böylece aynı geçiş sayısına sahip tüm iskeletler aynı çarpanla katkı yapar.
Eğer \(A\) veya \(B\) hiç yoksa artık herhangi bir kısıt kalmaz; dolayısıyla
$$W(p,q,r)=\binom{r+m}{m}\qquad\text{\(p=0\) veya \(q=0\) ise}.$$
Aksi halde
$$W(p,q,r)=\sum_{t\ge 1} N_{p,q}(t)\binom{r-2t+m}{m}$$
olur. Sayım \(p\) ile \(q\) açısından simetrik olduğu için uygulama önce bunları \(p\le q\) olacak şekilde sıralar. Bu durumda mümkün olan en büyük geçiş sayısı
$$t_{\max}=\min\left(m-1,\left\lfloor\frac{r}{2}\right\rfloor,\begin{cases} 2p-1,& p=q,\\ 2p,& p<q \end{cases}\right)$$
şeklindedir. Son sınır tamamen kombinatoriktir: daha az bulunan harf daha fazla alternasyon üretemez.
Burada \(m=4\) olur. Hem \(A\) hem \(B\) bulunduğu için geçiş sayılarına göre toplama yaparız.
\(t=1\) için olası iskeletler \(AABB\) ve \(BBAA\)'dır. Her biri \(2\) zorunlu \(C\) ister; geriye \(2\) serbest \(C\) kalır. Yerleşim sayısı
$$\binom{4-2+4}{4}=\binom{6}{4}=15$$
olduğundan katkı \(2\cdot 15=30\) eder.
\(t=2\) için olası iskeletler \(ABBA\) ve \(BAAB\)'dır. Bu kez \(4\) adet \(C\)'nin tamamı zorunludur; yerleşim çarpanı
$$\binom{4-4+4}{4}=\binom{4}{4}=1$$
olur ve katkı \(2\cdot 1=2\) gelir.
\(t=3\) olsaydı \(6\) adet \(C\) gerekirdi ama elimizde yalnızca \(4\) tane vardır; bu yüzden bu durum katkı yapmaz. Sonuç olarak
$$W(2,2,4)=30+2=32$$
elde edilir; bu da uygulamadaki kesin kontrol değeriyle aynıdır.
C++, Python ve Java implementasyonları aynı formülü uygular. Önce \(p\le q\) olacak şekilde yer değişimi yapılır, sonra \(m=p+q\) hesaplanır ve \(p=0\) ya da \(q=0\) ise doğrudan \(\binom{r+m}{m}\) değeri \(10^9+7\) modunda döndürülür.
\(r+m\)'e kadar faktöriyel tablosu kurmak yerine implementasyon
$$\binom{r+m}{m}=\prod_{i=1}^{m}\frac{r+i}{i}\pmod{10^9+7}$$
çarpımını \(1,2,\dots,m\) için modüler tersleri kullanarak hesaplar. Ayrıca \(\binom{p-1}{u}\) ve \(\binom{q-1}{u}\) dizileri artımlı biçimde hazırlanır; geçiş formülleri için gereken kısa satırlar bunlardır.
İkinci temel araç, yerleşim katsayısını baştan hesaplamak yerine güncelleyen şu özdeşliktir:
$$\binom{n-2}{m}=\binom{n}{m}\cdot\frac{(n-m)(n-m-1)}{n(n-1)}.$$
\(n=r+m\) değerinden başlanır ve her döngü adımı geçiş sayısını \(t-1\)'den \(t\)'ye taşır. Bu bölüm işlemlerini mod \(10^9+7\) altında güvenli yapmak için gereken ardışık paydaların tersleri önceden hesaplanır.
Son olarak kod \(t=1,\dots,t_{\max}\) aralığında dolaşır, tek/çift duruma göre uygun \(N_{p,q}(t)\) formülünü uygular, bunu \(\binom{r-2t+m}{m}\) ile çarpar ve sonucu mod \(10^9+7\) altında toplar.
Yer değişiminden sonra \(m=p+q\) ve yukarıdaki sınır \(t_{\max}\) olsun. \(m\)'ye kadar modüler tersleri önceden hesaplamak \(O(m)\) zaman ve \(O(m)\) bellek ister. Kısa binom dizileri \(O(t_{\max})\) maliyetlidir; geçişler üzerinden yapılan son toplam da \(O(t_{\max})\) sürer.
Dolayısıyla toplam karmaşıklık
$$O(m+t_{\max})=O(p+q)$$
zaman ve
$$O(m+t_{\max})=O(p+q)$$
bellektir. Büyük olan \(r\) değeri, boyutu \(r\) olan bir tablo yaratmaz; yalnızca modüler çarpımların içinde görünür.
Se nos dan \(p\) copias de \(A\), \(q\) copias de \(B\) y \(r\) copias de \(C\). Una palabra es válida si entre cualquier \(A\) y cualquier \(B\) hay al menos dos letras \(C\). Debemos contar todas las palabras válidas y devolver el resultado módulo \(10^9+7\).
El espacio bruto tiene tamaño \(\binom{p+q+r}{p,q,r}\), así que enumerar directamente no es viable para los parámetros reales. La simplificación decisiva es que, al eliminar todas las \(C\), solo importa cuántas veces la secuencia restante cambia entre \(A\) y \(B\).
Denotemos por \(W(p,q,r)\) el número de palabras válidas formadas con \(p\) letras \(A\), \(q\) letras \(B\) y \(r\) letras \(C\).
Sea
$$m=p+q.$$
Si borramos todas las \(C\) de una palabra, queda un esqueleto binario
$$s_1s_2\dots s_m,\qquad s_i\in\{A,B\},$$
con exactamente \(p\) letras \(A\) y \(q\) letras \(B\). Definimos su número de transiciones por
$$t(s)=\#\{\,i\in\{1,\dots,m-1\}: s_i\ne s_{i+1}\,\}.$$
Este valor cuenta cuántas fronteras consecutivas del esqueleto cambian de \(A\) a \(B\) o de \(B\) a \(A\).
Si dos letras consecutivas del esqueleto son distintas, el hueco correspondiente en la palabra completa debe contener al menos dos \(C\). Si no, ese par adyacente \(A/B\) violaría inmediatamente la condición.
La recíproca también vale. Si toda frontera de transición del esqueleto recibe al menos dos \(C\), entonces cualquier \(A\) y cualquier \(B\) de la palabra quedan separados por al menos una de esas fronteras y, por tanto, por al menos dos \(C\) en total.
Así, un esqueleto con \(t\) transiciones consume exactamente
$$2t$$
letras \(C\) obligatorias. Toda la restricción del problema se convierte en un coste por transición.
Sea \(N_{p,q}(t)\) el número de esqueletos \(A/B\) con \(p\) letras \(A\), \(q\) letras \(B\) y exactamente \(t\) transiciones. Un esqueleto con \(t\) transiciones tiene \(t+1\) bloques.
Si \(t=2u+1\) es impar, la palabra empieza y termina con letras distintas, así que hay \(u+1\) bloques de \(A\) y \(u+1\) bloques de \(B\). Particionar \(p\) en \(u+1\) longitudes positivas da \(\binom{p-1}{u}\) opciones, y lo mismo para \(q\). Como el esqueleto puede empezar por \(A\) o por \(B\), obtenemos
$$N_{p,q}(2u+1)=2\binom{p-1}{u}\binom{q-1}{u}.$$
Si \(t=2u\) es par, el esqueleto empieza y termina con la misma letra. O bien \(A\) ocupa \(u+1\) bloques y \(B\) ocupa \(u\), o bien ocurre al revés. Por tanto,
$$N_{p,q}(2u)=\binom{p-1}{u}\binom{q-1}{u-1}+\binom{p-1}{u-1}\binom{q-1}{u}.$$
Usamos la convención \(\binom{n}{k}=0\) cuando \(k<0\) o \(k>n\).
Fijemos un esqueleto con \(t\) transiciones. Después de reservar las \(2t\) letras \(C\) obligatorias, quedan
$$r-2t$$
letras \(C\) libres. Hay \(m+1\) huecos posibles: antes de la primera letra del esqueleto, después de la última y uno entre cada par consecutivo de letras del esqueleto.
Por stars and bars, el número de distribuciones es
$$\binom{(r-2t)+(m+1)-1}{(m+1)-1}=\binom{r-2t+m}{m},$$
siempre que \(2t\le r\). Luego todos los esqueletos con el mismo número de transiciones aportan el mismo factor.
Si una de las letras \(A\) o \(B\) no aparece, ya no hay restricción, y por tanto
$$W(p,q,r)=\binom{r+m}{m}\qquad\text{cuando }p=0\text{ o }q=0.$$
En caso contrario,
$$W(p,q,r)=\sum_{t\ge 1} N_{p,q}(t)\binom{r-2t+m}{m}.$$
Como el conteo es simétrico en \(p\) y \(q\), la implementación primero intercambia ambos valores para garantizar \(p\le q\). Entonces el máximo número posible de transiciones es
$$t_{\max}=\min\left(m-1,\left\lfloor\frac{r}{2}\right\rfloor,\begin{cases} 2p-1,& p=q,\\ 2p,& p<q. \end{cases}\right).$$
La última cota es puramente combinatoria: la letra menos frecuente no puede sostener más alternancias que esa cantidad.
Aquí \(m=4\). Como aparecen tanto \(A\) como \(B\), sumamos por número de transiciones.
Para \(t=1\), los esqueletos posibles son \(AABB\) y \(BBAA\). Cada uno necesita \(2\) letras \(C\) obligatorias, así que quedan \(2\) libres. El factor de inserción es
$$\binom{4-2+4}{4}=\binom{6}{4}=15,$$
de modo que la contribución es \(2\cdot 15=30\).
Para \(t=2\), los esqueletos posibles son \(ABBA\) y \(BAAB\). Ahora las \(4\) letras \(C\) quedan completamente forzadas, así que el factor de inserción vale
$$\binom{4-4+4}{4}=\binom{4}{4}=1,$$
y la contribución es \(2\cdot 1=2\).
Para \(t=3\) harían falta \(6\) letras \(C\), pero solo disponemos de \(4\), así que ese caso no aporta nada. En consecuencia,
$$W(2,2,4)=30+2=32,$$
en perfecto acuerdo con el valor exacto de comprobación usado por la implementación.
Las implementaciones en C++, Python y Java siguen exactamente esta fórmula. Primero intercambian las cantidades para asegurar \(p\le q\), fijan \(m=p+q\) y resuelven el caso sencillo \(p=0\) o \(q=0\) devolviendo \(\binom{r+m}{m}\) módulo \(10^9+7\).
En lugar de construir tablas factoriales hasta \(r+m\), la implementación evalúa
$$\binom{r+m}{m}=\prod_{i=1}^{m}\frac{r+i}{i}\pmod{10^9+7}$$
mediante inversos modulares de \(1,2,\dots,m\). También construye de forma incremental las filas cortas \(\binom{p-1}{u}\) y \(\binom{q-1}{u}\), suficientes para aplicar las fórmulas impar y par de \(N_{p,q}(t)\).
La segunda idea clave es actualizar el factor de inserción sin recalcular un nuevo coeficiente binomial desde cero:
$$\binom{n-2}{m}=\binom{n}{m}\cdot\frac{(n-m)(n-m-1)}{n(n-1)}.$$
Partiendo de \(n=r+m\), cada iteración avanza del recuento de transiciones \(t-1\) al de \(t\). Para que las divisiones sean válidas módulo \(10^9+7\), la implementación precalcula los inversos de los denominadores consecutivos que aparecen en esa recurrencia.
Finalmente, recorre \(t=1,\dots,t_{\max}\), evalúa la fórmula correcta para \(N_{p,q}(t)\) según la paridad de \(t\), multiplica por \(\binom{r-2t+m}{m}\) y acumula todo módulo \(10^9+7\).
Después del intercambio, sea \(m=p+q\) y \(t_{\max}\) el límite anterior. Precalcular los inversos modulares hasta \(m\) cuesta \(O(m)\) tiempo y memoria. Las tablas cortas de binomiales cuestan \(O(t_{\max})\), y la suma final sobre todos los valores de transición también cuesta \(O(t_{\max})\).
Por tanto, la complejidad total es
$$O(m+t_{\max})=O(p+q)$$
en tiempo y
$$O(m+t_{\max})=O(p+q)$$
en memoria. El valor enorme de \(r\) no genera ninguna tabla de tamaño \(r\); solo aparece dentro de productos modulares.
题目给出 \(p\) 个 \(A\)、\(q\) 个 \(B\) 和 \(r\) 个 \(C\)。如果任意一个 \(A\) 与任意一个 \(B\) 之间都至少隔着两个 \(C\)，那么这个单词就是合法的。我们需要统计所有合法单词的数量，并对 \(10^9+7\) 取模。
直接枚举的规模是 \(\binom{p+q+r}{p,q,r}\)，对真实参数完全不可行。真正有效的观察是：删去全部 \(C\) 之后，决定答案的不是具体位置，而是剩下的 \(A/B\) 序列一共发生了多少次类型切换。
记 \(W(p,q,r)\) 为用 \(p\) 个 \(A\)、\(q\) 个 \(B\)、\(r\) 个 \(C\) 构成的合法单词总数。
先设
$$m=p+q.$$
把一个单词中的全部 \(C\) 删除后，剩下的是一个长度为 \(m\) 的二元骨架
$$s_1s_2\dots s_m,\qquad s_i\in\{A,B\},$$
其中恰好有 \(p\) 个 \(A\) 和 \(q\) 个 \(B\)。对这个骨架，定义切换次数
$$t(s)=\#\{\,i\in\{1,\dots,m-1\}: s_i\ne s_{i+1}\,\}.$$
也就是说，\(t(s)\) 正好统计骨架中相邻两个位置从 \(A\) 变到 \(B\) 或从 \(B\) 变到 \(A\) 的次数。
如果骨架中相邻的两个字母不同，那么在完整单词中，这条边界之间至少要插入两个 \(C\)。否则这对相邻的 \(A/B\) 本身就会违反题目条件。
反过来，这个条件也已经足够。只要骨架里的每一条切换边界都放上至少两个 \(C\)，那么完整单词中的任意一个 \(A\) 和任意一个 \(B\) 之间，必然跨过至少一条这样的边界，因此它们之间至少隔着两个 \(C\)。
所以，切换次数为 \(t\) 的骨架恰好需要
$$2t$$
个强制性的 \(C\)。题目的限制于是被压缩成了一个简单的“切换成本”。
记 \(N_{p,q}(t)\) 为含 \(p\) 个 \(A\)、\(q\) 个 \(B\)、并且恰好有 \(t\) 次切换的 \(A/B\) 骨架数量。一个有 \(t\) 次切换的骨架会被分成 \(t+1\) 个连续块。
如果 \(t=2u+1\) 是奇数，那么骨架的首尾字母不同，因此会有 \(u+1\) 个 \(A\) 块和 \(u+1\) 个 \(B\) 块。把 \(p\) 分拆成 \(u+1\) 个正整数的方式有 \(\binom{p-1}{u}\) 种，把 \(q\) 分拆成 \(u+1\) 个正整数的方式有 \(\binom{q-1}{u}\) 种。又因为骨架可以从 \(A\) 开始，也可以从 \(B\) 开始，所以
$$N_{p,q}(2u+1)=2\binom{p-1}{u}\binom{q-1}{u}.$$
如果 \(t=2u\) 是偶数，那么骨架的首尾字母相同。此时要么 \(A\) 出现为 \(u+1\) 个块而 \(B\) 为 \(u\) 个块，要么两者互换，因此
$$N_{p,q}(2u)=\binom{p-1}{u}\binom{q-1}{u-1}+\binom{p-1}{u-1}\binom{q-1}{u}.$$
这里约定：当 \(k<0\) 或 \(k>n\) 时，\(\binom{n}{k}=0\)。
固定一个切换次数为 \(t\) 的骨架之后，先拿出 \(2t\) 个强制性的 \(C\)，还剩下
$$r-2t$$
个 \(C\) 可以自由分配。可以放置的位置一共有 \(m+1\) 个：骨架最前面一个、最后面一个，以及每一对相邻骨架字母之间各一个。
用 stars and bars 可得，自由分配的方案数为
$$\binom{(r-2t)+(m+1)-1}{(m+1)-1}=\binom{r-2t+m}{m},$$
前提是 \(2t\le r\)。因此，所有切换次数相同的骨架都会乘上同一个插入因子。
如果 \(A\) 或 \(B\) 其中一种根本不存在，那么条件自动满足，因此
$$W(p,q,r)=\binom{r+m}{m}\qquad\text{当 }p=0\text{ 或 }q=0\text{ 时}.$$
否则就有
$$W(p,q,r)=\sum_{t\ge 1} N_{p,q}(t)\binom{r-2t+m}{m}.$$
因为答案关于 \(p\) 与 \(q\) 完全对称，所以实现里会先交换它们，使得 \(p\le q\)。在这个前提下，可能的最大切换次数为
$$t_{\max}=\min\left(m-1,\left\lfloor\frac{r}{2}\right\rfloor,\begin{cases} 2p-1,& p=q,\\ 2p,& p<q. \end{cases}\right).$$
最后这个上界完全来自组合结构：数量较少的那种字母不可能支撑比这更多的交替。
此时 \(m=4\)。因为 \(A\) 和 \(B\) 都出现了，所以需要按切换次数分情况求和。
当 \(t=1\) 时，可行骨架只有 \(AABB\) 和 \(BBAA\)。每个骨架都需要 \(2\) 个强制 \(C\)，于是还剩 \(2\) 个自由 \(C\)。插入因子为
$$\binom{4-2+4}{4}=\binom{6}{4}=15,$$
所以这一部分贡献是 \(2\cdot 15=30\)。
当 \(t=2\) 时，可行骨架是 \(ABBA\) 和 \(BAAB\)。这时 \(4\) 个 \(C\) 全部都是强制性的，因此插入因子变成
$$\binom{4-4+4}{4}=\binom{4}{4}=1,$$
对应贡献是 \(2\cdot 1=2\)。
当 \(t=3\) 时，需要 \(6\) 个 \(C\)，但实际上只有 \(4\) 个，所以这一项为零。最终得到
$$W(2,2,4)=30+2=32,$$
这与实现中使用的精确校验值完全一致。
C++、Python 和 Java 实现都直接按照上面的公式来做。首先交换两个计数，使 \(p\le q\)，然后计算 \(m=p+q\)。如果 \(p=0\) 或 \(q=0\)，就直接返回 \(\binom{r+m}{m}\bmod 10^9+7\)。
实现并不会建立到 \(r+m\) 为止的阶乘表，而是利用
$$\binom{r+m}{m}=\prod_{i=1}^{m}\frac{r+i}{i}\pmod{10^9+7}$$
这个乘积形式，再配合 \(1,2,\dots,m\) 的模逆元来计算初始二项式系数。与此同时，还会递推构造出短小的两行系数 \(\binom{p-1}{u}\) 与 \(\binom{q-1}{u}\)，这已经足够处理奇偶两类 \(N_{p,q}(t)\) 公式。
另一个关键技巧是用递推更新插入因子，而不是每次重新计算一个新的二项式系数：
$$\binom{n-2}{m}=\binom{n}{m}\cdot\frac{(n-m)(n-m-1)}{n(n-1)}.$$
从 \(n=r+m\) 开始，每次循环就把切换次数从 \(t-1\) 推到 \(t\)。为了让模 \(10^9+7\) 下的除法合法，实现会预先算出这段连续分母的逆元。
最后，程序遍历 \(t=1,\dots,t_{\max}\)，根据 \(t\) 的奇偶性套用对应的块计数公式，乘上 \(\binom{r-2t+m}{m}\)，并把结果在模 \(10^9+7\) 下累加起来。
交换之后记 \(m=p+q\)，并令 \(t_{\max}\) 为上面的切换上界。预处理 \(1\) 到 \(m\) 的模逆元需要 \(O(m)\) 时间和 \(O(m)\) 内存。两条短二项式序列需要 \(O(t_{\max})\) 时间与空间，最后对所有切换次数的求和也需要 \(O(t_{\max})\)。
因此，总复杂度为
$$O(m+t_{\max})=O(p+q)$$
时间和
$$O(m+t_{\max})=O(p+q)$$
内存。注意，尽管 \(r\) 很大，但实现不会建立一个大小为 \(r\) 的数组；\(r\) 只出现在模乘法里。
Даны \(p\) букв \(A\), \(q\) букв \(B\) и \(r\) букв \(C\). Слово считается допустимым, если между любыми \(A\) и \(B\) находится не меньше двух букв \(C\). Нужно посчитать число всех допустимых слов по модулю \(10^9+7\).
Полный перебор имел бы размер \(\binom{p+q+r}{p,q,r}\), что для реальных параметров совершенно непрактично. Ключевое наблюдение состоит в том, что после удаления всех \(C\) важна только структура чередования букв \(A\) и \(B\).
Обозначим через \(W(p,q,r)\) количество допустимых слов, составленных из \(p\) букв \(A\), \(q\) букв \(B\) и \(r\) букв \(C\).
Положим
$$m=p+q.$$
Если из слова убрать все буквы \(C\), останется бинарный скелет
$$s_1s_2\dots s_m,\qquad s_i\in\{A,B\},$$
с ровно \(p\) буквами \(A\) и \(q\) буквами \(B\). Для такого скелета введем число переходов
$$t(s)=\#\{\,i\in\{1,\dots,m-1\}: s_i\ne s_{i+1}\,\}.$$
Это просто количество соседних границ, на которых буква меняется с \(A\) на \(B\) или с \(B\) на \(A\).
Если две соседние буквы скелета различны, то в полном слове между ними обязательно должны стоять хотя бы две буквы \(C\). Иначе эта соседняя пара \(A/B\) сразу нарушает условие задачи.
Верно и обратное. Если на каждой границе перехода поставить не меньше двух букв \(C\), то любые \(A\) и \(B\) в полном слове будут разделены хотя бы одной такой границей, а значит, между ними окажется как минимум две буквы \(C\).
Следовательно, скелет с \(t\) переходами требует ровно
$$2t$$
обязательных букв \(C\). Всё условие задачи сводится к цене за число переходов.
Пусть \(N_{p,q}(t)\) обозначает число \(A/B\)-скелетов с \(p\) буквами \(A\), \(q\) буквами \(B\) и ровно \(t\) переходами. У скелета с \(t\) переходами имеется \(t+1\) блоков.
Если \(t=2u+1\) нечётно, то скелет начинается и заканчивается разными буквами. Значит, в нем \(u+1\) блоков \(A\) и \(u+1\) блоков \(B\). Разбиение числа \(p\) на \(u+1\) положительных длин даёт \(\binom{p-1}{u}\) вариантов, и аналогично для \(q\). Поскольку скелет может начинаться как с \(A\), так и с \(B\), получаем
$$N_{p,q}(2u+1)=2\binom{p-1}{u}\binom{q-1}{u}.$$
Если \(t=2u\) чётно, то скелет начинается и заканчивается одной и той же буквой. Тогда либо у \(A\) имеется \(u+1\) блоков, а у \(B\) ровно \(u\), либо наоборот. Поэтому
$$N_{p,q}(2u)=\binom{p-1}{u}\binom{q-1}{u-1}+\binom{p-1}{u-1}\binom{q-1}{u}.$$
Здесь используется соглашение \(\binom{n}{k}=0\), если \(k<0\) или \(k>n\).
Зафиксируем скелет с \(t\) переходами. После резервирования \(2t\) обязательных букв \(C\) остаётся
$$r-2t$$
свободных букв \(C\). Для них есть \(m+1\) позиций: перед первой буквой скелета, после последней и по одной щели между каждой соседней парой букв скелета.
По формуле stars and bars число распределений равно
$$\binom{(r-2t)+(m+1)-1}{(m+1)-1}=\binom{r-2t+m}{m},$$
если только \(2t\le r\). Значит, все скелеты с одинаковым числом переходов дают одинаковый множитель.
Если одна из букв \(A\) или \(B\) отсутствует, никаких ограничений не остаётся, и потому
$$W(p,q,r)=\binom{r+m}{m}\qquad\text{при }p=0\text{ или }q=0.$$
В противном случае
$$W(p,q,r)=\sum_{t\ge 1} N_{p,q}(t)\binom{r-2t+m}{m}.$$
Поскольку ответ симметричен по \(p\) и \(q\), реализация сначала меняет их местами так, чтобы \(p\le q\). Тогда максимально возможное число переходов равно
$$t_{\max}=\min\left(m-1,\left\lfloor\frac{r}{2}\right\rfloor,\begin{cases} 2p-1,& p=q,\\ 2p,& p<q. \end{cases}\right).$$
Последняя граница чисто комбинаторна: более редкая буква не может поддерживать больше чередований.
Здесь \(m=4\). Поскольку присутствуют и \(A\), и \(B\), нужно суммировать по числу переходов.
Для \(t=1\) возможны скелеты \(AABB\) и \(BBAA\). Каждый из них требует \(2\) обязательных букв \(C\), так что остаётся \(2\) свободных \(C\). Число вставок равно
$$\binom{4-2+4}{4}=\binom{6}{4}=15,$$
поэтому вклад составляет \(2\cdot 15=30\).
Для \(t=2\) возможны скелеты \(ABBA\) и \(BAAB\). Теперь все \(4\) буквы \(C\) уже обязательны, и вставочный множитель равен
$$\binom{4-4+4}{4}=\binom{4}{4}=1,$$
так что вклад составляет \(2\cdot 1=2\).
Для \(t=3\) потребовалось бы \(6\) букв \(C\), но имеется только \(4\), поэтому этот случай не даёт вклада. В итоге
$$W(2,2,4)=30+2=32,$$
что точно совпадает с контрольным значением в реализации.
Реализации на C++, Python и Java следуют одной и той же формуле. Сначала они переставляют количества так, чтобы выполнялось \(p\le q\), затем вычисляют \(m=p+q\) и отдельно обрабатывают простой случай \(p=0\) или \(q=0\), возвращая \(\binom{r+m}{m}\bmod 10^9+7\).
Вместо таблиц факториалов до \(r+m\) реализация вычисляет
$$\binom{r+m}{m}=\prod_{i=1}^{m}\frac{r+i}{i}\pmod{10^9+7}$$
с помощью модульных обратных для \(1,2,\dots,m\). Параллельно она строит короткие строки биномиальных коэффициентов \(\binom{p-1}{u}\) и \(\binom{q-1}{u}\), которых достаточно для нечётной и чётной формул \(N_{p,q}(t)\).
Вторая важная идея состоит в том, чтобы обновлять вставочный множитель рекуррентно, не пересчитывая новый биномиальный коэффициент с нуля:
$$\binom{n-2}{m}=\binom{n}{m}\cdot\frac{(n-m)(n-m-1)}{n(n-1)}.$$
Начиная с \(n=r+m\), один шаг цикла переводит нас от числа переходов \(t-1\) к \(t\). Чтобы деление было корректным по модулю \(10^9+7\), реализация заранее вычисляет обратные для подряд идущих знаменателей, которые появляются в этой формуле.
После этого цикл по \(t=1,\dots,t_{\max}\) вычисляет подходящую формулу для \(N_{p,q}(t)\), умножает её на \(\binom{r-2t+m}{m}\) и накапливает ответ по модулю \(10^9+7\).
После перестановки положим \(m=p+q\), а через \(t_{\max}\) обозначим указанную выше границу. Предварительное вычисление модульных обратных до \(m\) требует \(O(m)\) времени и \(O(m)\) памяти. Короткие биномиальные таблицы стоят \(O(t_{\max})\), и итоговая сумма по всем переходам тоже занимает \(O(t_{\max})\).
Итак, общая сложность равна
$$O(m+t_{\max})=O(p+q)$$
по времени и
$$O(m+t_{\max})=O(p+q)$$
по памяти. Большое значение \(r\) не приводит к созданию массива длины \(r\); оно фигурирует только внутри модульных произведений.
لدينا \(p\) حرفًا من \(A\) و\(q\) حرفًا من \(B\) و\(r\) حرفًا من \(C\). تكون الكلمة صالحة إذا كان بين أي \(A\) وأي \(B\) حرفان على الأقل من \(C\). المطلوب هو عدّ جميع الكلمات الصالحة ثم إرجاع الناتج بترديد \(10^9+7\).
حجم فضاء العدّ المباشر هو \(\binom{p+q+r}{p,q,r}\)، ولذلك فالتعداد الخام غير ممكن عمليًا للمدخلات الحقيقية. الفكرة الحاسمة هي أنه بعد حذف جميع حروف \(C\)، لا يبقى مهمًا إلا عدد المرات التي يتبدل فيها التسلسل المتبقي بين \(A\) و\(B\).
لنرمز بعدد الكلمات الصالحة المبنية من \(p\) حرفًا \(A\) و\(q\) حرفًا \(B\) و\(r\) حرفًا \(C\) بالرمز \(W(p,q,r)\).
لنضع
$$m=p+q.$$
إذا حذفنا كل حروف \(C\) من كلمة ما، بقي لدينا هيكل ثنائي
$$s_1s_2\dots s_m,\qquad s_i\in\{A,B\},$$
يحتوي بالضبط على \(p\) حرفًا من \(A\) و\(q\) حرفًا من \(B\). ونعرّف عدد الانتقالات فيه بالصيغة
$$t(s)=\#\{\,i\in\{1,\dots,m-1\}: s_i\ne s_{i+1}\,\}.$$
أي أن \(t(s)\) هو عدد المواضع المتجاورة التي يتغير فيها الحرف من \(A\) إلى \(B\) أو من \(B\) إلى \(A\).
إذا كان حرفان متجاوران في الهيكل مختلفين، فلا بد أن تحتوي الفجوة المقابلة لهما في الكلمة الكاملة على حرفي \(C\) على الأقل. وإلا فإن هذا الزوج المتجاور من \(A/B\) سيخالف الشرط مباشرة.
والعكس صحيح أيضًا. فإذا وُضع حرفان من \(C\) على الأقل عند كل حدّ انتقال في الهيكل، فإن أي \(A\) وأي \(B\) في الكلمة سيقع بينهما حدّ انتقال واحد على الأقل، ومن ثم سيكون بينهما حرفان من \(C\) على الأقل.
إذن الهيكل الذي يحوي \(t\) انتقالات يستهلك بالضبط
$$2t$$
من حروف \(C\) الإلزامية. وبذلك تتحول قيود المسألة كلها إلى كلفة مرتبطة بعدد الانتقالات.
لنعرّف \(N_{p,q}(t)\) بأنه عدد هياكل \(A/B\) التي تحتوي على \(p\) أحرف من \(A\) و\(q\) أحرف من \(B\) وفيها بالضبط \(t\) انتقالات. الهيكل ذو \(t\) انتقالات يتكون من \(t+1\) كتل متتالية.
إذا كان \(t=2u+1\) فرديًا، فإن الكلمة تبدأ بحرف وتَنتهي بالحرف الآخر، ولذلك يوجد \(u+1\) كتل من \(A\) و\(u+1\) كتل من \(B\). وعدد طرق تقسيم \(p\) إلى \(u+1\) أطوال موجبة هو \(\binom{p-1}{u}\)، وكذلك \(q\). وبما أن الهيكل قد يبدأ بـ \(A\) أو بـ \(B\)، نحصل على
$$N_{p,q}(2u+1)=2\binom{p-1}{u}\binom{q-1}{u}.$$
أما إذا كان \(t=2u\) زوجيًا، فإن الهيكل يبدأ وينتهي بالحرف نفسه. عندئذ إما أن يملك \(A\) عددًا قدره \(u+1\) من الكتل و\(B\) عددًا قدره \(u\)، أو يحدث العكس. لذلك
$$N_{p,q}(2u)=\binom{p-1}{u}\binom{q-1}{u-1}+\binom{p-1}{u-1}\binom{q-1}{u}.$$
ونستخدم الاتفاقية المعتادة \(\binom{n}{k}=0\) عندما يكون \(k<0\) أو \(k>n\).
ثبّت هيكلًا له \(t\) انتقالات. بعد حجز \(2t\) من حروف \(C\) الإلزامية، يبقى لدينا
$$r-2t$$
من حروف \(C\) الحرة. توجد \(m+1\) فتحات ممكنة: قبل أول حرف في الهيكل، وبعد آخر حرف، وفتحة بين كل حرفين متتاليين من حروف الهيكل.
وبحسب صيغة stars and bars فإن عدد طرق التوزيع يساوي
$$\binom{(r-2t)+(m+1)-1}{(m+1)-1}=\binom{r-2t+m}{m},$$
وذلك بشرط \(2t\le r\). ومن ثم فإن كل الهياكل التي تملك العدد نفسه من الانتقالات تضرب في العامل نفسه.
إذا كان أحد الحرفين \(A\) أو \(B\) غير موجود أصلًا، فلا يبقى أي قيد، ومن ثم
$$W(p,q,r)=\binom{r+m}{m}.$$
وهذه الصيغة تنطبق عندما \(p=0\) أو \(q=0\).
أما في الحالة العامة فلدينا
$$W(p,q,r)=\sum_{t\ge 1} N_{p,q}(t)\binom{r-2t+m}{m}.$$
ولأن العدّ متناظر في \(p\) و\(q\)، فإن التنفيذ يبدأ بتبديلهما بحيث يصبح \(p\le q\). عندها يكون أكبر عدد ممكن من الانتقالات هو
$$t_{\max}=\min\left(m-1,\left\lfloor\frac{r}{2}\right\rfloor,\begin{cases} 2p-1,& p=q,\\ 2p,& p<q. \end{cases}\right).$$
والحد الأخير حدّ توافقي بحت: الحرف الأقل تكرارًا لا يستطيع أن يدعم عددًا أكبر من التناوبات.
هنا \(m=4\). وبما أن كلا الحرفين \(A\) و\(B\) موجود، فإننا نجمع على قيم عدد الانتقالات.
عندما \(t=1\)، تكون الهياكل الممكنة هي \(AABB\) و\(BBAA\). كل واحد منها يحتاج إلى \(2\) من حروف \(C\) الإلزامية، فيبقى \(2\) من حروف \(C\) الحرة. عامل الإدراج هو
$$\binom{4-2+4}{4}=\binom{6}{4}=15,$$
وبالتالي تكون المساهمة \(2\cdot 15=30\).
وعندما \(t=2\)، تكون الهياكل الممكنة هي \(ABBA\) و\(BAAB\). هنا تصبح جميع الحروف الأربعة من \(C\) إلزامية، ولذلك فإن عامل الإدراج يساوي
$$\binom{4-4+4}{4}=\binom{4}{4}=1,$$
وتكون المساهمة \(2\cdot 1=2\).
أما \(t=3\) فيتطلب \(6\) أحرف من \(C\)، بينما المتاح هو \(4\) فقط، لذا فهذه الحالة لا تضيف شيئًا. ومن ثم
$$W(2,2,4)=30+2=32,$$
وهو بالضبط مقدار التحقق الدقيق المستخدم في التنفيذ.
تتبع تطبيقات C++ وPython وJava الصيغة نفسها. فهي تبدأ بتبديل القيمتين بحيث يتحقق \(p\le q\)، ثم تحسب \(m=p+q\)، وتتعامل مع الحالة السهلة \(p=0\) أو \(q=0\) بإرجاع \(\binom{r+m}{m}\) بترديد \(10^9+7\).
وبدلًا من بناء جداول مضروب حتى \(r+m\)، تحسب الشيفرة
$$\binom{r+m}{m}=\prod_{i=1}^{m}\frac{r+i}{i}\pmod{10^9+7}$$
باستخدام المعكوسات المعيارية للأعداد \(1,2,\dots,m\). كما تبني بشكل تزايدي الصفين القصيرين \(\binom{p-1}{u}\) و\(\binom{q-1}{u}\)، وهما كل ما نحتاج إليه لتطبيق صيغ \(N_{p,q}(t)\) في حالتي الفردي والزوجي.
والفكرة التقنية الثانية هي تحديث عامل الإدراج بعلاقة عودية بدلًا من إعادة حساب معامل ثنائي جديد في كل مرة:
$$\binom{n-2}{m}=\binom{n}{m}\cdot\frac{(n-m)(n-m-1)}{n(n-1)}.$$
ابتداءً من \(n=r+m\)، تنقل كل دورة الحلقة الحساب من عدد الانتقالات \(t-1\) إلى \(t\). وحتى تكون القسمة صحيحة تحت الترديد \(10^9+7\)، يجري التنفيذ حساب المعكوسات المعيارية للمقامات المتتالية التي تظهر في هذه العلاقة.
وأخيرًا، تمر الشيفرة على \(t=1,\dots,t_{\max}\)، وتحسب الصيغة المناسبة لـ \(N_{p,q}(t)\) بحسب فردية \(t\) أو زوجيته، ثم تضربها في \(\binom{r-2t+m}{m}\) وتجمع الناتج كله بترديد \(10^9+7\).
بعد التبديل، لنكتب \(m=p+q\) ولتكن \(t_{\max}\) هي الحدود السابقة. إن حساب المعكوسات المعيارية حتى \(m\) يحتاج إلى \(O(m)\) زمنًا و\(O(m)\) ذاكرة. أما صفوف المعاملات الثنائية القصيرة فتحتاج إلى \(O(t_{\max})\)، وكذلك الحلقة الأخيرة التي تجمع جميع المساهمات عبر قيم الانتقالات.
لذلك يكون التعقيد الكلي
$$O(m+t_{\max})=O(p+q)$$
زمنًا و
$$O(m+t_{\max})=O(p+q)$$
ذاكرة. والقيمة الكبيرة \(r\) لا تنشئ أي جدول بحجم \(r\)، بل تظهر فقط داخل الضربات المعيارية.