基本数论
说一下一些基本数论算法的实现和简洁证明。
持续更新中。
620
T1简单。
T3需要注意到n,q并不同阶。那么说明不预处理亏大了。
另外的，两种转化：
将 |a-b| 转化成枚举分界点或者说 \(\sum_{}pre_i\times suf_{i+1}\)
会不重不漏算出。
事实上你也可以直接把111,11111 异或一下看popc。\(5-3=popcount(11111\mathrm{xor}111)\).
真的要记住预处理。
apio到NOI
.到NOI前的模拟赛，博客就写道这里了。The Last Month。Ragnarök。
7,19 Link
卷爷的模拟赛。我愿意成为APIO复刻活动。
很难受，如果APIO的时候好好听课好好总结今天的题就应该会了。
T1
让你维护两个pair集合，动态维护（插入删除） \(\min{(\max(a_1+a_2,b_1+b_2))},(a_1,b_1)\in
S_1,(a_2,b_2)
十分厉害的数论提
十分厉害。
\(x,y\in[1,p\times (p-1)]\) 求使得
\(x^y=y^x \bmod p\) 的对数。
首先这个东西不能用原根，阶去分析， 因为 \(x\) 可能大于 \(p\)，这样会产生一个 %p 不容易考虑了。
那只能观察这个定义域限制了。
先改写一下方程 ：\((x\bmod p)^{y\ \bmod
p-1}={(y\bmod p)}^{x\ \bmod
ARC140
未补完
Link
A
让你最多改 \(k\)
个字符，最大化循环位移得到的本质不同的串。
枚举循环节，然后贪心判断即可。。复杂度 \(O(d(n)n)\)。
B
题意你有俩操作必须轮流做，\(\mathrm{ARC \to
R},\mathrm{ARC\to AC}\)。
冷静思考一下发现最终有可能操作的一定是 \(R\) 旁边的数。
1操作相当于把 \(\mathrm{A
ABC251
Link
A,B,C都是模拟题没啥好说的。
D
最开始想的是贪心做，以为信息熵足够贪心就行，然后发现不对。。。。。
然后看拿什么1,2,4,8,15什么的自然想到能不能把二进制拆开那么做。，这样数量太多了。
所以大概就能想到按10进制分，就xx0000,xx00,xx这样三组恰好 297。
E
很简单的DP，拆下环就行。
F
想了一小会，是调整那样做，复杂度爆炸。
然后