这个题的理论最快速度是啥？

damocris @ 2020-05-03 09:13:58

by command_block @ 2020-05-03 09:20:58

P5048 请

by damocris @ 2020-05-03 09:26:18

@command_block orz,居然还真有更低的。。。

by FZzzz @ 2020-05-03 09:32:38

@command_block 5048 不也是这个复杂度吗，只是空间的一个根号砍了吧

by FZzzz @ 2020-05-03 09:33:35

@damocris 目前最低的复杂度是 P5048 最后提到的那个 n^{1.48541} 的做法，那篇 paper 你要不要

by FZzzz @ 2020-05-03 09:33:56

反正我是没看太懂

by damocris @ 2020-05-03 09:59:24

@FZzzz 不会是像矩阵乘法那种只有理论意义，实际从未实现的算法吧。如果是那种类型，对OI毫无意义

by FZzzz @ 2020-05-03 10:10:45

@damocris 艹那篇论文我现在找不到了……

本来就没说对 OI 有意义啊，OI 里你能用到的大概也就只是 O(n\sqrt n)+O(\sqrt n)+O(n) 了

by FZzzz @ 2020-05-03 10:11:08

实现从来不是算法的重点

by FZzzz @ 2020-07-10 20:01:00

@noip 啊是吗，溜了（

by FZzzz @ 2020-07-10 20:01:08

？/fad