长乐集训 - NOI模拟赛（二十九）「订正未完成」
再次垫底$\text{.jpg}$
$\text{score：20 + 0 + 10 = 30 rk：27/29}$
Problem A：sign题面
题解这题贼水，但我没想出来。。
我大概以为这不是数学所以没想到代入，或者是我忘记该点值表示可以 $O (\log A)$
反正全村就我没到及格线
题解懒得写了，就搬出题人给的吧
事实上，这个做法不能通过。
考虑上面做法复杂度瓶颈是快速幂。一个简单的$\text{trick}$是对于一个固定的 $son_u = k$，令 $M = \lceil \sqrt{A} \rceil$，预处理出 $k^0, k^1, k^2, …, k^{M - 1}$ 以及 $(k^M)^0, (k^M)^1, …, (k^M)^{M - 1}$。这样单次求某个点值就可以用 $O (1)$ 次算术运算求得。
时间复杂度为 $O ((n + \sqrt{A})\sqrt{n})$。
以上是出题人提供题解
代码123456789101112131415161718192021222324252627282930313233343536373839404142 ...