Let \(12n\) musicians be split on the first day into \(m=3n\) quartets. On the second day they must be split into \(t=4n\) trios, and no pair of musicians is allowed to play together twice. Because every pair inside a first-day quartet has already met, a valid second-day trio can contain at most one musician from each quartet. The task is to count all valid second-day schedules modulo
$$10^9+7.$$
The fixed first-day partition gives \(m\) distinguishable quartets. The whole problem becomes: how many ways can \(t\) trios be formed so that every trio draws one musician from three different quartets, while each quartet contributes all four of its musicians exactly once?
Introduce an \(m\times t\) matrix \(A\) with entries in \(\{0,1\}\):
$$A_{q,r}=1 \iff \text{trio }r\text{ contains one musician from quartet }q.$$
The no-repeat condition forces \(A_{q,r}\) to be binary, because a trio cannot take two musicians from the same quartet.
Each trio has exactly three musicians, so every column sum is
$$\sum_{q=1}^{m} A_{q,r}=3.$$
Each quartet contains four musicians and each of them must appear on day 2 exactly once, so every row sum is
$$\sum_{r=1}^{t} A_{q,r}=4.$$
Therefore the first combinatorial subproblem is to count \(0\)-\(1\) matrices with row sum \(4\) and column sum \(3\).
Process the trio columns from left to right. After some number of processed trios, every quartet has been used \(0\), \(1\), \(2\), \(3\), or \(4\) times. Quartets already used \(4\) times are finished and never matter again, so the state only needs
$$\mathbf{c}=(c_0,c_1,c_2,c_3),$$
where \(c_j\) is the number of quartets used exactly \(j\) times so far. The number used \(4\) times is implicit:
$$c_4=m-c_0-c_1-c_2-c_3.$$
Initially no day-2 trio has been built, hence
$$\mathbf{c}_{\text{start}}=(m,0,0,0).$$
To build the next trio, choose
$$x_j \text{ quartets from class }j \qquad (j=0,1,2,3),$$
subject to
$$x_0+x_1+x_2+x_3=3,\qquad 0\le x_j\le c_j.$$
This means the trio takes one musician from \(x_0\) previously unused quartets, one musician from \(x_1\) quartets already used once, and so on. The number of ways to make that choice is
$$\binom{c_0}{x_0}\binom{c_1}{x_1}\binom{c_2}{x_2}\binom{c_3}{x_3}.$$
There are only
$$\binom{3+4-1}{4-1}=\binom{6}{3}=20$$
possible quadruples \((x_0,x_1,x_2,x_3)\), so each state has a very small transition menu.
Every chosen quartet moves from usage class \(j\) to usage class \(j+1\). Therefore
$$c_0'=c_0-x_0,$$
$$c_1'=c_1-x_1+x_0,$$
$$c_2'=c_2-x_2+x_1,$$
$$c_3'=c_3-x_3+x_2.$$
If \(D_s(c_0,c_1,c_2,c_3)\) denotes the number of ordered partial incidence matrices after \(s\) processed trios, then the recurrence is
$$D_{s+1}(c_0',c_1',c_2',c_3') \mathrel{+}= D_s(c_0,c_1,c_2,c_3)\prod_{j=0}^{3}\binom{c_j}{x_j}.$$
The base case is
$$D_0(m,0,0,0)=1.$$
After all \(t\) trio columns have been processed, every quartet must have been used four times, so the terminal state is
$$D_t(0,0,0,0).$$
This quantity is the number of ordered incidence matrices. Call it \(N_{\text{mat}}\).
Once an incidence matrix is fixed, each quartet is attached to exactly four trio columns. Its four labeled musicians can be assigned to those four appearances in
$$4!=24$$
ways. Different quartets act independently, so the total refinement factor is
$$24^m.$$
However, the dynamic program processed the trio columns in an artificial order. A finished day-2 schedule is an unordered collection of \(t\) distinct trios, and every such schedule is counted once for each permutation of those \(t\) trio columns. Therefore we divide by \(t!\):
$$f(12n)=N_{\text{mat}}\cdot 24^m\cdot \frac{1}{t!}\pmod{10^9+7}.$$
Because \(10^9+7\) is prime, \((t!)^{-1}\) is computed with modular exponentiation using Fermat's little theorem.
For \(12\) musicians we have \(n=1\), so
$$m=3,\qquad t=4.$$
There are exactly three first-day quartets. Every second-day trio must use three different quartets, so each trio must take one musician from each of the three quartets. Hence the incidence matrix is forced: every one of its \(3\times 4\) entries is \(1\). Thus
$$N_{\text{mat}}=1.$$
Now each quartet distributes its four musicians across the four trio positions in \(4!\) ways, giving
$$24^3$$
ordered assignments. Since the four trios themselves are unordered, divide by
$$4!=24.$$
So the final count is
$$f(12)=\frac{24^3}{24}=24^2=576,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations all follow the same plan. They compute \(m=3n\) and \(t=4n\), precompute the binomial values \(\binom{i}{0},\binom{i}{1},\binom{i}{2},\binom{i}{3}\) for \(0\le i\le m\), and enumerate the \(20\) admissible pick patterns \((x_0,x_1,x_2,x_3)\).
The dynamic program stores only the currently reachable states \((c_0,c_1,c_2,c_3)\) in a hash map, which keeps the state space compressed. For each processed trio, the implementation loops over the current states, applies every legal pick pattern, multiplies by the corresponding product of binomial coefficients, and accumulates the result for the next layer modulo \(10^9+7\).
After \(t\) layers, the implementation reads the value at the final state \((0,0,0,0)\), multiplies by \(24^m\), computes \(t!\) modulo \(10^9+7\), inverts that factorial by fast modular exponentiation, and multiplies once more. The small checkpoints \(f(12)=576\) and \(f(24)=509089824\) are used to verify that the recurrence has been implemented correctly.
Let \(S\) be the maximum number of reachable DP states in any layer. Each state tries only \(20\) transition patterns, so the main loop runs in
$$O(20tS)=O(tS)$$
time. The binomial precomputation costs \(O(m)\), and the modular exponentiations for \(24^m\) and \((t!)^{-1}\) are negligible compared with the state transitions. The memory usage is
$$O(S),$$
because only the current and next hash-map layers are stored.
Es gibt \(12n\) Musiker. Am ersten Tag werden sie in \(m=3n\) Quartette eingeteilt, am zweiten Tag in \(t=4n\) Trios. Kein Musikerpaar darf zweimal zusammen auftreten. Da innerhalb eines Quartetts vom ersten Tag bereits jedes Paar zusammen war, darf ein gültiges Trio vom zweiten Tag aus jedem Quartett höchstens einen Musiker enthalten. Gesucht ist die Anzahl aller gültigen zweiten-Tages-Einteilungen modulo
$$10^9+7.$$
Die Quartette des ersten Tages gelten als fest und unterscheidbar. Damit reduziert sich die Aufgabe auf die Frage, wie man \(t\) Trios so bildet, dass jedes Trio Musiker aus genau drei verschiedenen Quartetten verwendet und jedes Quartett alle vier seiner Mitglieder genau einmal auf den zweiten Tag verteilt.
Wir führen eine \(m\times t\)-Matrix \(A\) mit Einträgen aus \(\{0,1\}\) ein:
$$A_{q,r}=1 \iff \text{Trio }r\text{ enthält einen Musiker aus Quartett }q.$$
Die Bedingung „kein Paar zweimal“ erzwingt die Binärität der Matrix, denn ein Trio darf nicht zwei Musiker aus demselben Quartett aufnehmen.
Jedes Trio hat genau drei Musiker, also gilt für jede Spalte
$$\sum_{q=1}^{m} A_{q,r}=3.$$
Jedes Quartett besitzt vier Musiker, die am zweiten Tag alle genau einmal auftreten müssen, also gilt für jede Zeile
$$\sum_{r=1}^{t} A_{q,r}=4.$$
Damit müssen wir zunächst die Anzahl der \(0\)-\(1\)-Matrizen mit Zeilensumme \(4\) und Spaltensumme \(3\) bestimmen.
Wir verarbeiten die Trio-Spalten von links nach rechts. Nach einigen bereits gebildeten Trios wurde jedes Quartett genau \(0\), \(1\), \(2\), \(3\) oder \(4\) Mal verwendet. Quartette mit \(4\) Einsätzen sind abgeschlossen und müssen nicht mehr explizit gespeichert werden. Daher genügt der Zustand
$$\mathbf{c}=(c_0,c_1,c_2,c_3),$$
wobei \(c_j\) die Anzahl der Quartette bezeichnet, die bisher genau \(j\) Mal benutzt wurden. Die Anzahl vollständig verbrauchter Quartette ist implizit:
$$c_4=m-c_0-c_1-c_2-c_3.$$
Am Anfang ist noch kein Trio gebaut worden, also
$$\mathbf{c}_{\text{start}}=(m,0,0,0).$$
Für das nächste Trio wählen wir
$$x_j \text{ Quartette aus Klasse }j \qquad (j=0,1,2,3),$$
unter den Nebenbedingungen
$$x_0+x_1+x_2+x_3=3,\qquad 0\le x_j\le c_j.$$
Das Trio nimmt also je einen Musiker aus \(x_0\) bisher unbenutzten Quartetten, aus \(x_1\) einmal benutzten Quartetten usw. Die Anzahl dieser Möglichkeiten ist
$$\binom{c_0}{x_0}\binom{c_1}{x_1}\binom{c_2}{x_2}\binom{c_3}{x_3}.$$
Es gibt nur
$$\binom{6}{3}=20$$
zulässige Vierer-Tupel \((x_0,x_1,x_2,x_3)\), also besitzt jeder Zustand nur sehr wenige mögliche Folgezustände.
Jedes gewählte Quartett wandert von Nutzungsklasse \(j\) nach \(j+1\). Daher gilt
$$c_0'=c_0-x_0,$$
$$c_1'=c_1-x_1+x_0,$$
$$c_2'=c_2-x_2+x_1,$$
$$c_3'=c_3-x_3+x_2.$$
Bezeichnet \(D_s(c_0,c_1,c_2,c_3)\) die Anzahl geordneter partieller Inzidenzmatrizen nach \(s\) verarbeiteten Trios, dann lautet die Rekurrenz
$$D_{s+1}(c_0',c_1',c_2',c_3') \mathrel{+}= D_s(c_0,c_1,c_2,c_3)\prod_{j=0}^{3}\binom{c_j}{x_j}.$$
Der Startwert ist
$$D_0(m,0,0,0)=1.$$
Nach allen \(t\) Trio-Spalten müssen sämtliche Quartette viermal benutzt worden sein, also endet die Rechnung im Zustand
$$D_t(0,0,0,0).$$
Diesen Wert nennen wir \(N_{\text{mat}}\): die Anzahl der geordneten Inzidenzmatrizen.
Ist eine Inzidenzmatrix fest, dann ist jedes Quartett mit genau vier Trio-Spalten verbunden. Seine vier beschrifteten Musiker können diesen vier Vorkommen in
$$4!=24$$
Arten zugeordnet werden. Über alle Quartette hinweg ergibt das den Faktor
$$24^m.$$
Die dynamische Programmierung verarbeitet die Trio-Spalten jedoch in künstlicher Reihenfolge. Ein fertiger Plan des zweiten Tages ist eine ungeordnete Menge von \(t\) verschiedenen Trios und wird daher für jede Permutation dieser \(t\) Spalten einmal gezählt. Deshalb teilen wir durch \(t!\):
$$f(12n)=N_{\text{mat}}\cdot 24^m\cdot \frac{1}{t!}\pmod{10^9+7}.$$
Da \(10^9+7\) prim ist, wird \((t!)^{-1}\) per modularer Potenzierung mit dem Satz von Fermat berechnet.
Für \(12\) Musiker ist \(n=1\), also
$$m=3,\qquad t=4.$$
Es gibt genau drei Quartette vom ersten Tag. Jedes Trio des zweiten Tages muss drei verschiedene Quartette benutzen und enthält damit zwangsläufig je einen Musiker aus jedem dieser drei Quartette. Die Inzidenzmatrix ist also eindeutig: alle \(3\times 4\) Einträge sind \(1\). Somit
$$N_{\text{mat}}=1.$$
Jedes Quartett verteilt anschließend seine vier Musiker in \(4!\) Arten auf die vier Trio-Positionen, also insgesamt
$$24^3$$
geordnete Zuweisungen. Da die vier Trios selbst ungeordnet sind, teilen wir durch
$$4!=24.$$
Damit folgt
$$f(12)=\frac{24^3}{24}=24^2=576,$$
genau der Kontrollwert der Implementierung.
Die Implementierungen in C++, Python und Java verwenden denselben Ablauf. Zunächst werden \(m=3n\) und \(t=4n\) berechnet. Danach werden die Binomialwerte \(\binom{i}{0},\binom{i}{1},\binom{i}{2},\binom{i}{3}\) für \(0\le i\le m\) vorbereitet und alle \(20\) möglichen Pick-Muster \((x_0,x_1,x_2,x_3)\) erzeugt.
Die DP speichert nur tatsächlich erreichbare Zustände \((c_0,c_1,c_2,c_3)\) in einer Hash-Map. Für jedes bereits verarbeitete Trio läuft das Programm über diese Zustände, probiert jedes zulässige Pick-Muster aus, multipliziert mit dem zugehörigen Produkt von Binomialkoeffizienten und akkumuliert den Beitrag im nächsten Layer modulo \(10^9+7\).
Nach \(t\) Schritten wird der Wert im Endzustand \((0,0,0,0)\) ausgelesen, mit \(24^m\) multipliziert, dann \(t!\) modulo \(10^9+7\) berechnet und per schneller modularer Exponentiation invertiert. Außerdem werden die Kontrollwerte \(f(12)=576\) und \(f(24)=509089824\) geprüft.
Sei \(S\) die maximale Anzahl erreichbarer DP-Zustände in einer Schicht. Jeder Zustand betrachtet nur \(20\) Übergangsmuster. Daher beträgt die Laufzeit
$$O(20tS)=O(tS).$$
Die Vorberechnung der Binomialkoeffizienten kostet \(O(m)\), und die modularen Potenzen für \(24^m\) sowie \((t!)^{-1}\) sind im Vergleich klein. Der Speicherverbrauch ist
$$O(S),$$
weil nur die aktuelle und die nächste Hash-Map-Schicht gehalten werden.
\(12n\) müzisyen var. İlk gün bunlar \(m=3n\) adet dörtlü gruba ayrılıyor. İkinci gün ise \(t=4n\) adet üçlü grup oluşturuluyor ve hiçbir müzisyen çifti iki kez birlikte çalamıyor. İlk gün aynı dörtlüde bulunan her ikili zaten bir kez birlikte çaldığı için, geçerli bir ikinci gün üçlüsü aynı dörtlüden en fazla bir kişi alabilir. İstenen şey, tüm geçerli ikinci gün düzenlerinin sayısını
$$10^9+7$$
modunda bulmaktır.
İlk günün dörtlüleri sabit ve ayırt edilebilir kabul edilir. Böylece problem şu hale gelir: \(t\) adet üçlü grup öyle kurulmalı ki her üçlü üç farklı dörtlüden birer müzisyen alsın ve her dörtlü dört üyesini de ikinci gün tam birer kez kullansın.
\(\{0,1\}\) değerli \(m\times t\) boyutlu bir \(A\) matrisi tanımlayalım:
$$A_{q,r}=1 \iff r\text{. üçlü grup, }q\text{. dörtlüden bir müzisyen içeriyor.}$$
“Aynı çift iki kez gelmesin” koşulu yüzünden bu matris ikili olmak zorundadır; çünkü bir üçlü aynı dörtlüden iki kişi alamaz.
Her üçlüde tam üç müzisyen olduğundan sütun toplamları
$$\sum_{q=1}^{m} A_{q,r}=3$$
olur. Her dörtlünün dört üyesi ikinci gün tam birer kez yer aldığı için satır toplamları da
$$\sum_{r=1}^{t} A_{q,r}=4$$
olur. Dolayısıyla ilk alt problem, satır toplamı \(4\) ve sütun toplamı \(3\) olan \(0\)-\(1\) matrisleri saymaktır.
Üçlü sütunlarını soldan sağa işleyelim. Bazı sütunlar işlendiğinde her dörtlü şimdiye kadar \(0\), \(1\), \(2\), \(3\) ya da \(4\) kez kullanılmıştır. \(4\) kez kullanılmış olanlar tamamlanmıştır ve artık yeni bir üçlüye katkı vermez. Bu yüzden durumu
$$\mathbf{c}=(c_0,c_1,c_2,c_3)$$
ile tutmak yeterlidir; burada \(c_j\), şu ana dek tam \(j\) kez kullanılmış dörtlü sayısıdır. Dört kez kullanılanların sayısı örtük olarak
$$c_4=m-c_0-c_1-c_2-c_3$$
şeklindedir. Başlangıçta henüz hiç üçlü kurulmadığı için
$$\mathbf{c}_{\text{başlangıç}}=(m,0,0,0)$$
olur.
Sıradaki üçlü için
$$x_j \text{ adet dörtlü, }j\text{ kullanım sınıfından seçilsin } \qquad (j=0,1,2,3).$$
Bunlar
$$x_0+x_1+x_2+x_3=3,\qquad 0\le x_j\le c_j$$
koşullarını sağlamalıdır. Yani yeni üçlü; henüz hiç kullanılmamış \(x_0\) dörtlüden, bir kez kullanılmış \(x_1\) dörtlüden vb. birer müzisyen alır. Böyle bir seçim sayısı
$$\binom{c_0}{x_0}\binom{c_1}{x_1}\binom{c_2}{x_2}\binom{c_3}{x_3}$$
kadardır. Ayrıca \(3\)'ün \(4\) sınıfa zayıf dağılımlarının sayısı
$$\binom{6}{3}=20$$
olduğu için, her durumdan çıkabilecek geçiş sayısı çok küçüktür.
Seçilen her dörtlü, bulunduğu sınıftan bir sonraki sınıfa geçer. Bu yüzden
$$c_0'=c_0-x_0,$$
$$c_1'=c_1-x_1+x_0,$$
$$c_2'=c_2-x_2+x_1,$$
$$c_3'=c_3-x_3+x_2$$
olur. Eğer \(D_s(c_0,c_1,c_2,c_3)\), \(s\) adet üçlü işlendiğinde elde edilen sıralı kısmi matris sayısını gösteriyorsa, özyineleme
$$D_{s+1}(c_0',c_1',c_2',c_3') \mathrel{+}= D_s(c_0,c_1,c_2,c_3)\prod_{j=0}^{3}\binom{c_j}{x_j}$$
şeklindedir. Başlangıç koşulu
$$D_0(m,0,0,0)=1$$
ve tüm \(t\) sütun işlendiğinde hedef durum
$$D_t(0,0,0,0)$$
olur. Buna sıralı ilişki matrisi sayısı, yani \(N_{\text{mat}}\), diyelim.
Bir ilişki matrisi sabitlendiğinde her dörtlü tam dört üçlü sütununa bağlanmıştır. O dörtlünün etiketli dört müzisyeni bu dört görünüme
$$4!=24$$
farklı biçimde yerleştirilebilir. Dörtlüler bağımsız olduğu için toplam çarpan
$$24^m$$
olur. Fakat dinamik program üçlü sütunlarını yapay bir sırayla işledi. Gerçekte ikinci gün programı, \(t\) farklı üçlünün sırasız bir kümesidir ve aynı son düzen bu \(t\) sütunun her permütasyonu için bir kez sayılır. Bu yüzden
$$f(12n)=N_{\text{mat}}\cdot 24^m\cdot \frac{1}{t!}\pmod{10^9+7}$$
yazılır. Modül asal olduğu için \((t!)^{-1}\) Fermat'ın küçük teoremiyle hızlı üs alma kullanılarak bulunur.
\(12\) müzisyen için \(n=1\) olduğundan
$$m=3,\qquad t=4$$
elde edilir. İlk günden üç dörtlü vardır. İkinci gün kurulacak her üçlü, üç farklı dörtlü kullanmak zorunda olduğundan, aslında her üçlü bu üç dörtlünün her birinden birer kişi almak zorundadır. Dolayısıyla ilişki matrisi tektir: tüm \(3\times 4\) girişler \(1\)'dir. Yani
$$N_{\text{mat}}=1.$$
Sonra her dörtlü dört müzisyenini dört üçlü konumuna \(4!\) biçimde dağıtır; toplam
$$24^3$$
sıralı atama vardır. Dört üçlü kendi aralarında sırasız olduğu için
$$4!=24$$
ile bölünür. Sonuç:
$$f(12)=\frac{24^3}{24}=24^2=576,$$
ki bu, uygulamanın kullandığı kontrol değeriyle aynıdır.
C++, Python ve Java uygulamalarının üçü de aynı planı izler. Önce \(m=3n\) ve \(t=4n\) hesaplanır. Ardından \(0\le i\le m\) için \(\binom{i}{0},\binom{i}{1},\binom{i}{2},\binom{i}{3}\) değerleri önceden hazırlanır ve mümkün olan \(20\) seçim deseni \((x_0,x_1,x_2,x_3)\) listelenir.
Dinamik program, sadece erişilebilir \((c_0,c_1,c_2,c_3)\) durumlarını bir hash map içinde tutar. Her işlenmiş üçlü adımında mevcut durumlar üzerinde dönülür, her yasal seçim deseni uygulanır, ilgili binom katsayıları çarpılır ve katkı bir sonraki katmana \(10^9+7\) modunda eklenir.
\(t\) adım sonunda \((0,0,0,0)\) durumundaki değer alınır, \(24^m\) ile çarpılır, \(t!\) mod \(10^9+7\) hesaplanır ve hızlı modüler üs alma ile tersi bulunur. Son çarpımdan sonra cevap elde edilir. Ayrıca \(f(12)=576\) ve \(f(24)=509089824\) kontrolleriyle doğrulama yapılır.
Herhangi bir katmandaki erişilebilir durumların en büyük sayısına \(S\) diyelim. Her durum sadece \(20\) geçiş deseni dener. Bu nedenle ana döngünün zamanı
$$O(20tS)=O(tS)$$
olur. Binom ön hesaplaması \(O(m)\) maliyetlidir; \(24^m\) ve \((t!)^{-1}\) için kullanılan modüler üs almalar ise ana DP maliyetine göre küçüktür. Bellek kullanımı
$$O(S)$$
düzeyindedir; çünkü yalnızca mevcut ve sonraki katman tutulur.
Hay \(12n\) músicos. El primer día se reparten en \(m=3n\) cuartetos y el segundo día en \(t=4n\) tríos. Ninguna pareja de músicos puede tocar junta dos veces. Como dentro de un cuarteto del primer día todas las parejas ya coincidieron, un trío válido del segundo día puede contener como máximo un músico de cada cuarteto. Se pide contar todos los horarios válidos del segundo día módulo
$$10^9+7.$$
La partición del primer día se considera fija y sus \(m\) cuartetos son distinguibles. Por tanto, el problema se transforma en contar cuántas maneras hay de formar \(t\) tríos tales que cada trío tome un músico de tres cuartetos distintos y cada cuarteto distribuya a sus cuatro miembros exactamente una vez en el segundo día.
Introducimos una matriz \(m\times t\) con entradas en \(\{0,1\}\):
$$A_{q,r}=1 \iff \text{el trío }r\text{ contiene un músico del cuarteto }q.$$
La restricción de no repetir parejas obliga a que la matriz sea binaria, porque un trío no puede tomar dos personas del mismo cuarteto.
Cada trío tiene exactamente tres músicos, así que cada columna satisface
$$\sum_{q=1}^{m} A_{q,r}=3.$$
Cada cuarteto tiene cuatro músicos y todos deben aparecer exactamente una vez el segundo día, así que cada fila satisface
$$\sum_{r=1}^{t} A_{q,r}=4.$$
El primer subproblema combinatorio es entonces contar matrices \(0\)-\(1\) con suma por fila \(4\) y suma por columna \(3\).
Procesamos las columnas de tríos de izquierda a derecha. Tras cierto número de tríos ya construidos, cada cuarteto ha sido usado \(0\), \(1\), \(2\), \(3\) o \(4\) veces. Los cuartetos usados \(4\) veces ya están terminados y no vuelven a intervenir, de modo que basta el estado
$$\mathbf{c}=(c_0,c_1,c_2,c_3),$$
donde \(c_j\) es el número de cuartetos usados exactamente \(j\) veces hasta ese momento. El número de cuartetos ya completos queda implícito:
$$c_4=m-c_0-c_1-c_2-c_3.$$
Al principio todavía no se ha construido ningún trío, luego
$$\mathbf{c}_{\text{inicio}}=(m,0,0,0).$$
Para crear el siguiente trío elegimos
$$x_j \text{ cuartetos de la clase }j \qquad (j=0,1,2,3),$$
con
$$x_0+x_1+x_2+x_3=3,\qquad 0\le x_j\le c_j.$$
Eso significa que el nuevo trío toma un músico de \(x_0\) cuartetos nunca usados, de \(x_1\) cuartetos usados una vez, etc. El número de formas de hacer esa elección es
$$\binom{c_0}{x_0}\binom{c_1}{x_1}\binom{c_2}{x_2}\binom{c_3}{x_3}.$$
Solo existen
$$\binom{6}{3}=20$$
cuádruplas posibles \((x_0,x_1,x_2,x_3)\), así que cada estado tiene muy pocos movimientos salientes.
Cada cuarteto elegido avanza de la clase \(j\) a la clase \(j+1\). Por tanto
$$c_0'=c_0-x_0,$$
$$c_1'=c_1-x_1+x_0,$$
$$c_2'=c_2-x_2+x_1,$$
$$c_3'=c_3-x_3+x_2.$$
Si \(D_s(c_0,c_1,c_2,c_3)\) es el número de matrices parciales ordenadas tras procesar \(s\) tríos, entonces
$$D_{s+1}(c_0',c_1',c_2',c_3') \mathrel{+}= D_s(c_0,c_1,c_2,c_3)\prod_{j=0}^{3}\binom{c_j}{x_j}.$$
La condición inicial es
$$D_0(m,0,0,0)=1,$$
y tras procesar las \(t\) columnas, el estado final debe ser
$$D_t(0,0,0,0).$$
Llamemos \(N_{\text{mat}}\) a ese número de matrices de incidencia ordenadas.
Fijada la matriz de incidencia, cada cuarteto queda unido a exactamente cuatro columnas de trío. Sus cuatro músicos etiquetados pueden asignarse a esas cuatro apariciones en
$$4!=24$$
formas. Como los cuartetos actúan de manera independiente, el factor total es
$$24^m.$$
Pero la programación dinámica recorre las columnas de los tríos en un orden artificial. Un horario final del segundo día es una colección no ordenada de \(t\) tríos distintos, y por ello queda contado una vez por cada permutación de esas \(t\) columnas. Así obtenemos
$$f(12n)=N_{\text{mat}}\cdot 24^m\cdot \frac{1}{t!}\pmod{10^9+7}.$$
Puesto que \(10^9+7\) es primo, \((t!)^{-1}\) se calcula mediante exponenciación modular usando el pequeño teorema de Fermat.
Con \(12\) músicos tenemos \(n=1\), luego
$$m=3,\qquad t=4.$$
Solo hay tres cuartetos del primer día. Cada trío del segundo día debe usar tres cuartetos distintos, así que necesariamente toma un músico de cada uno de esos tres cuartetos. La matriz de incidencia queda forzada: todas sus entradas \(3\times 4\) valen \(1\). En consecuencia,
$$N_{\text{mat}}=1.$$
Después, cada cuarteto reparte a sus cuatro músicos entre las cuatro posiciones de trío en \(4!\) maneras, lo que produce
$$24^3$$
asignaciones ordenadas. Como los cuatro tríos son no ordenados, dividimos por
$$4!=24.$$
Por tanto,
$$f(12)=\frac{24^3}{24}=24^2=576,$$
exactamente el valor de comprobación de la implementación.
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia. Calculan \(m=3n\) y \(t=4n\), precomputan los valores \(\binom{i}{0},\binom{i}{1},\binom{i}{2},\binom{i}{3}\) para \(0\le i\le m\) y enumeran los \(20\) patrones admisibles \((x_0,x_1,x_2,x_3)\).
La programación dinámica guarda únicamente los estados alcanzables \((c_0,c_1,c_2,c_3)\) en un diccionario hash. Para cada capa, el algoritmo recorre esos estados, aplica cada patrón legal, multiplica por el producto correspondiente de coeficientes binomiales y acumula el resultado de la capa siguiente módulo \(10^9+7\).
Al final de las \(t\) capas, la implementación toma el valor del estado \((0,0,0,0)\), lo multiplica por \(24^m\), calcula \(t!\) módulo \(10^9+7\), invierte ese factorial mediante exponenciación modular rápida y realiza la multiplicación final. También verifica los puntos de control \(f(12)=576\) y \(f(24)=509089824\).
Sea \(S\) el número máximo de estados DP alcanzables en una capa. Cada estado prueba solo \(20\) patrones de transición, así que el coste principal es
$$O(20tS)=O(tS).$$
La precalculación de binomiales cuesta \(O(m)\), y las exponenciaciones modulares para \(24^m\) e \((t!)^{-1}\) son pequeñas frente a la DP. La memoria utilizada es
$$O(S),$$
porque solo se almacenan la capa actual y la siguiente.
共有 \(12n\) 位音乐家。第一天先分成 \(m=3n\) 个四重奏，第二天再分成 \(t=4n\) 个三重奏，并且任何一对音乐家都不能再次同组。由于同一个第一天四重奏中的任意两人已经同组过一次，所以一个合法的第二天三重奏至多只能从同一个四重奏里取一人。题目要求统计所有合法的第二天分组方案数，并对
$$10^9+7$$
取模。
第一天的分组视为固定，因此这 \(m\) 个四重奏是彼此可区分的。于是问题可以改写成：如何构造 \(t\) 个三重奏，使得每个三重奏都从三个不同的四重奏各取一人，同时每个四重奏的四名成员都在第二天恰好出现一次。
定义一个 \(m\times t\) 的 \(0\)-\(1\) 矩阵 \(A\)：
$$A_{q,r}=1 \iff \text{第 }r\text{ 个三重奏包含来自第 }q\text{ 个四重奏的一名音乐家。}$$
“任意两人不能重复同组”这一条件强制矩阵条目只能是 \(0\) 或 \(1\)，因为同一个三重奏绝不可能从同一个四重奏中选两个人。
每个三重奏恰好有三个人，所以每一列都满足
$$\sum_{q=1}^{m} A_{q,r}=3.$$
每个四重奏有四名成员，且他们在第二天都必须恰好出现一次，所以每一行都满足
$$\sum_{r=1}^{t} A_{q,r}=4.$$
因此第一层组合问题，就是统计所有“行和为 \(4\)、列和为 \(3\)”的 \(0\)-\(1\) 矩阵。
按顺序一列一列地处理这些三重奏。处理了若干列之后，每个四重奏已经被使用的次数只可能是 \(0,1,2,3,4\) 之一。已经用满 \(4\) 次的四重奏以后不再参与，所以状态只需要保留
$$\mathbf{c}=(c_0,c_1,c_2,c_3),$$
其中 \(c_j\) 表示到当前为止恰好被使用了 \(j\) 次的四重奏个数。已经用满 \(4\) 次的四重奏数量不必单独存储，因为它由
$$c_4=m-c_0-c_1-c_2-c_3$$
唯一确定。初始时尚未构造任何第二天三重奏，因此
$$\mathbf{c}_{\text{start}}=(m,0,0,0).$$
为了构造下一个三重奏，从四个使用次数类别中分别选出
$$x_j \text{ 个四重奏} \qquad (j=0,1,2,3),$$
并满足
$$x_0+x_1+x_2+x_3=3,\qquad 0\le x_j\le c_j.$$
这表示新三重奏从 \(x_0\) 个从未使用过的四重奏、\(x_1\) 个已使用一次的四重奏等各取一名音乐家。给定当前状态，这种选择的数量是
$$\binom{c_0}{x_0}\binom{c_1}{x_1}\binom{c_2}{x_2}\binom{c_3}{x_3}.$$
而 \((x_0,x_1,x_2,x_3)\) 的可能模式总数只有
$$\binom{3+4-1}{4-1}=\binom{6}{3}=20,$$
所以每个状态只需要尝试非常少的转移类型。
被选中的四重奏会从“已使用 \(j\) 次”移动到“已使用 \(j+1\) 次”，因此有
$$c_0'=c_0-x_0,$$
$$c_1'=c_1-x_1+x_0,$$
$$c_2'=c_2-x_2+x_1,$$
$$c_3'=c_3-x_3+x_2.$$
若 \(D_s(c_0,c_1,c_2,c_3)\) 表示在已经处理完 \(s\) 个三重奏之后，得到该状态的有序部分关联矩阵数量，那么递推式就是
$$D_{s+1}(c_0',c_1',c_2',c_3') \mathrel{+}= D_s(c_0,c_1,c_2,c_3)\prod_{j=0}^{3}\binom{c_j}{x_j}.$$
初始条件为
$$D_0(m,0,0,0)=1.$$
当全部 \(t\) 列处理完成后，每个四重奏都必须正好被使用四次，因此最终目标状态为
$$D_t(0,0,0,0).$$
把这个值记作 \(N_{\text{mat}}\)。它统计的是按列有序的关联矩阵数量。
一旦关联矩阵固定，每个四重奏就恰好连接到四个三重奏列。这个四重奏内部的四位有标签音乐家，可以用
$$4!=24$$
种方式分配到这四次出现中。不同四重奏之间彼此独立，所以总乘子为
$$24^m.$$
但动态规划按人为规定的顺序处理三重奏列，而真正的第二天方案是 \(t\) 个不同三重奏组成的无序集合。于是同一个最终方案会因为三重奏列的不同排列而被重复计算 \(t!\) 次，所以必须除以 \(t!\)：
$$f(12n)=N_{\text{mat}}\cdot 24^m\cdot \frac{1}{t!}\pmod{10^9+7}.$$
由于 \(10^9+7\) 是素数，\((t!)^{-1}\) 可用费马小定理通过快速模幂求出。
当总人数为 \(12\) 时，\(n=1\)，因此
$$m=3,\qquad t=4.$$
第一天只有三个四重奏。第二天的每个三重奏必须来自三个不同的四重奏，于是每个三重奏都只能从这三个四重奏各取一人。也就是说，关联矩阵被完全固定为一个 \(3\times 4\) 的全 \(1\) 矩阵，所以
$$N_{\text{mat}}=1.$$
接下来，每个四重奏把自己的四位成员分配到四个三重奏位置上，有 \(4!\) 种方法，因此共有
$$24^3$$
个有序分配。由于四个三重奏本身并不带顺序，需要再除以
$$4!=24.$$
于是最终答案为
$$f(12)=\frac{24^3}{24}=24^2=576,$$
这与实现中使用的校验值完全一致。
C++、Python 和 Java 三份实现都遵循同一个算法框架。它们先计算 \(m=3n\) 与 \(t=4n\)，预先准备 \(\binom{i}{0},\binom{i}{1},\binom{i}{2},\binom{i}{3}\)（其中 \(0\le i\le m\)），再枚举全部 \(20\) 种合法的 \((x_0,x_1,x_2,x_3)\) 选择模式。
动态规划部分只保存当前可达的状态 \((c_0,c_1,c_2,c_3)\)，并用哈希表进行压缩存储。每处理一个三重奏层，就遍历当前所有状态，尝试每个合法模式，乘上相应的二项式系数乘积，把贡献累加到下一层，并始终对 \(10^9+7\) 取模。
在 \(t\) 层结束后，实现读取终止状态 \((0,0,0,0)\) 的值，将其乘以 \(24^m\)，再计算 \(t!\) 的模值并通过快速模幂求出逆元，最后完成除以 \(t!\) 的步骤。实现还会用 \(f(12)=576\) 和 \(f(24)=509089824\) 两个小规模检查点来验证递推是否正确。
设任意一层中可达状态数的最大值为 \(S\)。由于每个状态只需要尝试 \(20\) 个转移模式，主循环时间复杂度为
$$O(20tS)=O(tS).$$
预处理二项式系数需要 \(O(m)\) 时间，而计算 \(24^m\) 与 \((t!)^{-1}\) 的快速模幂相对于 DP 主体开销很小。空间复杂度为
$$O(S),$$
因为实现只保留当前层和下一层两张哈希表。
Есть \(12n\) музыкантов. В первый день они разбиваются на \(m=3n\) квартетов, а во второй день на \(t=4n\) трио. Ни одна пара музыкантов не должна оказаться вместе дважды. Поскольку внутри квартета первого дня каждая пара уже играла вместе, допустимое трио второго дня может содержать не более одного музыканта из каждого такого квартета. Нужно посчитать число всех допустимых расписаний второго дня по модулю
$$10^9+7.$$
Разбиение первого дня считаем фиксированным, поэтому \(m\) квартетов различимы. Тогда задача сводится к подсчету способов построить \(t\) трио так, чтобы каждое трио брало по одному музыканту из трех разных квартетов, а каждый квартет использовал всех своих четырех участников ровно по одному разу.
Введем \(m\times t\) матрицу \(A\) со значениями из \(\{0,1\}\):
$$A_{q,r}=1 \iff \text{трио }r\text{ содержит одного музыканта из квартета }q.$$
Условие отсутствия повторных пар делает матрицу двоичной: одно трио не может взять двух музыкантов из одного и того же квартета.
В каждом трио ровно три человека, значит для каждого столбца
$$\sum_{q=1}^{m} A_{q,r}=3.$$
В каждом квартете четыре музыканта, и все они должны появиться во второй день ровно один раз, поэтому для каждой строки
$$\sum_{r=1}^{t} A_{q,r}=4.$$
Итак, сначала нужно посчитать число \(0\)-\(1\) матриц с суммой \(4\) по строкам и \(3\) по столбцам.
Будем обрабатывать столбцы-трио слева направо. После некоторого числа шагов каждый квартет использован \(0\), \(1\), \(2\), \(3\) или \(4\) раза. Квартеты, уже использованные \(4\) раза, завершены и больше не участвуют. Поэтому достаточно состояния
$$\mathbf{c}=(c_0,c_1,c_2,c_3),$$
где \(c_j\) означает количество квартетов, использованных ровно \(j\) раз. Число полностью завершенных квартетов задается неявно:
$$c_4=m-c_0-c_1-c_2-c_3.$$
В начале еще не построено ни одного трио, значит
$$\mathbf{c}_{\text{start}}=(m,0,0,0).$$
Чтобы построить следующее трио, выбираем
$$x_j \text{ квартетов из класса }j \qquad (j=0,1,2,3),$$
причем
$$x_0+x_1+x_2+x_3=3,\qquad 0\le x_j\le c_j.$$
Это значит, что новое трио берет по одному музыканту из \(x_0\) еще не использованных квартетов, из \(x_1\) квартетов, уже использованных один раз, и так далее. Число таких выборов равно
$$\binom{c_0}{x_0}\binom{c_1}{x_1}\binom{c_2}{x_2}\binom{c_3}{x_3}.$$
Всего существует только
$$\binom{6}{3}=20$$
допустимых четверок \((x_0,x_1,x_2,x_3)\), поэтому из каждого состояния выходит очень мало переходов.
Каждый выбранный квартет переходит из класса использования \(j\) в класс \(j+1\). Поэтому
$$c_0'=c_0-x_0,$$
$$c_1'=c_1-x_1+x_0,$$
$$c_2'=c_2-x_2+x_1,$$
$$c_3'=c_3-x_3+x_2.$$
Если \(D_s(c_0,c_1,c_2,c_3)\) обозначает число упорядоченных частичных матриц инцидентности после обработки \(s\) трио, то рекуррентное соотношение имеет вид
$$D_{s+1}(c_0',c_1',c_2',c_3') \mathrel{+}= D_s(c_0,c_1,c_2,c_3)\prod_{j=0}^{3}\binom{c_j}{x_j}.$$
Начальное условие:
$$D_0(m,0,0,0)=1.$$
После обработки всех \(t\) столбцов каждый квартет должен быть использован четырежды, так что конечное состояние равно
$$D_t(0,0,0,0).$$
Обозначим это число через \(N_{\text{mat}}\): это количество упорядоченных матриц инцидентности.
Когда матрица инцидентности фиксирована, каждый квартет связан ровно с четырьмя столбцами-трио. Его четыре помеченных музыканта можно распределить по этим четырем появлениям
$$4!=24$$
способами. Для разных квартетов эти выборы независимы, поэтому общий множитель равен
$$24^m.$$
Но динамическая программа обрабатывает столбцы-трио в искусственном порядке. Готовое расписание второго дня представляет собой неупорядоченный набор из \(t\) различных трио, и потому каждое такое расписание учитывается по одному разу для каждой перестановки этих \(t\) столбцов. Значит, нужно разделить на \(t!\):
$$f(12n)=N_{\text{mat}}\cdot 24^m\cdot \frac{1}{t!}\pmod{10^9+7}.$$
Так как \(10^9+7\) является простым числом, обратный элемент к \(t!\) вычисляется быстрым возведением в степень по модулю с использованием малой теоремы Ферма.
При \(12\) музыкантах имеем \(n=1\), поэтому
$$m=3,\qquad t=4.$$
В первый день существует ровно три квартета. Любое трио второго дня обязано брать музыкантов из трех разных квартетов, значит каждое трио неизбежно содержит по одному музыканту из каждого из этих трех квартетов. Следовательно, матрица инцидентности полностью фиксирована и состоит из одних единиц размера \(3\times 4\). Поэтому
$$N_{\text{mat}}=1.$$
Далее каждый квартет распределяет своих четырех музыкантов по четырем позициям трио в \(4!\) вариантах, что дает
$$24^3$$
упорядоченных назначений. Поскольку сами четыре трио не упорядочены, делим на
$$4!=24.$$
Итак,
$$f(12)=\frac{24^3}{24}=24^2=576,$$
что точно совпадает с контрольным значением из реализации.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала вычисляются \(m=3n\) и \(t=4n\). Затем заранее подготавливаются значения \(\binom{i}{0},\binom{i}{1},\binom{i}{2},\binom{i}{3}\) для \(0\le i\le m\), а также перечисляются все \(20\) допустимых шаблонов \((x_0,x_1,x_2,x_3)\).
Динамическое программирование хранит только достижимые состояния \((c_0,c_1,c_2,c_3)\) в хеш-таблице. Для каждого слоя алгоритм проходит по текущим состояниям, пробует каждый допустимый шаблон, умножает на соответствующее произведение биномиальных коэффициентов и добавляет вклад в следующий слой по модулю \(10^9+7\).
После \(t\) шагов код берет значение конечного состояния \((0,0,0,0)\), умножает его на \(24^m\), вычисляет \(t!\) по модулю \(10^9+7\), находит обратный к нему элемент быстрым возведением в степень и выполняет последнее умножение. Также проверяются контрольные значения \(f(12)=576\) и \(f(24)=509089824\).
Пусть \(S\) — максимальное число достижимых DP-состояний в одном слое. Каждое состояние рассматривает только \(20\) шаблонов перехода, поэтому время работы основной части равно
$$O(20tS)=O(tS).$$
Предварительный расчет биномиальных коэффициентов занимает \(O(m)\), а модульные степени для \(24^m\) и \((t!)^{-1}\) малы по сравнению с DP. Память составляет
$$O(S),$$
поскольку хранятся только текущий и следующий слои.
لدينا \(12n\) موسيقيًا. في اليوم الأول يُقسَّمون إلى \(m=3n\) رباعيات، وفي اليوم الثاني إلى \(t=4n\) ثلاثيات. ولا يجوز لأي زوج من الموسيقيين أن يعزف معًا مرتين. وبما أن كل زوج داخل رباعية اليوم الأول قد اجتمع بالفعل مرة واحدة، فإن أي ثلاثي صالح في اليوم الثاني لا يمكنه أن يضم أكثر من موسيقي واحد من الرباعية نفسها. المطلوب هو عدّ جميع ترتيبات اليوم الثاني الصالحة بترديد
$$10^9+7.$$
نعتبر تقسيم اليوم الأول ثابتًا، ولذلك فإن الرباعيات \(m\) مميزة عن بعضها. وعندئذ تصبح المسألة: كم عدد الطرق لتكوين \(t\) ثلاثيات بحيث يأخذ كل ثلاثي موسيقيًا واحدًا من ثلاث رباعيات مختلفة، وفي الوقت نفسه تستخدم كل رباعية أعضاءها الأربعة كلّهم مرة واحدة بالضبط في اليوم الثاني.
نعرّف مصفوفة \(A\) من الحجم \(m\times t\) ومدخلاتها من \(\{0,1\}\). والمعنى هو أن \(A_{q,r}=1\) إذا وفقط إذا كان الثلاثي رقم \(r\) يحتوي على موسيقي واحد من الرباعية رقم \(q\).
شرط عدم تكرار الأزواج يفرض أن تكون المصفوفة ثنائية، لأن الثلاثي لا يستطيع أن يأخذ شخصين من الرباعية نفسها.
بما أن كل ثلاثي يضم ثلاثة موسيقيين تمامًا، فإن مجموع كل عمود يساوي
$$\sum_{q=1}^{m} A_{q,r}=3.$$
وبما أن كل رباعية تضم أربعة موسيقيين وكل واحد منهم يجب أن يظهر مرة واحدة فقط في اليوم الثاني، فإن مجموع كل صف يساوي
$$\sum_{r=1}^{t} A_{q,r}=4.$$
إذن المسألة الأولى هي عدّ المصفوفات الثنائية التي يكون مجموع كل صف فيها \(4\) ومجموع كل عمود فيها \(3\).
نُعالج أعمدة الثلاثيات واحدًا بعد الآخر. بعد معالجة عدد معين من الثلاثيات، تكون كل رباعية قد استُخدمت \(0\) أو \(1\) أو \(2\) أو \(3\) أو \(4\) مرات. الرباعيات التي استُخدمت \(4\) مرات انتهى دورها ولا نحتاج إلى تتبعها صراحة، لذا تكفي الحالة
$$\mathbf{c}=(c_0,c_1,c_2,c_3),$$
حيث يمثّل \(c_j\) عدد الرباعيات التي استُخدمت بالضبط \(j\) مرات حتى تلك اللحظة. أما عدد الرباعيات المكتملة فيُستنتج من
$$c_4=m-c_0-c_1-c_2-c_3.$$
في البداية لم يُنشأ أي ثلاثي بعد، ولذلك
$$\mathbf{c}^{(0)}=(m,0,0,0).$$
لبناء الثلاثي التالي نختار \(x_j\) رباعيات من الفئة \(j\) لكل \(j=0,1,2,3\)، مع الشرطين
$$x_0+x_1+x_2+x_3=3,\qquad 0\le x_j\le c_j.$$
أي إن الثلاثي الجديد يأخذ موسيقيًا واحدًا من \(x_0\) رباعيات غير مستخدمة بعد، ومن \(x_1\) رباعيات استُخدمت مرة واحدة، وهكذا. وعدد طرق هذا الاختيار هو
$$\binom{c_0}{x_0}\binom{c_1}{x_1}\binom{c_2}{x_2}\binom{c_3}{x_3}.$$
ولا يوجد إلا
$$\binom{6}{3}=20$$
نمطًا ممكنًا للرباعية \((x_0,x_1,x_2,x_3)\)، ولذلك يظل عدد الانتقالات من كل حالة صغيرًا جدًا.
كل رباعية مختارة تنتقل من فئة الاستخدام \(j\) إلى الفئة \(j+1\). ولذلك نحصل على
$$c_0'=c_0-x_0,$$
$$c_1'=c_1-x_1+x_0,$$
$$c_2'=c_2-x_2+x_1,$$
$$c_3'=c_3-x_3+x_2.$$
إذا كان \(D_s(c_0,c_1,c_2,c_3)\) يرمز إلى عدد مصفوفات الترابط الجزئية المرتبة بعد معالجة \(s\) ثلاثيات، فإن العلاقة الانتقالية تصبح
$$D_{s+1}(c_0',c_1',c_2',c_3') \mathrel{+}= D_s(c_0,c_1,c_2,c_3)\prod_{j=0}^{3}\binom{c_j}{x_j}.$$
وقيمة البداية هي
$$D_0(m,0,0,0)=1.$$
وبعد معالجة جميع الأعمدة \(t\)، يجب أن تكون كل الرباعيات قد استُخدمت أربع مرات، أي إن الحالة النهائية هي
$$D_t(0,0,0,0).$$
وسنسمي هذه الكمية \(N_{\text{mat}}\)، وهي عدد مصفوفات الترابط المرتبة.
عندما تثبت مصفوفة الترابط، تكون كل رباعية مرتبطة بأربعة أعمدة ثلاثية بالضبط. ويمكن توزيع موسيقييها الأربعة المميزين على هذه المواضع الأربعة بعدد
$$4!=24$$
من الطرق. وبما أن الرباعيات تعمل باستقلال، فإن عامل التوسيع الكلي هو
$$24^m.$$
لكن البرمجة الديناميكية عالجت أعمدة الثلاثيات بترتيب مصطنع. أما الجدول النهائي لليوم الثاني فهو مجموعة غير مرتبة من \(t\) ثلاثيات مختلفة، ولذلك يُعدّ كل جدول نهائي مرة لكل تبديل ممكن لهذه الأعمدة \(t\). ومن ثم يجب القسمة على \(t!\):
$$f(12n)=N_{\text{mat}}\cdot 24^m\cdot \frac{1}{t!}\pmod{10^9+7}.$$
ولأن \(10^9+7\) عدد أولي، فإن معكوس \(t!\) يحسب بواسطة الرفع السريع للأس باستخدام مبرهنة فيرما الصغرى.
إذا كان العدد الكلي \(12\)، فلدينا \(n=1\)، ومن ثم
$$m=3,\qquad t=4.$$
هناك ثلاث رباعيات فقط في اليوم الأول. وكل ثلاثي في اليوم الثاني يجب أن يستخدم ثلاث رباعيات مختلفة، وهذا يعني أنه لا بد أن يأخذ موسيقيًا واحدًا من كل رباعية من الرباعيات الثلاث. لذلك تصبح مصفوفة الترابط وحيدة ومكوّنة بالكامل من الآحاد من الحجم \(3\times 4\). وعليه
$$N_{\text{mat}}=1.$$
بعد ذلك توزّع كل رباعية أعضاءها الأربعة على مواضع الثلاثيات الأربع بعدد \(4!\) من الطرق، فينتج
$$24^3$$
توزيعًا مرتبًا. وبما أن الثلاثيات الأربع نفسها غير مرتبة، نقسم على
$$4!=24.$$
فتكون النتيجة
$$f(12)=\frac{24^3}{24}=24^2=576,$$
وهو تمامًا مقدار الفحص الصغير المستخدم في التنفيذ.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. فهي تحسب أولًا \(m=3n\) و\(t=4n\)، ثم تهيئ قيم \(\binom{i}{0},\binom{i}{1},\binom{i}{2},\binom{i}{3}\) لكل \(0\le i\le m\)، وتولّد الأنماط العشرين الممكنة للاختيار \((x_0,x_1,x_2,x_3)\).
تُخزَّن فقط الحالات القابلة للوصول \((c_0,c_1,c_2,c_3)\) في بنية تجزئة. وفي كل طبقة من طبقات الثلاثيات، تمرّ الخوارزمية على الحالات الحالية، وتجرّب كل نمط قانوني، وتضرب في حاصل ضرب معاملات ثنائية الحد الموافق، ثم تجمع الإسهام في الطبقة التالية بترديد \(10^9+7\).
بعد اكتمال \(t\) طبقات، يُقرأ مقدار الحالة النهائية \((0,0,0,0)\)، ثم يُضرب في \(24^m\)، ويُحسب \(t!\) بترديد \(10^9+7\)، ثم يُستخرج معكوسه بالرفع السريع للأس، وأخيرًا تجرى القسمة على \(t!\). كما تُستخدم القيمتان \(f(12)=576\) و\(f(24)=509089824\) بوصفهما نقطتي تحقق صغيرتين.
لنرمز إلى أكبر عدد من حالات DP القابلة للوصول في أي طبقة بالرمز \(S\). كل حالة تجرّب \(20\) نمط انتقال فقط، ولذا فإن زمن الجزء الرئيسي هو
$$O(20tS)=O(tS).$$
أما التحضير المسبق لمعاملات ثنائية الحد فيكلف \(O(m)\)، وحساب \(24^m\) ومعكوس \(t!\) صغير نسبيًا قياسًا بكلفة DP. واستهلاك الذاكرة هو
$$O(S),$$
لأن التنفيذ يحتفظ فقط بالطبقة الحالية والطبقة التالية.