#1371. [愚人节 2025 A] 追忆

[愚人节 2025 A] 追忆

Background

我常常追忆过去。

生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲,揉捻成天上朵朵白云。

云朵之间亦有分别:积云厚重,而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀,而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦,太过清楚则无法愉悦自己的幻想,过分模糊却又坠入虚无。只有薄雾间的山水,面纱下的女子,那恰到好处的朦胧,才能满足我对美的苛求。

追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友,推倒又重建的街道,种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来,我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间,在一个场景前驻足,在岁月的朦胧里瞭望过去的自己,感受尽可能多的甜蜜。美好的时光曾流过我的身体,我便心满意足。

过去已经凝固,我带着回忆向前,只是时常疏于保管,回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。

我该在哪里停留?我问我自己。

Description

小 X 在做「追忆」这道题时,毫无头绪。

仔细思考着,他想到了一个绝妙的做法。

比赛结束,他对这题并没有抱有太大希望,民间数据有些弱也是没有怎么影响他。

然而,成绩出来时,他有些傻眼了。

——他数组开小了。如果开得正确,他就可以拿下剩余的 12 分。

而他也恰恰被卡在省队线外两名——好在他有奖励名额。

但是,这一切仍然有些遗憾,不是吗?

根据你的经验,小 X 「追忆」这题的代码时间复杂度是多少?

Format

Input

Output

格式为 O(A)\texttt{O(A)},表示时间复杂度,其中 A\tt A 是一个表达式,约定:

  • ana\sqrt n 写作 a*sqrt(n)\texttt{a*sqrt(n)}
  • alogna\log n 写作 a*log(n)\texttt{a*log(n)}
  • axyax^y 写作 ax ˆy\texttt{ax\^ y}
  • xypqx^yp^q 写作 x ˆy*p ˆq\texttt{x\^ y*p\^ q}
  • (xy)pq(xy)^{pq} 写作 (xy) ˆ(pq)\texttt{(xy)\^ (pq)}
  • xypqx^{yp^q} 写作 x ˆ(yp ˆq)\texttt{x\^ (yp\^ q)}
  • xky+z\dfrac{xk}{y+z} 写作 xk/(y+z)\texttt{xk/(y+z)}
  • 存在常数 w=64w=64,该常数不可省略。
  • 原题中的 n,m,qn,m,q 不一定同阶,应当区分开来。
  • 如果时间复杂度是一个多项式,那么应当只保留会成为时间复杂度瓶颈的项。如对于时间复杂度 O(n+n2+m2+q)O(n+n^2+m^2+q),应当简化为 O(n2+m2)O(n^2+m^2);对于时间复杂度 O(n2w+qlogw)O\left(\dfrac{n^2}w+q\log w\right),应当简化为 O(n2w)O\left(\dfrac{n^2}w\right)
  • 只考虑单组测试数据(而非测试点)的时间复杂度。

保证答案已经涵盖了以上所有情况,并且如 x+yx+y 写作 x+y\texttt{x+y}y+x\texttt{y+x}xyxy 写作 xy\texttt{xy}yx\texttt{yx},都是可以的。

你应当给出尽可能严格的时间复杂度。

Samples


O(n^2/w)

Explanations

样例只是给予了一种可能的答案,不保证其正确。