1

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

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

如果我们知道一个索引，[i][j] {i+j = x}那么我们只需使用约束来[i++][j--]创建对角线，并且总是在 to 的范围内例如 在二维矩阵 A[6][6] 中，值 A[3][4] (x = 7)，对角线可以通过以下方式创建：[i--][j++]ij0m.

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 存在。请帮我找到解决方案

4

2 回答 2

1

对于 2D：对角线以下元素的计数是三角形数。

对于 3D：对角线平面以下元素的计数是四面体数

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

对于nD：n-单纯形（我不知道确切的英文术语）数字（是第一个（n-1）-单纯形数字的总和）。

Kth n-simplexial 的值为

 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 n (s) 有一个重要的性质：s 的 k 次方系数是从 n 个和数组成 k 的方法数。所以第n个到第k个系数的总和给了我们第k个对角线以下元素的计数

于 2012-09-24T12:53:37.980 回答
0

对于二维矩阵，您将问题转换为另一个问题，即count the elements below the diagonal including the diagonal.

尝试将其可视化为 3-d 矩阵。在 3 维矩阵的情况下，问题将简化为另一个问题，即count the elements below the diagonal plane including the diagonal

于 2012-09-24T12:35:13.967 回答