异或魔方

Question

问题：

在一个 m x n 维的魔幻矩形中，每个条目都是行和列的 XOR，索引为零。示例 (8 x 5)：

0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3

我需要找到每个条目的总和，但是，暴力破解将无法工作，因为输入范围在 10 到数百万之间。

我目前的工作：

我发现，对于 m x n 矩阵，其中 m 或 n 是 2 的幂，您可以将总和计算为 sum_range(0, m-1) * n，其中总和范围实际上只是相加第一个和第二个输入之间的每个数字。

当 m 和 n 都不是 2 的幂时，事情就变得有趣了。

您可以将 m x n 矩形拆分为由 2 的次方 m x n 矩形组成的矩形，如下所示：(15 x 15)

0, 1, 2, 3, 4, 5, 6, 7 | 8, 9, 10, 11 | 12, 13 | 14 | 
1, 0, 3, 2, 5, 4, 7, 6 | 9, 8, 11, 10 | 13, 12 | 15 | 
2, 3, 0, 1, 6, 7, 4, 5 | 10, 11, 8, 9 | 14, 15 | 12 | 
3, 2, 1, 0, 7, 6, 5, 4 | 11, 10, 9, 8 | 15, 14 | 13 | 
4, 5, 6, 7, 0, 1, 2, 3 | 12, 13, 14, 15 | 8, 9 | 10 | 
5, 4, 7, 6, 1, 0, 3, 2 | 13, 12, 15, 14 | 9, 8 | 11 | 
6, 7, 4, 5, 2, 3, 0, 1 | 14, 15, 12, 13 | 10, 11 | 8 | 
7, 6, 5, 4, 3, 2, 1, 0 | 15, 14, 13, 12 | 11, 10 | 9 | 
----------------------------------------------------
8, 9, 10, 11, 12, 13, 14, 15 | 0, 1, 2, 3 | 4, 5 | 6 | 
9, 8, 11, 10, 13, 12, 15, 14 | 1, 0, 3, 2 | 5, 4 | 7 | 
10, 11, 8, 9, 14, 15, 12, 13 | 2, 3, 0, 1 | 6, 7 | 4 | 
11, 10, 9, 8, 15, 14, 13, 12 | 3, 2, 1, 0 | 7, 6 | 5 | 
----------------------------------------------------
12, 13, 14, 15, 8, 9, 10, 11 | 4, 5, 6, 7 | 0, 1 | 2 | 
13, 12, 15, 14, 9, 8, 11, 10 | 5, 4, 7, 6 | 1, 0 | 3 | 
----------------------------------------------------
14, 15, 12, 13, 10, 11, 8, 9 | 6, 7, 4, 5 | 2, 3 | 0 | 
----------------------------------------------------

然后，使用我上面描述的公式，你可以得到沿对角线的每个正方形的总和（我的解释没有意义，所以这里有一张图）： not enough reputation for embeds ._.

我就是这样

我不明白如何在没有暴力破解的情况下根据 m 和 n 获得其他部分的总和。 记住，m 和 n 将是随机整数，它们可能非常非常大

我看到了一些规律，比如魔幻矩形是如何具有某种对称性的，边是数字 0 - (m-1) 的顺序，但是，我没有想出将其转化为代码的逻辑.

如能指出正确方向，我们将不胜感激。不是，但是，寻找代码，因为这是一个代码战争问题，那是作弊

参考问题：https://www.codewars.com/kata/59568be9cc15b57637000054/train/java

Answer 1

我们可以将矩阵划分为四个子指标并反复利用 sum_range(start, m-1) * n。为简单起见，我将使用递归进行解释，您可以使用队列轻松地将其转换为非递归解决方案。

让我们考虑更小的情况，一个 7x7 矩阵。其中，m=7（列），n=7（行）。求和 168.

[0, 1, 2, 3, 4, 5, 6]
[1, 0, 3, 2, 5, 4, 7]
[2, 3, 0, 1, 6, 7, 4]
[3, 2, 1, 0, 7, 6, 5]
[4, 5, 6, 7, 0, 1, 2]
[5, 4, 7, 6, 1, 0, 3]
[6, 7, 4, 5, 2, 3, 0]

我们可以将这个矩阵分为以下4个矩阵：

[0, 1, 2, 3] [4, 5, 6] [4, 5, 6, 7] [0, 1, 2]
[1, 0, 3, 2] [5, 4, 7] [5, 4, 7, 6] [1, 0, 3]
[2, 3, 0, 1] [6, 7, 4] [6, 7, 4, 5] [2, 3, 0]
[3, 2, 1, 0] [7, 6, 5]

这里第一个矩阵的维度等于 2 的最大可能幂，即 4。其余的只是父矩阵的剩余 3 个部分。
我们可以使用公式得到第一个矩阵的总和：rowSum*rows -> (m*(m-1)/2)*n -> (4*3/2)*4 -> 24

接下来我们考虑第二个子矩阵。并使用相同的策略分成 4 个部分：

[4, 5] [6] [6, 7] [4]
[5, 4] [7] [7, 6] [5]

这里，可以使用公式(rowSum - startSum)*rows->((m*(m-1)/2) - (start*(start-1)/2)) * n -> (6*5/2 - 4*3/2)*2 -> 18计算第一个子矩阵。这里，start = 4 xor 0.
从上面的讨论我们可以创建这样的递归函数：

int result = calculate(0,0,m,n);
System.out.println("Total: " + result);

int calculate(int m0, int n0, int m, int n) {
     System.out.print("calculating: (" +m0+","+n0 + ") (" + m +","+n+") ");

     if( (m0,n0) (m,n) is single dimensional array then)
            //use for loops do xor and return sum.

     //get maximum possible power of 2 that can be used to derive first sub matrix
     int pow = (int)(Math.log(m-m0) / Math.log(2));
     pow = (int)Math.pow(2, pow);
      
     //sum = sum(first sub matrix (m0,pow)(n0,pow))

     //sum += calculate(dimensions of second sub matrix)
     //sum += calculate(dimensions of third sub matrix)
     //sum += calculate(dimensions of fourth sub matrix)
    
     return sum;
}

int sum(int start, int m, int n) {
    m=m+start;
    int sum = (m*(m-1)/2);
    sum -= (start*(start-1)/2);
    sum *=n;
    System.out.println("sum="+sum);
    return sum;
}

以上代码应产生如下输出：

calculating: (0,0) (7,7) sum=24
calculating: (4,0) (7,4) sum=18
calculating: (6,0) (7,2) sum=13
calculating: (4,2) (6,4) sum=26
calculating: (6,2) (7,4) sum=9
calculating: (0,4) (4,7) sum=66
calculating: (4,4) (7,7) sum=2
calculating: (6,4) (7,6) sum=5
calculating: (4,6) (6,7) sum=5
calculating: (6,6) (7,7) sum=0
Total: 168

要使递归最少，请确保 m>n。如果不是，则交换值。
注：应作者要求，未提供工作代码。

异或魔方

XOR Magic Rectangle

java

matrix

xor

问题：

我目前的工作：

我就是这样