A die is a multiset of six face values chosen from \(\{1,\dots,N\}\); repeated faces are allowed, and the order of faces on a die is irrelevant. For two dice \(X\) and \(Y\), let \(W_{XY}\) denote the number of ordered face pairs \((x,y)\in X\times Y\) with \(x \gt y\). Since there are \(6\cdot 6=36\) comparisons, the statement “\(X\) beats \(Y\) with probability greater than \(1/2\)” is equivalent to \(W_{XY}\ge 19\). The goal is to count unordered triples \(\{A,B,C\}\) such that \(B\) beats \(A\), \(C\) beats \(B\), and \(A\) beats \(C\).
For every value \(v\in\{1,\dots,N\}\), write \(a_v,b_v,c_v\) for the number of faces equal to \(v\) on the dice \(A,B,C\). Then
$$\sum_{v=1}^{N} a_v=\sum_{v=1}^{N} b_v=\sum_{v=1}^{N} c_v=6,\qquad a_v,b_v,c_v\ge 0.$$
This representation is enough because permuting the six faces of a die does not change any pairwise win counts.
The implementation processes face values in increasing order. After finishing value \(v\), define the used-face counts
$$u_A=\sum_{t\le v} a_t,\qquad u_B=\sum_{t\le v} b_t,\qquad u_C=\sum_{t\le v} c_t.$$
The DP state stores \((u_A,u_B,u_C)\) together with the already determined directed wins \((W_{BA},W_{CB},W_{AC})\). Each win counter is capped at \(19\), because once a counter has reached the threshold, larger values are indistinguishable for the final decision.
Suppose the current layer assigns \(a_v=\alpha\), \(b_v=\beta\), \(c_v=\gamma\). A new face of \(B\) with value \(v\) beats exactly the previously placed faces of \(A\), because those are the faces with strictly smaller values. It does not beat equal-value faces placed in the same layer, and larger values have not been processed yet. Therefore the transition adds
$$\Delta W_{BA}=\beta\,u_A,\qquad \Delta W_{CB}=\gamma\,u_B,\qquad \Delta W_{AC}=\alpha\,u_C.$$
Every winning comparison is counted exactly once: at the moment when the larger of the two face values is inserted.
After updating a state, the code checks a simple optimistic upper bound. If \(B\) still has \(6-u_B\) faces left, then even in the best case those remaining faces can contribute at most \(6(6-u_B)\) further wins against \(A\). Hence a necessary condition is
$$W_{BA}+6(6-u_B)\ge 19.$$
By the same reasoning, the other two conditions are
$$W_{CB}+6(6-u_C)\ge 19,\qquad W_{AC}+6(6-u_A)\ge 19.$$
Any state violating one of these bounds is discarded immediately. On the last value, only states with \(u_A=u_B=u_C=6\) are legal.
The DP counts labeled triples satisfying the fixed cyclic orientation
$$B\to A,\qquad C\to B,\qquad A\to C.$$
Every valid nontransitive set contains three distinct dice, because a die cannot strictly beat itself. For one unordered set, exactly three labelings realize the same oriented cycle: the three cyclic rotations of \((A,B,C)\). The three reversed labelings would require the opposite inequalities and are therefore not counted. Thus
$$\text{unordered answer}=\frac{\text{ordered oriented count}}{3}.$$
The C++, Python, and Java solutions all implement this same DP. The C++ version precomputes the transitions for all \(7^3=343\) prefix-count triples, packs each state into a 32-bit integer key, stores counts in unsigned __int128, and can split large layers across multiple threads. The Python version keeps the identical packed state layout inside a dictionary, while the Java version uses dense long[] arrays plus active-key lists for speed. In all three languages, the DP starts from the empty state, iterates through the values \(1,2,\dots,N\), saturates every win counter at \(19\), and finally reads the terminal state
$$ (u_A,u_B,u_C,W_{BA},W_{CB},W_{AC})=(6,6,6,19,19,19). $$
The C++ implementation also verifies the method with two checkpoints: for \(N=7\) the count is \(9780\), and for \(N=6\) the DP matches a brute-force enumeration over all sorted dice triples.
Because every die has exactly six faces, the compressed state space is bounded by
$$7^3\cdot 20^3=2{,}744{,}000,$$
since each used-face counter has \(7\) possible values and each saturated win counter has \(20\) possible values. The transition list for a fixed prefix triple is also bounded by a constant. Therefore, for this Project Euler problem, the algorithm is linear in \(N\) with a large but fixed constant, while the memory usage is bounded by the reachable state set and does not grow asymptotically with \(N\). In practice the pruning rules remove most states long before the final layer.
Ein Würfel ist hier eine Multimenge aus sechs Augenzahlen aus \(\{1,\dots,N\}\); Wiederholungen sind erlaubt, und die Reihenfolge der Seiten spielt keine Rolle. Für zwei Würfel \(X\) und \(Y\) sei \(W_{XY}\) die Anzahl der geordneten Paare \((x,y)\in X\times Y\) mit \(x \gt y\). Da es \(6\cdot 6=36\) Vergleiche gibt, ist die Aussage „\(X\) schlägt \(Y\) mit Wahrscheinlichkeit größer als \(1/2\)” genau äquivalent zu \(W_{XY}\ge 19\). Gesucht ist die Anzahl ungeordneter Tripel \(\{A,B,C\}\) mit \(B\) schlägt \(A\), \(C\) schlägt \(B\) und \(A\) schlägt \(C\).
Für jeden Wert \(v\in\{1,\dots,N\}\) bezeichnen \(a_v,b_v,c_v\) die Anzahl der Seiten mit Wert \(v\) auf den Würfeln \(A,B,C\). Dann gilt
$$\sum_{v=1}^{N} a_v=\sum_{v=1}^{N} b_v=\sum_{v=1}^{N} c_v=6,\qquad a_v,b_v,c_v\ge 0.$$
Diese Darstellung genügt vollständig, weil das Umordnen der sechs Seiten eines Würfels keine Gewinnanzahl verändert.
Die Implementierung läuft die Augenzahlen aufsteigend durch. Nach Abschluss des Werts \(v\) definieren wir die bereits belegten Seitenzahlen
$$u_A=\sum_{t\le v} a_t,\qquad u_B=\sum_{t\le v} b_t,\qquad u_C=\sum_{t\le v} c_t.$$
Der DP-Zustand speichert \((u_A,u_B,u_C)\) zusammen mit den bereits feststehenden gerichteten Gewinnzahlen \((W_{BA},W_{CB},W_{AC})\). Jeder Gewinnzähler wird bei \(19\) abgeschnitten, denn oberhalb der Schwelle sind alle größeren Werte für die Entscheidung gleichwertig.
Angenommen, in der aktuellen Schicht werden \(a_v=\alpha\), \(b_v=\beta\), \(c_v=\gamma\) gesetzt. Eine neue \(B\)-Seite mit Wert \(v\) schlägt genau die bereits gesetzten Seiten von \(A\), denn diese haben strikt kleinere Werte. Gleich große Seiten aus derselben Schicht führen nur zu Gleichstand, und größere Werte sind noch gar nicht verarbeitet. Daher gilt
$$\Delta W_{BA}=\beta\,u_A,\qquad \Delta W_{CB}=\gamma\,u_B,\qquad \Delta W_{AC}=\alpha\,u_C.$$
Jeder gewinnende Vergleich wird also genau in der Schicht gezählt, in der der größere der beiden Werte eingefügt wird.
Nach jedem Übergang verwendet der Code eine optimistische obere Schranke. Hat \(B\) noch \(6-u_B\) freie Seiten, dann können diese im günstigsten Fall zusammen höchstens \(6(6-u_B)\) weitere Siege gegen \(A\) liefern. Notwendig ist also
$$W_{BA}+6(6-u_B)\ge 19.$$
Entsprechend müssen auch
$$W_{CB}+6(6-u_C)\ge 19,\qquad W_{AC}+6(6-u_A)\ge 19$$
gelten. Zustände, die eine dieser Bedingungen verletzen, werden sofort verworfen. In der letzten Schicht sind nur Zustände mit \(u_A=u_B=u_C=6\) zulässig.
Das DP zählt gelabelte Tripel mit der festen Orientierung
$$B\to A,\qquad C\to B,\qquad A\to C.$$
Jede gültige nichttransitive Menge besteht aus drei verschiedenen Würfeln, denn ein Würfel kann sich nicht selbst strikt schlagen. Für eine ungeordnete Menge liefern genau drei Beschriftungen dieselbe zyklische Orientierung, nämlich die drei zyklischen Rotationen von \((A,B,C)\). Die drei umgekehrten Beschriftungen würden die entgegengesetzten Ungleichungen verlangen und werden daher nicht mitgezählt. Also
$$\text{ungeordnete Antwort}=\frac{\text{geordnete orientierte Anzahl}}{3}.$$
Die Lösungen in C++, Python und Java setzen genau dieses DP um. Die C++-Version berechnet zunächst für alle \(7^3=343\) Präfix-Zustände die möglichen Übergänge vor, packt jeden Zustand in einen 32-Bit-Schlüssel, speichert die Anzahlen in unsigned __int128 und kann große Schichten optional auf mehrere Threads verteilen. Die Python-Version verwendet denselben gepackten Zustandsaufbau in einem Dictionary, während die Java-Version dichte long[]-Arrays mit Listen aktiver Schlüssel benutzt. In allen drei Sprachen startet das Verfahren beim leeren Zustand, iteriert über die Werte \(1,2,\dots,N\), sättigt jeden Gewinnzähler bei \(19\) und liest am Ende den Terminalzustand
$$ (u_A,u_B,u_C,W_{BA},W_{CB},W_{AC})=(6,6,6,19,19,19). $$
Die C++-Implementierung enthält außerdem zwei Korrektheitsprüfungen: Für \(N=7\) ergibt sich \(9780\), und für \(N=6\) stimmt das DP mit einer Brute-Force-Zählung über alle sortierten Würfeltripel überein.
Da jeder Würfel genau sechs Seiten hat, ist der komprimierte Zustandsraum nach oben durch
$$7^3\cdot 20^3=2{,}744{,}000$$
beschränkt: Jeder Zähler für benutzte Seiten hat \(7\) Werte, jeder gesättigte Gewinnzähler \(20\) Werte. Auch die Übergangsmenge für ein festes Präfix-Triple ist konstant beschränkt. Damit ist die Laufzeit für dieses Problem linear in \(N\) mit einem großen, aber festen Konstantenfaktor, und der Speicherverbrauch wird durch die erreichbaren Zustände beschränkt und wächst asymptotisch nicht mit \(N\). In der Praxis reduziert das Pruning die Zahl aktiver Zustände deutlich.
Burada bir zar, \(\{1,\dots,N\}\) kümesinden seçilmiş altı yüz değerinden oluşan bir çoklu kümedir; tekrar eden yüzlere izin vardır ve yüzlerin zar üzerindeki sırası önemli değildir. İki zar \(X\) ve \(Y\) için \(W_{XY}\), \(X\times Y\) içindeki sıralı \((x,y)\) çiftlerinden \(x \gt y\) olanların sayısıdır. Toplam karşılaştırma sayısı \(6\cdot 6=36\) olduğundan, “\(X\), \(Y\)'yi olasılık olarak \(1/2\)'den büyük bir oranla yener” ifadesi tam olarak \(W_{XY}\ge 19\) anlamına gelir. İstenen şey, \(B\) zarının \(A\)'yı, \(C\)'nin \(B\)'yi ve \(A\)'nın \(C\)'yi yendiği sırasız \(\{A,B,C\}\) üçlülerinin sayısıdır.
Her \(v\in\{1,\dots,N\}\) değeri için \(a_v,b_v,c_v\), sırasıyla \(A,B,C\) zarlarında \(v\) değerinin kaç kez geçtiğini göstersin. O zaman
$$\sum_{v=1}^{N} a_v=\sum_{v=1}^{N} b_v=\sum_{v=1}^{N} c_v=6,\qquad a_v,b_v,c_v\ge 0.$$
Bu temsil yeterlidir; çünkü bir zarın altı yüzünü yeniden sıralamak hiçbir kazanma sayısını değiştirmez.
Uygulama yüz değerlerini artan sırada gezer. \(v\) değeri tamamlandıktan sonra kullanılan yüz sayıları
$$u_A=\sum_{t\le v} a_t,\qquad u_B=\sum_{t\le v} b_t,\qquad u_C=\sum_{t\le v} c_t$$
olarak tanımlanır. DP durumu, \((u_A,u_B,u_C)\) ile birlikte o ana kadar kesinleşmiş yönlü kazanma sayaçlarını \((W_{BA},W_{CB},W_{AC})\) tutar. Her kazanma sayacı \(19\)'da doyurulur; çünkü eşik aşıldıktan sonra daha büyük değerler nihai karar açısından farklı bir durum oluşturmaz.
Bir katmanda \(a_v=\alpha\), \(b_v=\beta\), \(c_v=\gamma\) olsun. Değeri \(v\) olan yeni bir \(B\) yüzü, yalnızca daha önce yerleştirilmiş \(A\) yüzlerini yener; çünkü bunların değerleri kesin olarak daha küçüktür. Aynı katmanda eklenen eşit yüzler berabere kalır, daha büyük değerler ise henüz işlenmemiştir. Bu yüzden
$$\Delta W_{BA}=\beta\,u_A,\qquad \Delta W_{CB}=\gamma\,u_B,\qquad \Delta W_{AC}=\alpha\,u_C.$$
Yani her kazanç karşılaştırması tam bir kez, iki yüz arasından büyük olan değer eklendiği anda sayılır.
Her geçişten sonra kod iyimser bir üst sınır uygular. \(B\) zarında hâlâ \(6-u_B\) yüz boşsa, bunlar en iyi durumda bile \(A\)'ya karşı en fazla \(6(6-u_B)\) ek galibiyet getirebilir. Dolayısıyla gerekli koşul
$$W_{BA}+6(6-u_B)\ge 19$$
olur. Aynı düşünceyle
$$W_{CB}+6(6-u_C)\ge 19,\qquad W_{AC}+6(6-u_A)\ge 19$$
koşulları da zorunludur. Bu sınırları sağlayamayan durumlar hemen elenir. Son değerde ise yalnızca \(u_A=u_B=u_C=6\) olan durumlar kabul edilir.
DP, sabit yönlü döngüyü sağlayan etiketli üçlüleri sayar:
$$B\to A,\qquad C\to B,\qquad A\to C.$$
Her geçerli nontransitive kümede üç farklı zar bulunmak zorundadır; çünkü bir zar kendisini sıkı anlamda yenemez. Tek bir sırasız küme için aynı yönelimi veren tam üç etiketleme vardır: \((A,B,C)\)'nin üç döngüsel dönüşü. Ters yöndeki üç etiketleme ise karşıt eşitsizlikleri gerektirir ve sayılmaz. Bu nedenle
$$\text{sırasız cevap}=\frac{\text{sıralı yönlü sayı}}{3}.$$
C++, Python ve Java çözümleri aynı DP'yi uygular. C++ sürümü önce \(7^3=343\) önek-yüz sayımı durumu için tüm geçişleri önceden üretir, her durumu 32 bitlik bir anahtara paketler, sayıları unsigned __int128 ile tutar ve büyük katmanlarda çok iş parçacıklı çalışabilir. Python sürümü aynı paketli durum yapısını bir sözlükte saklar. Java sürümü ise hız için yoğun long[] dizileri ve aktif anahtar listeleri kullanır. Üç dilde de DP boş durumdan başlar, \(1,2,\dots,N\) değerlerini sırayla işler, her kazanma sayacını \(19\)'da doyurur ve sonunda
$$ (u_A,u_B,u_C,W_{BA},W_{CB},W_{AC})=(6,6,6,19,19,19) $$
terminal durumunun sayısını okuyup \(3\)'e böler. C++ uygulaması ayrıca iki doğrulama içerir: \(N=7\) için sonuç \(9780\)'dır; \(N=6\) için de DP sonucu, tüm sıralı olmayan zar üçlüleri üzerinde yapılan kaba kuvvet sayımıyla aynıdır.
Her zarın tam altı yüzü olduğu için sıkıştırılmış durum uzayı
$$7^3\cdot 20^3=2{,}744{,}000$$
ile üstten sınırlıdır; çünkü kullanılan yüz sayacı başına \(7\), doyurulmuş kazanma sayacı başına \(20\) olası değer vardır. Sabit bir önek üçlüsü için geçiş sayısı da sabit bir üst sınıra sahiptir. Dolayısıyla bu Project Euler problemi için algoritma, \(N\)'ye göre büyük fakat sabit bir katsayıyla doğrusal çalışır; bellek kullanımı ise erişilebilen durumlarla sınırlıdır ve asimptotik olarak \(N\) ile büyümez. Pratikte budama kuralları aktif durumların çoğunu çok erken yok eder.
Aquí un dado es un multiconjunto de seis valores tomados de \(\{1,\dots,N\}\); se permiten repeticiones y el orden de las caras no importa. Para dos dados \(X\) y \(Y\), sea \(W_{XY}\) el número de pares ordenados \((x,y)\in X\times Y\) con \(x \gt y\). Como hay \(6\cdot 6=36\) comparaciones, la condición “\(X\) vence a \(Y\) con probabilidad mayor que \(1/2\)” equivale exactamente a \(W_{XY}\ge 19\). Debemos contar los tríos no ordenados \(\{A,B,C\}\) tales que \(B\) vence a \(A\), \(C\) vence a \(B\) y \(A\) vence a \(C\).
Para cada valor \(v\in\{1,\dots,N\}\), definimos \(a_v,b_v,c_v\) como el número de caras iguales a \(v\) en \(A,B,C\). Entonces
$$\sum_{v=1}^{N} a_v=\sum_{v=1}^{N} b_v=\sum_{v=1}^{N} c_v=6,\qquad a_v,b_v,c_v\ge 0.$$
Esta codificación es suficiente porque permutar las seis caras de un dado no altera ningún conteo de victorias.
La implementación procesa los valores en orden creciente. Después de terminar el valor \(v\), definimos los conteos de caras ya usadas
$$u_A=\sum_{t\le v} a_t,\qquad u_B=\sum_{t\le v} b_t,\qquad u_C=\sum_{t\le v} c_t.$$
El estado del DP guarda \((u_A,u_B,u_C)\) junto con las victorias dirigidas ya determinadas \((W_{BA},W_{CB},W_{AC})\). Cada contador de victorias se satura en \(19\), porque cualquier valor superior produce exactamente el mismo efecto lógico al final.
Supongamos que en la capa actual se añaden \(a_v=\alpha\), \(b_v=\beta\), \(c_v=\gamma\). Una nueva cara de \(B\) con valor \(v\) vence exactamente a las caras de \(A\) colocadas antes, ya que esas caras tienen valores estrictamente menores. Las caras iguales añadidas en la misma capa solo producen empates, y los valores mayores todavía no se han procesado. Por tanto,
$$\Delta W_{BA}=\beta\,u_A,\qquad \Delta W_{CB}=\gamma\,u_B,\qquad \Delta W_{AC}=\alpha\,u_C.$$
Cada comparación ganadora se cuenta una sola vez: cuando se inserta la cara con el valor mayor.
Después de cada transición, el programa aplica una cota superior optimista. Si a \(B\) le quedan \(6-u_B\) caras por colocar, entonces incluso en el mejor caso esas caras solo pueden aportar \(6(6-u_B)\) victorias futuras contra \(A\). Por eso es necesario que
$$W_{BA}+6(6-u_B)\ge 19.$$
Del mismo modo, también deben cumplirse
$$W_{CB}+6(6-u_C)\ge 19,\qquad W_{AC}+6(6-u_A)\ge 19.$$
Todo estado que viole alguna de estas desigualdades se descarta de inmediato. En la última capa solo son válidos los estados con \(u_A=u_B=u_C=6\).
El DP cuenta tríos etiquetados con la orientación fija
$$B\to A,\qquad C\to B,\qquad A\to C.$$
Cada conjunto no transitivo válido contiene tres dados distintos, porque un dado no puede vencerse estrictamente a sí mismo. Para un mismo conjunto no ordenado, hay exactamente tres etiquetados que producen la misma orientación cíclica: las tres rotaciones de \((A,B,C)\). Las tres etiquetaciones invertidas exigirían las desigualdades opuestas y no se cuentan. Luego
$$\text{respuesta no ordenada}=\frac{\text{conteo ordenado orientado}}{3}.$$
Las versiones en C++, Python y Java implementan exactamente este DP. La versión en C++ precalcula las transiciones para los \(7^3=343\) triples posibles de conteos prefijo, empaqueta cada estado en una clave entera de 32 bits, almacena los conteos en unsigned __int128 y puede paralelizar las capas grandes. La versión en Python usa la misma codificación empaquetada dentro de un diccionario. La versión en Java emplea arreglos densos long[] y listas de claves activas para ganar velocidad. En los tres casos, el proceso parte del estado vacío, recorre los valores \(1,2,\dots,N\), satura cada contador de victorias en \(19\) y al final lee el estado terminal
$$ (u_A,u_B,u_C,W_{BA},W_{CB},W_{AC})=(6,6,6,19,19,19). $$
Además, la implementación en C++ incorpora dos verificaciones: para \(N=7\) el resultado es \(9780\), y para \(N=6\) el DP coincide con una enumeración por fuerza bruta sobre todos los tríos de dados ordenados canónicamente.
Como cada dado tiene exactamente seis caras, el espacio de estados comprimido está acotado por
$$7^3\cdot 20^3=2{,}744{,}000,$$
porque cada contador de caras usadas tiene \(7\) posibilidades y cada contador de victorias saturado tiene \(20\) posibilidades. El conjunto de transiciones para un triple prefijo fijo también está acotado por una constante. Por ello, para este problema la complejidad temporal es lineal en \(N\) con una constante grande pero fija, y la memoria queda limitada por los estados alcanzables, sin crecer asintóticamente con \(N\). En la práctica, la poda elimina la mayor parte de los estados mucho antes de llegar al valor final.
这里的一个骰子可以看成从 \(\{1,\dots,N\}\) 中取出的六个面值所形成的多重集；允许重复，骰子内部的面顺序并不重要。对于两个骰子 \(X\) 和 \(Y\)，记 \(W_{XY}\) 为所有有序面值对 \((x,y)\in X\times Y\) 中满足 \(x \gt y\) 的个数。由于总比较次数是 \(6\cdot 6=36\)，所以“\(X\) 以大于 \(1/2\) 的概率击败 \(Y\)”与 \(W_{XY}\ge 19\) 完全等价。题目要求统计所有无序三元组 \(\{A,B,C\}\)，使得 \(B\) 胜 \(A\)、\(C\) 胜 \(B\)、并且 \(A\) 胜 \(C\)。
对每个取值 \(v\in\{1,\dots,N\}\)，令 \(a_v,b_v,c_v\) 分别表示该值在 \(A,B,C\) 中出现的次数。于是有
$$\sum_{v=1}^{N} a_v=\sum_{v=1}^{N} b_v=\sum_{v=1}^{N} c_v=6,\qquad a_v,b_v,c_v\ge 0.$$
这种表示已经足够，因为同一个骰子内部重新排列六个面，不会改变任何胜负计数。
实现中按照面值递增处理。完成值 \(v\) 之后，定义已经放置的面数
$$u_A=\sum_{t\le v} a_t,\qquad u_B=\sum_{t\le v} b_t,\qquad u_C=\sum_{t\le v} c_t.$$
DP 状态记录 \((u_A,u_B,u_C)\) 和已经确定的三个方向胜场 \((W_{BA},W_{CB},W_{AC})\)。每个胜场计数都截断在 \(19\)，因为一旦达到阈值，更大的数值在最终判定中没有区别。
设当前层加入了 \(a_v=\alpha\)、\(b_v=\beta\)、\(c_v=\gamma\)。一个新加入且面值为 \(v\) 的 \(B\) 面，只会击败已经放入的 \(A\) 面，因为那些面的值严格更小。同层加入的相等值只会打平，而更大的值尚未处理。因此有
$$\Delta W_{BA}=\beta\,u_A,\qquad \Delta W_{CB}=\gamma\,u_B,\qquad \Delta W_{AC}=\alpha\,u_C.$$
也就是说，每一对真正产生胜负的比较，都会在其中较大值被放入时恰好统计一次。
每次转移之后，程序都会检查一个乐观上界。若 \(B\) 还剩 \(6-u_B\) 个面没有放置，那么即使在最理想情况下，这些面未来最多也只能再给 \(W_{BA}\) 贡献 \(6(6-u_B)\) 场胜利。因此必须满足
$$W_{BA}+6(6-u_B)\ge 19.$$
同理还必须满足
$$W_{CB}+6(6-u_C)\ge 19,\qquad W_{AC}+6(6-u_A)\ge 19.$$
任何违反这些不等式的状态都会立刻被丢弃。在最后一个数值层，只有 \(u_A=u_B=u_C=6\) 的状态才是合法终态。
DP 实际统计的是满足固定方向
$$B\to A,\qquad C\to B,\qquad A\to C$$
的带标签三元组。任何有效的非传递集合都包含三个不同的骰子，因为一个骰子不可能严格胜过自己。对同一个无序集合而言，恰好有三种标号会产生相同的循环方向，也就是 \((A,B,C)\) 的三种循环轮换；反方向的三种标号要求相反的不等式，因此不会被本 DP 计入。所以
$$\text{无序答案}=\frac{\text{有序定向计数}}{3}.$$
C++、Python 和 Java 三个版本都实现了同一个 DP。C++ 版本先为全部 \(7^3=343\) 个前缀面数三元组预计算转移，把状态打包成 32 位整数键，用 unsigned __int128 保存计数，并在状态很多时支持多线程。Python 版本沿用同样的打包方式，只是把状态存在字典里。Java 版本则使用稠密的 long[] 数组和活动键列表来提高速度。三个版本都会从空状态开始，依次处理 \(1,2,\dots,N\)，把三个胜场计数都截断到 \(19\)，最后读取终态
$$ (u_A,u_B,u_C,W_{BA},W_{CB},W_{AC})=(6,6,6,19,19,19). $$
C++ 代码还加入了两个校验点：当 \(N=7\) 时结果为 \(9780\)；当 \(N=6\) 时，DP 结果与对所有规范排序骰子三元组的暴力枚举完全一致。
由于每个骰子固定只有六个面，压缩后的状态总数上界为
$$7^3\cdot 20^3=2{,}744{,}000,$$
因为三个已用面数计数器各有 \(7\) 种取值，三个截断后的胜场计数器各有 \(20\) 种取值。对任意固定的前缀三元组，其可选转移数量也被常数限制。因此对本题来说，时间复杂度相对于 \(N\) 是线性的，只是常数较大；内存则由可达状态数控制，不会随 \(N\) 渐近增长。实际运行中，剪枝会在很早的阶段删除大多数状态。
Здесь каждый кубик рассматривается как мультимножество из шести значений из \(\{1,\dots,N\}\); повторения разрешены, а порядок граней несущественен. Для двух кубиков \(X\) и \(Y\) обозначим через \(W_{XY}\) число упорядоченных пар \((x,y)\in X\times Y\), для которых \(x \gt y\). Так как всего имеется \(6\cdot 6=36\) сравнений, условие «\(X\) побеждает \(Y\) с вероятностью больше \(1/2\)» в точности равносильно неравенству \(W_{XY}\ge 19\). Нужно посчитать неупорядоченные тройки \(\{A,B,C\}\), где \(B\) побеждает \(A\), \(C\) побеждает \(B\), а \(A\) побеждает \(C\).
Для каждого значения \(v\in\{1,\dots,N\}\) пусть \(a_v,b_v,c_v\) обозначают, сколько граней со значением \(v\) имеют кубики \(A,B,C\). Тогда
$$\sum_{v=1}^{N} a_v=\sum_{v=1}^{N} b_v=\sum_{v=1}^{N} c_v=6,\qquad a_v,b_v,c_v\ge 0.$$
Этого описания достаточно, потому что любая перестановка граней внутри одного кубика не меняет число выигрышных сравнений.
В реализации значения обрабатываются по возрастанию. После завершения слоя \(v\) определим числа уже размещённых граней:
$$u_A=\sum_{t\le v} a_t,\qquad u_B=\sum_{t\le v} b_t,\qquad u_C=\sum_{t\le v} c_t.$$
Состояние DP хранит \((u_A,u_B,u_C)\) и уже определившиеся направленные выигрыши \((W_{BA},W_{CB},W_{AC})\). Каждый счётчик выигрышей насыщается на уровне \(19\), потому что любое значение выше порога эквивалентно для финального условия.
Пусть на текущем слое добавляется \(a_v=\alpha\), \(b_v=\beta\), \(c_v=\gamma\). Новая грань кубика \(B\) со значением \(v\) побеждает ровно те грани кубика \(A\), которые уже были размещены раньше, так как у них строго меньшее значение. Грани того же значения, добавленные в том же слое, дают только ничьи, а большие значения ещё не обработаны. Поэтому
$$\Delta W_{BA}=\beta\,u_A,\qquad \Delta W_{CB}=\gamma\,u_B,\qquad \Delta W_{AC}=\alpha\,u_C.$$
Каждое выигрышное сравнение учитывается ровно один раз: в тот момент, когда вставляется большая из двух граней.
После каждого перехода программа использует оптимистичную верхнюю оценку. Если у \(B\) осталось \(6-u_B\) неразмещённых граней, то даже в лучшем случае они могут дать не более \(6(6-u_B)\) будущих побед над \(A\). Следовательно, необходимо условие
$$W_{BA}+6(6-u_B)\ge 19.$$
Точно так же обязаны выполняться
$$W_{CB}+6(6-u_C)\ge 19,\qquad W_{AC}+6(6-u_A)\ge 19.$$
Любое состояние, нарушающее хотя бы одно из этих неравенств, немедленно удаляется. На последнем слое допустимы только состояния с \(u_A=u_B=u_C=6\).
DP считает размеченные тройки с фиксированной ориентацией
$$B\to A,\qquad C\to B,\qquad A\to C.$$
Каждый корректный нетранзитивный набор содержит три различных кубика, поскольку кубик не может строго победить сам себя. Для одного неупорядоченного набора ровно три разметки дают ту же циклическую ориентацию: это три циклических сдвига \((A,B,C)\). Три обратные разметки потребовали бы противоположных неравенств и поэтому не учитываются. Значит,
$$\text{неупорядоченный ответ}=\frac{\text{упорядоченный ориентированный счёт}}{3}.$$
Версии на C++, Python и Java реализуют один и тот же DP. В C++ заранее строятся переходы для всех \(7^3=343\) троек префиксных счётчиков, каждое состояние упаковывается в 32-битный ключ, количества хранятся в unsigned __int128, а большие слои могут обрабатываться несколькими потоками. Версия на Python использует ту же упаковку состояния внутри словаря. Версия на Java применяет плотные массивы long[] и списки активных ключей для ускорения. Во всех трёх языках алгоритм стартует из пустого состояния, проходит значения \(1,2,\dots,N\), насыщает каждый счётчик побед на уровне \(19\), а в конце читает терминальное состояние
$$ (u_A,u_B,u_C,W_{BA},W_{CB},W_{AC})=(6,6,6,19,19,19). $$
Кроме того, C++-реализация содержит две проверки корректности: для \(N=7\) получается \(9780\), а для \(N=6\) DP совпадает с полным перебором всех канонически отсортированных троек кубиков.
Поскольку у каждого кубика ровно шесть граней, число сжатых состояний сверху ограничено выражением
$$7^3\cdot 20^3=2{,}744{,}000,$$
так как каждый счётчик использованных граней имеет \(7\) возможных значений, а каждый насыщенный счётчик побед имеет \(20\) значений. Множество переходов для фиксированной префиксной тройки тоже ограничено константой. Поэтому для этой задачи время работы линейно по \(N\) с большим, но фиксированным коэффициентом, а память определяется множеством достижимых состояний и асимптотически не растёт вместе с \(N\). На практике отсечение резко уменьшает число активных состояний задолго до последнего слоя.
في هذه المسألة يُمثَّل كل نرد على أنه متعدد مجموعة من ست قيم مأخوذة من \(\{1,\dots,N\}\)؛ يسمح بتكرار القيم، ولا يهم ترتيب الأوجه داخل النرد. ولأي نردين \(X\) و\(Y\)، نرمز بـ \(W_{XY}\) إلى عدد الأزواج المرتبة \((x,y)\in X\times Y\) التي تحقق \(x \gt y\). وبما أن عدد المقارنات الكلي هو \(6\cdot 6=36\)، فإن عبارة «\(X\) يهزم \(Y\) باحتمال أكبر من \(1/2\)» تكافئ تمامًا الشرط \(W_{XY}\ge 19\). المطلوب هو عدّ الثلاثيات غير المرتبة \(\{A,B,C\}\) التي فيها \(B\) يهزم \(A\)، و\(C\) يهزم \(B\)، و\(A\) يهزم \(C\).
لكل قيمة \(v\in\{1,\dots,N\}\)، لتكن \(a_v,b_v,c_v\) هي أعداد الأوجه ذات القيمة \(v\) في النرود \(A,B,C\) على الترتيب. عندئذٍ
$$\sum_{v=1}^{N} a_v=\sum_{v=1}^{N} b_v=\sum_{v=1}^{N} c_v=6,\qquad a_v,b_v,c_v\ge 0.$$
هذا التمثيل كافٍ بالكامل، لأن إعادة ترتيب الأوجه الستة داخل النرد لا تغيّر أي عدد من أعداد الانتصارات الثنائية.
التنفيذ يعالج القيم بترتيب تصاعدي. بعد الانتهاء من القيمة \(v\)، نعرّف أعداد الأوجه التي استُخدمت حتى تلك اللحظة كما يلي:
$$u_A=\sum_{t\le v} a_t,\qquad u_B=\sum_{t\le v} b_t,\qquad u_C=\sum_{t\le v} c_t.$$
حالة البرمجة الديناميكية تخزّن \((u_A,u_B,u_C)\) مع أعداد الانتصارات الموجَّهة التي حُسمت بالفعل \((W_{BA},W_{CB},W_{AC})\). وكل عدّاد انتصارات يُشبَع عند \(19\)، لأن أي قيمة أعلى من العتبة تعطي المعنى المنطقي نفسه في النهاية.
لنفترض أن الطبقة الحالية تضيف \(a_v=\alpha\)، و\(b_v=\beta\)، و\(c_v=\gamma\). الوجه الجديد من \(B\) ذي القيمة \(v\) يهزم بالضبط الأوجه الموضوعة سابقًا في \(A\)، لأن قيمها أصغر قطعًا. أما الأوجه المضافة في الطبقة نفسها وبالقيمة نفسها فتعطي تعادلات فقط، والقيم الأكبر لم تُعالج بعد. لذلك نحصل على
$$\Delta W_{BA}=\beta\,u_A,\qquad \Delta W_{CB}=\gamma\,u_B,\qquad \Delta W_{AC}=\alpha\,u_C.$$
وبذلك تُحتسب كل مقارنة رابحة مرة واحدة فقط: عند إدراج الوجه ذي القيمة الأكبر من الوجهين.
بعد كل انتقال يطبّق البرنامج حدًا أعلى متفائلًا. إذا بقي في \(B\) عدد \(6-u_B\) من الأوجه غير الموضوعة، فإن هذه الأوجه لا تستطيع حتى في أفضل الأحوال أن تضيف أكثر من \(6(6-u_B)\) انتصارًا مستقبليًا على \(A\). ومن ثم فشرط لازم هو
$$W_{BA}+6(6-u_B)\ge 19.$$
وبالمنطق نفسه يجب أيضًا أن يتحقق
$$W_{CB}+6(6-u_C)\ge 19,\qquad W_{AC}+6(6-u_A)\ge 19.$$
كل حالة تخالف أحد هذه القيود تُحذف فورًا. وفي الطبقة الأخيرة لا يُسمح إلا بالحالات التي تحقق \(u_A=u_B=u_C=6\).
تحسب البرمجة الديناميكية الثلاثيات الموسومة التي تحقق الاتجاه الدوري الثابت
$$B\to A,\qquad C\to B,\qquad A\to C.$$
كل مجموعة لا-انتقالية صحيحة تحتوي بالضرورة على ثلاثة نرود مختلفة، لأن النرد لا يمكن أن يهزم نفسه هزيمة صارمة. وبالنسبة إلى مجموعة غير مرتبة واحدة، فهناك بالضبط ثلاث تسميات تعطي هذا الاتجاه الدوري نفسه، وهي الدورانات الدورية الثلاث لـ \((A,B,C)\). أما التسميات الثلاث المعكوسة فتتطلب المتباينات العكسية، ولذلك لا تدخل في العد. إذا رمزنا إلى العدّ الموجَّه بـ \(O\) وإلى الجواب غير المرتب بـ \(U\)، فإن
$$U=\frac{O}{3}.$$
الإصدارات المكتوبة بـ C++ وPython وJava تنفّذ البرمجة الديناميكية نفسها. إصدار C++ يسبق فيبني الانتقالات لكل \(7^3=343\) ثلاثية ممكنة من أعداد الأوجه السابقة، ويضغط كل حالة في مفتاح صحيح من 32 بت، ويخزن الأعداد باستخدام unsigned __int128، كما يستطيع توزيع الطبقات الكبيرة على عدة خيوط. إصدار Python يستخدم تخطيط الضغط نفسه داخل قاموس. أما إصدار Java فيعتمد على مصفوفات كثيفة من النوع long[] مع قوائم للمفاتيح النشطة لزيادة السرعة. وفي اللغات الثلاث جميعًا تبدأ العملية من الحالة الفارغة، ثم تمر على القيم \(1,2,\dots,N\)، مع تشبيع عدّادات الانتصارات عند \(19\)، ثم تقرأ في النهاية الحالة الطرفية
$$ (u_A,u_B,u_C,W_{BA},W_{CB},W_{AC})=(6,6,6,19,19,19). $$
كما أن تنفيذ C++ يضيف اختبارين للتحقق: عندما \(N=7\) تكون النتيجة \(9780\)، وعندما \(N=6\) يطابق خرج البرمجة الديناميكية العدّ الكامل لكل ثلاثيات النرود المرتبة ترتيبًا معياريًا.
بما أن كل نرد يملك ستة أوجه بالضبط، فإن فضاء الحالات المضغوط محدود من الأعلى بـ
$$7^3\cdot 20^3=2{,}744{,}000,$$
لأن كل عدّاد لعدد الأوجه المستخدمة يملك \(7\) قيم ممكنة، وكل عدّاد انتصارات بعد التشبيع يملك \(20\) قيمة. كما أن عدد الانتقالات الممكنة لثلاثية بادئة ثابتة يبقى محدودًا بثابت. لذلك يكون الزمن بالنسبة إلى \(N\) خطيًا في هذه المسألة مع ثابت كبير لكنه ثابت، بينما الذاكرة يحدّها عدد الحالات القابلة للوصول ولا تنمو نموًا تقاربيًا مع \(N\). عمليًا، تؤدي قواعد التقليم إلى إزالة معظم الحالات قبل الوصول إلى القيمة الأخيرة بزمن طويل.