212 : 結合直方体の体積

座標軸に平行な直方体 (axis-aligned cuboid) は $\{(x_{0}, y_{0}, z_{0}), (dx, dy, dz)\}$ で与えられ, $x_{0} \leq \textnormal{X} \leq x_{0} + dx, y_{0} \leq \textnormal{Y} \leq y_{0} + dy, z_{0} \leq \textnormal{Z} \leq z_{0} + dz$, を満たす点で構成される. 直方体の体積は $dx \times dy \times dz$で求められる. 複数の直方体を結合したものの体積を考えた場合, 直方体に重なりがあれば, 結合直方体の体積は それぞれの直方体の体積の和より小さくなる.

$C_{1}, \dots, C_{50000}$ を以下のパラメータで与えられる座標軸に平行な直方体とする.

$$\begin{aligned} &x_{0} = S_{6n-5}\ \text{modulo}\ 10000 \\ &y_{0} = S_{6n-4}\ \text{modulo}\ 10000 \\ &z_{0} = S_{6n-3}\ \text{modulo}\ 10000 \\ &dx = 1 + (S_{6n-2}\ \text{modulo}\ 399) \\ &dy = 1 + (S_{6n-1}\ \text{modulo}\ 399) \\ &dz = 1 + (S_{6n}\ \text{modulo}\ 399) \end{aligned}$$

$S_{1},\dots,S_{300000}$ はラグ付きフィボナッチ法により生成される.

$$\begin{aligned} &1 \leq k \leq 55\ の場合, S_{k} = [100003 - 200003k + 300007k^{3}]\ (\text{modulo}\ 1000000) \\ &56 \leq k\ の場合, S_{k} = [S_{k-24} + S_{k-55}]\ (\text{modulo}\ 1000000) \end{aligned}$$

したがって, $C_{1}$ は $\{(7, 53, 183), (94, 369, 56)\}$, $C_{2}$ は $\{(2383, 3563, 5079), (42, 212, 344)\}$ となる

$C_{1}, \dots, C_{100}$ の結合直方体の体積は $723581599$ である.

$C_{1}, \dots, C_{50000}$ の結合直方体の体積を求めよ.