Compress a hand from a standard 52-card deck into a rank-count vector \(c=(c_1,\dots,c_{13})\), where \(0\le c_r\le 4\) and the ranks are \(A,2,\dots,10,J,Q,K\). The card values used by the problem are
\[ v=(1,2,3,4,5,6,7,8,9,10,10,10,10). \]
A count vector does not distinguish suits, so it stands for
\[ W(c)=\prod_{r=1}^{13}\binom{4}{c_r} \]
different physical hands: for each rank we choose \(c_r\) suits out of the four available. The goal is to count, with that multiplicity and excluding the empty hand, all vectors for which the face-value total
\[ H(c)=\sum_{r=1}^{13} v_r c_r \]
is exactly equal to the cribbage score used in the problem, namely
\[ C(c)=P(c)+R(c)+2F_{15}(c). \]
Here \(P(c)\) is the score from equal-rank pairs, \(R(c)\) is the score from runs, and \(F_{15}(c)\) counts card subsets whose values add up to 15. So the whole problem is an exact weighted count of the nonempty hands satisfying \(H(c)=C(c)\).
Since suits matter only through multiplicity, the real combinatorial object is the 13-dimensional vector \(c\). Every legal hand corresponds to exactly one such vector, and every vector represents \(W(c)\) suit assignments. That compression is what makes the problem finite: there are only \(5^{13}\) possible count vectors, because each rank may appear 0, 1, 2, 3, or 4 times.
The pair contribution is immediate. If rank \(r\) appears \(c_r\) times, then it contains \(\binom{c_r}{2}\) equal-rank pairs, each worth 2 points, so
\[ P(c)=2\sum_{r=1}^{13}\binom{c_r}{2}=\sum_{r=1}^{13} c_r(c_r-1). \]
The run contribution is slightly subtler. Break the rank line into maximal consecutive blocks of positive counts. For one such block \(a,a+1,\dots,b\), let
\[ L=b-a+1,\qquad M=\prod_{r=a}^{b} c_r. \]
Each choice of one card from every rank in that block produces a distinct run, so the block contributes \(L\cdot M\) if \(L\ge 3\), and 0 otherwise. Therefore
\[ R(c)=\sum_{\text{maximal positive blocks}} \mathbf{1}_{L\ge 3}\,L\,M. \]
This matches the usual cribbage behavior: a block such as \(A,A,2,3,4,5\) gives two runs of length 5, not a pile of shorter subruns, because the whole maximal block is scored at once.
For each rank \(r\), we may select \(d\) of its \(c_r\) copies into a subset, where \(0\le d\le c_r\). There are \(\binom{c_r}{d}\) ways to do that, and it contributes value \(d\,v_r\). Hence the generating function
\[ G_c(x)=\prod_{r=1}^{13}\left(\sum_{d=0}^{c_r}\binom{c_r}{d}x^{d v_r}\right) \]
has the property that
\[ F_{15}(c)=[x^{15}]\,G_c(x). \]
The implementations evaluate that coefficient by a short dynamic program on sums \(0,1,\dots,15\): after processing rank \(r\), the array entry for sum \(s\) stores how many subsets of the processed ranks have total \(s\). Because we only care about 15, the polynomial is truncated immediately.
Take the hand with two aces and one each of 2, 3, 4, and 5. In count-vector form, that means
\[ c_A=2,\quad c_2=c_3=c_4=c_5=1, \]
and all other entries are 0. Then
\[ H(c)=2\cdot 1+2+3+4+5=16. \]
The pair score is \(P(c)=2\), coming from the two aces. The ranks \(A,2,3,4,5\) form one maximal positive block of length 5, with multiplicity product \(2\cdot 1\cdot 1\cdot 1\cdot 1=2\), so
\[ R(c)=5\cdot 2=10. \]
For fifteens, the subset \(A+2+3+4+5\) sums to 15, and either ace may be chosen, so \(F_{15}(c)=2\). Therefore
\[ P(c)+R(c)+2F_{15}(c)=2+10+4=16=H(c). \]
This is exactly the kind of hand the program counts.
The main implementation trick is a meet-in-the-middle split after the sixth rank. A full count vector is written as
\[ c=(c^{L},c^{R}), \]
where the left half contains the first 6 ranks and the right half contains the remaining 7. For each half, the implementation precomputes a compact summary consisting of:
\[ H,\quad P,\quad R,\quad B=H-P-R,\quad W, \]
together with:
\[ f(s)=\#\{\text{subsets in this half with total } s\}\qquad (0\le s\le 15), \]
and the length, multiplicity product, and score of the prefix and suffix positive blocks. The point is that the expensive work for a half-hand is done once and then reused for every compatible half on the other side.
The left half and the right half are independent except at the split point. If the left half ends with a positive block and the right half begins with a positive block, those two pieces actually form one longer run block in the full hand. Let the left suffix have length and multiplicity \((\ell_L,m_L)\), and the right prefix have \((\ell_R,m_R)\). Define
\[ S(\ell,m)= \begin{cases} \ell m,& \ell\ge 3,\\ 0,& \ell<3. \end{cases} \]
Then the correction needed at the boundary is
\[ \operatorname{adjust}=S(\ell_L+\ell_R,m_Lm_R)-S(\ell_L,m_L)-S(\ell_R,m_R). \]
This quantity may add a new run that was too short in both halves, or it may replace two separate partial scores by one merged score. After this correction, the full run score is
\[ R(c)=R(c^{L})+R(c^{R})+\operatorname{adjust}. \]
The generating function also factors over the split:
\[ G_c(x)=G_{c^{L}}(x)\,G_{c^{R}}(x). \]
If \(f_L(s)\) and \(f_R(s)\) are the subset-count arrays for the two halves, then
\[ F_{15}(c)=\sum_{s=0}^{15} f_L(s)\,f_R(15-s). \]
The implementations store a reversed copy of the right array, so this becomes a 16-term dot product rather than a fresh subset-sum computation for every full hand.
For a merged hand, write
\[ B_L=H(c^{L})-P(c^{L})-R(c^{L}),\qquad B_R=H(c^{R})-P(c^{R})-R(c^{R}). \]
Since the full run score differs from \(R(c^{L})+R(c^{R})\) by exactly \(\operatorname{adjust}\), the target identity becomes
\[ H(c)-P(c)-R(c)=B_L+B_R-\operatorname{adjust}=2F_{15}(c). \]
So a left state and a right state form a valid hand precisely when the corrected left-right base value equals twice the dot-product count of fifteens. Whenever that happens, the contribution to the answer is \(W(c^{L})W(c^{R})\). The all-zero vector satisfies the identity trivially, so it is removed at the end by subtracting 1.
The C++, Python, and Java implementations first enumerate every possible count pattern in each half: \(5^6\) states on the left and \(5^7\) on the right. For every half-state they compute the hand total, pair score, internal run score, multiplicity, the truncated subset-sum polynomial up to 15, and the prefix/suffix block data needed for a later merge.
Each left half-state is paired with each right half-state. The implementation computes the boundary correction for a run that crosses the split, then forms
\[ \text{targetTwice}=B_L+B_R-\operatorname{adjust}. \]
If this value is negative, odd, or larger than 340, the pair is impossible and is skipped immediately. The upper bound 340 comes from the largest possible face-value sum of a full deck count vector. Otherwise the code evaluates the 16-term dot product for \(F_{15}\), stopping early if the partial sum has already exceeded the target.
When the equality test succeeds, the product of the two multiplicities is added to the total. This counts all suit assignments represented by the merged rank-count vector. The empty hand is excluded at the very end. The C++ and Java implementations parallelize the outer scan over left states; the Python entry point uses the same mathematical computation path rather than a different scoring rule.
Enumerating the half-states costs \(O(5^6)\) and \(O(5^7)\) summaries, each with only a constant-size dynamic program on sums \(0\) through \(15\). The dominant phase is the cartesian product of the two state sets, so the merge work is
\[ O(5^6\cdot 5^7\cdot 16)=O(5^{13}). \]
That means the method does not reduce the exponent of the search space. Its advantage is that the expensive scoring data for a half-hand is computed once and reused many times, so each full-hand test becomes only a boundary correction plus a 16-term dot product. Memory usage is
\[ O\!\big((5^6+5^7)\cdot 16\big), \]
coming from the stored half-state tables and their short subset-sum arrays.
Eine Hand aus einem Standarddeck mit 52 Karten wird zu einem Rangvektor \(c=(c_1,\dots,c_{13})\) komprimiert, wobei \(0\le c_r\le 4\) und die Ränge \(A,2,\dots,10,J,Q,K\) sind. Die im Problem verwendeten Kartenwerte sind
\[ v=(1,2,3,4,5,6,7,8,9,10,10,10,10). \]
Ein solcher Vektor unterscheidet die Farben nicht mehr und steht deshalb für
\[ W(c)=\prod_{r=1}^{13}\binom{4}{c_r} \]
verschiedene reale Hände: Für jeden Rang werden \(c_r\) Farben aus vier gewählt. Gesucht ist die gewichtete Anzahl aller nichtleeren Vektoren, für die die Augensumme
\[ H(c)=\sum_{r=1}^{13} v_r c_r \]
genau dem im Problem benutzten Cribbage-Score entspricht:
\[ C(c)=P(c)+R(c)+2F_{15}(c). \]
Dabei ist \(P(c)\) der Paar-Score, \(R(c)\) der Run-Score und \(F_{15}(c)\) die Anzahl der Teilmengen mit Wertsumme 15. Das Problem ist also eine exakte gewichtete Zählung aller nichtleeren Hände mit \(H(c)=C(c)\).
Da die Farben nur über ihre Vielfachheit eingehen, ist das eigentliche kombinatorische Objekt der 13-dimensionale Vektor \(c\). Jede zulässige Hand liefert genau einen solchen Vektor, und jeder Vektor repräsentiert \(W(c)\) verschiedene Farbzuweisungen. Dadurch wird das Problem endlich: Es gibt nur \(5^{13}\) mögliche Rangvektoren, weil jeder Rang 0, 1, 2, 3 oder 4-mal auftreten kann.
Der Paarbeitrag ist sofort klar. Tritt Rang \(r\) genau \(c_r\)-mal auf, dann enthält er \(\binom{c_r}{2}\) gleichrangige Paare, und jedes Paar ist 2 Punkte wert. Also gilt
\[ P(c)=2\sum_{r=1}^{13}\binom{c_r}{2}=\sum_{r=1}^{13} c_r(c_r-1). \]
Der Run-Beitrag ist etwas feiner. Zerlege die Rangachse in maximale zusammenhängende Blöcke positiver Zählwerte. Für einen solchen Block \(a,a+1,\dots,b\) setze
\[ L=b-a+1,\qquad M=\prod_{r=a}^{b} c_r. \]
Jede Wahl einer Karte aus jedem Rang des Blocks erzeugt einen eigenen Run. Daher trägt der Block \(L\cdot M\) bei, falls \(L\ge 3\), sonst 0. Somit
\[ R(c)=\sum_{\text{maximale positive Blöcke}} \mathbf{1}_{L\ge 3}\,L\,M. \]
Genau deshalb zählt eine Hand wie \(A,A,2,3,4,5\) als zwei Fünfer-Runs und nicht als Sammlung kürzerer Teilruns: Bewertet wird immer der maximale Block.
Für jeden Rang \(r\) können wir \(d\) seiner \(c_r\) Karten in eine Teilmenge aufnehmen, wobei \(0\le d\le c_r\). Das geht auf \(\binom{c_r}{d}\) Arten und erhöht die Summe um \(d\,v_r\). Daher hat die erzeugende Funktion
\[ G_c(x)=\prod_{r=1}^{13}\left(\sum_{d=0}^{c_r}\binom{c_r}{d}x^{d v_r}\right) \]
die Eigenschaft
\[ F_{15}(c)=[x^{15}]\,G_c(x). \]
Die Implementierungen berechnen diesen Koeffizienten mit einer kurzen dynamischen Programmierung über die Summen \(0,1,\dots,15\). Mehr wird nicht gebraucht, deshalb wird das Polynom sofort bei 15 abgeschnitten.
Betrachte die Hand mit zwei Assen sowie je einer 2, 3, 4 und 5. Im Rangvektor bedeutet das
\[ c_A=2,\quad c_2=c_3=c_4=c_5=1, \]
alle übrigen Einträge sind 0. Dann ist
\[ H(c)=2\cdot 1+2+3+4+5=16. \]
Der Paar-Score ist \(P(c)=2\), denn es gibt genau ein Ass-Paar. Die Ränge \(A,2,3,4,5\) bilden einen maximalen positiven Block der Länge 5 mit Produkt \(2\cdot 1\cdot 1\cdot 1\cdot 1=2\). Also
\[ R(c)=5\cdot 2=10. \]
Für Fünfzehner gilt: Die Teilmenge \(A+2+3+4+5\) ergibt 15, und wegen der beiden Asse gibt es dafür zwei verschiedene Wahlen. Also \(F_{15}(c)=2\). Damit folgt
\[ P(c)+R(c)+2F_{15}(c)=2+10+4=16=H(c). \]
Genau solche Hände werden gezählt.
Der zentrale Implementierungstrick ist ein Meet-in-the-middle-Schnitt nach dem sechsten Rang. Ein voller Rangvektor wird geschrieben als
\[ c=(c^{L},c^{R}), \]
wobei die linke Hälfte die ersten 6 Ränge und die rechte Hälfte die restlichen 7 enthält. Für jede Hälfte wird eine kompakte Zusammenfassung vorbereitet:
\[ H,\quad P,\quad R,\quad B=H-P-R,\quad W, \]
sowie
\[ f(s)=\#\{\text{Teilmengen dieser Hälfte mit Summe } s\}\qquad (0\le s\le 15), \]
und zusätzlich Länge, Produkt und Score des Präfix- bzw. Suffix-Blocks positiver Zählwerte. So wird die aufwendige Arbeit für eine Halbhand einmal erledigt und später vielfach wiederverwendet.
Links und rechts sind unabhängig, außer am Schnittpunkt. Endet die linke Hälfte mit einem positiven Block und beginnt die rechte Hälfte mit einem positiven Block, dann werden beide im Gesamtvektor zu einem längeren zusammenhängenden Run-Block. Hat das linke Suffix Länge und Produkt \((\ell_L,m_L)\) und das rechte Präfix \((\ell_R,m_R)\), dann definieren wir
\[ S(\ell,m)= \begin{cases} \ell m,& \ell\ge 3,\\ 0,& \ell<3. \end{cases} \]
Die nötige Korrektur lautet dann
\[ \operatorname{adjust}=S(\ell_L+\ell_R,m_Lm_R)-S(\ell_L,m_L)-S(\ell_R,m_R). \]
Dieser Term kann einen neuen Run hinzufügen oder zwei getrennt bewertete Teilstücke durch einen gemeinsamen Score ersetzen. Danach gilt für den Gesamtvektor
\[ R(c)=R(c^{L})+R(c^{R})+\operatorname{adjust}. \]
Auch die erzeugende Funktion faktorisiert über den Schnitt:
\[ G_c(x)=G_{c^{L}}(x)\,G_{c^{R}}(x). \]
Wenn \(f_L(s)\) und \(f_R(s)\) die Teilmengen-Arrays der beiden Hälften sind, dann ist
\[ F_{15}(c)=\sum_{s=0}^{15} f_L(s)\,f_R(15-s). \]
Die Implementierungen speichern rechts eine umgedrehte Kopie, damit daraus pro Hand nur noch ein Skalarprodukt mit 16 Termen wird.
Für die vereinigte Hand setzen wir
\[ B_L=H(c^{L})-P(c^{L})-R(c^{L}),\qquad B_R=H(c^{R})-P(c^{R})-R(c^{R}). \]
Weil sich der volle Run-Score von \(R(c^{L})+R(c^{R})\) genau um \(\operatorname{adjust}\) unterscheidet, wird die Zielgleichung zu
\[ H(c)-P(c)-R(c)=B_L+B_R-\operatorname{adjust}=2F_{15}(c). \]
Ein linkes und ein rechtes Halbobjekt bilden also genau dann eine gültige Hand, wenn dieser korrigierte Basiswert doppelt so groß ist wie die Anzahl der Fünfzehner aus dem Skalarprodukt. In diesem Fall trägt die Hand \(W(c^{L})W(c^{R})\) zur Antwort bei. Der Nullvektor erfüllt die Gleichung trivial und wird am Ende durch Subtraktion von 1 entfernt.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst alle möglichen Muster jeder Hälfte: \(5^6\) Zustände links und \(5^7\) rechts. Für jeden Halbzustand werden Augensumme, Paar-Score, interner Run-Score, Multiplikität, das bis 15 abgeschnittene Teilmengen-Polynom sowie die Präfix- und Suffix-Informationen gespeichert.
Jeder linke Halbzustand wird mit jedem rechten Halbzustand kombiniert. Zuerst berechnet die Implementierung die Grenzkorrektur für einen Run, der den Schnitt überquert. Danach bildet sie
\[ \text{targetTwice}=B_L+B_R-\operatorname{adjust}. \]
Ist dieser Wert negativ, ungerade oder größer als 340, wird das Paar sofort verworfen. Die Schranke 340 ist die maximale mögliche Augensumme eines vollständigen Rangvektors. Andernfalls wird das 16-gliedrige Skalarprodukt für \(F_{15}\) berechnet, mit vorzeitigem Abbruch, sobald die Zwischensumme das Ziel überschreitet.
Besteht das Gleichheitstesten, wird das Produkt der beiden Multiplikitäten addiert. So werden alle Farbzuweisungen gezählt, die vom zusammengefügten Rangvektor repräsentiert werden. Die leere Hand wird ganz am Schluss entfernt. C++ und Java parallelisieren die äußere Schleife über die linken Halbzustände; der Python-Einstieg nutzt denselben mathematischen Rechenweg.
Die Vorberechnung der Halbzustände kostet \(O(5^6)\) beziehungsweise \(O(5^7)\) Zusammenfassungen, jeweils mit einer dynamischen Programmierung konstanter Größe über die Summen \(0\) bis \(15\). Dominant ist das kartesische Produkt beider Zustandsmengen, daher beträgt die Fusionsarbeit
\[ O(5^6\cdot 5^7\cdot 16)=O(5^{13}). \]
Das Verfahren senkt also nicht den Exponenten des Suchraums. Sein Vorteil liegt darin, dass die aufwendigen Bewertungsdaten einer Halbhand nur einmal berechnet und dann oft wiederverwendet werden, sodass jeder vollständige Test nur noch aus einer Grenzkorrektur und einem kurzen Skalarprodukt besteht. Der Speicherbedarf ist
\[ O\!\big((5^6+5^7)\cdot 16\big), \]
verursacht durch die gespeicherten Halbzustände und ihre kurzen Teilmengen-Arrays.
Standart 52 kartlık bir desteden gelen bir el, \(c=(c_1,\dots,c_{13})\) biçiminde bir rank-sayım vektörüyle sıkıştırılır; burada \(0\le c_r\le 4\) ve rankler \(A,2,\dots,10,J,Q,K\) şeklindedir. Problemde kullanılan kart değerleri
\[ v=(1,2,3,4,5,6,7,8,9,10,10,10,10) \]
vektörüdür. Bu gösterim suitleri ayırt etmediği için tek bir sayım vektörü aslında
\[ W(c)=\prod_{r=1}^{13}\binom{4}{c_r} \]
farklı fiziksel eli temsil eder; çünkü her rank için dört suit içinden \(c_r\) tanesi seçilir. Amaç, boş el hariç, yüz değeri toplamı
\[ H(c)=\sum_{r=1}^{13} v_r c_r \]
olan ve aynı zamanda cribbage puanı
\[ C(c)=P(c)+R(c)+2F_{15}(c) \]
ile eşitlik sağlayan bütün elleri bu ağırlıkla saymaktır. Burada \(P(c)\) çiftlerden, \(R(c)\) run'lardan, \(F_{15}(c)\) ise toplamı 15 eden kart altkümelerinden gelir. Yani asıl hedef, \(H(c)=C(c)\) koşulunu sağlayan tüm boş olmayan vektörlerin tam ağırlıklı sayısını bulmaktır.
Suitler yalnızca çarpan olarak önemli olduğundan, esas kombinatoryal nesne 13 boyutlu \(c\) vektörüdür. Her geçerli el tam olarak bir böyle vektöre karşılık gelir; her vektör de \(W(c)\) kadar suit yerleşimi temsil eder. Bu sıkıştırma problemi sonlu hale getirir: Her rank 0, 1, 2, 3 veya 4 kez gelebileceği için toplam yalnızca \(5^{13}\) olası vektör vardır.
Çift katkısı doğrudan yazılır. Rank \(r\), \(c_r\) kez görünüyorsa \(\binom{c_r}{2}\) tane aynı rank çifti vardır ve her biri 2 puan eder. Dolayısıyla
\[ P(c)=2\sum_{r=1}^{13}\binom{c_r}{2}=\sum_{r=1}^{13} c_r(c_r-1) \]
olur. Run katkısı biraz daha dikkat ister. Pozitif sayımlardan oluşan ardışık rankleri, aralarında sıfır olmayan en büyük bloklara ayıralım. Böyle bir blok \(a,a+1,\dots,b\) ise
\[ L=b-a+1,\qquad M=\prod_{r=a}^{b} c_r \]
tanımlarını yapalım. Bloktaki her rankten bir kart seçimi ayrı bir run verdiğinden, \(L\ge 3\) ise blok katkısı \(L\cdot M\), aksi halde 0 olur. Böylece
\[ R(c)=\sum_{\text{maksimal pozitif bloklar}} \mathbf{1}_{L\ge 3}\,L\,M \]
formülünü elde ederiz. Bu yüzden \(A,A,2,3,4,5\) gibi bir yapı, kısa alt-run'ların yığını olarak değil, iki tane uzunluk 5 run olarak puanlanır; çünkü cribbage burada maksimal bloğu sayar.
Her rank \(r\) için, onun \(c_r\) kopyasından altkümeye \(d\) tanesini alabiliriz; burada \(0\le d\le c_r\). Bunun \(\binom{c_r}{d}\) yolu vardır ve toplam değere \(d\,v_r\) ekler. Bu nedenle
\[ G_c(x)=\prod_{r=1}^{13}\left(\sum_{d=0}^{c_r}\binom{c_r}{d}x^{d v_r}\right) \]
üretec fonksiyonu için
\[ F_{15}(c)=[x^{15}]\,G_c(x) \]
eşitliği geçerlidir. Uygulamalar bu katsayıyı, toplamlar \(0,1,\dots,15\) üzerinde çalışan kısa bir dinamik programlama ile hesaplar. 15'ten büyük katsayılar hiç gerekmeyeceği için anında budanır.
İki as ve birer tane 2, 3, 4, 5 içeren eli düşünelim. Sayım vektörü dilinde bu
\[ c_A=2,\quad c_2=c_3=c_4=c_5=1 \]
anlamına gelir; diğer tüm bileşenler 0'dır. O halde
\[ H(c)=2\cdot 1+2+3+4+5=16. \]
İki as bir çift oluşturduğu için \(P(c)=2\). Ayrıca \(A,2,3,4,5\) rankleri uzunluğu 5 olan tek bir maksimal pozitif blok oluşturur ve çarpım \(2\cdot 1\cdot 1\cdot 1\cdot 1=2\) olduğundan
\[ R(c)=5\cdot 2=10. \]
15 yapan altkümeler için \(A+2+3+4+5\) toplamı 15 eder ve iki farklı as seçilebildiğinden \(F_{15}(c)=2\) olur. Böylece
\[ P(c)+R(c)+2F_{15}(c)=2+10+4=16=H(c). \]
Program tam olarak bu tip elleri sayar.
Uygulamadaki ana fikir, altıncı rankten sonra meet-in-the-middle bölmesidir. Tam vektör
\[ c=(c^{L},c^{R}) \]
şeklinde yazılır; sol yarı ilk 6 ranki, sağ yarı kalan 7 ranki taşır. Her yarı için şu özet önceden hesaplanır:
\[ H,\quad P,\quad R,\quad B=H-P-R,\quad W, \]
buna ek olarak
\[ f(s)=\#\{\text{bu yarıda toplamı } s \text{ olan altkümeler}\}\qquad (0\le s\le 15), \]
ve başlangıçtaki ile sondaki pozitif blokların uzunluk, çarpım ve skor bilgileri tutulur. Böylece yarım elin pahalı hesapları bir kez yapılır ve karşı taraftaki pek çok yarıyla tekrar kullanılır.
Sol ve sağ yarılar, kesim noktası dışında bağımsızdır. Eğer sol yarı pozitif bir blokla bitiyor ve sağ yarı pozitif bir blokla başlıyorsa, bu iki parça tam elde tek bir daha uzun run bloğu oluşturur. Sol sonek için uzunluk ve çarpım \((\ell_L,m_L)\), sağ önek için \((\ell_R,m_R)\) olsun. Şu fonksiyonu tanımlayalım:
\[ S(\ell,m)= \begin{cases} \ell m,& \ell\ge 3,\\ 0,& \ell<3. \end{cases} \]
O zaman gerekli sınır düzeltmesi
\[ \operatorname{adjust}=S(\ell_L+\ell_R,m_Lm_R)-S(\ell_L,m_L)-S(\ell_R,m_R) \]
olur. Bu terim bazen iki yarıda tek başına puan vermeyen kısa blokları birleştirip yeni bir run ekler, bazen de ayrı ayrı sayılan iki parçayı tek birleşik skorla değiştirir. Sonuçta tam el için
\[ R(c)=R(c^{L})+R(c^{R})+\operatorname{adjust} \]
eşitliği geçerlidir.
Üreteç fonksiyonu bölme üzerinde çarpanlara ayrılır:
\[ G_c(x)=G_{c^{L}}(x)\,G_{c^{R}}(x). \]
İki yarının altküme sayım dizileri \(f_L(s)\) ve \(f_R(s)\) ise
\[ F_{15}(c)=\sum_{s=0}^{15} f_L(s)\,f_R(15-s) \]
olur. Uygulamalar sağ yarı için ters çevrilmiş bir dizi de sakladığından, bu hesap her tam el için yalnızca 16 terimli bir skaler çarpımdır.
Birleşik el için
\[ B_L=H(c^{L})-P(c^{L})-R(c^{L}),\qquad B_R=H(c^{R})-P(c^{R})-R(c^{R}) \]
yazalım. Tam run skoru, \(R(c^{L})+R(c^{R})\) değerinden yalnızca \(\operatorname{adjust}\) kadar farklı olduğu için hedef denklem
\[ H(c)-P(c)-R(c)=B_L+B_R-\operatorname{adjust}=2F_{15}(c) \]
haline gelir. Yani bir sol yarı ile bir sağ yarı, düzeltilmiş taban değeri tam olarak 15'lerin iki katına eşitse geçerli bir el oluşturur. Bu durumda cevaba \(W(c^{L})W(c^{R})\) eklenir. Tümü sıfır olan vektör eşitliği trivyal olarak sağladığı için en sonda 1 çıkarılır.
C++, Python ve Java uygulamaları önce her yarıdaki bütün sayım desenlerini üretir: solda \(5^6\), sağda \(5^7\) durum. Her yarım-durum için el toplamı, çift skoru, iç run skoru, çarpan ağırlığı, 15'e kadar kısaltılmış altküme-toplam polinomu ve daha sonra gerekli olacak önek/sonek blok bilgileri hesaplanır.
Her sol yarım-durum her sağ yarım-durumla eşleştirilir. Uygulama önce sınırı aşan olası run için düzeltmeyi hesaplar, sonra
\[ \text{targetTwice}=B_L+B_R-\operatorname{adjust} \]
değerini oluşturur. Bu değer negatifse, tekse veya 340'tan büyükse çift hemen elenir. 340 sınırı, tam bir rank vektörünün alabileceği en büyük yüz değeri toplamından gelir. Aksi halde \(F_{15}\) için 16 terimli skaler çarpım hesaplanır ve ara toplam hedefi aşarsa erken durulur.
Eşitlik sağlandığında iki yarının ağırlıkları çarpılıp toplama eklenir. Böylece birleştirilmiş rank vektörünün temsil ettiği bütün suit seçimleri doğru sayılmış olur. Boş el en sonda çıkarılır. C++ ve Java sürümleri dış döngüyü birden fazla iş parçacığına bölerek hızlandırır; Python girişi de aynı matematiksel hesap yolunu kullanır.
Yarım-durum ön hesaplaması \(O(5^6)\) ve \(O(5^7)\) özet maliyetine sahiptir; her özetin içinde yalnızca \(0\) ile \(15\) arasındaki toplamlar üzerinde sabit boyutlu bir DP vardır. Baskın aşama iki durum kümesinin Kartezyen çarpımıdır; bu yüzden birleştirme maliyeti
\[ O(5^6\cdot 5^7\cdot 16)=O(5^{13}) \]
olur. Yani yöntem arama uzayının üssünü düşürmez. Kazanç, tam bir elin pahalı skor bileşenlerini her seferinde sıfırdan hesaplamak yerine, yarım el özetlerini önceden üretip tekrar kullanmasından gelir. Bellek kullanımı
\[ O\!\big((5^6+5^7)\cdot 16\big) \]
mertebesindedir; bu da saklanan yarım-durum tabloları ve kısa altküme-toplam dizilerinden kaynaklanır.
Una mano de una baraja estándar de 52 cartas se comprime en un vector de conteos por rango \(c=(c_1,\dots,c_{13})\), donde \(0\le c_r\le 4\) y los rangos son \(A,2,\dots,10,J,Q,K\). Los valores usados en el problema son
\[ v=(1,2,3,4,5,6,7,8,9,10,10,10,10). \]
Como el vector no distingue palos, un mismo vector representa
\[ W(c)=\prod_{r=1}^{13}\binom{4}{c_r} \]
manos físicas distintas: para cada rango se eligen \(c_r\) palos entre los cuatro disponibles. La tarea consiste en contar, con esa multiplicidad y excluyendo la mano vacía, todos los vectores para los que la suma de valores
\[ H(c)=\sum_{r=1}^{13} v_r c_r \]
coincide exactamente con la puntuación de cribbage usada aquí, es decir
\[ C(c)=P(c)+R(c)+2F_{15}(c). \]
Aquí \(P(c)\) es la puntuación por parejas, \(R(c)\) la puntuación por corridas, y \(F_{15}(c)\) el número de subconjuntos de cartas cuyo valor suma 15. En otras palabras, hay que hacer un conteo ponderado exacto de todas las manos no vacías que cumplen \(H(c)=C(c)\).
Como los palos solo intervienen a través de la multiplicidad, el objeto combinatorio real es el vector de 13 componentes \(c\). Cada mano posible determina exactamente un vector, y cada vector representa \(W(c)\) elecciones de palos. Esta compresión hace el problema finito: solo existen \(5^{13}\) vectores posibles, porque cada rango puede aparecer 0, 1, 2, 3 o 4 veces.
La contribución de parejas es inmediata. Si el rango \(r\) aparece \(c_r\) veces, contiene \(\binom{c_r}{2}\) parejas del mismo rango, y cada una vale 2 puntos. Por tanto,
\[ P(c)=2\sum_{r=1}^{13}\binom{c_r}{2}=\sum_{r=1}^{13} c_r(c_r-1). \]
La puntuación por corridas requiere un poco más de estructura. Separamos la línea de rangos en bloques máximos consecutivos de conteos positivos. Para un bloque \(a,a+1,\dots,b\), definimos
\[ L=b-a+1,\qquad M=\prod_{r=a}^{b} c_r. \]
Cada elección de una carta de cada rango del bloque produce una corrida distinta. Así, el bloque aporta \(L\cdot M\) si \(L\ge 3\), y 0 si no. En consecuencia,
\[ R(c)=\sum_{\text{bloques positivos máximos}} \mathbf{1}_{L\ge 3}\,L\,M. \]
Esto explica por qué una mano como \(A,A,2,3,4,5\) puntúa como dos corridas de longitud 5 y no como una colección de subcorridas más cortas: en cribbage se valora el bloque máximo.
Para cada rango \(r\), podemos tomar \(d\) de sus \(c_r\) copias en un subconjunto, con \(0\le d\le c_r\). Hay \(\binom{c_r}{d}\) maneras de hacerlo, y la contribución al total es \(d\,v_r\). Por eso la función generadora
\[ G_c(x)=\prod_{r=1}^{13}\left(\sum_{d=0}^{c_r}\binom{c_r}{d}x^{d v_r}\right) \]
satisface
\[ F_{15}(c)=[x^{15}]\,G_c(x). \]
Las implementaciones calculan ese coeficiente con una programación dinámica corta sobre las sumas \(0,1,\dots,15\). Como solo interesa llegar a 15, el polinomio se trunca inmediatamente.
Tomemos la mano formada por dos ases y una carta de cada uno de los rangos 2, 3, 4 y 5. En el vector de conteos eso significa
\[ c_A=2,\quad c_2=c_3=c_4=c_5=1, \]
y todos los demás componentes valen 0. Entonces
\[ H(c)=2\cdot 1+2+3+4+5=16. \]
La puntuación por parejas es \(P(c)=2\), debido al par de ases. Además, los rangos \(A,2,3,4,5\) forman un único bloque máximo positivo de longitud 5 con producto \(2\cdot 1\cdot 1\cdot 1\cdot 1=2\), así que
\[ R(c)=5\cdot 2=10. \]
Para los quince, el subconjunto \(A+2+3+4+5\) suma 15, y como se puede elegir cualquiera de los dos ases, resulta \(F_{15}(c)=2\). Por tanto,
\[ P(c)+R(c)+2F_{15}(c)=2+10+4=16=H(c). \]
Ese es exactamente el tipo de mano que se añade al recuento final.
El truco principal de la implementación es una división meet-in-the-middle después del sexto rango. Un vector completo se escribe como
\[ c=(c^{L},c^{R}), \]
donde la mitad izquierda contiene los primeros 6 rangos y la derecha los 7 restantes. Para cada mitad se precomputa un resumen compacto con
\[ H,\quad P,\quad R,\quad B=H-P-R,\quad W, \]
junto con
\[ f(s)=\#\{\text{subconjuntos de esta mitad con suma } s\}\qquad (0\le s\le 15), \]
y la longitud, el producto de multiplicidades y la puntuación del bloque positivo inicial y final. Así el trabajo costoso de una media mano se hace una sola vez y luego se reutiliza para muchas combinaciones.
Las dos mitades son independientes salvo en el punto de corte. Si la izquierda termina en un bloque positivo y la derecha empieza con otro, ambos forman un único bloque más largo en la mano completa. Si el sufijo izquierdo tiene longitud y multiplicidad \((\ell_L,m_L)\) y el prefijo derecho tiene \((\ell_R,m_R)\), definimos
\[ S(\ell,m)= \begin{cases} \ell m,& \ell\ge 3,\\ 0,& \ell<3. \end{cases} \]
La corrección de frontera es entonces
\[ \operatorname{adjust}=S(\ell_L+\ell_R,m_Lm_R)-S(\ell_L,m_L)-S(\ell_R,m_R). \]
Ese término puede crear una nueva corrida que antes era demasiado corta, o sustituir dos puntuaciones parciales por la puntuación correcta del bloque fusionado. Con ello, la puntuación total por corridas pasa a ser
\[ R(c)=R(c^{L})+R(c^{R})+\operatorname{adjust}. \]
La función generadora también se factoriza con la partición:
\[ G_c(x)=G_{c^{L}}(x)\,G_{c^{R}}(x). \]
Si \(f_L(s)\) y \(f_R(s)\) son los arreglos de subconjuntos de ambas mitades, entonces
\[ F_{15}(c)=\sum_{s=0}^{15} f_L(s)\,f_R(15-s). \]
Las implementaciones guardan una copia invertida del arreglo derecho, de modo que esta operación se reduce a un producto escalar de 16 términos.
Para una mano completa escribimos
\[ B_L=H(c^{L})-P(c^{L})-R(c^{L}),\qquad B_R=H(c^{R})-P(c^{R})-R(c^{R}). \]
Como la puntuación total por corridas difiere de \(R(c^{L})+R(c^{R})\) exactamente en \(\operatorname{adjust}\), la identidad objetivo se convierte en
\[ H(c)-P(c)-R(c)=B_L+B_R-\operatorname{adjust}=2F_{15}(c). \]
Así, un estado izquierdo y uno derecho forman una mano válida exactamente cuando el valor base corregido coincide con el doble del número de quince obtenido por el producto escalar. En ese caso la contribución al total es \(W(c^{L})W(c^{R})\). El vector nulo satisface la igualdad de forma trivial, y por eso se elimina al final restando 1.
Las implementaciones en C++, Python y Java generan primero todos los patrones posibles de cada mitad: \(5^6\) estados a la izquierda y \(5^7\) a la derecha. Para cada medio-estado calculan la suma de valores, la puntuación por parejas, la puntuación interna por corridas, la multiplicidad, el polinomio truncado de sumas hasta 15 y la información de prefijo/sufijo necesaria para fusionar después.
Cada estado izquierdo se combina con cada estado derecho. La implementación calcula primero la corrección de frontera para una posible corrida que atraviese el corte y luego forma
\[ \text{targetTwice}=B_L+B_R-\operatorname{adjust}. \]
Si ese valor es negativo, impar o mayor que 340, la pareja se descarta enseguida. El límite 340 proviene de la máxima suma de valores posible en un vector completo. En caso contrario, se evalúa el producto escalar de 16 términos para \(F_{15}\), con corte anticipado si la suma parcial ya supera el objetivo.
Cuando la prueba de igualdad se cumple, se añade el producto de las multiplicidades de ambas mitades. Así se cuentan correctamente todas las elecciones de palos representadas por el vector fusionado. La mano vacía se excluye al final. Las versiones en C++ y Java paralelizan el barrido exterior sobre los estados izquierdos; la entrada en Python sigue la misma ruta matemática.
La precomputación de medio-estados cuesta \(O(5^6)\) y \(O(5^7)\) resúmenes, cada uno con una programación dinámica de tamaño constante sobre las sumas \(0\) a \(15\). La fase dominante es el producto cartesiano de ambos conjuntos de estados, así que el coste de fusión es
\[ O(5^6\cdot 5^7\cdot 16)=O(5^{13}). \]
Esto significa que el método no reduce el exponente del espacio de búsqueda. La mejora práctica viene de que la información costosa de una media mano se calcula una vez y se reutiliza muchas veces, de modo que cada comprobación completa queda reducida a una corrección de frontera y a un producto escalar corto. El uso de memoria es
\[ O\!\big((5^6+5^7)\cdot 16\big), \]
debido a las tablas de medio-estados almacenadas y a sus arreglos cortos de sumas de subconjuntos.
把一手来自标准 52 张扑克牌的牌压缩成一个按点数统计的向量 \(c=(c_1,\dots,c_{13})\)，其中 \(0\le c_r\le 4\)，13 个点数依次是 \(A,2,\dots,10,J,Q,K\)。题目使用的牌面数值是
\[ v=(1,2,3,4,5,6,7,8,9,10,10,10,10) \]
这个表示法不区分花色，因此一个计数向量实际上对应
\[ W(c)=\prod_{r=1}^{13}\binom{4}{c_r} \]
种不同的实际手牌，因为每个点数都要从 4 个花色里选出 \(c_r\) 张。题目要求按这个权重统计所有非空手牌，使得它们的牌面总和
\[ H(c)=\sum_{r=1}^{13} v_r c_r \]
恰好等于题目中采用的 cribbage 计分值
\[ C(c)=P(c)+R(c)+2F_{15}(c) \]
其中 \(P(c)\) 是对子得分，\(R(c)\) 是顺子得分，\(F_{15}(c)\) 表示牌值和为 15 的子集个数。所以整个问题就是：在所有非空计数向量中，精确地加权统计满足 \(H(c)=C(c)\) 的那些向量。
由于花色只通过“有多少种选择”这一乘法因子出现，真正需要研究的组合对象就是 13 维向量 \(c\)。每一手合法牌都唯一对应一个这样的向量，而每个向量又代表 \(W(c)\) 种花色分配。这样压缩之后，问题就变成有限问题：每个点数只能出现 0、1、2、3、4 次，因此一共只有 \(5^{13}\) 个候选向量。
对子分数最直接。若某个点数 \(r\) 出现了 \(c_r\) 次，则其中有 \(\binom{c_r}{2}\) 对同点数牌，每对得 2 分，因此
\[ P(c)=2\sum_{r=1}^{13}\binom{c_r}{2}=\sum_{r=1}^{13} c_r(c_r-1) \]
顺子分数稍微复杂一些。把 13 个点数按顺序排成一条线，把所有正计数分解成若干个极大连续块。对某个连续块 \(a,a+1,\dots,b\)，记
\[ L=b-a+1,\qquad M=\prod_{r=a}^{b} c_r \]
在这个块中，每个点数各选一张牌，就得到一条顺子，因此该块一共对应 \(M\) 条顺子；若块长 \(L\ge 3\)，该块贡献 \(L\cdot M\) 分，否则贡献 0。于是
\[ R(c)=\sum_{\text{max positive blocks}} \mathbf{1}_{L\ge 3}\,L\,M \]
这正好解释了为什么像 \(A,A,2,3,4,5\) 这样的手牌会被算作两条长度为 5 的顺子，而不是再额外把其中更短的子顺子单独加分：计分时看的是整段极大连续块。
对于每个点数 \(r\)，我们可以从它的 \(c_r\) 张牌中选出 \(d\) 张放进某个子集，其中 \(0\le d\le c_r\)。这样的选法有 \(\binom{c_r}{d}\) 种，带来的数值贡献是 \(d\,v_r\)。因此生成函数
\[ G_c(x)=\prod_{r=1}^{13}\left(\sum_{d=0}^{c_r}\binom{c_r}{d}x^{d v_r}\right) \]
满足
\[ F_{15}(c)=[x^{15}]\,G_c(x) \]
实现中并不会真的做高次多项式运算，而是只保留和为 \(0,1,\dots,15\) 的系数，用一个很短的动态规划数组逐点数更新。因为题目只关心是否凑出 15，所以所有大于 15 的项都可以立刻丢掉。
考虑这样一手牌：两张 A，再加上一张 2、一张 3、一张 4、一张 5。它对应的计数向量满足
\[ c_A=2,\quad c_2=c_3=c_4=c_5=1 \]
其余分量全为 0。于是牌面总和为
\[ H(c)=2\cdot 1+2+3+4+5=16 \]
两张 A 构成一个对子，所以 \(P(c)=2\)。同时，\(A,2,3,4,5\) 形成一个长度为 5 的极大连续块，其 multiplicity product 为 \(2\cdot 1\cdot 1\cdot 1\cdot 1=2\)，因此
\[ R(c)=5\cdot 2=10 \]
再看“15”：子集 \(A+2+3+4+5\) 的和正好是 15，而 A 有两张可选，所以 \(F_{15}(c)=2\)。最终得到
\[ P(c)+R(c)+2F_{15}(c)=2+10+4=16=H(c) \]
这正是程序要统计进去的一类手牌。
实现里的核心技巧是在第 6 个点数之后做一次 meet-in-the-middle 划分。完整向量写成
\[ c=(c^{L},c^{R}) \]
其中左半边包含前 6 个点数，右半边包含后 7 个点数。对每个半向量，程序都预先计算一个紧凑摘要，包含
\[ H,\quad P,\quad R,\quad B=H-P-R,\quad W \]
以及
\[ f(s)=\#\{\text{subsets in this half with total } s\}\qquad (0\le s\le 15) \]
此外，还要记录开头连续正块和结尾连续正块的长度、乘积以及它们各自的顺子得分。这样一来，半手牌里那些昂贵的计算只做一次，之后可以被另一侧的大量状态反复复用。
左右两半基本独立，唯一真正的耦合发生在分界点。如果左半边以一个正计数块结束，而右半边以一个正计数块开始，那么这两个块在完整手牌里其实应该合并成一个更长的连续块。设左侧后缀块的长度和乘积为 \((\ell_L,m_L)\)，右侧前缀块的长度和乘积为 \((\ell_R,m_R)\)，定义
\[ S(\ell,m)= \begin{cases} \ell m,& \ell\ge 3,\\ 0,& \ell<3 \end{cases} \]
那么跨边界的修正项就是
\[ \operatorname{adjust}=S(\ell_L+\ell_R,m_Lm_R)-S(\ell_L,m_L)-S(\ell_R,m_R) \]
这个修正有两种可能作用：要么把左右两边原本各自太短、单独不计分的块拼成一个新的顺子；要么把左右两边已经单独计过的局部顺子分数替换成完整合并后的正确分数。修正后，完整手牌的顺子分数就是
\[ R(c)=R(c^{L})+R(c^{R})+\operatorname{adjust} \]
生成函数在左右划分下同样可分解：
\[ G_c(x)=G_{c^{L}}(x)\,G_{c^{R}}(x) \]
若左右两边的子集统计数组分别是 \(f_L(s)\) 与 \(f_R(s)\)，那么
\[ F_{15}(c)=\sum_{s=0}^{15} f_L(s)\,f_R(15-s) \]
实现中右边还保存了一份倒序数组，因此每次合并只需要做一个固定长度为 16 的点积，而不必重新做整套子集和动态规划。
对完整手牌，记
\[ B_L=H(c^{L})-P(c^{L})-R(c^{L}),\qquad B_R=H(c^{R})-P(c^{R})-R(c^{R}) \]
由于完整顺子分数相对于 \(R(c^{L})+R(c^{R})\) 只差一个 \(\operatorname{adjust}\)，目标等式就变成
\[ H(c)-P(c)-R(c)=B_L+B_R-\operatorname{adjust}=2F_{15}(c) \]
因此，左半状态和右半状态恰好在“修正后的基值”等于“15 的个数的两倍”时，拼成一手合法牌。每当这个条件成立，答案就增加 \(W(c^{L})W(c^{R})\)。全零向量会平凡地满足等式，所以最后还要减去 1 把空手牌排除掉。
C++、Python 和 Java 实现都会先枚举左右两半的全部计数模式：左边 \(5^6\) 个，右边 \(5^7\) 个。对每个半状态，都预先算好牌面总和、对子分数、内部顺子分数、组合权重、截断到 15 的子集和多项式，以及后续合并所需的前缀/后缀块信息。
每个左状态都与每个右状态配对。实现先计算跨分界线的顺子修正，然后形成
\[ \text{targetTwice}=B_L+B_R-\operatorname{adjust} \]
如果这个值为负、为奇数，或者大于 340，那么这对状态不可能满足目标条件，直接跳过。340 这个上界来自完整手牌牌面总和的最大可能值。否则就计算 16 项点积得到 \(F_{15}\)，并在部分和已经超过目标时提前停止。
只要等式成立，就把左右两侧的 multiplicity 相乘后加入总数。这保证了所有由该计数向量代表的花色选择都被准确统计。空手牌最后单独扣除。C++ 和 Java 版本会把外层循环分给多个线程并行执行；Python 入口沿用同一套数学计算流程。
半状态预处理的成本分别是 \(O(5^6)\) 和 \(O(5^7)\)，每个状态内部只需要一个常数规模的动态规划数组，索引范围是 \(0\) 到 \(15\)。主导成本来自左右状态集合的笛卡尔积，因此合并阶段的复杂度为
\[ O(5^6\cdot 5^7\cdot 16)=O(5^{13}) \]
也就是说，这个方法并没有降低搜索空间的指数。它真正节省的是常数因子：完整手牌的复杂评分信息不再每次从头计算，而是拆成两个可缓存的半摘要，再加上一次边界修正和一个 16 项点积。内存复杂度为
\[ O\!\big((5^6+5^7)\cdot 16\big) \]
对应存储的半状态表以及它们的短子集和数组。
Любая рука из стандартной колоды в 52 карты сжимается в вектор счётчиков рангов \(c=(c_1,\dots,c_{13})\), где \(0\le c_r\le 4\), а ранги идут как \(A,2,\dots,10,J,Q,K\). Значения карт в задаче задаются вектором
\[ v=(1,2,3,4,5,6,7,8,9,10,10,10,10). \]
Поскольку такая запись не различает масти, один и тот же вектор соответствует
\[ W(c)=\prod_{r=1}^{13}\binom{4}{c_r} \]
разным физическим рукам: для каждого ранга нужно выбрать \(c_r\) мастей из четырёх. Требуется, с учётом этого веса и исключая пустую руку, посчитать все векторы, для которых сумма достоинств
\[ H(c)=\sum_{r=1}^{13} v_r c_r \]
точно совпадает со счётом в cribbage, используемым в задаче:
\[ C(c)=P(c)+R(c)+2F_{15}(c). \]
Здесь \(P(c)\) — очки за пары, \(R(c)\) — очки за ранны, а \(F_{15}(c)\) — число подмножеств карт с суммой 15. Иными словами, нужно выполнить точный взвешенный подсчёт всех непустых рук, удовлетворяющих равенству \(H(c)=C(c)\).
Так как масти влияют только через множитель кратности, основной комбинаторный объект здесь — 13-мерный вектор \(c\). Каждая допустимая рука задаёт ровно один такой вектор, и каждый вектор представляет \(W(c)\) различных выборов мастей. После такого сжатия задача становится конечной: всего существует \(5^{13}\) возможных векторов, потому что каждый ранг может встречаться 0, 1, 2, 3 или 4 раза.
Вклад пар считается сразу. Если ранг \(r\) встречается \(c_r\) раз, то в нём есть \(\binom{c_r}{2}\) пар одинакового ранга, и каждая пара даёт 2 очка. Поэтому
\[ P(c)=2\sum_{r=1}^{13}\binom{c_r}{2}=\sum_{r=1}^{13} c_r(c_r-1). \]
С раннами чуть тоньше. Разобьём последовательность рангов на максимальные подряд идущие блоки положительных счётчиков. Для блока \(a,a+1,\dots,b\) обозначим
\[ L=b-a+1,\qquad M=\prod_{r=a}^{b} c_r. \]
Каждый выбор одной карты из каждого ранга такого блока образует отдельный ранн. Поэтому блок даёт вклад \(L\cdot M\), если \(L\ge 3\), и 0 в противном случае. Значит,
\[ R(c)=\sum_{\text{максимальные положительные блоки}} \mathbf{1}_{L\ge 3}\,L\,M. \]
Именно поэтому рука вида \(A,A,2,3,4,5\) даёт две пятёрочные последовательности, а не набор более коротких подраннов: считается максимальный связный блок, а не все его подпоследовательности.
Для каждого ранга \(r\) можно выбрать в подмножество \(d\) карт из его \(c_r\) копий, где \(0\le d\le c_r\). Это можно сделать \(\binom{c_r}{d}\) способами, а суммарное достоинство увеличивается на \(d\,v_r\). Поэтому производящая функция
\[ G_c(x)=\prod_{r=1}^{13}\left(\sum_{d=0}^{c_r}\binom{c_r}{d}x^{d v_r}\right) \]
обладает свойством
\[ F_{15}(c)=[x^{15}]\,G_c(x). \]
В реализации этот коэффициент считается коротким динамическим программированием по суммам \(0,1,\dots,15\). Поскольку интересует только сумма 15, коэффициенты больших степеней даже не хранятся.
Возьмём руку из двух тузов и по одной карте рангов 2, 3, 4 и 5. В терминах вектора счётчиков это означает
\[ c_A=2,\quad c_2=c_3=c_4=c_5=1, \]
а все остальные компоненты равны 0. Тогда
\[ H(c)=2\cdot 1+2+3+4+5=16. \]
Пара тузов даёт \(P(c)=2\). Ранги \(A,2,3,4,5\) образуют один максимальный положительный блок длины 5 с произведением кратностей \(2\cdot 1\cdot 1\cdot 1\cdot 1=2\), следовательно
\[ R(c)=5\cdot 2=10. \]
Для пятнадцаток подмножество \(A+2+3+4+5\) имеет сумму 15, причём туз можно выбрать двумя способами, поэтому \(F_{15}(c)=2\). Получаем
\[ P(c)+R(c)+2F_{15}(c)=2+10+4=16=H(c). \]
Именно такие руки и попадают в итоговый ответ.
Главный технический приём — разбиение meet-in-the-middle после шестого ранга. Полный вектор записывается как
\[ c=(c^{L},c^{R}), \]
где левая половина содержит первые 6 рангов, а правая — оставшиеся 7. Для каждой половины заранее вычисляется компактное описание:
\[ H,\quad P,\quad R,\quad B=H-P-R,\quad W, \]
а также массив
\[ f(s)=\#\{\text{подмножества этой половины с суммой } s\}\qquad (0\le s\le 15), \]
и информация о длине, произведении кратностей и вкладе начального и конечного положительного блока. Идея в том, что дорогие вычисления для половины руки делаются один раз и потом используются много раз при слиянии.
Левая и правая части независимы, кроме точки разреза. Если левая половина заканчивается положительным блоком, а правая начинается положительным блоком, то в полной руке это на самом деле один длинный непрерывный блок. Пусть у левого суффикса длина и произведение равны \((\ell_L,m_L)\), а у правого префикса — \((\ell_R,m_R)\). Определим
\[ S(\ell,m)= \begin{cases} \ell m,& \ell\ge 3,\\ 0,& \ell<3. \end{cases} \]
Тогда граничная поправка равна
\[ \operatorname{adjust}=S(\ell_L+\ell_R,m_Lm_R)-S(\ell_L,m_L)-S(\ell_R,m_R). \]
Эта поправка либо создаёт новый ранн, который был слишком коротким по отдельности, либо заменяет два локальных вклада одним правильным вкладом склеенного блока. После этого полный счёт за ранны равен
\[ R(c)=R(c^{L})+R(c^{R})+\operatorname{adjust}. \]
Производящая функция тоже раскладывается по разбиению:
\[ G_c(x)=G_{c^{L}}(x)\,G_{c^{R}}(x). \]
Если \(f_L(s)\) и \(f_R(s)\) — массивы количества подмножеств для двух половин, то
\[ F_{15}(c)=\sum_{s=0}^{15} f_L(s)\,f_R(15-s). \]
В реализациях для правой половины хранится ещё и обращённый массив, поэтому вычисление сводится к скалярному произведению из 16 членов.
Для полной руки введём
\[ B_L=H(c^{L})-P(c^{L})-R(c^{L}),\qquad B_R=H(c^{R})-P(c^{R})-R(c^{R}). \]
Поскольку полный счёт за ранны отличается от \(R(c^{L})+R(c^{R})\) ровно на \(\operatorname{adjust}\), целевое равенство принимает вид
\[ H(c)-P(c)-R(c)=B_L+B_R-\operatorname{adjust}=2F_{15}(c). \]
Значит, левая и правая половины образуют допустимую руку тогда и только тогда, когда скорректированное базовое значение равно удвоенному числу пятнадцаток. В этом случае к ответу прибавляется \(W(c^{L})W(c^{R})\). Нулевой вектор удовлетворяет равенству тривиально, поэтому в конце из результата вычитается 1.
Реализации на C++, Python и Java сначала перечисляют все возможные шаблоны для каждой половины: \(5^6\) состояний слева и \(5^7\) справа. Для каждого полусостояния вычисляются сумма достоинств, очки за пары, внутренние ранны, вес кратности, усечённый до 15 полином подмножеств и данные о префиксном и суффиксном блоках.
Каждое левое состояние сопоставляется с каждым правым. Сначала вычисляется граничная поправка для ранна, пересекающего разрез, затем формируется значение
\[ \text{targetTwice}=B_L+B_R-\operatorname{adjust}. \]
Если оно отрицательно, нечётно или больше 340, такая пара сразу отбрасывается. Верхняя граница 340 возникает из максимальной возможной суммы достоинств у полного вектора счётчиков. Иначе считается 16-членное скалярное произведение для \(F_{15}\), причём вычисление прекращается раньше, если частичная сумма уже превысила цель.
Когда проверка равенства проходит, в ответ добавляется произведение кратностей двух половин. Тем самым корректно учитываются все выборы мастей, которые представляет объединённый вектор. Пустая рука исключается в самом конце. Версии на C++ и Java распараллеливают внешний проход по левым состояниям; Python-обёртка следует тому же математическому алгоритму.
Предвычисление полусостояний стоит \(O(5^6)\) и \(O(5^7)\) сводок, каждая из которых использует динамику постоянного размера по суммам от \(0\) до \(15\). Основная стоимость возникает из декартова произведения двух множеств состояний, поэтому этап слияния имеет сложность
\[ O(5^6\cdot 5^7\cdot 16)=O(5^{13}). \]
Иначе говоря, этот подход не уменьшает показатель степени у пространства поиска. Его выигрыш — в снижении констант: дорогие характеристики половины руки считаются один раз и затем многократно переиспользуются, так что проверка полной руки сводится к одной граничной поправке и короткому скалярному произведению. Память оценивается как
\[ O\!\big((5^6+5^7)\cdot 16\big), \]
что соответствует сохранённым таблицам полусостояний и их коротким массивам подмножеств.
تُمثَّل أي يد من رزمة قياسية من 52 بطاقة بمتجه عدٍّ حسب الرتبة \(c=(c_1,\dots,c_{13})\)، حيث \(0\le c_r\le 4\)، والرتب هي \(A,2,\dots,10,J,Q,K\). القيم المستخدمة في المسألة هي
\[ v=(1,2,3,4,5,6,7,8,9,10,10,10,10). \]
ولأن هذا التمثيل لا يميز بين الأشكال، فإن متجهًا واحدًا يمثّل في الحقيقة
\[ W(c)=\prod_{r=1}^{13}\binom{4}{c_r} \]
يدًا فعلية مختلفة، لأننا نختار لكل رتبة \(c_r\) أشكالًا من أصل أربعة. المطلوب هو عدّ جميع الأيدي غير الفارغة، مع هذا الوزن، التي يكون فيها مجموع القيم
\[ H(c)=\sum_{r=1}^{13} v_r c_r \]
مساويًا تمامًا لنقاط cribbage المعتمدة في المسألة:
\[ C(c)=P(c)+R(c)+2F_{15}(c). \]
هنا \(P(c)\) هو نقاط الأزواج، و\(R(c)\) هو نقاط السلاسل المتتالية، و\(F_{15}(c)\) هو عدد المجموعات الجزئية من البطاقات التي قيمتها 15. إذن المسألة هي عدّ موزون ودقيق لكل الأيدي غير الفارغة التي تحقق \(H(c)=C(c)\).
بما أن الأشكال لا تؤثر إلا عبر عامل تعددي، فإن الجسم التوافقي الحقيقي هنا هو المتجه ذو 13 مركبة \(c\). كل يد قانونية تقابل متجهًا واحدًا بالضبط، وكل متجه يمثل \(W(c)\) اختيارات مختلفة للأشكال. بهذا الضغط تصبح المسألة منتهية: فلكل رتبة خمس حالات ممكنة فقط، من 0 إلى 4، ولذلك يوجد \(5^{13}\) متجهًا مرشحًا لا غير.
مساهمة الأزواج مباشرة جدًا. إذا ظهرت الرتبة \(r\) بعدد \(c_r\)، فعدد الأزواج المتساوية في الرتبة هو \(\binom{c_r}{2}\)، وكل زوج قيمته نقطتان. لذلك
\[ P(c)=2\sum_{r=1}^{13}\binom{c_r}{2}=\sum_{r=1}^{13} c_r(c_r-1). \]
أما نقاط السلاسل فتحتاج إلى توصيف أدق. ننظر إلى خط الرتب ونقسمه إلى كتل قصوى متجاورة تكون فيها العدّات موجبة. إذا كانت إحدى هذه الكتل هي \(a,a+1,\dots,b\)، فنعرف
\[ L=b-a+1,\qquad M=\prod_{r=a}^{b} c_r. \]
كل اختيار لبطاقة واحدة من كل رتبة داخل هذه الكتلة يولد سلسلة مستقلة، ولهذا تسهم الكتلة بمقدار \(L\cdot M\) إذا كان \(L\ge 3\)، وإلا فمساهمتها صفر. ومن ثم
\[ R(c)=\sum_{\text{max positive blocks}} \mathbf{1}_{L\ge 3}\,L\,M. \]
وهذا يفسر مثلًا لماذا تعطي يد من الشكل \(A,A,2,3,4,5\) سلسلتين من الطول 5، ولا تُحسب معها سلاسل أقصر على نحو مستقل: التقييم يكون على مستوى الكتلة القصوى نفسها.
لكل رتبة \(r\)، نستطيع أن نختار \(d\) بطاقة من أصل \(c_r\) بطاقات لتدخل في مجموعة جزئية، حيث \(0\le d\le c_r\). عدد هذه الاختيارات هو \(\binom{c_r}{d}\)، ومساهمتها في المجموع هي \(d\,v_r\). لذلك فإن الدالة المولدة
\[ G_c(x)=\prod_{r=1}^{13}\left(\sum_{d=0}^{c_r}\binom{c_r}{d}x^{d v_r}\right) \]
تحقق العلاقة
\[ F_{15}(c)=[x^{15}]\,G_c(x). \]
التنفيذ لا يبني كثيرة حدود كبيرة فعلًا؛ بل يستعمل برمجة ديناميكية قصيرة على المجاميع \(0,1,\dots,15\). وبما أن ما بعد 15 لا يهم إطلاقًا، فإن كل شيء يُقصّ مباشرة عند هذه الدرجة.
لنأخذ يدًا فيها آسان، ومعهما بطاقة واحدة من كل من 2 و3 و4 و5. في متجه العد يعني هذا أن
\[ c_A=2,\quad c_2=c_3=c_4=c_5=1, \]
وبقية المركبات تساوي صفرًا. عندئذ
\[ H(c)=2\cdot 1+2+3+4+5=16. \]
الآسان يشكلان زوجًا واحدًا، إذن \(P(c)=2\). كما أن الرتب \(A,2,3,4,5\) تكوّن كتلة موجبة قصوى طولها 5، وحاصل ضرب التعدديات فيها هو \(2\cdot 1\cdot 1\cdot 1\cdot 1=2\)، وبالتالي
\[ R(c)=5\cdot 2=10. \]
أما بالنسبة إلى الخمس عشرة، فالمجموعة \(A+2+3+4+5\) مجموعها 15، ويمكن اختيار أي واحد من الآسين، لذا \(F_{15}(c)=2\). وعليه نحصل على
\[ P(c)+R(c)+2F_{15}(c)=2+10+4=16=H(c). \]
وهذا بالضبط نوع الأيدي التي يضيفها البرنامج إلى الجواب.
الحيلة الأساسية في التنفيذ هي تقسيم meet-in-the-middle بعد الرتبة السادسة. يكتب المتجه الكامل على الصورة
\[ c=(c^{L},c^{R}), \]
حيث يحوي النصف الأيسر أول 6 رتب، ويحوي النصف الأيمن الرتب السبع الباقية. لكل نصف تُحسب مسبقًا خلاصة مضغوطة تتضمن
\[ H,\quad P,\quad R,\quad B=H-P-R,\quad W, \]
إضافة إلى المصفوفة
\[ f(s)=\#\{\text{subsets in this half with total } s\}\qquad (0\le s\le 15). \]
كما تُخزن معلومات طول الكتلة الموجبة الأولى والأخيرة، وحاصل ضرب تعددياتها، ونقطتها الجزئية. الفكرة هي أن العمل المكلف لنصف اليد يُنجز مرة واحدة ثم يُعاد استعماله مع عدد كبير من الأنصاف المقابلة.
النصفان مستقلان تقريبًا، والاستثناء الوحيد يقع عند نقطة الفصل. إذا انتهى النصف الأيسر بكتلة موجبة وبدأ النصف الأيمن بكتلة موجبة، فإن هاتين الكتلتين تصبحان في اليد الكاملة كتلة واحدة أطول. إذا كان طول وحاصل ضرب كتلة الذيل اليسرى هما \((\ell_L,m_L)\)، وطول وحاصل ضرب كتلة المقدمة اليمنى هما \((\ell_R,m_R)\)، فنعرف
\[ S(\ell,m)= \begin{cases} \ell m,& \ell\ge 3,\\ 0,& \ell<3. \end{cases} \]
وعندها تكون تصحيحة الحد الفاصل
\[ \operatorname{adjust}=S(\ell_L+\ell_R,m_Lm_R)-S(\ell_L,m_L)-S(\ell_R,m_R). \]
قد تضيف هذه القيمة سلسلة جديدة لم تكن تُحتسب في أي نصف على حدة، أو قد تستبدل مجموعتين جزئيتين من النقاط بنقطة السلسلة الصحيحة بعد الدمج. وبعد التصحيح يصبح مجموع نقاط السلاسل في اليد الكاملة
\[ R(c)=R(c^{L})+R(c^{R})+\operatorname{adjust}. \]
الدالة المولدة نفسها تتفكك مع هذا التقسيم:
\[ G_c(x)=G_{c^{L}}(x)\,G_{c^{R}}(x). \]
إذا كانت \(f_L(s)\) و\(f_R(s)\) هما مصفوفتا عدّ المجموعات الجزئية في النصفين، فإن
\[ F_{15}(c)=\sum_{s=0}^{15} f_L(s)\,f_R(15-s). \]
ولأن التنفيذ يخزن أيضًا نسخة معكوسة من مصفوفة النصف الأيمن، فإن العملية كلها تصبح ضربًا قياسيًا من 16 حدًا فقط لكل يد كاملة.
لليد المدمجة نكتب
\[ B_L=H(c^{L})-P(c^{L})-R(c^{L}),\qquad B_R=H(c^{R})-P(c^{R})-R(c^{R}). \]
وبما أن نقاط السلاسل الكاملة تختلف عن \(R(c^{L})+R(c^{R})\) بمقدار \(\operatorname{adjust}\) فقط، فإن شرط المسألة يصبح
\[ H(c)-P(c)-R(c)=B_L+B_R-\operatorname{adjust}=2F_{15}(c). \]
إذًا يشكل نصف أيسر مع نصف أيمن يدًا صحيحة إذا وفقط إذا كانت القيمة الأساسية بعد التصحيح مساوية لضعف عدد الخمس عشرة الناتج من الضرب القياسي. وعندما يتحقق ذلك نضيف \(W(c^{L})W(c^{R})\) إلى الجواب. أما المتجه الصفري فيحقق العلاقة بصورة بديهية، ولذلك يُطرح 1 في النهاية لاستبعاد اليد الفارغة.
تنفذ النسخ المكتوبة بـ C++ وPython وJava أولًا جميع أنماط العد الممكنة في كل نصف: عددها \(5^6\) في اليسار و\(5^7\) في اليمين. ولكل حالة نصفية تحسب مجموع القيم، ونقاط الأزواج، ونقاط السلاسل الداخلية، ووزن التعدد، وكثيرة حدود المجاميع الجزئية حتى 15، ثم بيانات الكتلتين الأولى والأخيرة اللازمة للدمج.
تُزاوج كل حالة يسارية مع كل حالة يمينية. يحسب التنفيذ أولًا تصحيحة السلسلة العابرة للحد، ثم يبني القيمة
\[ \text{targetTwice}=B_L+B_R-\operatorname{adjust}. \]
إذا كانت هذه القيمة سالبة، أو فردية، أو أكبر من 340، تُرفض هذه الثنائية مباشرة. الحد 340 يأتي من أكبر مجموع ممكن لقيم البطاقات في متجه كامل. وإذا نجحت هذه التصفية، يُحسب الضرب القياسي ذو الـ 16 حدًا للحصول على \(F_{15}\)، مع إيقاف مبكر إذا تجاوز المجموع الجزئي الهدف المطلوب.
عندما ينجح اختبار المساواة، يضيف الكود حاصل ضرب تعددي النصفين إلى المجموع الكلي. بهذا تُحسب جميع اختيارات الأشكال التي يمثلها المتجه المدمج بدقة. وتُستبعد اليد الفارغة في آخر خطوة. كما تقوم نسختا C++ وJava بتوزيع الحلقة الخارجية على عدة خيوط، بينما يستخدم مدخل Python المسار الرياضي نفسه.
تكلفة تجهيز الحالات النصفية هي \(O(5^6)\) و\(O(5^7)\) ملخصات، وكل ملخص يحتاج فقط إلى برمجة ديناميكية ثابتة الحجم على المجاميع من \(0\) إلى \(15\). أما المرحلة المسيطرة فهي حاصل الضرب الديكارتي لمجموعتي الحالات، ولذلك تكون كلفة الدمج
\[ O(5^6\cdot 5^7\cdot 16)=O(5^{13}). \]
هذا يعني أن الطريقة لا تخفض أسّ فضاء البحث نفسه. مكسبها الحقيقي هو في خفض العوامل الثابتة: معلومات التقييم المكلفة لنصف اليد تُحسب مرة واحدة ثم يعاد استخدامها، بحيث يتحول اختبار اليد الكاملة إلى تصحيحة حدية واحدة وضرب قياسي قصير. أما الذاكرة فتبلغ
\[ O\!\big((5^6+5^7)\cdot 16\big), \]
وذلك بسبب جداول الحالات النصفية المخزنة ومصفوفات المجاميع الجزئية القصيرة التابعة لها.