使用按位异或运算符直接计算递归中的元素
Directly compute element in recursion using bitwise XOR operator
让我们有一个矩阵 M X N 矩阵 A[i][j] 部分给出如：（从行=0列=0开始）：
1) 对于所有 1<=i<=N A[0][i]=0
2) 对于所有 0<=j<=M A[j][0]=1
矩阵构造A[i][j]进一步为：
对于所有 1<=i<=N 和 1<=j<=M, A[i][j] =A[i-1][j]^A[i][j-1]，其中^表示按位异或运算。
如果我想得到一些值 A[i][j]，我怎样才能直接得到它（而不实际计算所有 1...j-1 和 1.. 的 A[i][j] .i-1)?有模式吗？鉴于 M 和 N 太大。
让我们绘制出矩阵 A 的前 16 行和前 16 列：
1000000000000000
1111111111111111
1010101010101010
1100110011001100
1000100010001000
1111000011110000
1010000010100000
1100000011000000
1000000010000000
1111111100000000
1010101000000000
1100110000000000
1000100000000000
1111000000000000
1010000000000000
1100000000000000
你的问题 "is there a pattern" 的答案很清楚 "Yes!" 左上角的 8x8 子矩阵被直接复制到它自己的下方，也直接复制到右边，除了右边的副本有一个0 在它的左上角而不是 1。右下角的 8x8 子矩阵全是 0，除了它在左上角有一个 1。如果我们只研究前 8 行和前 8 列，就会出现完全相同的模式：
10000000
11111111
10101010
11001100
10001000
11110000
10100000
11000000
左上角的 4x4 子矩阵被直接复制到它自己的下方，也直接复制到右边，除了右边的副本在其左上角有一个 0 而不是 1。右下角的 4x4 子矩阵是全是 0，除了左上角有一个 1。
这种递归自相似性使得矩阵 A 成为分形，与 Sierpinski triangle.
非常相似
递归自相似性还使我们能够使用 i 和 j 的二进制表示轻松计算 A[i][j]。令 B 为 i 或 j 的二进制表示中的最高位集合。然后下面的程序将return A[i][j]的正确值：
- 对于 b = B 到 0：
- 如果 j=0 限制为位 0 到 b，则 return 1（我们在第一列，全是 1）
- 否则如果 i=0 限制为位 0 到 b，则 return 0（我们在第一行）
- 否则如果 i 和 j 都在位 b 中存储了 1，则 return 0 除非每个中的所有剩余位均为 0，在这种情况下 return 1
- else继续（我们递归到一个更小的子矩阵）
该算法运行时间复杂度为 O(log(max(i,j)))，比原始方法的 O(ij) 运行时间快得多。
让我们通过几个例子来看看这个算法的实际应用：
A[9][9] = 0 来自上面的矩阵。在二进制表示中，i = 1001 和 j = 1001。两者的最高有效位均为 1，并且在该位之后设置了一些位，因此根据上述规则我们 return 0.
A[9][3] = 1 来自上面的矩阵。在二进制表示中，i = 1001 和 j = 0011。在最左边（最高有效位），i 有一个 1，j 有一个 0。因此我们继续下一位（递归），其中都有一个 0。我们再次继续下一位，其中 i 有一个 0，j 有一个 1。因此我们继续到最后一位。两者都有一个 1 并且所有后续位都是 0（这是平凡的，因为没有后续位），所以我们 return 1.
A[9][4] = 1 来自上面的矩阵。在二进制表示中，i = 1001 和 j = 0100。在最左边（最高有效位），i 有一个 1，j 有一个 0。因此我们继续下一位（递归），其中 i 有一个 0，j 有a 1。我们再次进行下一位，其中都有一个 0。j 在这个位和所有后续位中都有一个 0，所以我们 return 1.
该算法的一个有趣含义是每一行 k（对于 k > 0）都有一个周期为 2^B 的重复模式，其中 B 是行号二进制表示的最高有效位。例如，第 3 行（二进制表示 11）重复 1100，而第 9 行（二进制表示 1001）重复 1111111100000000。这意味着第 k > 0 行的完整重复系列可以在 O(k) 存储中表示，并且可以在 O(k) 中计算(k log k) 时间，分别计算 A[k,j] for j = 0, 1, ..., 2^ceiling(log_2 k)-1.
让我们有一个矩阵 M X N 矩阵 A[i][j] 部分给出如：（从行=0列=0开始）：
1) 对于所有 1<=i<=N A[0][i]=0
2) 对于所有 0<=j<=M A[j][0]=1
矩阵构造A[i][j]进一步为：
对于所有 1<=i<=N 和 1<=j<=M, A[i][j] =A[i-1][j]^A[i][j-1]，其中^表示按位异或运算。
如果我想得到一些值 A[i][j]，我怎样才能直接得到它（而不实际计算所有 1...j-1 和 1.. 的 A[i][j] .i-1)?有模式吗？鉴于 M 和 N 太大。
让我们绘制出矩阵 A 的前 16 行和前 16 列：
1000000000000000
1111111111111111
1010101010101010
1100110011001100
1000100010001000
1111000011110000
1010000010100000
1100000011000000
1000000010000000
1111111100000000
1010101000000000
1100110000000000
1000100000000000
1111000000000000
1010000000000000
1100000000000000
你的问题 "is there a pattern" 的答案很清楚 "Yes!" 左上角的 8x8 子矩阵被直接复制到它自己的下方，也直接复制到右边，除了右边的副本有一个0 在它的左上角而不是 1。右下角的 8x8 子矩阵全是 0，除了它在左上角有一个 1。如果我们只研究前 8 行和前 8 列，就会出现完全相同的模式：
10000000
11111111
10101010
11001100
10001000
11110000
10100000
11000000
左上角的 4x4 子矩阵被直接复制到它自己的下方，也直接复制到右边，除了右边的副本在其左上角有一个 0 而不是 1。右下角的 4x4 子矩阵是全是 0，除了左上角有一个 1。
这种递归自相似性使得矩阵 A 成为分形，与 Sierpinski triangle.
非常相似递归自相似性还使我们能够使用 i 和 j 的二进制表示轻松计算 A[i][j]。令 B 为 i 或 j 的二进制表示中的最高位集合。然后下面的程序将return A[i][j]的正确值：
- 对于 b = B 到 0：
- 如果 j=0 限制为位 0 到 b，则 return 1（我们在第一列，全是 1）
- 否则如果 i=0 限制为位 0 到 b，则 return 0（我们在第一行）
- 否则如果 i 和 j 都在位 b 中存储了 1，则 return 0 除非每个中的所有剩余位均为 0，在这种情况下 return 1
- else继续（我们递归到一个更小的子矩阵）
该算法运行时间复杂度为 O(log(max(i,j)))，比原始方法的 O(ij) 运行时间快得多。
让我们通过几个例子来看看这个算法的实际应用：
A[9][9] = 0 来自上面的矩阵。在二进制表示中，i = 1001 和 j = 1001。两者的最高有效位均为 1，并且在该位之后设置了一些位，因此根据上述规则我们 return 0.
A[9][3] = 1 来自上面的矩阵。在二进制表示中，i = 1001 和 j = 0011。在最左边（最高有效位），i 有一个 1，j 有一个 0。因此我们继续下一位（递归），其中都有一个 0。我们再次继续下一位，其中 i 有一个 0，j 有一个 1。因此我们继续到最后一位。两者都有一个 1 并且所有后续位都是 0（这是平凡的，因为没有后续位），所以我们 return 1.
A[9][4] = 1 来自上面的矩阵。在二进制表示中，i = 1001 和 j = 0100。在最左边（最高有效位），i 有一个 1，j 有一个 0。因此我们继续下一位（递归），其中 i 有一个 0，j 有a 1。我们再次进行下一位，其中都有一个 0。j 在这个位和所有后续位中都有一个 0，所以我们 return 1.
该算法的一个有趣含义是每一行 k（对于 k > 0）都有一个周期为 2^B 的重复模式，其中 B 是行号二进制表示的最高有效位。例如，第 3 行（二进制表示 11）重复 1100，而第 9 行（二进制表示 1001）重复 1111111100000000。这意味着第 k > 0 行的完整重复系列可以在 O(k) 存储中表示，并且可以在 O(k) 中计算(k log k) 时间，分别计算 A[k,j] for j = 0, 1, ..., 2^ceiling(log_2 k)-1.