For each \(n\), let \(f(n)\) be the number of \(n\)-card hands from a standard 52-card deck that contain a Badugi: a 4-card selection whose suits are all different and whose ranks are all different. The required quantity is
$$\sum_{n=4}^{13} f(n).$$
The local solutions do not enumerate hands directly. They process the 13 ranks one by one and keep track of which suit subsets can already be realized using cards taken from distinct ranks.
Let the suit universe be \(U=\{\mathrm{S},\mathrm{H},\mathrm{D},\mathrm{C}\}\). For each rank \(r\), define a subset \(T_r\subseteq U\): suit \(b\in U\) belongs to \(T_r\) exactly when the card of rank \(r\) and suit \(b\) is present in the hand.
Because a fixed rank contains exactly one card of each suit, choosing \(T_r\) completely determines the cards of that rank. Therefore each hand corresponds to exactly one sequence \((T_1,\dots,T_{13})\) with \(T_r\subseteq U\), and the hand size is
$$n=\sum_{r=1}^{13} |T_r|.$$
Simply knowing which suits appear in the full hand is not enough: the four witness cards must also come from different ranks. After processing some ranks, define \(\mathcal R\) as the family of suit subsets that can be formed by choosing cards from pairwise distinct processed ranks.
Equivalently, \(M\subseteq U\) belongs to \(\mathcal R\) if we can pick \(|M|\) cards from already processed ranks, no two with the same rank, so that their set of suits is exactly \(M\).
There are only \(2^4=16\) suit subsets, so \(\mathcal R\) itself can be stored as a 16-bit mask. Bit \(j\) is set when the suit subset encoded by \(j\) is reachable. Initially only the empty subset is reachable:
$$\mathcal R_0=\{\varnothing\},\qquad \mathrm{rmask}=1.$$
This compression is sufficient because future ranks only need to know which suit subsets are achievable with distinct ranks; the identities of the earlier ranks never matter again.
Suppose the current rank contributes suit set \(T\subseteq U\). The actual hand may contain all cards in \(T\), so the hand size increases by \(|T|\). However, a Badugi witness may use at most one card from this rank, otherwise two chosen cards would share a rank.
Hence every reachable subset \(M\in\mathcal R\) can either stay unchanged, or be extended by one unused suit \(b\in T\setminus M\):
$$M \longrightarrow M\cup\{b\},\qquad b\in T\setminus M.$$
Therefore the updated reachable family is
$$\mathcal R'=\mathcal R\cup \left\{M\cup\{b\}: M\in\mathcal R,\ b\in T\setminus M\right\}.$$
This is exactly the transition precomputed by build_updates() in C++ and Java, and memoized by get_update(rmask, t) in Python.
Let \(D_r(n,\mathrm{rmask})\) be the number of ways to process the first \(r\) ranks such that the hand currently has \(n\) cards and the reachable-family bitmask is \(\mathrm{rmask}\). The initial condition is
$$D_0(0,1)=1.$$
For every current state and every suit subset \(T\subseteq U\), we add the current count to the next state
$$D_{r+1}\bigl(n+|T|,\mathrm{upd}(\mathrm{rmask},T)\bigr).$$
After all 13 ranks, a hand contains a Badugi exactly when the full suit set \(U\) is reachable. In the bit encoding this is subset \(1111_2=15\), so
$$f(n)=\sum_{\substack{\mathrm{rmask}\\ \text{bit }15\text{ set}}} D_{13}(n,\mathrm{rmask}).$$
For \(n=4\), every Badugi hand must use all four suits and four distinct ranks, so we may choose the ranks and then assign the four suits:
$$f(4)=\binom{13}{4}\cdot 4! = 17160.$$
The C++ implementation checks this value and also verifies
$$f(5)=514800.$$
Running the full DP yields the Project Euler answer
$$\sum_{n=4}^{13} f(n)=862400558448.$$
The C++ and Java programs precompute update[rmask][t] for all \(2^{16}\) reachability masks and all 16 suit masks \(t\). They then run a rolling two-layer DP over hand sizes \(0,\dots,13\). The Python version uses the same state definition, but stores only visited states in dictionaries and memoizes transitions lazily.
The constant kMaxN = 13 matches the problem statement: larger hand sizes are irrelevant to \(\sum_{n=4}^{13} f(n)\), so transitions with \(n+|T| > 13\) are skipped immediately.
The dense DP loops over 13 ranks, 14 hand sizes, \(2^{16}\) reachability masks, and 16 suit masks. Thus the dominant running time is
$$O\!\left(13\cdot 14\cdot 2^{16}\cdot 16\right).$$
Memory usage is two DP layers of size \(14\times 2^{16}\), so
$$O\!\left(14\cdot 2^{16}\right)$$
64-bit counters, plus the precomputed transition table of size \(2^{16}\times 16\). The Python version has the same worst-case state space, but in practice stores only nonzero states.
Für jedes \(n\) sei \(f(n)\) die Anzahl der \(n\)-Karten-Hände aus einem Standarddeck mit 52 Karten, die ein Badugi enthalten: eine Auswahl von 4 Karten mit paarweise verschiedenen Farben und paarweise verschiedenen Rängen. Gesucht ist
$$\sum_{n=4}^{13} f(n).$$
Die lokalen Lösungen enumerieren die Hände nicht direkt, sondern verarbeiten die 13 Ränge nacheinander und merken sich, welche Farb-Teil-mengen sich bereits mit Karten aus verschiedenen Rängen bilden lassen.
Sei \(U=\{\mathrm{S},\mathrm{H},\mathrm{D},\mathrm{C}\}\) die Menge der vier Farben. Für jeden Rang \(r\) definieren wir eine Teilmenge \(T_r\subseteq U\): Eine Farbe \(b\in U\) gehört genau dann zu \(T_r\), wenn die Karte mit Rang \(r\) und Farbe \(b\) in der Hand liegt.
Da ein fester Rang genau eine Karte pro Farbe besitzt, bestimmt \(T_r\) die Wahl in diesem Rang vollständig. Somit entspricht jede Hand genau einer Folge \((T_1,\dots,T_{13})\) mit \(T_r\subseteq U\), und die Handgröße ist
$$n=\sum_{r=1}^{13} |T_r|.$$
Es genügt nicht zu wissen, welche Farben irgendwo in der Hand vorkommen; die vier Zeugen-Karten müssen außerdem aus verschiedenen Rängen stammen. Nach Verarbeitung einiger Ränge sei \(\mathcal R\) die Familie aller Farb-Teil-mengen, die sich durch Wahl von Karten aus paarweise verschiedenen bereits verarbeiteten Rängen bilden lassen.
Anders gesagt: \(M\subseteq U\) liegt genau dann in \(\mathcal R\), wenn man \(|M|\) Karten aus schon verarbeiteten Rängen wählen kann, ohne einen Rang doppelt zu verwenden, sodass die Menge ihrer Farben genau \(M\) ist.
Es gibt nur \(2^4=16\) Farb-Teil-mengen. Daher kann \(\mathcal R\) selbst als 16-Bit-Maske gespeichert werden. Bit \(j\) ist gesetzt, wenn die durch \(j\) kodierte Farbmenge erreichbar ist. Anfangs ist nur die leere Menge erreichbar:
$$\mathcal R_0=\{\varnothing\},\qquad \mathrm{rmask}=1.$$
Diese Kompression reicht aus, weil spätere Übergänge nur davon abhängen, welche Farb-Teil-mengen mit verschiedenen Rängen erreichbar sind; die konkreten früheren Ränge sind danach irrelevant.
Der aktuelle Rang liefere die Farbmenge \(T\subseteq U\). Die Hand selbst darf alle Karten aus \(T\) enthalten, daher wächst die Handgröße um \(|T|\). Für einen Badugi-Zeugen darf man aus diesem Rang aber höchstens eine Karte verwenden, sonst würden zwei gewählte Karten denselben Rang haben.
Jede erreichbare Menge \(M\in\mathcal R\) kann also unverändert bleiben oder durch eine noch nicht benutzte Farbe \(b\in T\setminus M\) erweitert werden:
$$M \longrightarrow M\cup\{b\},\qquad b\in T\setminus M.$$
Damit ergibt sich die neue Erreichbarkeitsfamilie zu
$$\mathcal R'=\mathcal R\cup \left\{M\cup\{b\}: M\in\mathcal R,\ b\in T\setminus M\right\}.$$
Genau diesen Übergang berechnet build_updates() in C++ und Java vor; die Python-Version memoisiert dieselbe Funktion in get_update(rmask, t).
Sei \(D_r(n,\mathrm{rmask})\) die Anzahl der Möglichkeiten, die ersten \(r\) Ränge so zu verarbeiten, dass die Hand aktuell \(n\) Karten besitzt und die Erreichbarkeitsmaske \(\mathrm{rmask}\) ist. Die Initialbedingung lautet
$$D_0(0,1)=1.$$
Für jeden Zustand und jede Farb-Teilmenge \(T\subseteq U\) addieren wir die aktuelle Anzahl zum Folgezustand
$$D_{r+1}\bigl(n+|T|,\mathrm{upd}(\mathrm{rmask},T)\bigr).$$
Nach allen 13 Rängen enthält die Hand genau dann ein Badugi, wenn die volle Farbmenge \(U\) erreichbar ist. In der Bitkodierung ist das die Teilmenge \(1111_2=15\). Also gilt
$$f(n)=\sum_{\substack{\mathrm{rmask}\\ \text{bit }15\text{ set}}} D_{13}(n,\mathrm{rmask}).$$
Für \(n=4\) muss jede Badugi-Hand alle vier Farben und vier verschiedene Ränge verwenden. Man wählt also zuerst die 4 Ränge und ordnet dann die 4 Farben zu:
$$f(4)=\binom{13}{4}\cdot 4! = 17160.$$
Die C++-Implementierung prüft diesen Wert und außerdem
$$f(5)=514800.$$
Das vollständige DP liefert schließlich die Project-Euler-Antwort
$$\sum_{n=4}^{13} f(n)=862400558448.$$
Die C++- und Java-Programme berechnen zunächst update[rmask][t] für alle \(2^{16}\) Erreichbarkeitsmasken und alle 16 Farbmasken \(t\). Danach läuft ein Rolling-DP mit zwei Ebenen über die Handgrößen \(0,\dots,13\). Die Python-Version benutzt dieselbe Zustandsdefinition, speichert aber nur tatsächlich besuchte Zustände in Dictionaries und berechnet Übergänge bei Bedarf.
Die Konstante kMaxN = 13 entspricht exakt der Aufgabenstellung: Größere Handgrößen tragen nicht zu \(\sum_{n=4}^{13} f(n)\) bei, daher werden Übergänge mit \(n+|T| > 13\) sofort verworfen.
Das dichte DP iteriert über 13 Ränge, 14 Handgrößen, \(2^{16}\) Erreichbarkeitsmasken und 16 Farbmasken. Die dominante Laufzeit ist daher
$$O\!\left(13\cdot 14\cdot 2^{16}\cdot 16\right).$$
Der Speicherbedarf besteht aus zwei DP-Schichten der Größe \(14\times 2^{16}\), also
$$O\!\left(14\cdot 2^{16}\right)$$
64-Bit-Zählern, plus der vorberechneten Übergangstabelle der Größe \(2^{16}\times 16\). Die Python-Lösung hat denselben Worst Case, speichert praktisch aber nur Nichtnull-Zustände.
Her \(n\) için \(f(n)\), standart 52 kartlık desteden seçilen \(n\) kartlık eller içinde en az bir Badugi içeren el sayısı olsun. Burada Badugi, türleri farklı ve rankleri farklı olan 4 kartlık bir seçimdir. İstenen toplam
$$\sum_{n=4}^{13} f(n).$$
Yerel çözümler elleri doğrudan tek tek gezmez. Bunun yerine 13 ranki sırayla işler ve şu ana kadar farklı ranklerden seçilerek hangi tür altkümelerinin elde edilebildiğini tutar.
Dört türün kümesi \(U=\{\mathrm{S},\mathrm{H},\mathrm{D},\mathrm{C}\}\) olsun. Her rank \(r\) için \(T_r\subseteq U\) altkümesini tanımlayalım: \(b\in U\) tam ve ancak ranki \(r\), türü \(b\) olan kart eldeyse \(T_r\)'ye girer.
Sabit bir rankte her türden tam bir kart bulunduğu için, \(T_r\) seçimi o rankten gelen kartları tamamen belirler. Dolayısıyla her el, \(T_r\subseteq U\) olan tek bir \((T_1,\dots,T_{13})\) dizisine karşılık gelir ve elin boyutu
$$n=\sum_{r=1}^{13} |T_r|$$
şeklindedir.
Elde dört türün görünmesi tek başına yeterli değildir; bu dört tanık kartın ayrıca farklı ranklerden gelmesi gerekir. Bazı rankler işlendiğinde, \(\mathcal R\) kümesini şu şekilde tanımlayalım: İşlenmiş ranklerden, her rankten en fazla bir kart alarak oluşturulabilen tüm tür altkümeleri.
Başka bir deyişle, \(M\subseteq U\) ancak ve ancak daha önce işlenmiş ranklerden \(|M|\) adet kart seçilebiliyor, hiçbir rank tekrarlanmıyor ve seçilen kartların tür kümesi tam olarak \(M\) oluyorsa \(\mathcal R\)'ye aittir.
Toplam yalnızca \(2^4=16\) tür altkümesi vardır. Bu yüzden \(\mathcal R\) de 16 bitlik bir maske ile saklanabilir. \(j\). bit, \(j\) ile kodlanan tür altkümesi erişilebiliyorsa 1 olur. Başlangıçta sadece boş küme erişilebilirdir:
$$\mathcal R_0=\{\varnothing\},\qquad \mathrm{rmask}=1.$$
Bu sıkıştırma yeterlidir; çünkü sonraki ranklerde önemli olan tek şey, geçmişte tam olarak hangi ranklerin kullanıldığı değil, farklı ranklerle hangi tür altkümelerinin kurulabildiğidir.
Şimdi güncel rankin tür kümesi \(T\subseteq U\) olsun. Elin kendisi \(T\)'deki tüm kartları içerebilir; bu yüzden el boyutu \(|T|\) kadar artar. Fakat bir Badugi tanığında bu rankten en fazla bir kart kullanılabilir; aksi halde iki seçili kart aynı ranke sahip olur.
Bu nedenle her erişilebilir \(M\in\mathcal R\) ya olduğu gibi kalır ya da \(T\setminus M\) içinden henüz kullanılmamış bir tür \(b\) ile genişler:
$$M \longrightarrow M\cup\{b\},\qquad b\in T\setminus M.$$
Dolayısıyla yeni erişilebilir aile
$$\mathcal R'=\mathcal R\cup \left\{M\cup\{b\}: M\in\mathcal R,\ b\in T\setminus M\right\}$$
olur. C++ ve Java'daki build_updates() tam olarak bu dönüşümü önceden hesaplar; Python sürümü ise aynı fonksiyonu get_update(rmask, t) ile memoize eder.
\(D_r(n,\mathrm{rmask})\), ilk \(r\) rank işlendiğinde elde \(n\) kart bulunmasının ve erişilebilir-aile maskesinin \(\mathrm{rmask}\) olmasının kaç farklı yolu olduğunu göstersin. Başlangıç koşulu
$$D_0(0,1)=1$$
şeklindedir.
Her mevcut durum ve her \(T\subseteq U\) için, sayıyı şu sonraki duruma ekleriz:
$$D_{r+1}\bigl(n+|T|,\mathrm{upd}(\mathrm{rmask},T)\bigr).$$
Tüm 13 rank işlendiğinde el ancak ve ancak tam tür kümesi \(U\) erişilebiliyorsa bir Badugi içerir. Bit kodlamasında bu \(1111_2=15\) altkümesine karşılık gelir. Dolayısıyla
$$f(n)=\sum_{\substack{\mathrm{rmask}\\ \text{bit }15\text{ set}}} D_{13}(n,\mathrm{rmask}).$$
\(n=4\) için her Badugi eli dört farklı tür ve dört farklı rank kullanmak zorundadır. Önce 4 rank seçilir, sonra dört tür bu ranklere dağıtılır:
$$f(4)=\binom{13}{4}\cdot 4! = 17160.$$
C++ uygulaması bu değeri ve ayrıca
$$f(5)=514800$$
sonucunu kontrol eder. Tam DP çalıştırıldığında Project Euler cevabı
$$\sum_{n=4}^{13} f(n)=862400558448$$
olarak elde edilir.
C++ ve Java programları önce tüm \(2^{16}\) erişilebilirlik maskeleri ve 16 tür maskesi \(t\) için update[rmask][t] tablosunu hazırlar. Ardından el boyutları \(0,\dots,13\) üzerinde iki katmanlı bir rolling DP çalıştırırlar. Python sürümü aynı durum tanımını kullanır; fakat yalnızca ziyaret edilen durumları sözlüklerde tutar ve geçişleri ihtiyaç anında hesaplar.
kMaxN = 13 sabiti doğrudan sorudan gelir: \(\sum_{n=4}^{13} f(n)\) dışında kalan daha büyük el boyutları ilgisizdir. Bu yüzden \(n+|T| > 13\) olan geçişler hemen atılır.
Yoğun DP, 13 rank, 14 el boyutu, \(2^{16}\) erişilebilirlik maskesi ve 16 tür maskesi üzerinden döner. Bu nedenle baskın çalışma süresi
$$O\!\left(13\cdot 14\cdot 2^{16}\cdot 16\right)$$
olur. Bellek kullanımı, boyutu \(14\times 2^{16}\) olan iki DP katmanı nedeniyle
$$O\!\left(14\cdot 2^{16}\right)$$
64 bit sayaçtır; buna ek olarak \(2^{16}\times 16\) boyutlu önceden hesaplanmış geçiş tablosu bulunur. Python sürümünün en kötü durum uzayı aynıdır, fakat pratikte sadece sıfır olmayan durumları tutar.
Para cada \(n\), sea \(f(n)\) el número de manos de \(n\) cartas de una baraja estándar de 52 cartas que contienen un Badugi: una selección de 4 cartas con palos todos distintos y rangos todos distintos. Debemos calcular
$$\sum_{n=4}^{13} f(n).$$
Las soluciones locales no enumeran las manos directamente. Recorren los 13 rangos uno por uno y recuerdan qué subconjuntos de palos ya pueden realizarse usando cartas tomadas de rangos distintos.
Sea \(U=\{\mathrm{S},\mathrm{H},\mathrm{D},\mathrm{C}\}\) el conjunto de palos. Para cada rango \(r\), definimos un subconjunto \(T_r\subseteq U\): un palo \(b\in U\) pertenece a \(T_r\) si y solo si la carta de rango \(r\) y palo \(b\) está en la mano.
Como un rango fijo contiene exactamente una carta de cada palo, elegir \(T_r\) determina por completo las cartas de ese rango. Así, cada mano corresponde a una única sucesión \((T_1,\dots,T_{13})\) con \(T_r\subseteq U\), y el tamaño de la mano es
$$n=\sum_{r=1}^{13} |T_r|.$$
No basta con saber qué palos aparecen en la mano completa; las cuatro cartas testigo también deben proceder de rangos diferentes. Después de procesar algunos rangos, definimos \(\mathcal R\) como la familia de subconjuntos de palos que pueden formarse eligiendo cartas de rangos procesados, sin repetir rango.
De forma equivalente, \(M\subseteq U\) pertenece a \(\mathcal R\) si podemos escoger \(|M|\) cartas de rangos ya procesados, todas con rangos distintos, de modo que el conjunto de sus palos sea exactamente \(M\).
Solo existen \(2^4=16\) subconjuntos de palos, así que \(\mathcal R\) puede almacenarse como una máscara de 16 bits. El bit \(j\) vale 1 cuando el subconjunto codificado por \(j\) es alcanzable. Al principio solo es alcanzable el subconjunto vacío:
$$\mathcal R_0=\{\varnothing\},\qquad \mathrm{rmask}=1.$$
Esta compresión es suficiente porque los rangos concretos ya usados no vuelven a importar; para los rangos futuros solo importa qué conjuntos de palos son posibles manteniendo rangos distintos.
Supongamos que el rango actual aporta el conjunto de palos \(T\subseteq U\). La mano real puede contener todas las cartas de \(T\), por lo que el tamaño total aumenta en \(|T|\). Sin embargo, un testigo de Badugi puede usar como mucho una carta de este rango; de lo contrario, dos cartas elegidas compartirían rango.
Por tanto, cada conjunto alcanzable \(M\in\mathcal R\) puede permanecer igual o extenderse con un palo no usado \(b\in T\setminus M\):
$$M \longrightarrow M\cup\{b\},\qquad b\in T\setminus M.$$
En consecuencia, la nueva familia alcanzable es
$$\mathcal R'=\mathcal R\cup \left\{M\cup\{b\}: M\in\mathcal R,\ b\in T\setminus M\right\}.$$
Eso es exactamente lo que precalcula build_updates() en C++ y Java, mientras que la versión en Python memoiza la misma transformación mediante get_update(rmask, t).
Sea \(D_r(n,\mathrm{rmask})\) el número de formas de procesar los primeros \(r\) rangos de modo que la mano tenga \(n\) cartas y la máscara de alcanzabilidad sea \(\mathrm{rmask}\). La condición inicial es
$$D_0(0,1)=1.$$
Para cada estado actual y cada subconjunto \(T\subseteq U\), añadimos la cantidad actual al siguiente estado
$$D_{r+1}\bigl(n+|T|,\mathrm{upd}(\mathrm{rmask},T)\bigr).$$
Tras los 13 rangos, una mano contiene un Badugi exactamente cuando el conjunto completo de palos \(U\) es alcanzable. En la codificación por bits eso corresponde al subconjunto \(1111_2=15\), así que
$$f(n)=\sum_{\substack{\mathrm{rmask}\\ \text{bit }15\text{ set}}} D_{13}(n,\mathrm{rmask}).$$
Para \(n=4\), toda mano Badugi debe usar los cuatro palos y cuatro rangos distintos. Podemos elegir los rangos y luego asignar los cuatro palos:
$$f(4)=\binom{13}{4}\cdot 4! = 17160.$$
La implementación en C++ comprueba este valor y también verifica
$$f(5)=514800.$$
Al ejecutar todo el DP se obtiene la respuesta de Project Euler
$$\sum_{n=4}^{13} f(n)=862400558448.$$
Los programas en C++ y Java precalculan update[rmask][t] para las \(2^{16}\) máscaras de alcanzabilidad y las 16 máscaras de palos \(t\). Después ejecutan un DP rodante de dos capas sobre tamaños de mano \(0,\dots,13\). La versión en Python usa la misma definición de estado, pero guarda solo los estados visitados en diccionarios y memoiza las transiciones cuando se necesitan.
La constante kMaxN = 13 coincide exactamente con el enunciado: los tamaños mayores no contribuyen a \(\sum_{n=4}^{13} f(n)\), por lo que cualquier transición con \(n+|T| > 13\) se descarta de inmediato.
El DP denso recorre 13 rangos, 14 tamaños de mano, \(2^{16}\) máscaras de alcanzabilidad y 16 máscaras de palos. Por tanto, el coste dominante es
$$O\!\left(13\cdot 14\cdot 2^{16}\cdot 16\right).$$
La memoria corresponde a dos capas DP de tamaño \(14\times 2^{16}\), es decir,
$$O\!\left(14\cdot 2^{16}\right)$$
contadores de 64 bits, además de la tabla de transiciones precalculada de tamaño \(2^{16}\times 16\). La versión en Python tiene el mismo peor caso teórico, pero en la práctica solo mantiene estados no nulos.
对每个 \(n\)，记 \(f(n)\) 为标准 52 张牌中所有 \(n\) 张手牌里“至少包含一个 Badugi”的数量。这里的 Badugi 指 4 张牌，它们的花色两两不同、点数也两两不同。目标是计算
$$\sum_{n=4}^{13} f(n).$$
本地解法并不直接枚举手牌，而是按 13 个点数逐层处理，并记录“在已处理点数中，使用互不相同的点数时，哪些花色子集已经可以实现”。
设花色全集为 \(U=\{\mathrm{S},\mathrm{H},\mathrm{D},\mathrm{C}\}\)。对每个点数 \(r\)，定义一个子集 \(T_r\subseteq U\)：当且仅当点数为 \(r\)、花色为 \(b\) 的那张牌在手中时，\(b\in T_r\)。
因为固定点数下每种花色恰好只有一张牌，所以一旦确定 \(T_r\)，该点数层的选牌就完全确定。于是每一手牌都唯一对应于一个序列 \((T_1,\dots,T_{13})\)，其中每个 \(T_r\subseteq U\)，并且手牌大小满足
$$n=\sum_{r=1}^{13} |T_r|.$$
仅仅知道整手牌里出现了哪些花色还不够，因为构成 Badugi 的 4 张见证牌还必须来自不同点数。处理完若干点数后，定义 \(\mathcal R\) 为这样一族花色子集：它们可以通过“从已处理点数中选牌，且每个点数至多选一张”得到。
等价地，若 \(M\subseteq U\) 属于 \(\mathcal R\)，就表示我们能从已处理部分中选出 \(|M|\) 张牌，这些牌的点数互不相同，并且它们的花色集合恰好是 \(M\)。
花色子集总共只有 \(2^4=16\) 个，因此 \(\mathcal R\) 本身可以编码成一个 16 位掩码。第 \(j\) 位为 1 表示编号 \(j\) 对应的花色子集可达。初始时只有空集可达：
$$\mathcal R_0=\{\varnothing\},\qquad \mathrm{rmask}=1.$$
这种压缩是充分的，因为在后续转移中，真正重要的不是之前究竟用了哪些点数，而是“保持点数互异时，哪些花色集合目前可实现”。
设当前点数提供的花色集合为 \(T\subseteq U\)。真实手牌可以包含 \(T\) 中的所有牌，因此手牌大小增加 \(|T|\)。但是在 Badugi 见证中，这个点数最多只能贡献一张牌，否则会出现两个选中牌点数相同。
因此，对任意可达集合 \(M\in\mathcal R\)，它要么保持不变，要么用一个尚未使用的花色 \(b\in T\setminus M\) 扩展：
$$M \longrightarrow M\cup\{b\},\qquad b\in T\setminus M.$$
于是更新后的可达族为
$$\mathcal R'=\mathcal R\cup \left\{M\cup\{b\}: M\in\mathcal R,\ b\in T\setminus M\right\}.$$
C++ 和 Java 中的 build_updates() 正是在预计算这个转移；Python 版本则通过 get_update(rmask, t) 按需记忆化相同的函数。
令 \(D_r(n,\mathrm{rmask})\) 表示处理完前 \(r\) 个点数后，当前手牌大小为 \(n\)，且可达集合掩码为 \(\mathrm{rmask}\) 的方案数。初始条件是
$$D_0(0,1)=1.$$
对每个当前状态和每个 \(T\subseteq U\)，都把当前方案数加到下一状态
$$D_{r+1}\bigl(n+|T|,\mathrm{upd}(\mathrm{rmask},T)\bigr).$$
当 13 个点数全部处理完后，若且唯若完整花色集 \(U\) 可达，这手牌才包含 Badugi。在位编码里，这对应子集 \(1111_2=15\)，因此
$$f(n)=\sum_{\substack{\mathrm{rmask}\\ \text{bit }15\text{ set}}} D_{13}(n,\mathrm{rmask}).$$
当 \(n=4\) 时，任何 Badugi 手牌都必须恰好使用四种花色和四个不同点数，所以先选 4 个点数，再把 4 个花色分配给它们：
$$f(4)=\binom{13}{4}\cdot 4! = 17160.$$
C++ 实现会检查这个值，同时还验证
$$f(5)=514800.$$
完整运行 DP 后得到 Project Euler 的答案
$$\sum_{n=4}^{13} f(n)=862400558448.$$
C++ 和 Java 程序先为全部 \(2^{16}\) 个可达掩码以及 16 个花色掩码 \(t\) 预计算 update[rmask][t]。然后它们在手牌大小 \(0,\dots,13\) 上做两层滚动 DP。Python 版本使用完全相同的状态定义，但只在字典里保存实际访问到的状态，并按需记忆化转移。
常量 kMaxN = 13 与题目要求完全一致：因为只需要 \(\sum_{n=4}^{13} f(n)\)，更大的手牌大小没有贡献，所以任何 \(n+|T| > 13\) 的转移都会立刻跳过。
稠密 DP 的主循环遍历 13 个点数、14 个手牌大小、\(2^{16}\) 个可达掩码以及 16 个花色掩码，因此主导时间复杂度为
$$O\!\left(13\cdot 14\cdot 2^{16}\cdot 16\right).$$
内存方面，需要两个大小为 \(14\times 2^{16}\) 的 DP 层，即
$$O\!\left(14\cdot 2^{16}\right)$$
个 64 位计数器，外加一个大小为 \(2^{16}\times 16\) 的预计算转移表。Python 版本的最坏状态空间相同，但实际通常只保存非零状态。
Для каждого \(n\) обозначим через \(f(n)\) число \(n\)-карточных рук из стандартной колоды в 52 карты, содержащих хотя бы один Badugi: набор из 4 карт с попарно различными мастями и попарно различными рангами. Нужно вычислить
$$\sum_{n=4}^{13} f(n).$$
Локальные решения не перебирают руки напрямую. Они проходят 13 рангов по очереди и хранят информацию о том, какие подмножества мастей уже можно реализовать, выбирая карты из разных рангов.
Пусть \(U=\{\mathrm{S},\mathrm{H},\mathrm{D},\mathrm{C}\}\) — множество мастей. Для каждого ранга \(r\) определим подмножество \(T_r\subseteq U\): масть \(b\in U\) входит в \(T_r\) тогда и только тогда, когда карта ранга \(r\) и масти \(b\) присутствует в руке.
Поскольку для фиксированного ранга есть ровно одна карта каждой масти, выбор \(T_r\) полностью определяет вклад этого ранга. Значит, каждая рука однозначно задается последовательностью \((T_1,\dots,T_{13})\) с \(T_r\subseteq U\), а размер руки равен
$$n=\sum_{r=1}^{13} |T_r|.$$
Недостаточно знать, какие масти вообще встречаются в руке: четыре карты-свидетеля должны еще и иметь разные ранги. После обработки части рангов обозначим через \(\mathcal R\) семейство тех подмножеств мастей, которые можно получить, выбирая карты из уже обработанных рангов, не повторяя ранг.
Иначе говоря, \(M\subseteq U\) принадлежит \(\mathcal R\), если можно выбрать \(|M|\) карт из обработанной части так, чтобы их ранги были попарно различны, а множество их мастей было ровно \(M\).
Всего подмножеств мастей \(2^4=16\), поэтому \(\mathcal R\) удобно хранить как 16-битную маску. Бит \(j\) равен 1, если подмножество мастей с кодом \(j\) достижимо. Изначально достижимо только пустое подмножество:
$$\mathcal R_0=\{\varnothing\},\qquad \mathrm{rmask}=1.$$
Такого сжатия достаточно, потому что в дальнейших переходах важны не конкретные прошлые ранги, а только то, какие наборы мастей уже достижимы при условии различных рангов.
Пусть текущий ранг дает множество мастей \(T\subseteq U\). Реальная рука может содержать все карты из \(T\), поэтому размер руки увеличивается на \(|T|\). Но в качестве свидетеля Badugi из этого ранга можно взять не более одной карты, иначе два выбранных свидетеля имели бы одинаковый ранг.
Следовательно, каждое достижимое множество \(M\in\mathcal R\) либо остается как есть, либо расширяется одной еще не использованной мастью \(b\in T\setminus M\):
$$M \longrightarrow M\cup\{b\},\qquad b\in T\setminus M.$$
Поэтому новое семейство достижимых множеств равно
$$\mathcal R'=\mathcal R\cup \left\{M\cup\{b\}: M\in\mathcal R,\ b\in T\setminus M\right\}.$$
Именно этот переход заранее вычисляет build_updates() в C++ и Java, а в Python та же функция лениво кешируется через get_update(rmask, t).
Пусть \(D_r(n,\mathrm{rmask})\) — число способов обработать первые \(r\) рангов так, чтобы в текущей руке было \(n\) карт, а маска достижимости была равна \(\mathrm{rmask}\). Начальное условие:
$$D_0(0,1)=1.$$
Для каждого состояния и каждого \(T\subseteq U\) мы прибавляем текущий счетчик к состоянию
$$D_{r+1}\bigl(n+|T|,\mathrm{upd}(\mathrm{rmask},T)\bigr).$$
После обработки всех 13 рангов рука содержит Badugi тогда и только тогда, когда достижимо полное множество мастей \(U\). В битовой кодировке это подмножество \(1111_2=15\), поэтому
$$f(n)=\sum_{\substack{\mathrm{rmask}\\ \text{bit }15\text{ set}}} D_{13}(n,\mathrm{rmask}).$$
При \(n=4\) любая рука Badugi обязана использовать все четыре масти и четыре различных ранга. Значит, сначала выбираем 4 ранга, затем распределяем по ним 4 масти:
$$f(4)=\binom{13}{4}\cdot 4! = 17160.$$
Это значение проверяется в C++-реализации, так же как и
$$f(5)=514800.$$
Полный запуск DP дает ответ задачи Project Euler:
$$\sum_{n=4}^{13} f(n)=862400558448.$$
Программы на C++ и Java сначала строят таблицу update[rmask][t] для всех \(2^{16}\) масок достижимости и всех 16 мастевых масок \(t\). Затем выполняется двухслойный rolling DP по размерам руки \(0,\dots,13\). Версия на Python использует то же описание состояния, но хранит только реально посещенные состояния в словарях и вычисляет переходы по требованию.
Константа kMaxN = 13 в точности соответствует условию: размеры руки больше 13 не влияют на \(\sum_{n=4}^{13} f(n)\), поэтому переходы с \(n+|T| > 13\) отбрасываются сразу.
Плотная динамика перебирает 13 рангов, 14 размеров руки, \(2^{16}\) масок достижимости и 16 мастевых масок. Значит, основная временная сложность равна
$$O\!\left(13\cdot 14\cdot 2^{16}\cdot 16\right).$$
По памяти нужны два слоя DP размера \(14\times 2^{16}\), то есть
$$O\!\left(14\cdot 2^{16}\right)$$
64-битных счетчиков, плюс заранее построенная таблица переходов размера \(2^{16}\times 16\). У Python та же теоретическая верхняя граница, но на практике хранятся только ненулевые состояния.
لكل \(n\)، لتكن \(f(n)\) عدد الأيدي المكوّنة من \(n\) بطاقة من رزمة قياسية من 52 بطاقة والتي تحتوي على Badugi واحد على الأقل، أي اختيارًا من 4 بطاقات تكون أنواعها كلها مختلفة ورتبها كلها مختلفة. المطلوب حساب
$$\sum_{n=4}^{13} f(n).$$
الحلول المحلية لا تعدّ الأيدي مباشرة. بدلًا من ذلك، تمر على الرتب الثلاث عشرة رتبةً رتبة، وتحتفظ بالمعلومات عن مجموعات الأنواع التي يمكن تحقيقها بالفعل باختيار بطاقات من رتب مختلفة.
لتكن مجموعة الأنواع \(U=\{\mathrm{S},\mathrm{H},\mathrm{D},\mathrm{C}\}\). ولكل رتبة \(r\)، نعرّف مجموعة جزئية \(T_r\subseteq U\): يكون النوع \(b\in U\) ضمن \(T_r\) إذا وفقط إذا كانت البطاقة ذات الرتبة \(r\) والنوع \(b\) موجودة في اليد.
وبما أن كل رتبة ثابتة تحتوي بطاقة واحدة بالضبط من كل نوع، فإن اختيار \(T_r\) يحدد بالكامل ما أخذناه من تلك الرتبة. لذلك كل يد تقابل تسلسلًا وحيدًا \((T_1,\dots,T_{13})\) حيث \(T_r\subseteq U\)، ويكون حجم اليد
$$n=\sum_{r=1}^{13} |T_r|.$$
معرفة الأنواع الموجودة في اليد كلها ليست كافية، لأن البطاقات الأربع الشاهدة يجب أن تأتي أيضًا من رتب مختلفة. بعد معالجة بعض الرتب، نعرّف \(\mathcal R\) بوصفها عائلة مجموعات الأنواع التي يمكن تكوينها باختيار بطاقات من الرتب المعالجة، على ألا نختار أكثر من بطاقة واحدة من أي رتبة.
وبصورة مكافئة، يكون \(M\subseteq U\) عنصرًا في \(\mathcal R\) إذا استطعنا اختيار \(|M|\) بطاقات من الرتب التي عولجت سابقًا بحيث تكون رتبها جميعًا مختلفة، وتكون مجموعة أنواعها بالضبط هي \(M\).
عدد مجموعات الأنواع الممكنة هو فقط \(2^4=16\)، ولذلك يمكن تخزين \(\mathcal R\) نفسها بقناع من 16 بت. تكون البت رقم \(j\) مفعّلة إذا كانت مجموعة الأنواع المرمّزة بالعدد \(j\) قابلة للوصول. في البداية لا تكون قابلة للوصول إلا المجموعة الفارغة:
$$\mathcal R_0=\{\varnothing\},\qquad \mathrm{rmask}=1.$$
هذا الضغط كافٍ لأن الرتب القديمة نفسها لا تعود مهمة في المراحل اللاحقة؛ المهم فقط هو معرفة أي مجموعات أنواع يمكن تحقيقها مع الحفاظ على اختلاف الرتب.
لنفرض أن الرتبة الحالية تعطي مجموعة الأنواع \(T\subseteq U\). يمكن لليد الفعلية أن تحتوي جميع بطاقات \(T\)، ولذلك يزداد حجم اليد بمقدار \(|T|\). لكن شاهد Badugi لا يستطيع أن يستخدم أكثر من بطاقة واحدة من هذه الرتبة، وإلا اشتركت بطاقتان مختارتان في الرتبة نفسها.
لذلك فإن كل مجموعة قابلة للوصول \(M\in\mathcal R\) إما تبقى كما هي، أو تتمدّد بنوع غير مستخدم بعد \(b\in T\setminus M\):
$$M \longrightarrow M\cup\{b\},\qquad b\in T\setminus M.$$
ومن ثم تصبح عائلة الوصول الجديدة
$$\mathcal R'=\mathcal R\cup \left\{M\cup\{b\}: M\in\mathcal R,\ b\in T\setminus M\right\}.$$
وهذا بالضبط ما تقوم الدالة build_updates() بحسابه مسبقًا في C++ وJava، بينما تنفذ نسخة Python الفكرة نفسها مع التخزين المؤقت في get_update(rmask, t).
لنعرّف \(D_r(n,\mathrm{rmask})\) بأنه عدد الطرق لمعالجة أول \(r\) رتب بحيث يصبح في اليد الحالية \(n\) بطاقة وتكون قناع الوصول هو \(\mathrm{rmask}\). شرط البداية هو
$$D_0(0,1)=1.$$
ولكل حالة حالية ولكل \(T\subseteq U\)، نضيف العدد الحالي إلى الحالة التالية
$$D_{r+1}\bigl(n+|T|,\mathrm{upd}(\mathrm{rmask},T)\bigr).$$
بعد معالجة الرتب الثلاث عشرة كلها، تحتوي اليد على Badugi إذا وفقط إذا كانت مجموعة الأنواع الكاملة \(U\) قابلة للوصول. وفي الترميز الثنائي تمثل هذه المجموعة بالقيمة \(1111_2=15\)، ولذلك
$$f(n)=\sum_{\substack{\mathrm{rmask}\\ \text{bit }15\text{ set}}} D_{13}(n,\mathrm{rmask}).$$
عندما \(n=4\)، فإن أي يد Badugi يجب أن تستعمل الأنواع الأربعة كلها وأربع رتب مختلفة. لذا نختار أولًا 4 رتب، ثم نوزع عليها الأنواع الأربعة:
$$f(4)=\binom{13}{4}\cdot 4! = 17160.$$
وتتحقق نسخة C++ من هذه القيمة، وكذلك من
$$f(5)=514800.$$
أما تشغيل DP كاملًا فيعطي جواب Project Euler:
$$\sum_{n=4}^{13} f(n)=862400558448.$$
برنامجا C++ وJava يبنيان أولًا الجدول update[rmask][t] لكل أقنعة الوصول وعددها \(2^{16}\)، ولكل أقنعة الأنواع الستة عشر \(t\). بعد ذلك يشغّلان DP بصفّين متناوبين على أحجام الأيدي \(0,\dots,13\). أما نسخة Python فتستخدم تعريف الحالة نفسه، لكنها تحفظ فقط الحالات التي تمت زيارتها فعلًا داخل قواميس، وتحسب الانتقالات عند الحاجة.
الثابت kMaxN = 13 يطابق نص المسألة مباشرة: الأحجام الأكبر من 13 لا تدخل في \(\sum_{n=4}^{13} f(n)\)، ولذلك تُهمَل فورًا أي نقلة تحقق \(n+|T| > 13\).
يدور DP الكثيف على 13 رتبة، و14 قيمة لحجم اليد، و\(2^{16}\) قناع وصول، و16 قناع أنواع. لذلك يكون الزمن الغالب
$$O\!\left(13\cdot 14\cdot 2^{16}\cdot 16\right).$$
أما الذاكرة فتعادل طبقتين من DP بحجم \(14\times 2^{16}\)، أي
$$O\!\left(14\cdot 2^{16}\right)$$
عدادات 64-بت، بالإضافة إلى جدول الانتقالات المسبق بحجم \(2^{16}\times 16\). نسخة Python لها نفس الحد الأعلى نظريًا، لكنها عمليًا تخزن فقط الحالات غير الصفرية.