We have an \(x\times y\times z\) rectangular box filled with \(xyz\) identical dice. Each die may be rotated, and whenever two cells share a face, the two touching labels must be equal. If \(f(x,y,z)\) is the number of possible global arrangements, the examples are \(f(1,1,1)=24\) and \(f(2,3,4)=18432\). The target is \(f(9,10,11)\).
The important observation is that a die orientation is not an arbitrary assignment of six labels. A cube has three pairs of opposite faces. Ignoring the signs within each opposite pair, an orientation first assigns these three opposite-face pairs to the three coordinate directions of the box. Then it chooses which member of each pair faces the positive direction. This separates the count into an unsigned skeleton count and a signed orientation count.
Represent the three opposite-face pairs by \(A,B,C\). At a cell \((i,j,k)\), let \(X(i,j,k)\), \(Y(i,j,k)\), and \(Z(i,j,k)\) be the opposite-face pair used by the faces perpendicular to the \(x\)-, \(y\)-, and \(z\)-axis. In every cell these three values must be a permutation of \(A,B,C\). If two neighboring dice touch across an \(x\)-face, both touching labels belong to the same opposite-face pair, so the \(x\)-pair is constant along each \(x\)-line. Therefore
\[ X(i,j,k)=X_{j,k},\qquad Y(i,j,k)=Y_{i,k},\qquad Z(i,j,k)=Z_{i,j}. \]
The local condition \(\{X_{j,k},Y_{i,k},Z_{i,j}\}=\{A,B,C\}\) has a strong consequence: in any valid unsigned skeleton, at least one box direction carries a globally fixed opposite-face pair. To see why, suppose \(X\) takes two different values in a fixed \(k\)-slice as \(j\) varies. Then \(Y_{i,k}\) is forced to be the third value for every \(i\), and the corresponding \(Z\)-entries are forced as well. Repeating this argument through the rectangular grid propagates the forced pair assignment. If no direction were globally fixed, two such forced propagations would conflict on a rectangle. Thus every skeleton is of one of three types: the \(x\)-direction is globally fixed, or the \(y\)-direction is globally fixed, or the \(z\)-direction is globally fixed.
Count the skeletons of the first type. Choose the fixed opposite-face pair for the \(x\)-direction in \(3\) ways. For each \(x\)-coordinate \(i\), the remaining two pairs can be assigned to the \(y\)- and \(z\)-directions in either order, independently. This gives \(3\cdot 2^x\) skeletons. Similarly the other two types contribute \(3\cdot 2^y\) and \(3\cdot 2^z\).
However, the six completely constant skeletons, one for each global permutation of \(A,B,C\) onto the coordinate axes, have been counted in all three types. They should be counted once, not three times. Hence the unsigned count is
\[ 3\cdot 2^x+3\cdot 2^y+3\cdot 2^z-2\cdot 6 =3(2^x+2^y+2^z-4). \]
Now fix one unsigned skeleton and count the signs. For each line parallel to the \(x\)-axis, choose a sign variable \(a_{j,k}\); for each \(y\)-line choose \(b_{i,k}\); for each \(z\)-line choose \(c_{i,j}\). Moving one step along a coordinate axis flips the sign of that axis because the positive face of one die must equal the negative face of the next. The remaining condition is that the signed permutation at every cell is an actual cube rotation, i.e. it has determinant \(+1\). In sign variables this has the form
\[ a_{j,k}b_{i,k}c_{i,j}=r_{i,j,k}, \]
where \(r_{i,j,k}\in\{\pm1\}\) is already determined by the unsigned skeleton and coordinate parity.
The number of solutions does not depend on the particular right-hand side. In additive notation over \(\mathbb F_2\), the homogeneous system is
\[ a_{j,k}+b_{i,k}+c_{i,j}=0. \]
Every homogeneous solution is
\[ a_{j,k}=u_j+w_k,\qquad b_{i,k}=v_i+w_k,\qquad c_{i,j}=u_j+v_i. \]
The parameters \(u_0,\ldots,u_{y-1}\), \(v_0,\ldots,v_{x-1}\), and \(w_0,\ldots,w_{z-1}\) have one global redundancy, so there are \(x+y+z-1\) independent sign bits. Thus every unsigned skeleton supports exactly
\[ 2^{x+y+z-1} \]
signed arrangements.
Multiplying the two independent factors gives the closed form
\[ f(x,y,z)=3(2^x+2^y+2^z-4)\,2^{x+y+z-1}. \]
The production computation only evaluates this formula. The helper routine that generates orientations constructs the \(24\) rotation-preserving signed permutations of the three axes. The brute-force routine is deliberately kept only for small boxes; it checks the formula against direct search for \(1\times1\times2\), \(1\times2\times2\), \(2\times2\times1\), and \(2\times2\times2\). The two stated examples are also asserted before printing the target value.
After the derivation, the target computation is \(O(1)\) time and \(O(1)\) memory: it performs a few shifts and multiplications. The brute-force validator is exponential and is intentionally restricted to tiny boxes; it is not part of the real target computation.
Ein \(x\times y\times z\)-Quader ist mit \(xyz\) identischen Würfeln gefüllt. Jeder Würfel darf gedreht werden, und zwei aneinanderliegende Flächen müssen denselben Wert zeigen. Für die Anzahl der möglichen Gesamtanordnungen gilt in den Beispielen \(f(1,1,1)=24\) und \(f(2,3,4)=18432\). Gesucht ist \(f(9,10,11)\).
Der entscheidende Punkt ist, dass eine Würfellage keine beliebige Belegung von sechs Flächen ist. Ein Würfel besitzt drei Paare gegenüberliegender Flächen. Ignoriert man zunächst das Vorzeichen innerhalb jedes Paares, ordnet eine Lage diese drei Gegenflächenpaare den drei Raumrichtungen des Kastens zu. Danach wird festgelegt, welche Seite jedes Paares in die positive Richtung zeigt. Dadurch zerfällt die Zählung in eine vorzeichenlose Skelettzählung und eine Vorzeichenzählung.
Bezeichne die drei Gegenflächenpaare mit \(A,B,C\). In der Zelle \((i,j,k)\) seien \(X(i,j,k)\), \(Y(i,j,k)\) und \(Z(i,j,k)\) die Paare, die zu den Flächen senkrecht zur \(x\)-, \(y\)- und \(z\)-Achse gehören. In jeder Zelle sind diese drei Werte eine Permutation von \(A,B,C\). Berühren sich zwei Nachbarwürfel über eine \(x\)-Fläche, dann gehören die berührenden Beschriftungen zum selben Gegenflächenpaar. Daher ist das \(x\)-Paar entlang jeder \(x\)-Geraden konstant:
\[ X(i,j,k)=X_{j,k},\qquad Y(i,j,k)=Y_{i,k},\qquad Z(i,j,k)=Z_{i,j}. \]
Die lokale Bedingung \(\{X_{j,k},Y_{i,k},Z_{i,j}\}=\{A,B,C\}\) erzwingt eine starke globale Struktur: In jedem gültigen vorzeichenlosen Skelett trägt mindestens eine Raumrichtung ein überall festes Gegenflächenpaar. Wenn etwa \(X\) in einer festen \(k\)-Schicht bei verschiedenen \(j\) zwei verschiedene Werte annimmt, muss \(Y_{i,k}\) für jedes \(i\) der dritte Wert sein, und die entsprechenden \(Z\)-Einträge sind ebenfalls festgelegt. Diese Festlegung propagiert durch Rechtecke des Gitters. Gäbe es keine global feste Richtung, würden zwei solche Propagationen auf einem Rechteck widersprüchliche Werte erzwingen.
Zähle nun die Skelette, bei denen die \(x\)-Richtung global fest ist. Das feste Gegenflächenpaar kann in \(3\) Arten gewählt werden. Für jede \(x\)-Koordinate \(i\) können die beiden übrigen Paare in einer von zwei Reihenfolgen auf \(y\)- und \(z\)-Richtung verteilt werden. Das liefert \(3\cdot 2^x\) Skelette. Entsprechend entstehen \(3\cdot 2^y\) und \(3\cdot 2^z\) für die beiden anderen festen Richtungen.
Die sechs vollständig konstanten Skelette, also die globalen Permutationen von \(A,B,C\) auf die drei Koordinatenachsen, wurden jedoch in allen drei Klassen gezählt. Sie sollen einmal statt dreimal zählen. Die vorzeichenlose Anzahl ist daher
\[ 3\cdot 2^x+3\cdot 2^y+3\cdot 2^z-2\cdot 6 =3(2^x+2^y+2^z-4). \]
Nun fixiere ein solches Skelett und zähle die Vorzeichen. Für jede Gerade parallel zur \(x\)-Achse wähle eine Variable \(a_{j,k}\), für jede \(y\)-Gerade eine Variable \(b_{i,k}\), und für jede \(z\)-Gerade eine Variable \(c_{i,j}\). Bei einem Schritt entlang einer Achse wechselt das zugehörige Vorzeichen, weil die positive Fläche des einen Würfels der negativen Fläche des nächsten entsprechen muss. Zusätzlich muss die signierte Permutation in jeder Zelle eine echte Würfelrotation sein, also Determinante \(+1\) haben. Dies ergibt Gleichungen
\[ a_{j,k}b_{i,k}c_{i,j}=r_{i,j,k}, \]
wobei \(r_{i,j,k}\in\{\pm1\}\) durch Skelett und Koordinatenparität festgelegt ist.
Die Zahl der Lösungen hängt nicht von der speziellen rechten Seite ab. Über \(\mathbb F_2\) lautet das homogene System
\[ a_{j,k}+b_{i,k}+c_{i,j}=0. \]
Alle homogenen Lösungen haben die Form
\[ a_{j,k}=u_j+w_k,\qquad b_{i,k}=v_i+w_k,\qquad c_{i,j}=u_j+v_i. \]
Die Parameter \(u_j\), \(v_i\) und \(w_k\) besitzen genau eine globale Redundanz. Somit bleiben \(x+y+z-1\) unabhängige Bits, und jedes Skelett erlaubt genau \(2^{x+y+z-1}\) Vorzeichenbelegungen.
Multiplikation beider Faktoren liefert
\[ f(x,y,z)=3(2^x+2^y+2^z-4)\,2^{x+y+z-1}. \]
Die eigentliche Berechnung wertet nur diese Formel aus. Die Orientierungsroutine erzeugt die \(24\) orientierungserhaltenden signierten Permutationen der drei Achsen. Die direkte Suche wird nur als Test für kleine Kästen benutzt; sie vergleicht die Formel mit \(1\times1\times2\), \(1\times2\times2\), \(2\times2\times1\) und \(2\times2\times2\). Auch die beiden Beispiele aus der Aufgabenstellung werden geprüft.
Für die Zielinstanz ist die Laufzeit \(O(1)\) und der Speicherverbrauch \(O(1)\). Es werden nur einige Zweierpotenzen und Multiplikationen berechnet. Die exponentielle Brute-Force-Suche bleibt auf winzige Kontrollfälle beschränkt.
Bir \(x\times y\times z\) kutu \(xyz\) adet özdeş zarla dolduruluyor. Her zar döndürülebiliyor ve ortak yüzeye sahip iki hücrede, temas eden yüzlerdeki değerler eşit olmak zorunda. Olası düzenleme sayısı \(f(x,y,z)\) olsun. Verilen örnekler \(f(1,1,1)=24\) ve \(f(2,3,4)=18432\). Hedef \(f(9,10,11)\) değeridir.
Temel nokta şudur: Bir zar yönelimi altı yüzün keyfi bir yerleşimi değildir. Küpün üç çift karşıt yüzü vardır. Önce bu üç karşıt-yüz çiftinin kutunun üç koordinat yönüne nasıl atandığını sayarız; sonra her çiftte hangi yüzün pozitif yöne baktığını belirleyen işaretleri sayarız. Böylece problem iki bağımsız parçaya ayrılır: işaretsiz iskelet sayısı ve işaret sayısı.
Üç karşıt-yüz çiftini \(A,B,C\) ile gösterelim. \((i,j,k)\) hücresinde \(x\)-, \(y\)- ve \(z\)-eksenlerine dik yüzlerde kullanılan karşıt-yüz çiftleri sırasıyla \(X(i,j,k)\), \(Y(i,j,k)\), \(Z(i,j,k)\) olsun. Her hücrede bu üç değer \(A,B,C\)'nin bir permütasyonudur. İki zar \(x\)-yönünde temas ettiğinde, ortak yüzlerdeki değer aynı olduğundan \(x\)-yönüne ait karşıt-yüz çifti aynı \(x\)-doğrusu boyunca sabit kalır. Bu yüzden
\[ X(i,j,k)=X_{j,k},\qquad Y(i,j,k)=Y_{i,k},\qquad Z(i,j,k)=Z_{i,j}. \]
Yerel koşul \(\{X_{j,k},Y_{i,k},Z_{i,j}\}=\{A,B,C\}\) güçlü bir sınıflandırma verir: Her geçerli işaretsiz iskelette kutu yönlerinden en az biri tüm kutu boyunca tek bir karşıt-yüz çiftine sabitlenmiştir. Örneğin \(X\), sabit bir \(k\)-katmanında farklı \(j\) değerleri için iki farklı değer alırsa, \(Y_{i,k}\) her \(i\) için üçüncü değere zorlanır; buna bağlı \(Z\)-girdileri de zorlanır. Bu zorlama dikdörtgenler boyunca yayılır. Hiçbir yön global sabit olmasaydı, iki farklı yayılım aynı dikdörtgende çelişen atamalar üretirdi.
\(x\)-yönünün global sabit olduğu iskeletleri sayalım. Sabit karşıt-yüz çifti \(3\) şekilde seçilir. Her \(x\)-koordinatı \(i\) için kalan iki çift, \(y\)- ve \(z\)-yönlerine iki olası sıradan biriyle atanabilir. Bu \(3\cdot 2^x\) iskelet verir. Benzer şekilde \(y\) ve \(z\) yönleri için \(3\cdot 2^y\) ve \(3\cdot 2^z\) gelir.
Fakat tamamen sabit olan altı iskelet, yani \(A,B,C\)'nin koordinat eksenlerine global permütasyonları, üç sınıfın hepsinde sayılmıştır. Bunlar üç kez değil bir kez sayılmalıdır. Dolayısıyla işaretsiz iskelet sayısı
\[ 3\cdot 2^x+3\cdot 2^y+3\cdot 2^z-2\cdot 6 =3(2^x+2^y+2^z-4). \]
Şimdi bir işaretsiz iskeleti sabitleyelim ve işaretleri sayalım. \(x\)-eksenine paralel her doğru için \(a_{j,k}\), \(y\)-doğruları için \(b_{i,k}\), \(z\)-doğruları için \(c_{i,j}\) işaret değişkenleri seçilir. Bir eksen boyunca bir adım ilerlemek, o eksene ait işareti değiştirir; çünkü bir zarın pozitif yüzü, komşu zarın negatif yüzüyle aynı değeri taşımalıdır. Ayrıca her hücredeki işaretli permütasyon gerçek bir küp dönüşü olmalı, yani determinantı \(+1\) olmalıdır. Bu koşul
\[ a_{j,k}b_{i,k}c_{i,j}=r_{i,j,k} \]
biçimindedir; burada \(r_{i,j,k}\in\{\pm1\}\) iskeletten ve koordinat paritesinden belirlenir.
Çözüm sayısı sağ tarafın özel değerine bağlı değildir. \(\mathbb F_2\) üzerinde homojen sistem
\[ a_{j,k}+b_{i,k}+c_{i,j}=0 \]
şeklindedir. Tüm homojen çözümler
\[ a_{j,k}=u_j+w_k,\qquad b_{i,k}=v_i+w_k,\qquad c_{i,j}=u_j+v_i \]
olarak yazılır. \(u_j\), \(v_i\), \(w_k\) parametrelerinde bir global fazlalık vardır; bu yüzden bağımsız işaret biti sayısı \(x+y+z-1\) olur. Her işaretsiz iskelet tam olarak \(2^{x+y+z-1}\) işaretli düzenleme üretir.
İki faktörü çarptığımızda kapalı formül elde edilir:
\[ f(x,y,z)=3(2^x+2^y+2^z-4)\,2^{x+y+z-1}. \]
Asıl çözüm sadece bu formülü hesaplar. Yardımcı yönelim fonksiyonu, üç eksenin determinantı \(+1\) olan \(24\) işaretli permütasyonunu üretir. Brute-force arama yalnızca küçük doğrulama örnekleri içindir; formülü \(1\times1\times2\), \(1\times2\times2\), \(2\times2\times1\), \(2\times2\times2\) kutularında doğrudan sayımla karşılaştırır. Problemde verilen iki örnek de ayrıca assert edilir.
Hedef hesaplama \(O(1)\) zaman ve \(O(1)\) bellek kullanır. Yalnızca birkaç bit kaydırma ve çarpma yapılır. Üstel brute-force doğrulayıcı gerçek çözümün parçası değildir; sadece çok küçük kutularda çalıştırılır.
Una caja \(x\times y\times z\) contiene \(xyz\) dados idénticos. Cada dado puede rotarse, y cada par de caras en contacto debe mostrar el mismo valor. Si \(f(x,y,z)\) cuenta las configuraciones posibles, se dan \(f(1,1,1)=24\) y \(f(2,3,4)=18432\). La instancia objetivo es \(f(9,10,11)\).
Una orientación de un dado no es una asignación arbitraria de seis etiquetas. El cubo tiene tres pares de caras opuestas. Primero se decide qué par de caras opuestas corresponde a cada una de las tres direcciones de la caja; después se decide qué miembro de cada par mira en la dirección positiva. Por eso el conteo se divide en un esqueleto sin signos y un conteo de signos.
Denotemos los tres pares opuestos por \(A,B,C\). En la celda \((i,j,k)\), sean \(X(i,j,k)\), \(Y(i,j,k)\) y \(Z(i,j,k)\) los pares usados por las caras perpendiculares a los ejes \(x,y,z\). En cada celda forman una permutación de \(A,B,C\). Si dos dados se tocan en dirección \(x\), el par asociado a esa dirección es constante a lo largo de esa línea \(x\). Así
\[ X(i,j,k)=X_{j,k},\qquad Y(i,j,k)=Y_{i,k},\qquad Z(i,j,k)=Z_{i,j}. \]
La condición local \(\{X_{j,k},Y_{i,k},Z_{i,j}\}=\{A,B,C\}\) fuerza una estructura global: en todo esqueleto válido, alguna dirección de la caja tiene un par opuesto fijo en toda la caja. Si, por ejemplo, \(X\) toma dos valores distintos dentro de una misma capa \(k\), entonces \(Y_{i,k}\) queda forzado al tercer valor para todo \(i\), y también quedan forzadas las entradas correspondientes de \(Z\). Al propagar esta restricción por rectángulos, la ausencia de una dirección global fija produciría una contradicción.
Contemos los esqueletos donde la dirección \(x\) está fija. El par fijo se elige de \(3\) maneras. Para cada coordenada \(x=i\), los dos pares restantes pueden asignarse a \(y\) y \(z\) en cualquiera de dos órdenes. Esto da \(3\cdot 2^x\). Las otras direcciones aportan \(3\cdot 2^y\) y \(3\cdot 2^z\).
Los seis esqueletos completamente constantes, correspondientes a permutaciones globales de \(A,B,C\) sobre los ejes, se han contado en las tres clases. Deben contarse una sola vez, no tres. Por tanto el número de esqueletos sin signo es
\[ 3\cdot 2^x+3\cdot 2^y+3\cdot 2^z-2\cdot 6 =3(2^x+2^y+2^z-4). \]
Fijado un esqueleto, se cuentan los signos. Para cada línea paralela al eje \(x\) se toma una variable \(a_{j,k}\); para cada línea \(y\), una variable \(b_{i,k}\); para cada línea \(z\), una variable \(c_{i,j}\). Al avanzar una celda por un eje, el signo de ese eje cambia, porque la cara positiva de un dado debe coincidir con la cara negativa del siguiente. Además, la permutación con signos en cada celda debe ser una rotación del cubo, con determinante \(+1\). Esto produce
\[ a_{j,k}b_{i,k}c_{i,j}=r_{i,j,k}. \]
El número de soluciones no depende del lado derecho particular. En notación aditiva sobre \(\mathbb F_2\), el sistema homogéneo es
\[ a_{j,k}+b_{i,k}+c_{i,j}=0. \]
Toda solución homogénea es
\[ a_{j,k}=u_j+w_k,\qquad b_{i,k}=v_i+w_k,\qquad c_{i,j}=u_j+v_i. \]
Los parámetros tienen una redundancia global, de modo que quedan \(x+y+z-1\) bits independientes. Cada esqueleto sin signos admite exactamente \(2^{x+y+z-1}\) elecciones de signos.
La fórmula final es
\[ f(x,y,z)=3(2^x+2^y+2^z-4)\,2^{x+y+z-1}. \]
El cálculo principal solo evalúa esta fórmula. La rutina de orientaciones construye las \(24\) permutaciones con signo que preservan la orientación del cubo. La búsqueda exhaustiva se mantiene solo para verificar cajas pequeñas y se compara con la fórmula en varios casos de control, además de comprobar los dos ejemplos del enunciado.
La instancia objetivo se resuelve en tiempo \(O(1)\) y memoria \(O(1)\). La búsqueda exhaustiva es exponencial, pero solo se ejecuta en cajas diminutas como prueba interna.
一个 \(x\times y\times z\) 的长方体盒子中放入 \(xyz\) 个相同的骰子。每个骰子可以旋转，并且任意两个相邻骰子的接触面必须显示相同数值。记可行摆放数为 \(f(x,y,z)\)。题目给出 \(f(1,1,1)=24\) 和 \(f(2,3,4)=18432\)，要求 \(f(9,10,11)\)。
一个骰子的朝向可以分成两层来理解。立方体有三对相对面。先忽略每一对内部哪一面朝正方向，只看这三对相对面分别分配给盒子的 \(x,y,z\) 三个方向；这称为无符号骨架。然后再决定每一对中哪一面朝正方向；这就是符号选择。
把三对相对面记为 \(A,B,C\)。在格点 \((i,j,k)\) 处，令 \(X(i,j,k)\)、\(Y(i,j,k)\)、\(Z(i,j,k)\) 分别表示垂直于三个坐标轴的面所使用的相对面对。每个格点中它们必须是 \(A,B,C\) 的一个排列。沿 \(x\) 方向相邻的两个骰子接触时，接触的标签相同，因此 \(x\) 方向使用的相对面对沿每条 \(x\)-直线不变：
\[ X(i,j,k)=X_{j,k},\qquad Y(i,j,k)=Y_{i,k},\qquad Z(i,j,k)=Z_{i,j}. \]
局部条件 \(\{X_{j,k},Y_{i,k},Z_{i,j}\}=\{A,B,C\}\) 给出强约束：任意合法的无符号骨架中，至少有一个盒子方向在全局固定为同一对相对面。例如若某个固定 \(k\) 层中 \(X\) 随 \(j\) 取到两个不同值，那么 \(Y_{i,k}\) 对所有 \(i\) 都被迫等于第三个值，相应的 \(Z\) 也被迫确定。把这种强制关系沿矩形传播，若没有任何全局固定方向，就会在某个矩形中产生矛盾。
若 \(x\) 方向全局固定，固定的相对面对有 \(3\) 种选择。对每个 \(x\)-坐标 \(i\)，剩下两对可以按两种顺序分给 \(y\) 和 \(z\) 方向，所以有 \(3\cdot2^x\) 个骨架。同理另外两个方向给出 \(3\cdot2^y\) 和 \(3\cdot2^z\)。
六个完全常数骨架，也就是把 \(A,B,C\) 全局排列到三个坐标轴上的方式，在三类中都被计算了。它们应只计一次，因此无符号骨架数为
\[ 3\cdot 2^x+3\cdot 2^y+3\cdot 2^z-2\cdot 6 =3(2^x+2^y+2^z-4). \]
固定一个骨架后，计算符号数。每条平行于 \(x\) 轴的线有变量 \(a_{j,k}\)，每条 \(y\)-线有 \(b_{i,k}\)，每条 \(z\)-线有 \(c_{i,j}\)。沿某个轴移动一步时，该轴的符号会翻转，因为一个骰子的正向面必须等于下一个骰子的反向面。同时每个格点的带符号排列必须是实际立方体旋转，即行列式为 \(+1\)：
\[ a_{j,k}b_{i,k}c_{i,j}=r_{i,j,k}. \]
解的数量只取决于齐次系统。用 \(\mathbb F_2\) 的加法记号，齐次系统为
\[ a_{j,k}+b_{i,k}+c_{i,j}=0. \]
它的全部解可写成
\[ a_{j,k}=u_j+w_k,\qquad b_{i,k}=v_i+w_k,\qquad c_{i,j}=u_j+v_i. \]
这些参数有一个全局冗余，因此独立位数为 \(x+y+z-1\)。每个无符号骨架支持 \(2^{x+y+z-1}\) 种符号选择。
最终得到闭式公式
\[ f(x,y,z)=3(2^x+2^y+2^z-4)\,2^{x+y+z-1}. \]
主计算只代入这个公式。辅助函数生成 \(24\) 个保持方向的带符号轴排列。暴力搜索只用于很小盒子的校验，并检查题目给出的两个样例。
目标计算是 \(O(1)\) 时间和 \(O(1)\) 空间。暴力搜索是指数级，但只用于小规模断言。
В прямоугольную коробку \(x\times y\times z\) помещены \(xyz\) одинаковых кубиков-игральных костей. Каждый кубик можно повернуть, а любые две соприкасающиеся грани должны иметь одинаковое значение. Пусть \(f(x,y,z)\) обозначает число допустимых расстановок. Даны примеры \(f(1,1,1)=24\) и \(f(2,3,4)=18432\); требуется найти \(f(9,10,11)\).
Ориентация кубика естественно распадается на две части. У куба есть три пары противоположных граней. Сначала считаем, какая пара противоположных граней назначена каждому из трех направлений коробки; это беззнаковый скелет. Затем выбираем, какая грань каждой пары смотрит в положительном направлении; это знаковая часть.
Обозначим пары противоположных граней через \(A,B,C\). В ячейке \((i,j,k)\) пусть \(X(i,j,k)\), \(Y(i,j,k)\), \(Z(i,j,k)\) обозначают пары, соответствующие граням, перпендикулярным осям \(x,y,z\). В каждой ячейке эти три значения образуют перестановку \(A,B,C\). Если два кубика соседствуют вдоль оси \(x\), то пара для направления \(x\) постоянна вдоль всей этой \(x\)-линии. Поэтому
\[ X(i,j,k)=X_{j,k},\qquad Y(i,j,k)=Y_{i,k},\qquad Z(i,j,k)=Z_{i,j}. \]
Локальное условие \(\{X_{j,k},Y_{i,k},Z_{i,j}\}=\{A,B,C\}\) приводит к глобальной классификации: в любом допустимом беззнаковом скелете хотя бы одно направление коробки имеет одну и ту же пару противоположных граней во всех ячейках. Если, например, \(X\) в фиксированном слое \(k\) принимает два разных значения при разных \(j\), то \(Y_{i,k}\) для всех \(i\) вынуждено быть третьим значением, а соответствующие значения \(Z\) также фиксируются. Распространение таких ограничений по прямоугольникам показало бы противоречие, если бы ни одно направление не было глобально фиксированным.
Посчитаем скелеты, где направление \(x\) глобально фиксировано. Фиксированная пара выбирается \(3\) способами. Для каждой координаты \(i\) оставшиеся две пары можно распределить между направлениями \(y\) и \(z\) в одном из двух порядков. Это дает \(3\cdot2^x\) скелетов. Аналогично получаем \(3\cdot2^y\) и \(3\cdot2^z\).
Шесть полностью постоянных скелетов, то есть глобальные перестановки \(A,B,C\) по координатным осям, посчитаны во всех трех классах. Их надо считать один раз, а не три. Поэтому число беззнаковых скелетов равно
\[ 3\cdot 2^x+3\cdot 2^y+3\cdot 2^z-2\cdot 6 =3(2^x+2^y+2^z-4). \]
Теперь зафиксируем скелет и посчитаем знаки. Для каждой линии, параллельной оси \(x\), вводится переменная \(a_{j,k}\); для \(y\)-линий \(b_{i,k}\); для \(z\)-линий \(c_{i,j}\). При переходе на одну клетку вдоль оси соответствующий знак меняется, потому что положительная грань одного кубика совпадает с отрицательной гранью следующего. Кроме того, знаковая перестановка в каждой ячейке должна быть настоящим поворотом куба, то есть иметь определитель \(+1\):
\[ a_{j,k}b_{i,k}c_{i,j}=r_{i,j,k}. \]
Число решений не зависит от конкретной правой части. В аддитивной записи над \(\mathbb F_2\) однородная система имеет вид
\[ a_{j,k}+b_{i,k}+c_{i,j}=0. \]
Все ее решения задаются формулами
\[ a_{j,k}=u_j+w_k,\qquad b_{i,k}=v_i+w_k,\qquad c_{i,j}=u_j+v_i. \]
В параметрах есть одна глобальная избыточность, поэтому независимых битов ровно \(x+y+z-1\). Значит, каждый беззнаковый скелет допускает \(2^{x+y+z-1}\) знаковых расстановок.
Итоговая формула:
\[ f(x,y,z)=3(2^x+2^y+2^z-4)\,2^{x+y+z-1}. \]
Основная часть программы просто вычисляет эту формулу. Вспомогательная функция строит \(24\) ориентации куба как знаковые перестановки осей с определителем \(+1\). Перебор используется только для маленьких контрольных коробок и сравнивается с формулой; также проверяются два примера из условия.
Целевая задача решается за \(O(1)\) времени и \(O(1)\) памяти. Экспоненциальный перебор ограничен только тестовыми размерами.
لدينا صندوق أبعاده \(x\times y\times z\) مملوء بـ \(xyz\) نردا متطابقا. يمكن تدوير كل نرد، ويجب أن تحمل كل وجهين متلامسين القيمة نفسها. إذا كان \(f(x,y,z)\) هو عدد الترتيبات الممكنة، فالمعطيان هما \(f(1,1,1)=24\) و \(f(2,3,4)=18432\). المطلوب هو \(f(9,10,11)\).
اتجاه النرد ينقسم طبيعيا إلى جزأين. للمكعب ثلاثة أزواج من الأوجه المتقابلة. أولا نحدد أي زوج من هذه الأزواج يوافق كل اتجاه من اتجاهات الصندوق الثلاثة؛ وهذا هو الهيكل غير الموقّع. ثم نحدد أي وجه من كل زوج ينظر إلى الاتجاه الموجب؛ وهذا هو جزء الإشارات.
لنرمز إلى أزواج الأوجه المتقابلة بـ \(A,B,C\). في الخلية \((i,j,k)\)، نرمز بـ \(X(i,j,k)\)، \(Y(i,j,k)\)، \(Z(i,j,k)\) إلى الأزواج المستخدمة في الاتجاهات \(x,y,z\). في كل خلية تكون هذه القيم الثلاث تبديلة لـ \(A,B,C\). إذا تلامس نردان في اتجاه \(x\)، فإن الزوج المرتبط بهذا الاتجاه يبقى ثابتا على طول خط \(x\)، ولذلك
\[ X(i,j,k)=X_{j,k},\qquad Y(i,j,k)=Y_{i,k},\qquad Z(i,j,k)=Z_{i,j}. \]
الشرط المحلي \(\{X_{j,k},Y_{i,k},Z_{i,j}\}=\{A,B,C\}\) يفرض بنية عالمية قوية: في كل هيكل غير موقّع صالح يوجد اتجاه واحد على الأقل من اتجاهات الصندوق يحمل زوجا ثابتا في كل الخلايا. فإذا أخذ \(X\) قيمتين مختلفتين داخل طبقة ثابتة \(k\)، فإن \(Y_{i,k}\) يجبر على أن يكون القيمة الثالثة لكل \(i\)، كما تجبر قيم \(Z\) المقابلة. نشر هذا القيد عبر المستطيلات يؤدي إلى تناقض إذا لم يكن هناك أي اتجاه ثابت عالميا.
نعد الهياكل التي يكون فيها اتجاه \(x\) ثابتا عالميا. الزوج الثابت يختار بثلاث طرق. ولكل إحداثي \(x=i\)، يمكن توزيع الزوجين الباقيين على اتجاهي \(y\) و \(z\) بترتيبين ممكنين. إذن العدد هو \(3\cdot2^x\). وبالمثل نحصل على \(3\cdot2^y\) و \(3\cdot2^z\) للاتجاهين الآخرين.
لكن الهياكل الستة الثابتة تماما، وهي تبديلات \(A,B,C\) العالمية على المحاور الثلاثة، عُدت في الأصناف الثلاثة. يجب أن تعد مرة واحدة لا ثلاث مرات. لذلك عدد الهياكل غير الموقعة هو
\[ 3\cdot 2^x+3\cdot 2^y+3\cdot 2^z-2\cdot 6 =3(2^x+2^y+2^z-4). \]
بعد تثبيت الهيكل نعد الإشارات. لكل خط مواز لمحور \(x\) نأخذ متغيرا \(a_{j,k}\)، ولكل خط في اتجاه \(y\) متغيرا \(b_{i,k}\)، ولكل خط في اتجاه \(z\) متغيرا \(c_{i,j}\). عند التحرك خطوة على محور ما تنقلب إشارة ذلك المحور، لأن الوجه الموجب لنرد يجب أن يساوي الوجه السالب للنرد التالي. كذلك يجب أن تكون التبديلة الموقعة في كل خلية دورانا حقيقيا للمكعب، أي ذات محدد \(+1\):
\[ a_{j,k}b_{i,k}c_{i,j}=r_{i,j,k}. \]
عدد الحلول لا يعتمد على الطرف الأيمن المحدد. بالترميز الجمعي فوق \(\mathbb F_2\)، النظام المتجانس هو
\[ a_{j,k}+b_{i,k}+c_{i,j}=0. \]
وكل حل متجانس يكتب بالشكل
\[ a_{j,k}=u_j+w_k,\qquad b_{i,k}=v_i+w_k,\qquad c_{i,j}=u_j+v_i. \]
في هذه المعلمات فائض عالمي واحد، ولذلك يوجد \(x+y+z-1\) بتا مستقلا. كل هيكل غير موقّع يعطي بالضبط \(2^{x+y+z-1}\) ترتيبا موقّعا.
إذن الصيغة المغلقة هي
\[ f(x,y,z)=3(2^x+2^y+2^z-4)\,2^{x+y+z-1}. \]
الحساب الأساسي يقيم هذه الصيغة فقط. الدالة المساعدة تولد \(24\) دورانا للمكعب بوصفها تبديلات موقعة للمحاور ذات محدد \(+1\). أما البحث الكامل فيستخدم فقط للتحقق من صناديق صغيرة، إضافة إلى التحقق من المثالين المعطيين في نص المسألة.
الحساب الهدف يستخدم زمنا \(O(1)\) وذاكرة \(O(1)\). البحث الكامل أسي، لكنه محصور في حالات تحقق صغيرة جدا.