def strassen(a, b):
    n = len(a)
    if n == 0 or len(b) != n:
        raise ValueError("需要两个同阶非空方阵")
    if any(len(row) != n for row in a) or any(len(row) != n for row in b):
        raise ValueError("需要两个同阶非空方阵")

    def add(x, y, sign=1):
        # sign为-1时计算x-y
        return [[x[i][j] + sign * y[i][j] for j in range(len(x))]
                for i in range(len(x))]

    def split(x):
        half = len(x) // 2
        return (
            [row[:half] for row in x[:half]],
            [row[half:] for row in x[:half]],
            [row[:half] for row in x[half:]],
            [row[half:] for row in x[half:]],
        )

    def multiply(x, y):
        if len(x) == 1:
            return [[x[0][0] * y[0][0]]]
        a11, a12, a21, a22 = split(x)
        b11, b12, b21, b22 = split(y)
        m1 = multiply(add(a11, a22), add(b11, b22))
        m2 = multiply(add(a21, a22), b11)
        m3 = multiply(a11, add(b12, b22, -1))
        m4 = multiply(a22, add(b21, b11, -1))
        m5 = multiply(add(a11, a12), b22)
        m6 = multiply(add(a21, a11, -1), add(b11, b12))
        m7 = multiply(add(a12, a22, -1), add(b21, b22))

        c11 = add(add(add(m1, m4), m5, -1), m7)
        c12 = add(m3, m5)
        c21 = add(m2, m4)
        c22 = add(add(add(m1, m2, -1), m3), m6)
        half = len(x) // 2
        return ([c11[i] + c12[i] for i in range(half)]
                + [c21[i] + c22[i] for i in range(half)])

    size = 1
    while size < n:
        size *= 2
    padded_a = [[0] * size for _ in range(size)]
    padded_b = [[0] * size for _ in range(size)]
    for i in range(n):
        padded_a[i][:n] = a[i][:]
        padded_b[i][:n] = b[i][:]
    result = multiply(padded_a, padded_b)
    return [row[:n] for row in result[:n]]


print(strassen([[1, 2], [3, 4]], [[5, 6], [7, 8]]))
print(strassen([[1, 2, 3], [4, 5, 6], [7, 8, 9]],
               [[1, 0, 0], [0, 1, 0], [0, 0, 1]]))
print(strassen([[-2]], [[3]]))

输出：

[[19, 22], [43, 50]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
[[-6]]

每行都独立创建，不能用 [[0] * size] * size 创建补零矩阵，否则多行会引用同一个列表。整数加减乘法在 Python 中精确执行，没有浮点舍入。

算法执行过程

对2×2主示例，各块均为1×1，7个递归乘法直接到达标量边界。

乘积	标量计算	值
$M_1$	$(1+4)(5+8)$	65
$M_2$	$(3+4)\times5$	35
$M_3$	$1\times(6-8)$	-2
$M_4$	$4\times(7-5)$	8
$M_5$	$(1+2)\times8$	24
$M_6$	$(3-1)(5+6)$	22
$M_7$	$(2-4)(7+8)$	-30

重组得到：

\begin{aligned} C_{11}&=65+8-24-30=19,\\ C_{12}&=-2+24=22,\\ C_{21}&=35+8=43,\\ C_{22}&=65-35-2+22=50. \end{aligned}

第二个示例阶数为3，先补成4×4方阵，递归计算后裁剪前三行、前三列。与单位矩阵相乘应恢复原矩阵，可用来检查补零和裁剪是否正确。

复杂度分析

令原阶数为 $n$ 、补齐阶数为 $s$ ，有 $n\leq s<2n$ （ $n=1$ 时 $s=1$ ）。以下按单次标量加减乘法为单位成本；大整数元素的实际运算还取决于其位数。

时间复杂度：

T(s)=7T(s/2)+O(s^2),\qquad T(s)=O(s^{\log_2 7})=O(n^{\log_2 7})\approx O(n^{2.807}).

当前层的分块、矩阵加减和拼接均为二次工作。补零与裁剪的 $O(n^2)$ 不改变总上界。普通四块乘法执行8个子调用，递推为 $8T(s/2)+O(s^2)$ ，仍得到 $O(s^3)$ 。

辅助空间复杂度： $O(n^2)$ ，包括补齐矩阵、分块、中间乘积和结果矩阵；调用栈深度为 $O(\log(n+1))$ 。七个分支顺序执行，沿调用链的同时存活矩阵面积按几何级数递减，不能把空间直接写成七叉树的全部节点数。最终输出另需 $O(n^2)$ 空间。

本实现递归到标量，补齐阶数 $s=2^q$ 时，乘法叶子数为 $7^q$ 。当 $n=3$ 时补到4，做49次标量叶子乘法，比普通3×3算法的27次还多。因此渐近优势不保证小矩阵更快；本篇以清楚展示七乘法结构为目的。

易错点

四分后依旧做8次乘法，却声称实现了 Strassen。 关键在于七个乘积和正确的重组公式。
将矩阵乘积的左右顺序交换。 分配律可以使用，交换律一般不能使用。
在重组时错写负号。 特别核对 $C_{11}$ 中的 $-M_5$ 和 $C_{22}$ 中的 $-M_2$ 。
奇数阶直接等半划分。 本实现先补零到2的幂，保证每层四个子块同阶。
返回补齐后的整个矩阵。 题目要求输出原阶数，需要裁剪。
把乘法数量减少理解成所有输入都更快。 增加的加减、复制和补零会影响实际耗时。

课堂练习

1×1输入 [[4]] 与 [[-3]] 返回什么？
2×2主示例中，若遗漏 $C_{11}$ 的 $-M_5$ ，会错算成多少？
阶数5补齐到几？本实现共有多少个标量乘法叶子？
若把七乘法改为普通八乘法，为什么对数递归深度仍不能保证亚立方时间？

参考答案

[[-12]]。
$65+8-30=43$ ，而正确值为19。
补齐到8，递归有3层分块，叶子数为 $7^3=343$ 。普通5×5三重循环有125次标量乘法，说明补零和小规模常数不能忽略。
分支数也参与总工作量。 $T(s)=8T(s/2)+O(s^2)$ 的叶子数量为 $8^{\log_2 s}=s^3$ ，因此时间仍为 $O(s^3)$ 。