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
说明
请注意,样例输出并不是正确答案!它仅用于展示输出格式。