证明：矩阵乘法存在 O(n^2) 做法

· · 休闲·娱乐

听说在 CSP 前写专栏能增加 316381099 的 rp。

申明：本文没有使用 AI。

前置知识

(+,+)$ 矩阵积的 $O(n^2)$ 做法：$c_{i,j}=\sum\limits^{n}_{k=1}a_{i,k} + b_{k,j} = \left(\sum\limits^{n}_{k=1}a_{i,k}\right) + \left(\sum\limits^{n}_{k=1} b_{k,j}\right) (\times,\times)$ 矩阵积的 $O(n^2)$ 做法：$c_{i,j}=\prod\limits^{n}_{k=1}a_{i,k} \times b_{k,j} = \left(\prod\limits^{n}_{k=1}a_{i,k}\right) \times \left(\prod\limits^{n}_{k=1} b_{k,j}\right)

前缀和 / 积处理即可。

一些引理

引理 1：对于任意实数 a,b，满足 \max(a^2, b^2) \ge ab。

证明：

什么，你说这里只有 |x|,|y| \le \sqrt 5 的情况？

证明 (C++ Remix)：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll inf = 'inf';
mt19937 rnd(316381099);

ll Rnd(ll l, ll r) { return l + rnd() % (r - l + 1); }

int main() {
    for (int i = 1; i <= 316381099; i++) {
        ll x = Rnd(-inf, inf);
        ll y = Rnd(-inf, inf);
        if (max(x * x, y * y) < x * y) {
            cout << "滚木";
            break;
        }
    }
    return 0;
}

注意到这份代码什么都没输出。

什么，你说这份代码没有覆盖所有的可能性？

「5.对使用随机数和随机算法的程序的申诉，不予受理；」—— CCF

证毕。\blacksquare

引理 2：+ 和 \times 都是实数。

证明：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll add = '+';
const ll mul = '×';

int main() {
    srand(316381099);
    int x = rand();
    return 0;
}

注意到这份代码通过了编译。

什么，你说什么？

「5.对使用随机数和随机算法的程序的申诉，不予受理；」—— CCF

证毕。\blacksquare

证明 (\times,+) 矩阵积存在 O(n^2) 做法

矩阵内积（Frobenius 内积）：对于两个矩阵 A,B ，其内积常记为 (A,B) = \operatorname{tr}(A^TB)。

钦定 + 和 \times 可以是 1 \times 1 的矩阵，根据计算机图形学，+^{T}=+, \times^{T}=\times，因此：

(+,+) = \operatorname{tr}(++) = ++ (\times,\times) = \operatorname{tr}(\times\times) = \times\times (\times,+) = \operatorname{tr}(\times+) = \times+

代入 a=\times,b=+。

\max(++, \times\times)&\ge\times+ \\ \max\left((+,+), (\times,\times)\right)&\ge(\times,+) \\ \max\left(O(n^2), O(n^2)\right)&\ge(\times,+) \\ O(n^2)&\ge(\times,+) \end{align*}

注意到读入矩阵至少需要 O(n^2) 时间，因此我们证明了 (\times,+) 矩阵积存在恰好等于 O(n^2) 的做法。

？？？

什么，你说读入矩阵和计算矩乘的复杂度都可以达到 O(0)？

「申诉服务费每题50元」—— CCF。

前面忘了，可以通过洛谷私信联系我获取缴费通道，绝对不是因为后面忘了。

316381099。