We are given \(s\) suits, each suit has ranks \(1,2,\dots,n\), and each tile type appears at most four times. A valid Mahjong-style hand consists of exactly \(t\) melds together with one pair, where a meld is either a triple of identical tiles or a run of three consecutive ranks inside one suit.
The goal is to count all valid hands modulo \(10^9+7\). The implementations evaluate the extremely large case \(W(10^8,10^8,30)\), so any approach based on direct enumeration is hopeless. The entire solution therefore compresses the local suit constraints into a finite automaton, builds one-suit counting polynomials, and only then combines the suits.
Let \(W(n,s,t)\) denote the number of valid hands with \(n\) ranks per suit, \(s\) suits, and exactly \(t\) melds. The key observation is that suits interact only through the total meld count and the fact that exactly one suit contains the unique pair.
Fix one suit and write its tile multiplicities as \(c_1,\dots,c_n\), where every \(c_i\) lies in \(\{0,1,2,3,4\}\). A zero count breaks all possible runs, so no meld can cross a rank with \(c_i=0\).
Therefore a suit decomposes into maximal contiguous blocks of positive counts. Each block can be analyzed independently, and the only remaining global question inside that suit is how many zero gaps are inserted between the blocks. This is why the solution first counts contiguous positive blocks and postpones the placement of zeros until later.
Consider a positive block with counts \(d_1,\dots,d_L\), where every \(d_i\in\{1,2,3,4\}\). We process the block from left to right. Before rank \(i\), the local state is \((u,v,\pi)\):
\(u\) is the number of runs started at rank \(i-1\) that still need tiles at ranks \(i\) and \(i+1\).
\(v\) is the number of runs started at rank \(i-2\) that need one final tile at rank \(i\).
\(\pi\in\{0,1\}\) records whether the unique pair has already been used inside the current block.
At rank \(i\), at least \(u+v\) tiles are forced, because those tiles must continue or finish the already open runs. If \(d_i\ge u+v\), let
$$r_i=d_i-u-v.$$
From these remaining tiles we may optionally spend \(2\) tiles on the pair, start some new runs at rank \(i\), and use the rest as triples. If \(\delta\in\{0,1\}\) indicates whether the pair is used at rank \(i\), and \(q_i\) is the number of new runs started there, then the transition is valid exactly when
$$0\le q_i\le r_i-2\delta,\qquad r_i-2\delta-q_i\equiv 0 \pmod 3.$$
The next state becomes
$$ (u,v,\pi)\longrightarrow(q_i,u,\max(\pi,\delta)). $$
Because several choices of \((\delta,q_i)\) may be possible for the same input count \(d_i\), the natural local machine is nondeterministic. The implementations determinize it once and then run ordinary dynamic programming on the reachable deterministic states.
Let \(\mathcal{B}_0(L,M)\) be the number of positive blocks of length \(L\) and total tile count \(M\) that end with no unfinished runs and no pair. Let \(\mathcal{B}_1(L,M)\) be the analogous count with exactly one pair used.
These values are obtained by pushing the deterministic automaton through all block lengths up to \(3t+2\) and all tile totals up to \(3t+2\). That cutoff is sufficient because a complete hand with \(t\) melds and one pair contains only \(3t+2\) tiles in total, so no single suit or block can contribute more than that.
The residue classes are forced:
$$\mathcal{B}_0(L,M)\neq 0 \Longrightarrow M\equiv 0 \pmod 3,$$
$$\mathcal{B}_1(L,M)\neq 0 \Longrightarrow M\equiv 2 \pmod 3.$$
Indeed, a block with no pair is built entirely from melds and therefore uses a multiple of three tiles, while a block with one pair uses \(2\) more than a multiple of three.
A suit can contain several positive blocks separated by zero-count ranks. Let \(\mathcal{D}_{0,k}(L,M)\) be the number of ways to choose exactly \(k\) blocks whose total positive length is \(L\), total tile count is \(M\), and which contain no pair overall. Let \(\mathcal{D}_{1,k}(L,M)\) be the analogous quantity with exactly one pair overall.
The block convolution is then
$$\mathcal{D}_{0,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_0(L',M'),$$
$$\mathcal{D}_{1,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{1,k}(L,M)\,\mathcal{B}_0(L',M')+\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_1(L',M').$$
Only one block is allowed to contribute the pair, so the second recurrence has exactly two sources. Also, there can be at most \(t+1\) blocks in one suit, because each nonempty block must contribute at least one group, and a full hand has only \(t\) melds plus one pair.
Suppose a one-suit configuration uses \(k\) positive blocks whose lengths sum to \(L\). The remaining \(n-L\) ranks have count zero. Write the zero gaps as
$$z_0+z_1+\cdots+z_k=n-L,$$
where \(z_0\) is the leading zero run, \(z_k\) is the trailing zero run, and the interior gaps \(z_1,\dots,z_{k-1}\) must each satisfy \(z_i\ge 1\) so that the blocks stay separated.
After setting \(z_i'=z_i-1\) for \(1\le i\le k-1\), we get
$$z_0+z_1'+\cdots+z_{k-1}'+z_k=n-L-k+1,$$
so the number of embeddings is
$$\binom{n-L+1}{k}.$$
This placement factor is one of the main simplifications in the algorithm. For example, if \(n=7\), the chosen blocks have total positive length \(L=4\), and there are \(k=2\) blocks, then the number of placements is \(\binom{7-4+1}{2}=\binom{4}{2}=6\).
After multiplying each \(\mathcal{D}_{\varepsilon,k}(L,M)\) by the placement factor, we obtain one-suit totals
$$A_M(n)=\sum_{k,L}\mathcal{D}_{0,k}(L,M)\binom{n-L+1}{k},$$
$$B_M(n)=\sum_{k,L}\mathcal{D}_{1,k}(L,M)\binom{n-L+1}{k}.$$
Now define \(T_u(n)=A_{3u}(n)\) and \(P_u(n)=B_{3u+2}(n)\). In words, \(T_u(n)\) counts one-suit configurations contributing exactly \(u\) melds and no pair, while \(P_u(n)\) counts one-suit configurations contributing exactly \(u\) melds together with the pair.
Introduce the truncated generating functions
$$\mathcal{T}_n(x)=\sum_{u\ge 0}T_u(n)x^u,\qquad \mathcal{P}_n(x)=\sum_{u\ge 0}P_u(n)x^u.$$
Exactly one suit carries the pair, so the full answer is
$$\boxed{W(n,s,t)=s\cdot [x^t]\;\mathcal{P}_n(x)\,\mathcal{T}_n(x)^{\,s-1}\pmod{10^9+7}.}$$
The coefficient of \(x^t\) enforces that the total number of melds across all suits is exactly \(t\).
With one suit, four ranks, and exactly one meld, every legal hand has \(3\cdot 1+2=5\) tiles. There are two cases.
Triple plus pair: choose the triple rank in \(4\) ways and the pair rank in one of the remaining \(3\) ways, giving \(4\cdot 3=12\).
Run plus pair: the only runs are \(123\) and \(234\), so there are \(2\) possible runs. For each run, the pair can be placed at any of the \(4\) ranks, giving \(2\cdot 4=8\).
Therefore
$$W(4,1,1)=12+8=20,$$
which agrees with the small sanity case checked by the implementations.
The C++, Python, and Java implementations all follow the same pipeline. First they build the reachable deterministic automaton corresponding to the local block rules above. Acceptance is split into two categories: blocks that finish with no pair and blocks that finish with exactly one pair.
Next they run a dynamic program over block length and tile total, but only for positive counts \(1,2,3,4\). Zero-count ranks are deliberately excluded at this stage because zeros are handled later by the explicit placement factor \(\binom{n-L+1}{k}\).
After the contiguous block counts are known, the implementations run a second convolution-style dynamic program that combines many blocks inside one suit, once for the no-pair case and once for the one-pair case. This produces the tables indexed by block count, total positive length, and total tile count.
Then, for each admissible pair \((k,L)\), they multiply by \(\binom{n-L+1}{k}\) modulo \(10^9+7\). Because \(k\le t+1\) is small even when \(n\) is enormous, the binomial coefficient is computed as a short falling product times the modular inverse of \(k!\), rather than by precomputing factorials up to \(n\).
Finally the one-suit coefficients are packed into the truncated polynomials \(\mathcal{T}_n(x)\) and \(\mathcal{P}_n(x)\). The no-pair polynomial is raised to the \((s-1)\)-st power by binary exponentiation with truncation at degree \(t\), multiplied by the pair polynomial, and the coefficient of \(x^t\) is extracted and multiplied by \(s\).
Let \(T=3t+2\). The deterministic automaton has constant size with respect to the input parameters, so the local block precomputation runs in \(O(T^2)\) time and uses \(O(T^2)\) working memory, up to that constant automaton factor.
The dominant part is the block-combination dynamic program. There are \(O(T^2)\) possible block types \((L,M)\), each convolution touches \(O(T^2)\) table cells, and this is repeated for \(O(t)\) block counts. Since \(T=O(t)\), the full precomputation is \(O(t^5)\) time with \(O(t^3)\) stored state.
Once the one-suit tables are built, the final evaluation for given \(n\) and \(s\) takes \(O(t^3+t^2\log s)\) time: \(O(t^3)\) to aggregate the one-suit coefficients and \(O(t^2\log s)\) for truncated polynomial exponentiation. This is exactly why the method remains practical even when \(n\) and \(s\) are both \(10^8\).
Gegeben sind \(s\) Farben, jede Farbe besitzt die Ränge \(1,2,\dots,n\), und jede Steinart kommt höchstens viermal vor. Eine gültige Mahjong-artige Hand besteht aus genau \(t\) Melds und genau einem Paar, wobei ein Meld entweder ein Drilling gleicher Steine oder eine Folge aus drei aufeinanderfolgenden Rängen innerhalb derselben Farbe ist.
Gesucht ist die Anzahl aller gültigen Hände modulo \(10^9+7\). Die Implementierungen berechnen den riesigen Fall \(W(10^8,10^8,30)\), daher ist jede direkte Enumeration ausgeschlossen. Die Lösung komprimiert zuerst die lokalen Regeln einer einzelnen Farbe in einen endlichen Automaten, erzeugt daraus Ein-Farben-Polynome und kombiniert erst danach die Farben.
Sei \(W(n,s,t)\) die Anzahl gültiger Hände mit \(n\) Rängen pro Farbe, \(s\) Farben und genau \(t\) Melds. Der entscheidende Punkt ist: Verschiedene Farben wechselwirken nur über die Gesamtzahl der Melds und darüber, dass genau eine Farbe das einzige Paar enthält.
Fixiere eine Farbe und schreibe ihre Multiplizitäten als \(c_1,\dots,c_n\) mit \(c_i\in\{0,1,2,3,4\}\). Sobald an einem Rang \(c_i=0\) gilt, kann keine Folge über diese Stelle hinweg laufen.
Darum zerfällt eine Farbe in maximale zusammenhängende Blöcke positiver Werte. Jeder Block lässt sich unabhängig analysieren; global bleibt innerhalb der Farbe nur noch die Frage, wie viele Null-Lücken zwischen den Blöcken liegen. Genau deshalb zählt die Lösung zunächst zusammenhängende positive Blöcke und fügt die Nullen erst später wieder ein.
Betrachte einen positiven Block mit Häufigkeiten \(d_1,\dots,d_L\), wobei jedes \(d_i\in\{1,2,3,4\}\) liegt. Wir verarbeiten den Block von links nach rechts. Vor Rang \(i\) sei der lokale Zustand \((u,v,\pi)\):
\(u\) ist die Zahl der Folgen, die bei Rang \(i-1\) begonnen wurden und noch Steine bei Rang \(i\) und \(i+1\) benötigen.
\(v\) ist die Zahl der Folgen, die bei Rang \(i-2\) begonnen wurden und bei Rang \(i\) ihren letzten Stein brauchen.
\(\pi\in\{0,1\}\) merkt, ob das einzige Paar in diesem Block bereits verwendet wurde.
Bei Rang \(i\) sind mindestens \(u+v\) Steine fest vorgegeben, weil diese offenen Folgen fortgesetzt oder abgeschlossen werden müssen. Falls \(d_i\ge u+v\), setzen wir
$$r_i=d_i-u-v.$$
Aus diesen restlichen Steinen darf man optional \(2\) für das Paar verwenden, einige neue Folgen bei Rang \(i\) starten und den Rest in Drillinge zerlegen. Bezeichnet \(\delta\in\{0,1\}\) die Entscheidung für ein Paar an Rang \(i\), und \(q_i\) die Zahl neu gestarteter Folgen, so ist der Übergang genau dann zulässig, wenn
$$0\le q_i\le r_i-2\delta,\qquad r_i-2\delta-q_i\equiv 0 \pmod 3.$$
Der nächste Zustand ist dann
$$ (u,v,\pi)\longrightarrow(q_i,u,\max(\pi,\delta)). $$
Da für denselben Eingabewert \(d_i\) mehrere Paare \((\delta,q_i)\) möglich sein können, ist die natürliche lokale Maschine nichtdeterministisch. Die Implementierungen determinisieren sie einmal und führen danach ein gewöhnliches dynamisches Programm über die erreichbaren deterministischen Zustände aus.
Sei \(\mathcal{B}_0(L,M)\) die Anzahl positiver Blöcke der Länge \(L\) mit insgesamt \(M\) Steinen, die ohne offene Folgen und ohne Paar enden. Entsprechend sei \(\mathcal{B}_1(L,M)\) die Anzahl mit genau einem verwendeten Paar.
Diese Werte entstehen, indem der deterministische Automat für alle Blocklängen bis \(3t+2\) und alle Steinzahlen bis \(3t+2\) vorwärts geschoben wird. Diese Schranke genügt, weil eine vollständige Hand mit \(t\) Melds und einem Paar insgesamt nur \(3t+2\) Steine besitzt; also kann weder eine einzelne Farbe noch ein einzelner Block mehr beitragen.
Die Restklassen sind erzwungen:
$$\mathcal{B}_0(L,M)\neq 0 \Longrightarrow M\equiv 0 \pmod 3,$$
$$\mathcal{B}_1(L,M)\neq 0 \Longrightarrow M\equiv 2 \pmod 3.$$
Ein Block ohne Paar besteht nur aus Melds und verwendet daher ein Vielfaches von drei Steinen. Ein Block mit einem Paar benutzt genau \(2\) mehr als ein Vielfaches von drei.
Eine Farbe kann mehrere positive Blöcke besitzen, getrennt durch Ränge mit Nullbelegung. Sei \(\mathcal{D}_{0,k}(L,M)\) die Anzahl von Konfigurationen aus genau \(k\) Blöcken mit positiver Gesamtlänge \(L\), Gesamtsteinzahl \(M\) und insgesamt keinem Paar. Analog sei \(\mathcal{D}_{1,k}(L,M)\) die entsprechende Zahl mit genau einem Paar insgesamt.
Die Blockfaltung lautet
$$\mathcal{D}_{0,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_0(L',M'),$$
$$\mathcal{D}_{1,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{1,k}(L,M)\,\mathcal{B}_0(L',M')+\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_1(L',M').$$
Nur ein einziger Block darf das Paar liefern, daher hat die zweite Rekursion genau diese beiden Quellen. Außerdem kann es in einer Farbe höchstens \(t+1\) Blöcke geben, weil jeder nichtleere Block mindestens eine Gruppe beiträgt und eine vollständige Hand nur \(t\) Melds plus ein Paar besitzt.
Angenommen, eine Ein-Farben-Konfiguration verwendet \(k\) positive Blöcke mit Gesamtlänge \(L\). Dann gibt es \(n-L\) Ränge mit Belegung \(0\). Schreibe die Null-Lücken als
$$z_0+z_1+\cdots+z_k=n-L,$$
wobei \(z_0\) die führende Null-Lücke, \(z_k\) die abschließende Null-Lücke und die inneren Lücken \(z_1,\dots,z_{k-1}\) jeweils mindestens \(1\) sein müssen, damit die Blöcke getrennt bleiben.
Mit \(z_i'=z_i-1\) für \(1\le i\le k-1\) wird daraus
$$z_0+z_1'+\cdots+z_{k-1}'+z_k=n-L-k+1,$$
also ist die Zahl der Einbettungen
$$\binom{n-L+1}{k}.$$
Genau dieser Platzierungsfaktor vereinfacht den globalen Teil der Aufgabe. Beispiel: Für \(n=7\), Gesamtlänge \(L=4\) und \(k=2\) Blöcke erhält man \(\binom{7-4+1}{2}=\binom{4}{2}=6\) mögliche Platzierungen.
Nach Multiplikation jeder \(\mathcal{D}_{\varepsilon,k}(L,M)\) mit dem Platzierungsfaktor erhält man die Ein-Farben-Summen
$$A_M(n)=\sum_{k,L}\mathcal{D}_{0,k}(L,M)\binom{n-L+1}{k},$$
$$B_M(n)=\sum_{k,L}\mathcal{D}_{1,k}(L,M)\binom{n-L+1}{k}.$$
Nun definieren wir \(T_u(n)=A_{3u}(n)\) und \(P_u(n)=B_{3u+2}(n)\). \(T_u(n)\) zählt also Ein-Farben-Konfigurationen mit genau \(u\) Melds und ohne Paar, während \(P_u(n)\) Ein-Farben-Konfigurationen mit genau \(u\) Melds und dem Paar zählt.
Die abgeschnittenen erzeugenden Funktionen sind
$$\mathcal{T}_n(x)=\sum_{u\ge 0}T_u(n)x^u,\qquad \mathcal{P}_n(x)=\sum_{u\ge 0}P_u(n)x^u.$$
Da genau eine Farbe das Paar trägt, folgt für die Gesamtlösung
$$\boxed{W(n,s,t)=s\cdot [x^t]\;\mathcal{P}_n(x)\,\mathcal{T}_n(x)^{\,s-1}\pmod{10^9+7}.}$$
Der Koeffizient von \(x^t\) erzwingt, dass über alle Farben hinweg genau \(t\) Melds entstehen.
Bei nur einer Farbe, vier Rängen und genau einem Meld hat jede gültige Hand genau \(3\cdot 1+2=5\) Steine. Es gibt zwei Fälle.
Drilling plus Paar: Wähle den Rang des Drillings auf \(4\) Arten und den Rang des Paares auf eine der verbleibenden \(3\) Arten. Das liefert \(4\cdot 3=12\).
Folge plus Paar: Die einzigen Folgen sind \(123\) und \(234\), also gibt es \(2\) mögliche Folgen. Für jede davon kann das Paar an einem beliebigen der \(4\) Ränge liegen. Das gibt \(2\cdot 4=8\).
Daher
$$W(4,1,1)=12+8=20,$$
genau wie im kleinen Testfall der Implementierungen.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Pipeline. Zuerst bauen sie den erreichbaren deterministischen Automaten, der die lokalen Blockregeln kapselt. Die akzeptierenden Zustände werden dabei in zwei Klassen getrennt: Block endet ohne Paar oder Block endet mit genau einem Paar.
Anschließend läuft ein dynamisches Programm über Blocklängen und Gesamtsteinzahlen, allerdings nur für positive Multiplizitäten \(1,2,3,4\). Null-Ränge werden an dieser Stelle bewusst ausgelassen, weil sie später exakt über den Faktor \(\binom{n-L+1}{k}\) eingefügt werden.
Sobald die zusammenhängenden Blockzahlen vorliegen, führen die Implementierungen ein zweites faltungsartiges dynamisches Programm aus, das viele Blöcke innerhalb einer Farbe zusammensetzt, einmal für den Fall ohne Paar und einmal für den Fall mit einem Paar. So entstehen Tabellen nach Blockzahl, positiver Gesamtlänge und Gesamtsteinzahl.
Danach wird für jedes zulässige Paar \((k,L)\) mit \(\binom{n-L+1}{k}\) modulo \(10^9+7\) multipliziert. Weil \(k\le t+1\) klein bleibt, obwohl \(n\) riesig sein kann, wird der Binomialkoeffizient als kurzes fallendes Produkt mal modularer Inversen von \(k!\) berechnet und nicht über Fakultäten bis \(n\).
Zum Schluss werden die Ein-Farben-Koeffizienten in die abgeschnittenen Polynome \(\mathcal{T}_n(x)\) und \(\mathcal{P}_n(x)\) gepackt. Das Paar-freie Polynom wird mittels binärer Exponentiation bis zur Potenz \(s-1\) erhoben, bei jedem Schritt auf Grad \(t\) abgeschnitten, danach mit dem Paar-Polynom multipliziert, und schließlich wird der Koeffizient von \(x^t\) gelesen und mit \(s\) multipliziert.
Sei \(T=3t+2\). Der deterministische Automat hat bezüglich der Eingabeparameter konstante Größe. Daher läuft die lokale Block-Vorberechnung in \(O(T^2)\) Zeit und benötigt \(O(T^2)\) Arbeitsraum, bis auf diesen konstanten Automatenfaktor.
Der dominierende Teil ist das dynamische Programm zur Blockkombination. Es gibt \(O(T^2)\) mögliche Blocktypen \((L,M)\), jede Faltung berührt \(O(T^2)\) Tabellenzellen, und dies wiederholt sich für \(O(t)\) Blockzahlen. Da \(T=O(t)\) gilt, kostet die vollständige Vorberechnung \(O(t^5)\) Zeit bei \(O(t^3)\) gespeichertem Zustand.
Wenn die Ein-Farben-Tabellen einmal gebaut sind, benötigt die Auswertung für gegebene \(n\) und \(s\) noch \(O(t^3+t^2\log s)\) Zeit: \(O(t^3)\) für die Aggregation der Ein-Farben-Koeffizienten und \(O(t^2\log s)\) für die abgeschnittene Polynompotenz. Genau deshalb bleibt das Verfahren praktikabel, obwohl \(n\) und \(s\) beide \(10^8\) sein können.
Elimizde \(s\) farklı renk, her renkte \(1,2,\dots,n\) sıraları ve her taş tipinden en fazla dört kopya var. Geçerli bir Mahjong-benzeri el, tam olarak \(t\) adet meld ile bir adet çiftten oluşur; burada meld ya aynı taştan üçlü ya da aynı renkte ardışık üç sıradan oluşan bir seridir.
İstenen şey tüm geçerli ellerin sayısını \(10^9+7\) modunda hesaplamaktır. Uygulamalar \(W(10^8,10^8,30)\) gibi dev bir durumu çözdüğü için doğrudan tarama imkansızdır. Bu yüzden çözüm önce tek bir rengin yerel kurallarını sonlu bir otomata indirger, sonra tek-renk polinomlarını üretir ve en sonda renkleri birleştirir.
\(W(n,s,t)\), \(n\) sıra, \(s\) renk ve tam \(t\) meld içeren geçerli el sayısı olsun. Ana gözlem şudur: farklı renkler birbiriyle sadece toplam meld sayısı ve tek bir rengin çifti taşıması üzerinden etkileşir.
Tek bir rengi sabitleyip taş adetlerini \(c_1,\dots,c_n\) şeklinde yazalım; her \(c_i\) değeri \(\{0,1,2,3,4\}\) kümesindedir. Bir sırada \(c_i=0\) olduğunda hiçbir seri o noktadan geçemez.
Bu nedenle bir renk, pozitif değerlerden oluşan en büyük bitişik bloklara ayrılır. Her blok bağımsız incelenebilir; renk düzeyinde geriye sadece bu blokların arasına kaç tane sıfır boşluğu konacağı kalır. Çözümün önce bitişik pozitif blokları sayıp sıfırları daha sonra geri eklemesinin nedeni tam olarak budur.
\(d_1,\dots,d_L\) adetlerinden oluşan bir pozitif blok düşünelim; her \(d_i\in\{1,2,3,4\}\) olsun. Bloğu soldan sağa işleriz. \(i\). sıradan hemen önceki yerel durum \((u,v,\pi)\) olsun:
\(u\), \(i-1\). sırada başlamış ve \(i\) ile \(i+1\). sıralarda taş bekleyen seri sayısıdır.
\(v\), \(i-2\). sırada başlamış ve son taşı \(i\). sırada bekleyen seri sayısıdır.
\(\pi\in\{0,1\}\), bu blok içinde tek çiftin kullanılıp kullanılmadığını gösterir.
\(i\). sırada en az \(u+v\) taş zorunludur; çünkü açık serileri sürdürmek veya bitirmek için bu taşlar harcanır. Eğer \(d_i\ge u+v\) ise
$$r_i=d_i-u-v$$
tanımını yaparız. Bu kalan taşlardan isteğe bağlı olarak \(2\) tanesi çifte ayrılabilir, bir kısmıyla yeni seriler başlatılabilir ve kalan taşlar üçlüler halinde tüketilebilir. \(\delta\in\{0,1\}\) çifti o sırada kullanma kararı, \(q_i\) ise o sırada başlatılan yeni seri sayısı olsun. Geçiş tam ve ancak şu koşullarda geçerlidir:
$$0\le q_i\le r_i-2\delta,\qquad r_i-2\delta-q_i\equiv 0 \pmod 3.$$
Sonraki durum
$$ (u,v,\pi)\longrightarrow(q_i,u,\max(\pi,\delta)). $$
Aynı giriş değeri \(d_i\) için birden fazla \((\delta,q_i)\) seçimi mümkün olabildiğinden doğal yerel makine deterministik değildir. Uygulamalar bu yapıyı bir kez deterministik hale getirip daha sonra erişilebilen deterministik durumlar üzerinde standart DP uygular.
\(\mathcal{B}_0(L,M)\), uzunluğu \(L\), toplam taş sayısı \(M\) olan; açık seri bırakmadan ve çift kullanmadan biten pozitif blokların sayısı olsun. \(\mathcal{B}_1(L,M)\) ise tam bir çift kullanıp biten karşılık gelen sayı olsun.
Bu değerler, deterministik otomatın blok uzunluğu en fazla \(3t+2\) ve toplam taş sayısı en fazla \(3t+2\) olacak şekilde ilerletilmesiyle elde edilir. Bu sınır yeterlidir; çünkü \(t\) meld ve bir çiftten oluşan tam bir elde toplam taş sayısı yalnızca \(3t+2\) olabilir. Dolayısıyla tek bir renk ya da tek bir blok bundan fazla katkı veremez.
Kalan sınıflar zorunludur:
$$\mathcal{B}_0(L,M)\neq 0 \Longrightarrow M\equiv 0 \pmod 3,$$
$$\mathcal{B}_1(L,M)\neq 0 \Longrightarrow M\equiv 2 \pmod 3.$$
Çiftsiz bir blok tamamen meldlerden oluştuğu için taş sayısı 3'ün katıdır. Tek çift içeren bir blok ise 3'ün katından tam \(2\) fazla taş kullanır.
Bir renk, aralarında sıfır adetli sıralar bulunan birden çok pozitif blok içerebilir. \(\mathcal{D}_{0,k}(L,M)\), toplam pozitif uzunluğu \(L\), toplam taş sayısı \(M\) olan ve toplamda hiç çift içermeyen tam \(k\) bloklu yapıların sayısı olsun. \(\mathcal{D}_{1,k}(L,M)\) ise toplamda tam bir çift içeren karşılık gelen sayı olsun.
Blok konvolüsyonu şu şekildedir:
$$\mathcal{D}_{0,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_0(L',M'),$$
$$\mathcal{D}_{1,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{1,k}(L,M)\,\mathcal{B}_0(L',M')+\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_1(L',M').$$
Yalnızca tek bir blok çifti sağlayabilir; bu yüzden ikinci bağıntıda tam iki kaynak vardır. Ayrıca bir renkte en fazla \(t+1\) blok bulunabilir, çünkü boş olmayan her blok en az bir grup getirir ve tam elde yalnızca \(t\) meld ile bir çift vardır.
Bir tek-renk yapısının toplam uzunluğu \(L\) olan \(k\) pozitif blok kullandığını varsayalım. Geriye \(n-L\) tane sıfır adetli sıra kalır. Bu sıfır boşluklarını
$$z_0+z_1+\cdots+z_k=n-L$$
şeklinde yazalım. Burada \(z_0\) baştaki, \(z_k\) sondaki sıfır boşluğudur; iç boşluklar \(z_1,\dots,z_{k-1}\) ise blokların ayrık kalması için en az \(1\) olmalıdır.
\(1\le i\le k-1\) için \(z_i'=z_i-1\) tanımıyla
$$z_0+z_1'+\cdots+z_{k-1}'+z_k=n-L-k+1$$
elde edilir. Dolayısıyla yerleştirme sayısı
$$\binom{n-L+1}{k}$$
olur. Bu katsayı çözümün en önemli sadeleşmelerinden biridir. Örneğin \(n=7\), toplam uzunluk \(L=4\) ve blok sayısı \(k=2\) ise yerleştirme sayısı \(\binom{7-4+1}{2}=\binom{4}{2}=6\) olur.
Her \(\mathcal{D}_{\varepsilon,k}(L,M)\) terimi yerleştirme katsayısı ile çarpıldıktan sonra tek-renk toplamları
$$A_M(n)=\sum_{k,L}\mathcal{D}_{0,k}(L,M)\binom{n-L+1}{k},$$
$$B_M(n)=\sum_{k,L}\mathcal{D}_{1,k}(L,M)\binom{n-L+1}{k}$$
elde edilir. Şimdi \(T_u(n)=A_{3u}(n)\) ve \(P_u(n)=B_{3u+2}(n)\) tanımlarını yapalım. Yani \(T_u(n)\), tek bir rengin tam \(u\) meld üretip çift üretmediği; \(P_u(n)\) ise tam \(u\) meld ile çifti birlikte ürettiği durumları sayar.
Kesilmiş üreteç fonksiyonları
$$\mathcal{T}_n(x)=\sum_{u\ge 0}T_u(n)x^u,\qquad \mathcal{P}_n(x)=\sum_{u\ge 0}P_u(n)x^u$$
olsun. Çifti tam olarak bir renk taşıdığı için genel cevap
$$\boxed{W(n,s,t)=s\cdot [x^t]\;\mathcal{P}_n(x)\,\mathcal{T}_n(x)^{\,s-1}\pmod{10^9+7}.}$$
\(x^t\) katsayısı, tüm renkler boyunca toplam meld sayısının tam olarak \(t\) olmasını zorlar.
Tek renk, dört sıra ve tam bir meld durumunda her geçerli elde toplam \(3\cdot 1+2=5\) taş vardır. İki olasılık bulunur.
Üçlü artı çift: Üçlünün sırası \(4\) farklı şekilde, çiftin sırası ise kalan \(3\) sıradan biri olarak seçilir. Toplam \(4\cdot 3=12\).
Seri artı çift: Olası seriler yalnızca \(123\) ve \(234\) olduğundan \(2\) seri seçeneği vardır. Her seri için çift, \(4\) sıranın herhangi birine yerleştirilebilir. Bu da \(2\cdot 4=8\) verir.
Dolayısıyla
$$W(4,1,1)=12+8=20,$$
ve bu değer uygulamaların küçük doğrulama örneğiyle aynıdır.
C++, Python ve Java uygulamaları aynı işlem hattını izler. Önce yukarıdaki yerel blok kurallarını temsil eden erişilebilir deterministik otomat kurulur. Kabul durumları iki sınıfa ayrılır: çiftsiz biten bloklar ve tam bir çiftle biten bloklar.
Sonra blok uzunluğu ve toplam taş sayısı üzerinde bir DP çalıştırılır; ancak burada yalnızca pozitif adetler \(1,2,3,4\) kullanılır. Sıfır adetli sıralar bu aşamada bilerek dışarıda bırakılır, çünkü daha sonra \(\binom{n-L+1}{k}\) yerleştirme katsayısı ile tam olarak geri eklenirler.
Bitişik blok sayıları hesaplandıktan sonra, uygulamalar ikinci bir konvolüsyon tipi DP çalıştırarak aynı renk içindeki birçok bloğu birleştirir. Bu işlem çiftsiz toplam durumlar ve tek çiftli toplam durumlar için ayrı ayrı yapılır. Sonuç tabloları blok sayısı, toplam pozitif uzunluk ve toplam taş sayısına göre indekslenir.
Daha sonra her uygun \((k,L)\) çifti için \(\binom{n-L+1}{k}\) katsayısı \(10^9+7\) modunda hesaplanıp çarpılır. \(k\le t+1\) küçük kaldığı için, \(n\) çok büyük olsa bile binom katsayısı uzun bir önhesap yerine kısa bir düşen çarpım ile \(k!\)'nin modüler tersi kullanılarak bulunur.
Son adımda tek-renk katsayıları kesilmiş \(\mathcal{T}_n(x)\) ve \(\mathcal{P}_n(x)\) polinomlarına yerleştirilir. Çiftsiz polinom \((s-1)\). kuvvete ikili üs alma ile yükseltilir, her çarpımda derece \(t\) üzerinde kesilir, ardından çiftli polinomla çarpılır ve \(x^t\) katsayısı okunup \(s\) ile çarpılır.
\(T=3t+2\) olsun. Deterministik otomatın boyutu giriş parametrelerine göre sabittir. Bu yüzden yerel blok önhesabı \(O(T^2)\) zamanda ve \(O(T^2)\) çalışma alanında yapılır; sabit otomat faktörü bu ifadeye dahil değildir.
Baskın maliyet blokları birleştiren DP'dedir. Olası blok tipleri \((L,M)\) için \(O(T^2)\) seçenek vardır, her konvolüsyon \(O(T^2)\) hücreye dokunur ve bu işlem \(O(t)\) farklı blok sayısı için tekrarlanır. \(T=O(t)\) olduğundan toplam önhesap maliyeti \(O(t^5)\) zaman ve \(O(t^3)\) depolanmış durum olur.
Tek-renk tabloları hazırlandıktan sonra belirli \(n\) ve \(s\) için son değerlendirme \(O(t^3+t^2\log s)\) zamanda yapılır: \(O(t^3)\) tek-renk katsayılarını toplamak, \(O(t^2\log s)\) ise kesilmiş polinom üs alımı içindir. Bu nedenle \(n\) ve \(s\) değerleri \(10^8\) olsa bile yöntem pratik kalır.
Tenemos \(s\) palos, cada palo posee los rangos \(1,2,\dots,n\), y cada tipo de ficha aparece como mucho cuatro veces. Una mano válida de estilo Mahjong consta de exactamente \(t\) melds y una pareja, donde un meld es o bien un trío de fichas iguales o bien una escalera de tres rangos consecutivos dentro del mismo palo.
La tarea es contar todas las manos válidas módulo \(10^9+7\). Las implementaciones evalúan el caso enorme \(W(10^8,10^8,30)\), así que el recorrido directo del espacio de estados queda descartado. La solución primero comprime las restricciones locales de un palo en un autómata finito, luego construye polinomios de un solo palo y solo al final combina los palos.
Sea \(W(n,s,t)\) el número de manos válidas con \(n\) rangos por palo, \(s\) palos y exactamente \(t\) melds. La observación central es que los palos solo interactúan a través del número total de melds y del hecho de que exactamente un palo contiene la pareja única.
Fijemos un palo y escribamos sus multiplicidades como \(c_1,\dots,c_n\), con cada \(c_i\in\{0,1,2,3,4\}\). En cuanto aparece un \(c_i=0\), ninguna escalera puede cruzar esa posición.
Por eso un palo se descompone en bloques máximos contiguos de valores positivos. Cada bloque puede analizarse por separado, y a nivel global dentro de ese palo solo queda decidir cuántos huecos de ceros se insertan entre bloques. Esa es la razón por la que el método cuenta primero bloques positivos contiguos y solo después recoloca los ceros.
Consideremos un bloque positivo con multiplicidades \(d_1,\dots,d_L\), donde cada \(d_i\in\{1,2,3,4\}\). Procesamos el bloque de izquierda a derecha. Antes del rango \(i\), el estado local es \((u,v,\pi)\):
\(u\) es el número de escaleras iniciadas en el rango \(i-1\) que aún necesitan fichas en los rangos \(i\) e \(i+1\).
\(v\) es el número de escaleras iniciadas en el rango \(i-2\) que necesitan una ficha final en el rango \(i\).
\(\pi\in\{0,1\}\) indica si la pareja única ya fue usada dentro del bloque.
En el rango \(i\), al menos \(u+v\) fichas están forzadas, porque deben continuar o cerrar las escaleras abiertas. Si \(d_i\ge u+v\), definimos
$$r_i=d_i-u-v.$$
Con estas fichas restantes podemos gastar opcionalmente \(2\) en la pareja, iniciar algunas escaleras nuevas en el rango \(i\) y usar el resto en tríos. Si \(\delta\in\{0,1\}\) indica si la pareja se usa en el rango \(i\), y \(q_i\) es el número de escaleras nuevas que empiezan allí, entonces la transición es válida exactamente cuando
$$0\le q_i\le r_i-2\delta,\qquad r_i-2\delta-q_i\equiv 0 \pmod 3.$$
El siguiente estado pasa a ser
$$ (u,v,\pi)\longrightarrow(q_i,u,\max(\pi,\delta)). $$
Como para un mismo valor de entrada \(d_i\) puede haber varias elecciones posibles de \((\delta,q_i)\), la máquina local natural es no determinista. Las implementaciones la determinizan una vez y luego ejecutan programación dinámica ordinaria sobre los estados deterministas alcanzables.
Sea \(\mathcal{B}_0(L,M)\) el número de bloques positivos de longitud \(L\) y total \(M\) que terminan sin escaleras abiertas y sin pareja. Sea \(\mathcal{B}_1(L,M)\) el conteo análogo con exactamente una pareja usada.
Estos valores se obtienen propagando el autómata determinista para todas las longitudes de bloque hasta \(3t+2\) y todos los totales de fichas hasta \(3t+2\). Ese corte basta porque una mano completa con \(t\) melds y una pareja contiene solo \(3t+2\) fichas en total, así que ni un solo palo ni un solo bloque pueden aportar más que eso.
Las clases residuales están forzadas:
$$\mathcal{B}_0(L,M)\neq 0 \Longrightarrow M\equiv 0 \pmod 3,$$
$$\mathcal{B}_1(L,M)\neq 0 \Longrightarrow M\equiv 2 \pmod 3.$$
En efecto, un bloque sin pareja se compone solo de melds y por tanto usa un múltiplo de tres fichas. Un bloque con una pareja usa exactamente \(2\) más que un múltiplo de tres.
Un palo puede contener varios bloques positivos separados por rangos de multiplicidad cero. Sea \(\mathcal{D}_{0,k}(L,M)\) el número de configuraciones con exactamente \(k\) bloques, longitud positiva total \(L\), total de fichas \(M\) y ninguna pareja en conjunto. Sea \(\mathcal{D}_{1,k}(L,M)\) el valor correspondiente con exactamente una pareja en conjunto.
La convolución de bloques es
$$\mathcal{D}_{0,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_0(L',M'),$$
$$\mathcal{D}_{1,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{1,k}(L,M)\,\mathcal{B}_0(L',M')+\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_1(L',M').$$
Solo un bloque puede aportar la pareja, por eso la segunda recurrencia tiene exactamente esas dos fuentes. Además, en un palo no puede haber más de \(t+1\) bloques, porque cada bloque no vacío aporta al menos un grupo y una mano completa contiene solo \(t\) melds más una pareja.
Supongamos que una configuración de un palo usa \(k\) bloques positivos cuya longitud total es \(L\). Entonces quedan \(n-L\) rangos con multiplicidad cero. Escribimos los huecos de ceros como
$$z_0+z_1+\cdots+z_k=n-L,$$
donde \(z_0\) es el hueco inicial, \(z_k\) es el final, y los huecos interiores \(z_1,\dots,z_{k-1}\) deben satisfacer \(z_i\ge 1\) para mantener separados los bloques.
Si definimos \(z_i'=z_i-1\) para \(1\le i\le k-1\), obtenemos
$$z_0+z_1'+\cdots+z_{k-1}'+z_k=n-L-k+1,$$
de modo que el número de incrustaciones es
$$\binom{n-L+1}{k}.$$
Este factor de colocación es una de las simplificaciones principales del método. Por ejemplo, si \(n=7\), la longitud positiva total es \(L=4\) y hay \(k=2\) bloques, entonces el número de colocaciones es \(\binom{7-4+1}{2}=\binom{4}{2}=6\).
Después de multiplicar cada \(\mathcal{D}_{\varepsilon,k}(L,M)\) por el factor de colocación, obtenemos los totales de un palo
$$A_M(n)=\sum_{k,L}\mathcal{D}_{0,k}(L,M)\binom{n-L+1}{k},$$
$$B_M(n)=\sum_{k,L}\mathcal{D}_{1,k}(L,M)\binom{n-L+1}{k}.$$
Definimos ahora \(T_u(n)=A_{3u}(n)\) y \(P_u(n)=B_{3u+2}(n)\). En otras palabras, \(T_u(n)\) cuenta configuraciones de un solo palo que aportan exactamente \(u\) melds y ninguna pareja, mientras que \(P_u(n)\) cuenta las que aportan exactamente \(u\) melds junto con la pareja.
Introducimos las funciones generadoras truncadas
$$\mathcal{T}_n(x)=\sum_{u\ge 0}T_u(n)x^u,\qquad \mathcal{P}_n(x)=\sum_{u\ge 0}P_u(n)x^u.$$
Como exactamente un palo lleva la pareja, la respuesta global es
$$\boxed{W(n,s,t)=s\cdot [x^t]\;\mathcal{P}_n(x)\,\mathcal{T}_n(x)^{\,s-1}\pmod{10^9+7}.}$$
El coeficiente de \(x^t\) impone que el número total de melds entre todos los palos sea exactamente \(t\).
Con un solo palo, cuatro rangos y exactamente un meld, toda mano válida tiene \(3\cdot 1+2=5\) fichas. Hay dos casos.
Trío más pareja: elegimos el rango del trío de \(4\) maneras y el rango de la pareja entre los \(3\) restantes. Eso da \(4\cdot 3=12\).
Escalera más pareja: las únicas escaleras son \(123\) y \(234\), así que hay \(2\) posibilidades. Para cada una, la pareja puede situarse en cualquiera de los \(4\) rangos. Eso produce \(2\cdot 4=8\).
Por tanto
$$W(4,1,1)=12+8=20,$$
en acuerdo con el pequeño caso de control usado por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero construyen el autómata determinista alcanzable que representa las reglas locales de un bloque. Los estados de aceptación se separan en dos familias: bloques que terminan sin pareja y bloques que terminan con exactamente una pareja.
Después ejecutan una programación dinámica sobre la longitud del bloque y el total de fichas, pero solo usando multiplicidades positivas \(1,2,3,4\). Los rangos con cero fichas se excluyen de forma deliberada en esta etapa porque más adelante se reincorporan exactamente mediante el factor \(\binom{n-L+1}{k}\).
Una vez conocidos los conteos de bloques contiguos, las implementaciones aplican una segunda programación dinámica de tipo convolución para combinar muchos bloques dentro de un mismo palo, una vez para el caso sin pareja y otra para el caso con una pareja. Así se obtienen tablas indexadas por número de bloques, longitud positiva total y total de fichas.
Luego, para cada par admisible \((k,L)\), multiplican por \(\binom{n-L+1}{k}\) módulo \(10^9+7\). Como \(k\le t+1\) es pequeño incluso cuando \(n\) es enorme, el coeficiente binomial se calcula como un producto descendente corto multiplicado por el inverso modular de \(k!\), en vez de precomputar factoriales hasta \(n\).
Por último, los coeficientes de un palo se empaquetan en los polinomios truncados \(\mathcal{T}_n(x)\) y \(\mathcal{P}_n(x)\). El polinomio sin pareja se eleva a la potencia \(s-1\) mediante exponenciación binaria con truncamiento en grado \(t\), se multiplica por el polinomio con pareja, y se extrae el coeficiente de \(x^t\), que después se multiplica por \(s\).
Sea \(T=3t+2\). El autómata determinista tiene tamaño constante con respecto a los parámetros de entrada. Por tanto, la precomputación local de bloques cuesta \(O(T^2)\) tiempo y \(O(T^2)\) memoria de trabajo, salvo por ese factor constante del autómata.
La parte dominante es la programación dinámica que combina bloques. Existen \(O(T^2)\) tipos posibles de bloque \((L,M)\), cada convolución toca \(O(T^2)\) celdas de tabla, y esto se repite para \(O(t)\) cantidades de bloques. Como \(T=O(t)\), la precomputación completa cuesta \(O(t^5)\) tiempo y mantiene \(O(t^3)\) estado almacenado.
Una vez construidas las tablas de un solo palo, la evaluación final para valores dados de \(n\) y \(s\) requiere \(O(t^3+t^2\log s)\) tiempo: \(O(t^3)\) para agregar los coeficientes de un palo y \(O(t^2\log s)\) para la exponenciación polinómica truncada. Esa es la razón por la que el método sigue siendo viable aunque \(n\) y \(s\) valgan \(10^8\).
题目有 \(s\) 个花色，每个花色有 \(1,2,\dots,n\) 这些点数，而且每一种牌最多出现四张。一个合法的麻将式手牌恰好由 \(t\) 个面子和一对将牌组成，其中面子要么是同一张牌的刻子，要么是同一花色里连续三个点数的顺子。
要求是把所有合法手牌的数量对 \(10^9+7\) 取模。实现实际计算的是 \(W(10^8,10^8,30)\) 这样的超大参数，因此不可能暴力枚举。整套方法的思路是：先把单个花色的局部约束压缩成有限自动机，再构造单花色计数多项式，最后才在花色层面合并。
记 \(W(n,s,t)\) 为每个花色有 \(n\) 个点数、总共有 \(s\) 个花色、并且恰好包含 \(t\) 个面子的合法手牌数量。最关键的观察是：不同花色之间并不会在局部结构上相互影响，它们只通过“总面子数必须等于 \(t\)”以及“全局只能出现一对将牌”这两个条件发生耦合。
先固定一个花色，把它在各个点数上的张数写成 \(c_1,\dots,c_n\)，其中每个 \(c_i\in\{0,1,2,3,4\}\)。一旦某个点数处出现 \(c_i=0\)，任何顺子都不可能跨过这个位置。
因此，一个花色会自然分裂成若干个“所有张数都为正”的极大连续区间。每个这样的区间都可以独立分析，而花色层面剩下的唯一问题就是：这些正区间之间夹了多少个零。也正因为如此，算法先数 连续正块，然后再用组合数把零间隔重新插回去。
设一个正块的张数为 \(d_1,\dots,d_L\)，其中每个 \(d_i\in\{1,2,3,4\}\)。我们从左到右处理这个块。处理到第 \(i\) 个点数之前，用状态 \((u,v,\pi)\) 描述局部信息：
\(u\) 表示在第 \(i-1\) 个点数开启、并且还需要第 \(i\) 和第 \(i+1\) 个点数来完成的顺子数量。
\(v\) 表示在第 \(i-2\) 个点数开启、并且只差第 \(i\) 个点数就结束的顺子数量。
\(\pi\in\{0,1\}\) 表示这个正块内部是否已经使用过那唯一的一对将牌。
在第 \(i\) 个点数处，至少有 \(u+v\) 张牌是被强制使用的，因为它们必须拿去延续或者收尾已经开启的顺子。如果 \(d_i\ge u+v\)，令
$$r_i=d_i-u-v.$$
这些剩余牌可以做三件事：可选地拿出 \(2\) 张作为将牌、用若干张在当前位置新开顺子、其余的凑成刻子。若 \(\delta\in\{0,1\}\) 表示是否在当前位置使用将牌，\(q_i\) 表示在当前位置新开的顺子数，那么转移成立当且仅当
$$0\le q_i\le r_i-2\delta,\qquad r_i-2\delta-q_i\equiv 0 \pmod 3.$$
新的状态为
$$ (u,v,\pi)\longrightarrow(q_i,u,\max(\pi,\delta)). $$
由于同一个输入值 \(d_i\) 可能对应多个 \((\delta,q_i)\) 选择，所以自然得到的是一个非确定型局部机器。实现先把它做一次子集构造，变成确定型自动机，然后再在可达状态上运行普通动态规划。
记 \(\mathcal{B}_0(L,M)\) 为长度为 \(L\)、总牌数为 \(M\) 的连续正块中，能够在没有未完成顺子且没有将牌的情况下结束的方案数。记 \(\mathcal{B}_1(L,M)\) 为对应地恰好使用了一对将牌的方案数。
这些值通过在确定型自动机上推进所有长度不超过 \(3t+2\)、总牌数不超过 \(3t+2\) 的情况得到。这个上界已经足够，因为完整手牌总共只有 \(3t+2\) 张牌，所以任何一个花色、甚至其中一个连续正块，都不可能贡献超过这个数量。
非零项的模 \(3\) 余数是被结构强制决定的：
$$\mathcal{B}_0(L,M)\neq 0 \Longrightarrow M\equiv 0 \pmod 3,$$
$$\mathcal{B}_1(L,M)\neq 0 \Longrightarrow M\equiv 2 \pmod 3.$$
原因很直接：没有将牌的块完全由面子组成，所以牌数必然是 \(3\) 的倍数；包含一对将牌的块则比 \(3\) 的倍数多 \(2\) 张。
一个花色可以包含多个连续正块，它们之间由若干个零张数点数隔开。记 \(\mathcal{D}_{0,k}(L,M)\) 为恰好使用 \(k\) 个正块、总正长度为 \(L\)、总牌数为 \(M\)、并且整体上不含将牌的方案数。类似地，\(\mathcal{D}_{1,k}(L,M)\) 表示整体上恰好含有一对将牌的方案数。
块级卷积满足
$$\mathcal{D}_{0,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_0(L',M'),$$
$$\mathcal{D}_{1,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{1,k}(L,M)\,\mathcal{B}_0(L',M')+\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_1(L',M').$$
第二个递推式之所以只有这两项，是因为全局最多只能有一对将牌，所以只有“前面已经有将牌，本块不带将牌”和“前面没有将牌，本块提供将牌”这两种可能。另一方面，一个花色中的块数不会超过 \(t+1\)，因为每个非空块至少要提供一个组，而完整手牌总共只有 \(t\) 个面子加一对将牌。
假设某个单花色配置使用了 \(k\) 个正块，它们的正长度总和为 \(L\)。那么剩下 \(n-L\) 个位置的张数为零。把这些零间隔写成
$$z_0+z_1+\cdots+z_k=n-L,$$
其中 \(z_0\) 是最左端零段，\(z_k\) 是最右端零段，而内部的 \(z_1,\dots,z_{k-1}\) 都必须至少为 \(1\)，否则相邻两个正块就会连成一个更大的块。
令 \(z_i'=z_i-1\)（\(1\le i\le k-1\)），就得到
$$z_0+z_1'+\cdots+z_{k-1}'+z_k=n-L-k+1.$$
于是可放置方式数为
$$\binom{n-L+1}{k}.$$
这是整个算法里非常关键的组合化简。比如 \(n=7\)、总正长度 \(L=4\)、块数 \(k=2\) 时，放置数就是 \(\binom{7-4+1}{2}=\binom{4}{2}=6\)。
将每个 \(\mathcal{D}_{\varepsilon,k}(L,M)\) 乘上放置因子后，得到单花色总数
$$A_M(n)=\sum_{k,L}\mathcal{D}_{0,k}(L,M)\binom{n-L+1}{k},$$
$$B_M(n)=\sum_{k,L}\mathcal{D}_{1,k}(L,M)\binom{n-L+1}{k}.$$
接着定义 \(T_u(n)=A_{3u}(n)\) 与 \(P_u(n)=B_{3u+2}(n)\)。也就是说，\(T_u(n)\) 统计单个花色恰好贡献 \(u\) 个面子且不带将牌的方案数，\(P_u(n)\) 统计单个花色恰好贡献 \(u\) 个面子并同时承担那一对将牌的方案数。
于是定义截断生成函数
$$\mathcal{T}_n(x)=\sum_{u\ge 0}T_u(n)x^u,\qquad \mathcal{P}_n(x)=\sum_{u\ge 0}P_u(n)x^u.$$
因为恰好只有一个花色携带将牌，所以总答案为
$$\boxed{W(n,s,t)=s\cdot [x^t]\;\mathcal{P}_n(x)\,\mathcal{T}_n(x)^{\,s-1}\pmod{10^9+7}.}$$
\([x^t]\) 表示取 \(x^t\) 的系数，它正好保证所有花色贡献的面子总数恰为 \(t\)。
当只有一个花色、四个点数并且恰好需要一个面子时，合法手牌总牌数是 \(3\cdot 1+2=5\)。这时可以直接人工分类。
刻子加将牌：刻子的点数有 \(4\) 种选法，将牌必须选在另外 \(3\) 个点数之一，所以共有 \(4\cdot 3=12\) 种。
顺子加将牌：唯一的顺子只有 \(123\) 和 \(234\) 两种。每种顺子下，将牌都可以落在 \(4\) 个点数中的任意一个，因此共有 \(2\cdot 4=8\) 种。
所以
$$W(4,1,1)=12+8=20,$$
这与实现中使用的小规模校验值完全一致。
C++、Python 和 Java 三个实现遵循完全相同的阶段。第一步是建立上面那个局部规则所对应的可达确定型自动机，并把接受状态分成两类：一类表示块结束时没有将牌，另一类表示块结束时恰好已经用了将牌。
第二步是在“块长度”和“总牌数”两个维度上做动态规划，不过这里只允许正张数 \(1,2,3,4\)。零张数位置在这一步被刻意忽略，因为它们会在后面通过显式的放置因子 \(\binom{n-L+1}{k}\) 重新加入。
拿到连续正块的计数后，实现再做第二层卷积型动态规划，把多个块合并成一个完整花色，分别处理“整体无将牌”和“整体恰有一对将牌”两种状态。这样就得到按块数、总正长度和总牌数索引的表。
随后，对每个可行的 \((k,L)\) 都乘上 \(\binom{n-L+1}{k}\) 模 \(10^9+7\)。因为 \(k\le t+1\) 始终很小，即使 \(n\) 极大，也不需要预处理到 \(n\) 的阶乘；只需计算一个很短的下降乘积，再乘上 \(k!\) 的模逆元即可。
最后，把单花色系数装入截断多项式 \(\mathcal{T}_n(x)\) 和 \(\mathcal{P}_n(x)\)。无将牌多项式通过二进制幂提升到 \(s-1\) 次方，并在每次乘法后截断到次数 \(t\)；再与含将牌多项式相乘，取出 \(x^t\) 系数，最后乘上 \(s\)。
记 \(T=3t+2\)。确定型自动机的规模相对于输入参数是常数，因此局部块预处理需要 \(O(T^2)\) 时间和 \(O(T^2)\) 工作空间，这里隐藏了一个自动机常数因子。
真正占主导的是块合并动态规划。可能的块类型 \((L,M)\) 有 \(O(T^2)\) 种，每次卷积会访问 \(O(T^2)\) 个表格单元，而这个过程还要对 \(O(t)\) 个块数层重复。由于 \(T=O(t)\)，完整预处理的时间复杂度是 \(O(t^5)\)，存储状态量是 \(O(t^3)\)。
当单花色表已经构建完成后，给定 \(n\) 和 \(s\) 的最终计算只需 \(O(t^3+t^2\log s)\) 时间：其中 \(O(t^3)\) 用来聚合单花色系数，\(O(t^2\log s)\) 用来做截断多项式快速幂。这也解释了为什么即使 \(n\) 和 \(s\) 都达到 \(10^8\)，该方法仍然可行。
Имеется \(s\) мастей, в каждой масти есть ранги \(1,2,\dots,n\), и каждая конкретная плитка может встречаться не более четырёх раз. Корректная Mahjong-подобная рука состоит ровно из \(t\) мeld'ов и одной пары, где meld означает либо тройку одинаковых плиток, либо последовательность из трёх соседних рангов внутри одной масти.
Нужно посчитать число всех корректных рук по модулю \(10^9+7\). Реально вычисляется огромный случай \(W(10^8,10^8,30)\), так что полный перебор невозможен. Поэтому решение сначала сжимает локальные ограничения одной масти в конечный автомат, затем строит полиномы для одной масти и только после этого объединяет масти между собой.
Пусть \(W(n,s,t)\) обозначает число корректных рук при \(n\) рангах в масти, \(s\) мастях и ровно \(t\) meld'ах. Ключевое наблюдение состоит в том, что разные масти взаимодействуют только через суммарное число meld'ов и через условие, что ровно одна масть содержит единственную пару.
Зафиксируем одну масть и запишем её кратности как \(c_1,\dots,c_n\), где каждый \(c_i\in\{0,1,2,3,4\}\). Если в некотором ранге стоит \(c_i=0\), ни одна последовательность не может пересечь это место.
Следовательно, масть естественным образом распадается на максимальные связные блоки положительных значений. Каждый такой блок можно анализировать независимо, а на уровне всей масти остаётся лишь вопрос, сколько нулевых промежутков вставить между блоками. Именно поэтому алгоритм сначала считает непрерывные положительные блоки, а нули добавляет позже комбинаторным множителем.
Рассмотрим положительный блок с кратностями \(d_1,\dots,d_L\), где каждое \(d_i\in\{1,2,3,4\}\). Идём слева направо. Перед обработкой ранга \(i\) локальное состояние равно \((u,v,\pi)\):
\(u\) обозначает число последовательностей, начатых в ранге \(i-1\) и ещё требующих плитки рангов \(i\) и \(i+1\).
\(v\) обозначает число последовательностей, начатых в ранге \(i-2\) и нуждающихся в последней плитке ранга \(i\).
\(\pi\in\{0,1\}\) показывает, использована ли уже единственная пара внутри текущего блока.
В ранге \(i\) как минимум \(u+v\) плиток уже обязаны быть потрачены, потому что они продолжают или завершают ранее открытые последовательности. Если \(d_i\ge u+v\), положим
$$r_i=d_i-u-v.$$
Оставшиеся плитки можно распределить так: при желании взять \(2\) плитки на пару, часть пустить на новые последовательности, начинающиеся в ранге \(i\), а остаток разложить на тройки. Если \(\delta\in\{0,1\}\) означает использование пары в ранге \(i\), а \(q_i\) обозначает число новых последовательностей, стартующих там, то переход допустим тогда и только тогда, когда
$$0\le q_i\le r_i-2\delta,\qquad r_i-2\delta-q_i\equiv 0 \pmod 3.$$
Следующее состояние равно
$$ (u,v,\pi)\longrightarrow(q_i,u,\max(\pi,\delta)). $$
Для одного и того же входного значения \(d_i\) может существовать несколько допустимых пар \((\delta,q_i)\), поэтому естественная локальная машина является недетерминированной. Реализации один раз проводят детерминизацию методом подмножеств, после чего запускают обычное динамическое программирование по достижимым детерминированным состояниям.
Обозначим через \(\mathcal{B}_0(L,M)\) число положительных блоков длины \(L\) и общего веса \(M\), которые заканчиваются без незавершённых последовательностей и без пары. Аналогично, \(\mathcal{B}_1(L,M)\) обозначает число таких блоков с ровно одной использованной парой.
Эти значения получаются путём продвижения детерминированного автомата по всем длинам блока до \(3t+2\) и всем суммарным числам плиток до \(3t+2\). Этого достаточно, потому что в полной руке с \(t\) meld'ами и одной парой всего \(3t+2\) плиток, значит, ни одна масть и ни один отдельный блок не могут дать больше.
Остатки по модулю \(3\) здесь принудительны:
$$\mathcal{B}_0(L,M)\neq 0 \Longrightarrow M\equiv 0 \pmod 3,$$
$$\mathcal{B}_1(L,M)\neq 0 \Longrightarrow M\equiv 2 \pmod 3.$$
Блок без пары целиком состоит из meld'ов и потому использует кратное трём число плиток. Блок с одной парой использует на \(2\) больше, чем кратное трём.
В одной масти может быть несколько положительных блоков, разделённых рангами с нулевой кратностью. Пусть \(\mathcal{D}_{0,k}(L,M)\) обозначает число конфигураций ровно из \(k\) блоков с суммарной положительной длиной \(L\), суммарным числом плиток \(M\) и без пары в целом. Аналогично, \(\mathcal{D}_{1,k}(L,M)\) считает случаи с ровно одной парой в целом.
Блочная свёртка имеет вид
$$\mathcal{D}_{0,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_0(L',M'),$$
$$\mathcal{D}_{1,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{1,k}(L,M)\,\mathcal{B}_0(L',M')+\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_1(L',M').$$
Во второй формуле ровно два источника, потому что только один блок во всей масти может принести пару. Кроме того, число блоков в одной масти не превосходит \(t+1\): каждый непустой блок даёт как минимум одну группу, а вся рука содержит лишь \(t\) meld'ов и одну пару.
Пусть конфигурация одной масти использует \(k\) положительных блоков суммарной длины \(L\). Тогда остаётся \(n-L\) рангов с нулевой кратностью. Запишем нулевые промежутки как
$$z_0+z_1+\cdots+z_k=n-L,$$
где \(z_0\) - начальный промежуток, \(z_k\) - конечный, а внутренние промежутки \(z_1,\dots,z_{k-1}\) обязаны быть не меньше \(1\), иначе соседние блоки сольются.
Если положить \(z_i'=z_i-1\) для \(1\le i\le k-1\), получится
$$z_0+z_1'+\cdots+z_{k-1}'+z_k=n-L-k+1,$$
и число размещений равно
$$\binom{n-L+1}{k}.$$
Это один из главных комбинаторных шагов всей схемы. Например, при \(n=7\), суммарной положительной длине \(L=4\) и \(k=2\) блоках число размещений равно \(\binom{7-4+1}{2}=\binom{4}{2}=6\).
После умножения каждого \(\mathcal{D}_{\varepsilon,k}(L,M)\) на множитель размещения получаем одномастные суммы
$$A_M(n)=\sum_{k,L}\mathcal{D}_{0,k}(L,M)\binom{n-L+1}{k},$$
$$B_M(n)=\sum_{k,L}\mathcal{D}_{1,k}(L,M)\binom{n-L+1}{k}.$$
Теперь определим \(T_u(n)=A_{3u}(n)\) и \(P_u(n)=B_{3u+2}(n)\). Иными словами, \(T_u(n)\) считает конфигурации одной масти, дающие ровно \(u\) meld'ов и не содержащие пару, а \(P_u(n)\) - конфигурации, дающие ровно \(u\) meld'ов вместе с парой.
Введём усечённые производящие функции
$$\mathcal{T}_n(x)=\sum_{u\ge 0}T_u(n)x^u,\qquad \mathcal{P}_n(x)=\sum_{u\ge 0}P_u(n)x^u.$$
Поскольку ровно одна масть несёт пару, общий ответ имеет вид
$$\boxed{W(n,s,t)=s\cdot [x^t]\;\mathcal{P}_n(x)\,\mathcal{T}_n(x)^{\,s-1}\pmod{10^9+7}.}$$
Извлечение коэффициента при \(x^t\) гарантирует, что суммарное число meld'ов по всем мастям ровно равно \(t\).
Если масть всего одна, рангов четыре и нужен ровно один meld, то любая корректная рука содержит \(3\cdot 1+2=5\) плиток. Здесь есть два случая.
Тройка плюс пара: ранг тройки выбирается \(4\) способами, а ранг пары - одним из оставшихся \(3\). Итого \(4\cdot 3=12\).
Последовательность плюс пара: возможны только последовательности \(123\) и \(234\), то есть \(2\) варианта. Для каждой из них пару можно поместить в любой из \(4\) рангов. Получаем \(2\cdot 4=8\).
Следовательно,
$$W(4,1,1)=12+8=20,$$
что совпадает с малым контрольным случаем из реализаций.
Реализации на C++, Python и Java используют одну и ту же последовательность шагов. Сначала строится достижимый детерминированный автомат, представляющий локальные правила блока. Принимающие состояния делятся на две группы: блок завершился без пары и блок завершился с ровно одной парой.
Затем запускается динамическое программирование по длине блока и суммарному числу плиток, но только для положительных кратностей \(1,2,3,4\). Нулевые ранги на этом этапе сознательно исключаются, потому что потом они возвращаются точным размещающим множителем \(\binom{n-L+1}{k}\).
Когда подсчитаны все непрерывные блоки, реализации выполняют второе свёрточное динамическое программирование, объединяя множество блоков в одну масть: отдельно для общего случая без пары и для общего случая с одной парой. В результате получаются таблицы по числу блоков, суммарной положительной длине и суммарному числу плиток.
Далее для каждой допустимой пары \((k,L)\) выполняется умножение на \(\binom{n-L+1}{k}\) по модулю \(10^9+7\). Поскольку \(k\le t+1\) мало даже при огромном \(n\), биномиальный коэффициент вычисляется коротким падающим произведением, умноженным на модульную обратную величину к \(k!\), а не через факториалы до \(n\).
Наконец, коэффициенты одной масти упаковываются в усечённые полиномы \(\mathcal{T}_n(x)\) и \(\mathcal{P}_n(x)\). Полином без пары возводится в степень \(s-1\) двоичным возведением в степень с усечением по степени \(t\), затем умножается на полином с парой, после чего берётся коэффициент при \(x^t\) и умножается на \(s\).
Положим \(T=3t+2\). Детерминированный автомат имеет постоянный размер относительно параметров входа. Поэтому локальная предобработка блоков требует \(O(T^2)\) времени и \(O(T^2)\) рабочей памяти, с точностью до постоянного автомата.
Основная стоимость приходится на динамическое программирование, комбинирующее блоки. Возможных типов блоков \((L,M)\) имеется \(O(T^2)\), одна свёртка затрагивает \(O(T^2)\) ячеек таблицы, и это повторяется для \(O(t)\) уровней по числу блоков. Так как \(T=O(t)\), полная предобработка имеет сложность \(O(t^5)\) по времени и хранит \(O(t^3)\) состояния.
После построения одномастных таблиц финальное вычисление для заданных \(n\) и \(s\) занимает \(O(t^3+t^2\log s)\) времени: \(O(t^3)\) уходит на агрегацию одномастных коэффициентов и \(O(t^2\log s)\) - на усечённое полиномиальное возведение в степень. Именно поэтому метод остаётся практичным даже при \(n=s=10^8\).
لدينا \(s\) ألوان، وفي كل لون الرتب \(1,2,\dots,n\)، وكل نوع من القطع يظهر في أقصى حد أربع مرات. اليد الصحيحة على نمط Mahjong تتكون من \(t\) مجموعات ثلاثية تمامًا مع زوج واحد، حيث تكون المجموعة الثلاثية إما ثلاث قطع متماثلة أو متتالية من ثلاث رتب متجاورة داخل اللون نفسه.
المطلوب هو عدّ جميع الأيدي الصحيحة بترديد \(10^9+7\). والتنفيذات تحسب الحالة الضخمة \(W(10^8,10^8,30)\)، لذلك فالحصر المباشر غير ممكن. ولهذا يبدأ الحل بضغط القيود المحلية للون الواحد في أوتوماتون منتهٍ، ثم يبني كثيرات حدود خاصة باللون الواحد، ثم يدمج الألوان في المرحلة الأخيرة فقط.
لنرمز بـ \(W(n,s,t)\) إلى عدد الأيدي الصحيحة عندما يكون في كل لون \(n\) رتب، ولدينا \(s\) ألوان، ونريد بالضبط \(t\) مجموعات ثلاثية. الملاحظة الأساسية هي أن الألوان المختلفة لا تتفاعل محليًا، بل يقتصر التفاعل على شرطين فقط: مجموع عدد المجموعات الثلاثية عبر جميع الألوان يجب أن يساوي \(t\)، وباليد كلها يوجد زوج واحد فقط.
ثبّت لونًا واحدًا، واكتب أعداد القطع في رتب هذا اللون على صورة \(c_1,\dots,c_n\)، حيث كل \(c_i\in\{0,1,2,3,4\}\). إذا ظهر موضع فيه \(c_i=0\)، فلا يمكن لأي متتالية أن تعبر ذلك الموضع.
إذًا ينقسم اللون طبيعيًا إلى كتل متجاورة عظمى تكون فيها جميع القيم موجبة. ويمكن تحليل كل كتلة على حدة، ثم تبقى على مستوى اللون كله مسألة واحدة فقط: كم عدد الفجوات الصفرية بين هذه الكتل؟ ولهذا يعدّ الحل أولًا الكتل الموجبة المتجاورة ثم يعيد إدخال الأصفار لاحقًا بعامل توافقي صريح.
لنأخذ كتلة موجبة ذات تكرارات \(d_1,\dots,d_L\)، حيث كل \(d_i\in\{1,2,3,4\}\). نعالج الكتلة من اليسار إلى اليمين. قبل الرتبة \(i\) تكون الحالة المحلية \((u,v,\pi)\):
\(u\) هو عدد المتتاليات التي بدأت في الرتبة \(i-1\) وما زالت تحتاج إلى قطع عند الرتبتين \(i\) و\(i+1\).
\(v\) هو عدد المتتاليات التي بدأت في الرتبة \(i-2\) وتحتاج إلى قطعة أخيرة عند الرتبة \(i\).
\(\pi\in\{0,1\}\) يحدد هل استُخدم الزوج الوحيد داخل هذه الكتلة أم لا.
عند الرتبة \(i\)، هناك على الأقل \(u+v\) قطع مفروضة الاستعمال، لأنها يجب أن تواصل أو تُنهي المتتاليات المفتوحة سابقًا. إذا كان \(d_i\ge u+v\)، نعرّف
$$r_i=d_i-u-v.$$
هذه القطع المتبقية يمكن التعامل معها بثلاث طرق: قد نقتطع منها \(2\) للزوج، وقد نبدأ بها بعض المتتاليات الجديدة في الرتبة \(i\)، وما يبقى يجب أن يتجمع في ثلاثيات متطابقة. إذا كانت \(\delta\in\{0,1\}\) تدل على استخدام الزوج في الرتبة \(i\)، وكان \(q_i\) هو عدد المتتاليات الجديدة التي تبدأ هناك، فإن الانتقال يكون صحيحًا إذا وفقط إذا تحقق
$$0\le q_i\le r_i-2\delta,\qquad r_i-2\delta-q_i\equiv 0 \pmod 3.$$
ثم تصبح الحالة التالية
$$ (u,v,\pi)\longrightarrow(q_i,u,\max(\pi,\delta)). $$
وبما أن القيمة نفسها \(d_i\) قد تسمح بعدة اختيارات مختلفة لـ \((\delta,q_i)\)، فإن الآلة المحلية الطبيعية غير حتمية. لذلك تقوم التنفيذات أولًا بتحويلها إلى أوتوماتون حتمي بطريقة المجموعات الجزئية، ثم تشغّل بعد ذلك برمجة ديناميكية عادية على الحالات الحتمية القابلة للوصول.
لنرمز بـ \(\mathcal{B}_0(L,M)\) إلى عدد الكتل الموجبة ذات الطول \(L\) ومجموع القطع \(M\) التي تنتهي من دون أي متتالية غير مكتملة ومن دون زوج. ولنرمز بـ \(\mathcal{B}_1(L,M)\) إلى العدد المناظر عندما تحتوي الكتلة على زوج واحد بالضبط.
تُحسب هذه القيم بدفع الأوتوماتون الحتمي عبر جميع الأطوال حتى \(3t+2\) وجميع مجاميع القطع حتى \(3t+2\). وهذا الحد كافٍ لأن اليد الكاملة التي تحتوي \(t\) مجموعات ثلاثية وزوجًا واحدًا لا تملك أصلًا إلا \(3t+2\) قطعة، فلا يمكن لكتلة واحدة أو حتى لون واحد أن يساهم بأكثر من ذلك.
وفئات البواقي modulo \(3\) مفروضة بنيويًا:
$$\mathcal{B}_0(L,M)\neq 0 \Longrightarrow M\equiv 0 \pmod 3,$$
$$\mathcal{B}_1(L,M)\neq 0 \Longrightarrow M\equiv 2 \pmod 3.$$
فالكتلة الخالية من الزوج مؤلفة من مجموعات ثلاثية فقط، ولذلك يكون عدد قطعها من مضاعفات \(3\). أما الكتلة التي تحتوي زوجًا واحدًا فتزيد بمقدار \(2\) على مضاعف لـ \(3\).
قد يحتوي اللون الواحد على عدة كتل موجبة تفصل بينها رتب عددها صفر. ولْيكن \(\mathcal{D}_{0,k}(L,M)\) هو عدد التراكيب التي تستخدم بالضبط \(k\) كتل، ويكون مجموع أطوالها الموجبة \(L\)، ومجموع قطعها \(M\)، ولا تحتوي في المجموع على أي زوج. وبالمثل، فإن \(\mathcal{D}_{1,k}(L,M)\) يعدّ الحالات التي تحتوي في المجموع على زوج واحد بالضبط.
وعند مستوى الكتل تصبح عملية الدمج
$$\mathcal{D}_{0,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_0(L',M'),$$
$$\mathcal{D}_{1,k+1}(L+L',M+M')\;{+}{=}\;\mathcal{D}_{1,k}(L,M)\,\mathcal{B}_0(L',M')+\mathcal{D}_{0,k}(L,M)\,\mathcal{B}_1(L',M').$$
ولا يظهر في العلاقة الثانية إلا هذان المصدران لأن زوجًا واحدًا فقط مسموح به على مستوى اللون كله. كذلك لا يمكن أن يزيد عدد الكتل في اللون الواحد على \(t+1\)، لأن كل كتلة غير فارغة يجب أن تسهم بمجموعة واحدة على الأقل، بينما اليد الكاملة لا تحتوي إلا على \(t\) مجموعات ثلاثية وزوج واحد.
افترض أن تركيبًا بلون واحد يستخدم \(k\) كتل موجبة ويكون مجموع أطوالها \(L\). إذن يبقى \(n-L\) رتبة ذات عدد صفر. اكتب الفجوات الصفرية على الصورة
$$z_0+z_1+\cdots+z_k=n-L,$$
حيث \(z_0\) هي الفجوة الأولى، و\(z_k\) هي الفجوة الأخيرة، أما الفجوات الداخلية \(z_1,\dots,z_{k-1}\) فيجب أن تحقق \(z_i\ge 1\) حتى تبقى الكتل منفصلة.
إذا وضعنا \(z_i'=z_i-1\) لكل \(1\le i\le k-1\)، نحصل على
$$z_0+z_1'+\cdots+z_{k-1}'+z_k=n-L-k+1,$$
ومن ثم يكون عدد طرق التموضع
$$\binom{n-L+1}{k}.$$
وهذا العامل التوافقي أحد أهم تبسيطات الحل. فمثلًا إذا كان \(n=7\)، وكان مجموع الأطوال الموجبة \(L=4\)، وعدد الكتل \(k=2\)، فإن عدد التموضعات يساوي \(\binom{7-4+1}{2}=\binom{4}{2}=6\).
بعد ضرب كل \(\mathcal{D}_{\varepsilon,k}(L,M)\) في عامل التموضع، نحصل على مجاميع اللون الواحد
$$A_M(n)=\sum_{k,L}\mathcal{D}_{0,k}(L,M)\binom{n-L+1}{k},$$
$$B_M(n)=\sum_{k,L}\mathcal{D}_{1,k}(L,M)\binom{n-L+1}{k}.$$
ثم نعرّف \(T_u(n)=A_{3u}(n)\) و\(P_u(n)=B_{3u+2}(n)\). أي أن \(T_u(n)\) يعدّ تراكيب اللون الواحد التي تسهم بـ \(u\) مجموعات ثلاثية من دون زوج، بينما \(P_u(n)\) يعدّ التراكيب التي تسهم بـ \(u\) مجموعات ثلاثية ومعها الزوج.
نقدم بعد ذلك الدوال المولدة المقطوعة
$$\mathcal{T}_n(x)=\sum_{u\ge 0}T_u(n)x^u,\qquad \mathcal{P}_n(x)=\sum_{u\ge 0}P_u(n)x^u.$$
وبما أن لونًا واحدًا فقط يحمل الزوج، فإن الجواب النهائي هو
$$\boxed{W(n,s,t)=s\cdot [x^t]\;\mathcal{P}_n(x)\,\mathcal{T}_n(x)^{\,s-1}\pmod{10^9+7}.}$$
واستخراج معامل \(x^t\) يفرض أن يكون مجموع عدد المجموعات الثلاثية على جميع الألوان مساويًا تمامًا لـ \(t\).
إذا كان لدينا لون واحد فقط وأربع رتب ونريد مجموعة ثلاثية واحدة بالضبط، فإن كل يد صحيحة تحتوي \(3\cdot 1+2=5\) قطع. وعندئذ توجد حالتان فقط.
ثلاثية متماثلة مع زوج: نختار رتبة الثلاثية بـ \(4\) طرق، ثم نختار رتبة الزوج من بين \(3\) رتب متبقية، فنحصل على \(4\cdot 3=12\).
متتالية مع زوج: المتتاليتان الوحيدتان هما \(123\) و\(234\)، أي \(2\) احتمالان. ولكل متتالية يمكن وضع الزوج في أي رتبة من الرتب الأربع، فنحصل على \(2\cdot 4=8\).
إذن
$$W(4,1,1)=12+8=20,$$
وهو نفس مثال التحقق الصغير الموجود في التنفيذات.
تتبع تنفيذات C++ وPython وJava خط الأنابيب نفسه. في البداية يُبنى الأوتوماتون الحتمي القابل للوصول الذي يعبّر عن قواعد الكتلة المحلية السابقة. ثم تُقسّم حالات القبول إلى فئتين: كتل تنتهي بلا زوج، وكتل تنتهي بزوج واحد بالضبط.
بعد ذلك تُشغَّل برمجة ديناميكية على طول الكتلة ومجموع القطع، مع السماح فقط بالتكرارات الموجبة \(1,2,3,4\). أما الرتب ذات التكرار الصفري فتُستبعد عمدًا من هذه المرحلة، لأنها ستعاد لاحقًا بصورة دقيقة عبر عامل التموضع \(\binom{n-L+1}{k}\).
وبعد معرفة أعداد الكتل المتجاورة، تشغّل التنفيذات برمجة ديناميكية ثانية من نمط الالتفاف لدمج عدد كبير من الكتل داخل اللون الواحد، مرة للحالة التي لا تحتوي زوجًا، ومرة للحالة التي تحتوي زوجًا واحدًا. وهكذا تتكوّن جداول مفهرسة بعدد الكتل، ومجموع الطول الموجب، ومجموع القطع.
ثم يُضرب كل زوج مسموح \((k,L)\) في \(\binom{n-L+1}{k}\) بترديد \(10^9+7\). ولأن \(k\le t+1\) صغير حتى عندما يكون \(n\) هائلًا، فلا حاجة إلى حساب مضروب حتى \(n\)؛ يكفي حاصل ضرب تنازلي قصير مع معكوس \(k!\) بترديد أولي.
وفي النهاية تُحزَّم معاملات اللون الواحد داخل كثيري الحدود المقطوعين \(\mathcal{T}_n(x)\) و\(\mathcal{P}_n(x)\). ثم يُرفع كثير الحدود الخالي من الزوج إلى القوة \(s-1\) باستعمال الأس الثنائي مع قطع الدرجات الأعلى من \(t\)، وبعد ذلك يُضرب في كثير الحدود الذي يحمل الزوج، ويُستخرج معامل \(x^t\)، ثم يُضرب الناتج في \(s\).
لنضع \(T=3t+2\). حجم الأوتوماتون الحتمي ثابت بالنسبة إلى معاملات المسألة، ولذلك فإن الحساب المسبق المحلي للكتل يحتاج إلى \(O(T^2)\) زمنًا و\(O(T^2)\) ذاكرة عمل، مع إهمال عامل ثابت خاص بالأوتوماتون نفسه.
أما الكلفة المسيطرة فتأتي من البرمجة الديناميكية التي تجمع الكتل. فهناك \(O(T^2)\) أنواع ممكنة من الكتل \((L,M)\)، وكل عملية التفاف تلامس \(O(T^2)\) خلية، ويتكرر ذلك عبر \(O(t)\) مستويات لعدد الكتل. وبما أن \(T=O(t)\)، فإن الكلفة الكلية للحساب المسبق هي \(O(t^5)\) زمنًا مع \(O(t^3)\) حالة مخزنة.
وبعد بناء جداول اللون الواحد، يصبح التقييم النهائي لقيم \(n\) و\(s\) المعطاة في حدود \(O(t^3+t^2\log s)\): جزء \(O(t^3)\) لتجميع معاملات اللون الواحد، وجزء \(O(t^2\log s)\) لرفع كثيرات الحدود المقطوعة بسرعة. وهذا يفسر بقاء الطريقة عملية حتى عندما يكون كل من \(n\) و\(s\) مساويًا لـ \(10^8\).