关于莫比乌斯函数的子段和最大值
  • 板块学术版
  • 楼主飞雨烟雁
  • 当前回复19
  • 已保存回复19
  • 发布时间2023/1/20 21:15
  • 上次更新2023/10/24 03:28:32
查看原帖
关于莫比乌斯函数的子段和最大值
375984
飞雨烟雁楼主2023/1/20 21:15

在解决一道莫比乌斯反演时想到的一个问题:

数列 {μ(1),μ(2),...,μ(n)}\{\mu(1),\mu(2),...,\mu(n)\} 的连续子段和的最大值的量级会是多少?

为了解决这个问题,我写了个程序计算,结果如下:

nnAnsn\text{Ans}_ n
10410^46464
10510^5208208
10610^6679679
10710^722212221

可以看出,这个量级或许是 O(n)O(\sqrt n),但我不会证。故来求助各位大佬(虽然我感觉这个问题比 μ\mu 前缀和的量级还难)。

2023/1/20 21:15
加载中...