题目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₃₀₀₀₀₀ 由“缓慢型 Fibonacci 生成器” 生成：

对于 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₅₀₀₀₀ 的联合体积为多少？