algorithm - 在 N 维矩阵中找到大于 x 的值，其中 x 是索引之和

Question

我们给定一个 [m][m][m] 阶的 N 维矩阵...n 次，其中值位置包含其索引的值和。例如在 6x6 矩阵中 A , 位置 A[3][4] 处的值将是 7。

我们必须找出大于 x 的元素的总数。对于二维矩阵，我们有以下方法:

如果我们知道一个索引说[i][j] {i+j = x}然后我们通过做 [i++][j--] 创建对角线的 [i--][j++]约束 i和 j始终在 0 范围内至 m.例如，在值 A[3][4] (x = 7) 的二维矩阵 A[6][6] 中，可以通过以下方式创建对角线:

A[1][6] -> A[2][5] -> A[3][4] -> A[4][3] -> A[5][2] -> A[6][2]

这里我们将我们的问题转化为另一个问题，即计算包括对角线在内的对角线以下的元素。我们可以轻松算入 O(m)复杂性而不是花费 O(m^2)其中 2是矩阵的顺序。但是如果我们考虑 N 维矩阵，我们将如何做，因为在 N 维矩阵中如果我们知道那个位置的索引，其中索引总和为 x说 A[i1][i2][i3][i4]....[in]次。然后可能有多个满足该条件的对角线，比如做 i1--我们可以增加 {i2, i3, i4....in} 中的任何一个

因此，上面使用的二维矩阵方法在这里变得无用......因为只有两个变量 i1 和 i2 存在。请帮我找到解决方案

Answer 1

对于 2D:对角线以下元素的数量是 triangular number .

对于 3D:对角线平面以下的元素数是 tetrahedral number

请注意，第 K 个四面体数是前 K 个三角形数的和。

对于 nD:n-simplexial(我不知道确切的英文术语)数(是前 (n-1)-simplexial 数的总和)。

第k个n-单纯形的值为

 S(k, n) = k * (k+1) * (k+2).. (k + n - 1) / n! = BinomialCoefficient(k+n-1, n)

编辑:此方法“按原样”适用于主反对角(超)平面以下的有限 X 值。

生成函数的方法:让我们有多项式

A(s)=1+s+s^2+s^3+..+s^m

那就是n次方
B(s) = Aⁿ(s) 有一个重要的性质:s 的 k 次方系数是 n 个被加数组成 k 的方法数。因此，第 n 个到第 k 个系数的总和给出了第 k 个对角线以下元素的计数