QOJ.ac

QOJ

Límite de tiempo: 1.0 s Límite de memoria: 1024 MB Puntuación total: 100 Meme Task

#8032. 计算大师

Estadísticas

Little Cyan Fish 在全国青少年信息学奥林匹克竞赛冬令营(WC)中参加了一场算法讲座。在讲座中,一位神秘的讲师谈到了矩阵乘法,这是一种从两个矩阵产生一个矩阵的二元运算。

对于矩阵乘法,第一个矩阵的列数必须等于第二个矩阵的行数。所得矩阵(称为矩阵积)的行数等于第一个矩阵的行数,列数等于第二个矩阵的列数。矩阵 $A$ 和 $B$ 的乘积记为 $C = AB$。

$$C_{i,j} = \sum_{k} A_{i,k}B_{k,j}$$

这位神秘的讲师特别提到了矩阵乘法的计算复杂度,它决定了矩阵乘法运算的执行速度。直接应用矩阵乘法的数学定义,得到一种在域上将两个 $n \times n$ 矩阵相乘需要 $O(n^3)$ 次域运算的算法。第一个被发现的更快算法是 Volker Strassen 在 1969 年提出的 Strassen 算法,通常被称为“快速矩阵乘法”。

“矩阵乘法指数”(通常记为 $\omega$)是使得任何两个 $n \times n$ 矩阵在域上都可以使用 $n^{\omega+o(1)}$ 次域运算相乘的最小实数。这种符号在算法研究中很常用,因此使用矩阵乘法作为子程序的算法,其运行时间界限可以随着 $\omega$ 界限的改进而更新。使用朴素下界和教科书式矩阵乘法的上界,可以直接得出 $2 \le \omega \le 3$。$\omega$ 是否等于 $2$ 是理论计算机科学中的一个重大开放性问题,目前有一系列研究致力于开发矩阵乘法算法以获得 $\omega$ 的改进界限。

在冬令营中,神秘讲师展示了下表来说明矩阵乘法指数的时间线。关于矩阵乘法算法渐近复杂度的最佳公告界限是由 Williams、Xu、Xu 和 Zhou 在 2023 年 7 月的一份预印本中给出的。

年份 $\omega$ 的界限 作者
1969 2.8074 Strassen
1978 2.796 Pan
1979 2.780 Bini, Capovani, Romani
1981 2.522 Schönhage
1981 2.517 Romani
1981 2.496 Coppersmith, Winograd
1986 2.479 Strassen
1990 2.3755 Coppersmith, Winograd
2010 ? Stothers
2012 ? Williams
2014 ? Le Gall
2020 ? Alman, Williams
2022 ? Duan, Wu, Zhou
2023 ? Williams, Xu, Xu, and Zhou

然而,Little Cyan Fish 没有认真听神秘讲师的课。冬令营结束后,他忘记了表中最后几行的信息。他想知道,截至 2024 年 1 月 12 日,$\omega$ 的最佳公告上界是多少?

输入格式

本题没有输入。

输出格式

输出一行,包含一个实数,表示截至 2024 年 1 月 12 日 $\omega$ 的最佳公告界限。

如果你的答案的绝对误差不超过 $10^{-3}$,则被视为正确。形式化地说,假设你的输出为 $a$,评测答案为 $b$,则当且仅当 $|a-b| \le 10^{-3}$ 时,你的输出被接受。

样例

样例输入 1

<no input>

样例输出 1

2.1145141919810

说明

请注意,样例输出并不是正确答案!它仅用于展示输出格式。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.