这题 @Determinant 和 @gxy001 讲了一个不基于 BSGS 的做法。大致是 Adleman–Manders–Miller 算法。这个做法的最终复杂度分析中，两位都忽略掉了 $\Theta(n)$ 这个项。 看起来这个因子人畜无害，毕竟指数能有多大呢？ 但其实，对于素数 $p$，作为 $p-1$ 的一个…

这种题目的中间结论——除非在看到题目之前就知道它——对于解题是没有意义的。只要能猜到最后的答案，就一定能以某种方式证明所有的结论。所谓的这些中间结论就变成了最终的答案的简单推论。比如本题中这个「局面的 SG 值是单个点的 SG 值的 Nim 和」就是这样的中间结论。 这样的中间结论不能成为思考的起点。 对于这种题目，思…

非树边不要访问两次。

大概其就是在无向图里选 $K$ 条路径，顶点集互不相交，求最大边权和。 这玩意拆个点之后是不是就是费用流了，所以有凸性成立。

本题其实就是 [P1484 种树](https://www.luogu.com.cn/problem/P1484)。 因为需要进行到询问包含结点区间或者与结点区间相离，所以每一个区间询问 $[l,r]$ 都相当于将至多三个区间 $[1,l-1]$、$[l,r]$、$[r+1,n]$ 分成若干个结点区间的并——这些结点就…

这道题的凸性没人证明，补一下。 其实是四边形不等式。本题目是区间分拆问题。设区间 $[l,r]$ 的成本为 $$ w(l,r)=\dfrac{l-1}{r}. $$ 本题问的是将区间 $[1,n]$ 拆成 $k$ 份并最小化上述成本的解 $ans$。最终答案就是 $k-ans$。 那么，问题的凸性只需要验证上述成本函数…

在讨论《WQS 二分做法是假的》回复：

@[迟暮天复明](luogu://user/222865) 你这个好像也是凸的？我跑出来的结果是 6 3 0 0 叉 wqs 二分具体得看实现方式吧。一般思路就是多询问几种凸性不满足的情况。

本题并没有凸性，虽然绝大多数时候凸性是成立的。所以，本题并不能够通过 WQS 二分求解。[这篇题解](https://www.luogu.com.cn/article/8ie7jfxe) 是有问题的。 用 [排名最高的题解](https://www.luogu.com.cn/article/2yka4zbk) 改了一个…

这题用平衡树会更方便一些，不用离散化。直接写个 WBLT，然后写个结点回收，就也用不了多少空间，还跑得飞快。 具体讲一下思路，就是每个结点处存当前线段参数 $(a,b,c,n)$ 和所求的和式 $su$。显然，对于线段 $$ y=(ax+b)/c,~1\le x\le n $$ 来说，所求和式等于 $$ \begin{…

在讨论《求助》回复：

注意第一个分量的变化，设 $t'=(t-\lfloor t\rfloor)^{-1}$，那么，在两轮迭代后（每轮包括两次递归），第一个分量不大于 $$ n(t-\lfloor t\rfloor)(t'-\lfloor t'\rfloor). $$ 这相当于缩小到了原来的 $$ 1-\dfrac{\lfloor t'\r…

在讨论《这道题为什么加个gcd就不会爆long long?》回复：

实际上，这是因为 [二次无理数的连分数展开算法](https://oi-wiki.org/math/number-theory/continued-fraction/#%E4%BA%8C%E6%AC%A1%E6%97%A0%E7%90%86%E6%95%B0) 中，系数 $P$ 和 $Q$ 具有界 $\Theta(\s…

对 [这篇题解](https://www.luogu.com.cn/article/ub9rdvqn) 的一点补充。 沿用记号，状态转移方程为 $$ f_{i,j} = \max\{f_{i-1,j},f_{i-k,j-1}+s_i-s_{i-k}\}. $$ 现在归纳证明两点： 1. $f_{i,j}-f_{i-k,…

首先注意到 $$ \Delta E = \int_{t}^{t+\Delta t}(1-v)dt = \Delta t - (\Delta L-s\Delta t). $$ 因此，同一段路的能量消耗只与传送带速度 $s$，移动距离 $\Delta L$ 和移动时间有关 $\Delta t$，与 $v$ 的变化曲线无关。…

设 $f(i,v)$ 为处理完前 $i$ 堆泥土且结余 $v$ 单位泥土的最小成本。问题的答案就是 $f(n,0)$。 可以写出状态转移方程： $$ f(i,v) = \min_w f(i-1,w)+|w|Z+h((b_i-a_i)-(w-v)), $$ 其中， $$ h(\delta) = \max\{\delta,…

有一个看起来完全不像是 slope trick 的题目，做法其实和本题是一致的。 > [CF865D](https://www.luogu.com.cn/problem/CF865D) ：给定股票价格序列，每天买一股、卖一股或者什么的都不做，要求最后一天结束时不持有股票，问最大利润。 这个问题等价于「求将价格序列调整为…

在讨论《洛谷讨论区恢复公告》回复：

Codeforces 的题目不能提交，但是不能提交就不能看讨论区。这是不是有 bug

提供另一种推式子的方法。 如同其他题解解释的那样，求出原根 $g$ 后，问题转化为计算离散对数 $$ K\sum_{m=1}^M\sum_{n=1}^N[m\perp n]\log_g\dfrac{(m+n-1)!}{m!n!}. $$ 为简化记号，下令 $$ N_d = \lfloor N/d\rfloor,~M_d…

好像很多 AC 记录的代码都算不对 1e13 的值。这题数据范围是不是压根就没开到 1e13。建议加强。

本题题面翻译有误，直接将题意转化了，应当更换题面，并且撤换当前的题解。@管理员

如果你的程序对小模数报错，可能是预处理欧拉函数的时候，取模用的是 $p$ 而不是 $(p-1)$。

对于Pollard Rho算法的判环，最开始Pollard在1975年的算法使用的是Floyd判环，后来Brent在1980年提出了Brent判环，对Floyd判环做了常数上的改进。两个算法关于rho的长度都是线性的，但是Brent的判环执行函数迭代的次数比Floyd的少，且使得Pollard Rho算法的平均运行时间…

对于Pollard Rho算法的判环，最开始Pollard在1974年的算法使用的是Floyd判环，后来Brent在1980年提出了Brent判环，对Floyd判环做了常数上的改进。两个算法关于rho的长度都是线性的，但是Brent的判环执行函数迭代的次数比Floyd的少，且使得Pollard Rho算法的平均运行时间…

在讨论《为什么以及怎样用上下界优化保证平方复杂度》回复：

@[ricky_lin](/user/78206) 谢谢回复。是的，看起来只是一个不大的优化。很多题解的代码的确动态更新size并且限制了循环的上界，但是没有控制循环的下界；这样导致代码还是$O(n^3)$的。我着重想说的是，这个不起眼的下界也很重要。因为我之前踩过这个坑，看大家没有很强调这个的，所以过来提了一嘴。

在讨论《为什么以及怎样用上下界优化保证平方复杂度》回复：

代码里漏了更新sz的代码，看个意思就行

本题是典型的树上背包，正确的算法复杂度是$O(nk)$，其中$n$是树的大小，$k$是可选的物品数量。subtask1是用来卡$O(n^3)$的错误写法的（不开O2的情况下）。在我正确通过了subtask1之后，我终于想通了为啥以及如何正确地做上下界优化，特发此贴以帮助后面卡在这里的人思考。 正如很多别的复杂度分析的文…