2025 Autumn MX

Day1

模拟赛咋坠机了。

数论

整除

可以用去估计。

唯一分解定理

高维点表示。

线性筛

考虑每次在数前加入更小的质因子，以此来获得新的数。这便是线性筛。可以在筛的过程中方便的考察质因子相关的性质。

区间筛

只会有一个大于的质因子。

至多有两个大于的质因子。

因而在内考虑即可，两边质因子没有交集。

辗转相除法

复杂度可以分析到。

如果且，那么有。

可以考虑势能分析。

其实是一种形式的容斥。

同余

等价于。

划分等价类。

考虑既约剩余系，显然有是固定的。

接下来证明对，也是的既约剩余系。

考虑证明对，不可能。这是显然的，因为这等价于，而和都不为。

那么就会有，即。

也即。

记为欧拉函数，我们获得了欧拉定理的

Miller-Rabin 素性检测

考虑对素数，显然有。

考虑如果是偶数，那么。

如果，我们假装他通过了素性测试。

如果，那么也应当有。因而可以不断的进行这样的素性测试，当中的因子被用完后，我们假装他通过了素性测试。

否则我们确实可以确定他没有通过素性测试。

取充分多的数做，若全部通过，我们可以假装他是素数。

但是我们假装取到内的这些质数做就已经是「充分多的」。

这听起来很没道理，因为我们事实上可以直接假装一个数是素数。（雾）

乘法逆元与 Wilson 定理

考虑映射结构很美。

映射到自己，其他两两配对。

因而有。

exgcd

略。

excrt

略。

BSGS

其实也是分块 trick。

把拆成，用哈希表记忆化。

整除分块

考虑最大的，使得。

有，因为

，也就是说，块筛是封闭的。

杂项

是质数。

Day2

凸轮。

QOJ1834

随机化/jk

考察必要条件。

取，使得，询问后可以得出之间的边数。

CF348D Turtles

格路计数

HDU 7541

考虑定理，将最长上升子序列长度转为最长下降子序列的数量。

我们等价于在最长下降子序列数量不多于，

P4126 [AHOI2009] 最小割

最小割等于最大流。

这是正确的，因为此时全部割断使得图不联通时，不可以继续从原点流向汇点，此时恰好是流最大的情况。而继续割会导致不可能的流量凭空产生，因此最小割的时候取到最大流。

考虑残量网络上的强连通分量。

对于一条初始解中满流的边

如果在残量网络上存在另外的边可以从走到，那么这不是必须边。

Day3

CodeForces-1787C

性质题。

发现是一个一次型性质，不妨将换为。

考察每个位置的贡献，发现这是关于的一次函数，最值一定在端点处取到，就全赢了。

CodeForces-1740E

考虑随意排列权值，随意删除顺序似乎限制很松。

于是转而考察什么样的情况是不行的，发现有相同祖先的两点不能和这个祖先同时贡献到答案中。

然后合并子树时讨论一下是否包含当前根即可。

problem:洛谷-P5664

好像很早之前就想做了来着。

观察一下限制，发现很神秘，出现次数大于的列至多只有一列。

所以考虑容斥即可，不合法情况之间一定不交。

CodeForces-2152A

唐。

考察如何制造凹陷即可。

抛硬币

列方程解期望。

涂色

可以用森林来描述不交与包含的关系，并且在已知存在祖先关系的情况下可以通过区间长度来比较深度。

Day4

模拟赛估分 60 + 40 + 100 + 0

实际得分 0 + 30 + 100 + 0

？

前缀和

可减性。

P4137 Rmq Problem / mex

离线一下询问挂在右端点上就全对了。

考虑用最晚出现的位置刻画是否在区间内出现过即可。

分块

不需要维护整体答案，可以接受的合并。

tag 之间不需要复合，直接下放到 val 中。

太优秀了。

分治

考虑跨过终点的对象。

于是我们相当于以一个 log 的代价去掉了一个限制。

缺一分治或者线段树分治状物可以帮助我们以一个 log 的代价去掉删除的操作。

有无群友帮忙看看昨天模拟赛 T1 化成了这个柿子还有优化空间吗

Rainbow-Automaton's blog