---

Problem 212

---

Combined Volume of Cuboids

An axis-aligned cuboid, specified by parameters { (x₀,y₀,z₀), (dx,dy,dz) }, consists of all points (X,Y,Z) such that x₀ ≤ X ≤ x₀+dx, y₀ ≤ Y ≤ y₀+dy and z₀ ≤ Z ≤ z₀+dz. The volume of the cuboid is the product, dx × dy × dz. The combined volume of a collection of cuboids is the volume of their union and will be less than the sum of the individual volumes if any cuboids overlap.

Let C₁,…,C₅₀₀₀₀ be a collection of 50000 axis-aligned cuboids such that C_n has parameters

x₀ = S_6n-5 modulo 10000
y₀ = S_6n-4 modulo 10000
z₀ = S_6n-3 modulo 10000
dx = 1 + (S_6n-2 modulo 399)
dy = 1 + (S_6n-1 modulo 399)
dz = 1 + (S_6n modulo 399)

where S₁,…,S₃₀₀₀₀₀ come from the “Lagged Fibonacci Generator”:

For 1 ≤ k ≤ 55, S_k = [100003 - 200003k + 300007k³]   (modulo 1000000)
For 56 ≤ k, S_k = [S_k-24 + S_k-55]   (modulo 1000000)

Thus, C₁ has parameters {(7,53,183),(94,369,56)}, C₂ has parameters {(2383,3563,5079),(42,212,344)}, and so on.

The combined volume of the first 100 cuboids, C₁,…,C₁₀₀, is 723581599.

What is the combined volume of all 50000 cuboids, C₁,…,C₅₀₀₀₀ ?

---

立方体组合体积

一个与轴平行的立方体可以用参数{ (x₀,y₀,z₀), (dx,dy,dz) }表示，包含所有满足x₀ ≤ X ≤ x₀+dx、y₀ ≤ Y ≤ y₀+dy和z₀ ≤ Z ≤ z₀+dz的点(X,Y,Z)。该立方体的体积为乘积dx × dy × dz。一系列立方体的组合体积是它们的并的体积；如果其中有立方体相交，这些立方体的组合体积将会比各自体积之和要来得小。

记C₁、……、C₅₀₀₀₀是一系列共50000个与轴平行的立方体，其中C_n的参数为

x₀ = S_6n-5 modulo 10000
y₀ = S_6n-4 modulo 10000
z₀ = S_6n-3 modulo 10000
dx = 1 + (S_6n-2 modulo 399)
dy = 1 + (S_6n-1 modulo 399)
dz = 1 + (S_6n modulo 399)

这里的S₁、……、S₃₀₀₀₀₀来自如下的“延迟斐波那契生成器”：

对于1 ≤ k ≤ 55，S_k = [100003 - 200003k + 300007k³]   (modulo 1000000)
对于56 ≤ k，S_k = [S_k-24 + S_k-55]   (modulo 1000000)

因此，C₁的参数为{(7,53,183),(94,369,56)}，C₂的参数为{(2383,3563,5079),(42,212,344)}，依此类推。

前100个立方体C₁、……、C₁₀₀的组合体积是723581599。

全部50000个立方体C₁、……、C₅₀₀₀₀的组合体积是多少？

---