997. 骰子方盒计数(Counting Arrangements of Dice in a Box)

在一个 \(x\times y\times z\) 的盒子中排列了 \(xyz\) 个骰子，相邻骰子的相贴面数字相同。所有骰子在旋转下不可区分。令 \(f(x,y,z)\) 为可能的排列方式数目。已知 \(f(1,1,1)=24\)，\(f(2,3,4)=18432\)。求 \(f(9,10,11)\)。

分析：骰子有 24 种朝向。将问题分解为"数对-轴分配"（3 对 \(\{1,6\},\{2,5\},\{3,4\}\) 分配到 \(x,y,z\) 轴）与"符号配置"（每轴的正反面选哪侧）。相邻约束使符号沿轴交替，整体自由度对应网格的"轴链着色"计数，导出闭式公式。

一、数学背景

标准骰子有 6 个面，数字 \(1\sim6\)，对面之和为 \(7\)。三对数字 \(\{1,6\},\{2,5\},\{3,4\}\) 分别分配给 \(x,y,z\) 轴（沿轴的两面取该对的数字）。每个骰子的 24 种朝向 = 6 种轴分配 × 4 种手性正确的符号组合（\(s_x\oplus s_y\oplus s_z=0\)，其中 \(s_x=0\) 表示 \(+x\) 面取该对的小数、\(s_x=1\) 取大数）。

相邻约束： - \(x\) 方向相邻：\(s_x\) 翻转（\(s_x(i+1,j,k)=1-s_x(i,j,k)\)） - \(y\) 方向相邻：\(s_y\) 翻转 - \(z\) 方向相邻：\(s_z\) 翻转

二、轴链着色模型

定义行/列/柱级别的变量： - \(X(j,k)\)：\(x\) 轴链 \((j,k)\) 的颜色（对的三元标号 \(1,2,3\)） - \(Y(i,k)\)：\(y\) 轴链 \((i,k)\) 的颜色 - \(Z(i,j)\)：\(z\) 轴链 \((i,j)\) 的颜色

约束：对每个骰子 \((i,j,k)\)，三色互异：\(\{X(j,k),Y(i,k),Z(i,j)\}=\{1,2,3\}\)。

计数思路：要么某方向全部同色，要么不发生。设 \(A\) 为 \(X\) 全同色的配置，\(B\) 为 \(Y\) 全同色，\(C\) 为 \(Z\) 全同色。容斥原理给出：

故链着色数 \(C(x,y,z)=3(2^x+2^y+2^z)-12\)。

三、符号配置

给定链着色，符号 \(s_x,s_y,s_z\) 需满足手性约束 \(s_x\oplus s_y\oplus s_z=0\) 并沿轴交替。方程 \(s_x\oplus s_y\oplus s_z=0\) 以分离变量参数化后，自由度为 \(2^{x+y+z-1}\)。最终：

验证：\(f(1,1,1)=3\cdot(2+2+2-4)\cdot2^2=3\cdot2\cdot4=24\) ✓ \(f(2,3,4)=3\cdot(4+8+16-4)\cdot2^8=3\cdot24\cdot256=18432\) ✓

四、代码实现与说明

"""
Project Euler Problem 997: Counting Arrangements of Dice in a Box

f(x,y,z) counts arrangements of xyz indistinguishable dice in a x*y*z box
where touching faces have the same value.

Formula: f(x,y,z) = 3 * (2^x + 2^y + 2^z - 4) * 2^(x+y+z-1)
"""


def f(x: int, y: int, z: int) -> int:
    """Return the number of valid dice arrangements in an x*y*z box."""
    return 3 * (2 ** x + 2 ** y + 2 ** z - 4) * (2 ** (x + y + z - 1))


if __name__ == "__main__":
    assert f(1, 1, 1) == 24, f"f(1,1,1)={f(1,1,1)} != 24"
    assert f(2, 3, 4) == 18432, f"f(2,3,4)={f(2,3,4)} != 18432"

    result = f(9, 10, 11)
    print(result)

代码说明：

f

• 参数 \(x,y,z\) 为盒子三维尺寸。返回合法排列数。
• 公式直接计算：
• \(3\)：三种颜色（数对）分配方案的基础因子。
• \((2^x+2^y+2^z-4)\)：链着色数除以 3 的部分。容斥原理的结果。
• \(2^{x+y+z-1}\)：符号配置的自由度。手性约束将总符号空间 \(2^{x+y+z}\) 减半。

主程序

• 断言验证两个给定样例。
• 输出 \(f(9,10,11)\) 的结果。