作者： NGC5457
-
超-4运算在 Z/nZ 上的收敛性 – 欧拉函数与扩展欧拉定理
扩展欧拉定理揭示了对于任意模数 $n$，有
$$
a^b\bmod n=\begin{cases}
a^b,&b<\varphi(n)\\
a^{b\bmod \varphi(n)+\varphi(n)},&\text{otherwise}
\end{cases}.
$$我们又知道若分解质因数 $x=\sum p_i^{c_i}$，则 $\varphi(x)=x\prod (p_i-1)/p_i$。则若 $x>1$，若 $2\mid x$，$\varphi(x)\leq x/2$；否则，$2\mid\varphi(x)$。记 $\varphi^{(k)}(x)=\underbrace{\varphi(\varphi(\cdots\varphi(}_{k\text{ layers}}x)\cdots))$，则 $\newcommand\bigO{\operatorname{O}}\bigO(\log n)$ 级别的 $k$ 就能使其收敛到 $1$。
因此对于 $\mathbb{Z}/n\mathbb{Z}$ 上的超-4运算 $a_1^{a_2^{a_3^{⋰}}}$，结合扩展欧拉定理得到，在指数塔的 $\bigO(\log n)$ 层就将得到 $\bmod\varphi(1)+\varphi(1)\equiv 1$ 的指数。从而它是收敛的。 （更多…）
-
维护树上编号连续节点构成连通块/虚树的一种方法
维护连通块
现有一棵 $n$ 个节点的树。我们构建一最小的连通块 $S(l,r)$，包含编号在 $[l,r]$ 中的所有节点。多次询问，每次对于任意一对 $[l,r]$，询问关于这连通块的信息。
如果可以离线/可持久化，此类问题有一通用思路：用扫描线维护“$r$ 固定时不同 $l$ 构成连通块的信息”。若 $[p,q]\subseteq[l,r]$，则 $S(l,r)\supseteq S(p,q)$；对于一固定的 $r$，我们维护 $l$ 分别取 $r,r-1,\cdots,1$（向左拓展）时，连通块的增量。对于点 $x$，我们记录 $t_r(x)$ 表示 $r$ 固定时使得 $x\in S(l,r)$ 的最大的 $l$。假设已经对于 $r$ 维护好了；现在拓展到 $r’=r+1$。
若 $x\notin \{r,r+1\}$，则 $t_{r+1}(x)\neq t_{r}(x)$ 是
- $x$ 在 $r$ 到 $r+1$ 的简单路径上，且
- $t_{r+1}(x)=r$
的充分必要条件。
考虑任意 $l$。由于 $S$ 是极小的，故将 $r+1$“加入”$S(l,r)$ 得到 $S(l,r+1)$，只需找到 $r+1$ 和连通块在树上最接近节点之间的路径，将路径上所有点加入连通块；由树的性质，此路径是通向 $[l,r]$ 中任意节点的必经之路，也即 $r,r+1$ 的最短路径的某一前缀。又当 $l=r$ 时，$S(l,r+1)$ 就是该路径本身；再有 $[p,q]\subseteq[l,r]\Longrightarrow S(l,r)\supseteq S(p,q)$，故本命题得证。
因此，我们需将整条路径上的点的最大出现时间整体覆盖成 $t_{r+1}(x)=r$（$r+1$ 本身除外，它是 $t_{r+1}(r+1)=r+1$）。可以使用珂朵莉树和树剖维护连续的 $t(x)$ 相同的一段。设 $Φ$ 表示连续段个数。每次覆盖操作会对 $\newcommand\bigO{\operatorname{O}}\bigO(\log n)$ 条重链执行“删除若干连续段，加入 $\bigO(1)$ 个连续段”的操作。又 $Φ\leq n$，则 $Φ$ 的总变化量是 $\bigO(n\log n)$ 的。因此若用对数级别有序关联式容器（如
std::map），总时间复杂度为 $\bigO(n\log^2 n)$。
（更多…） -
MOCK PTS- 20231122 B – 迷失 – 强连通图所有环长度之最大公约数
题意简述
给定不含重边的有向图 $G$，设其邻接矩阵为 $A$，定义其元素的“加”为逻辑或，“乘”为逻辑与。问 $A^c,c=1,2,\cdots$ 在何时出现循环节（$c=k$），以及最小循环节长度 $d$（即，$A^k=A^{k+d}$，$k,d$ 均最小）。
题意转化
在原图上，从 $u$ 出发，可用恰 $b$ 步走到 $v$，则在 $b$ 次迭代后的图上有有向边 $(u,v)$。问最少迭代多少次后图的形态出现循环节。
强连通图的所有环环长的最大公约数
任意找一点 $u$，只需考虑经过 $u$ 的所有环。
考虑有一不经过 $u$ 的环，其长为 $a$；另有一经过所有点的环（本图强连通），其长为 $b$。则有 $\gcd(a,b,a+b)=\gcd(a,a+b)$。
我们任意找一棵本图的搜索树。设其根为 $u$。设节点 $v$ 的深度为 $\newcommand\dep{\operatorname{dep}}\dep(v)$。设某经过 $u$ 的有限长度的环依次经过了非树边（横叉边、返祖边） $(v_1,w_1),(v_2,w_2),\cdots,(v_t,w_t)$。那么其环长在答案中可以被 $\gcd(|\dep(v_i)+1-\dep(w_i)|,i\in\{1,2,\cdots,t\})$ 取代。
可得 $w_i$ 一定是 $v_{i+1}$ 的祖先。我们删去 $(v_1,w_1)$，得到另一个环；这环与原来环的长度差为 $\dep(w_1)-\dep(v_1)-1$。这两环均在答案中作出贡献；又由于 $\gcd(a,b)=\gcd(a,b-a)$，则我们将原来的环长等价替换为两个数：其一即 $|\dep(w_1)-\dep(v_1)-1|$，其二为现在的环长。再继续删除 $(v_2,w_2),\cdots$，便等价地换为 $t+1$ 个数。
因此我们遍历一遍搜索树，就可以在 $\operatorname{O}(n\log n)$ 的时间内求出所有环环长之 $\gcd$。 （更多…）
-
MOCK NOIP 20231027 T2 – 缺金木 – 线段树的“双半群”模型
题意简述
给定长为 $n$ 的序列 $a$。要求支持以下操作：
- 给定 $l,r,x$，将 $a_i,l\leq i\leq r$ 全部加上 $x$；
- 给定 $l,r,x$，将 $a_i,l\leq i\leq r$ 全部乘以 $x$；
- 给定 $l,r,x$，若这是第 $k$ 次操作，则保护 $a_i,l\leq i\leq r$ 直到第 $k+x$ 次操作（含），这期间操作 $1,2$ 对 $a_i$ 无效。若 $a_i$ 已经被保护到 $x’,x’>k+x$，则这一保护不会失效。
- 给定 $l,r$，输出 $\sum_{i=l}^{r} a_i$，对 $10^9+7$ 取余。
$n,m\leq 2\times 10^5$。
半群、双半群模型——线段树到底能维护怎样的信息？——caijianhong 的博客园
-
“一日一夜兮！不见日月。”
晚自习下课有些时候了。我从机房下到三班教室放笔袋。
推门就见李季鸿被壁咚了。
嗯。壁咚。从我的角度看已经体肤相接了。虽然我知道他和那个女生关系很近，但也没想到那么近。
真如轰雷掣电哪。于是自然地，在空荡荡的走廊里，在寒夜冷雨的校门外，又回荡着“一日一夜兮！不见日月。”的怒吼。 （更多…）
-
闲话
通过大量观察，我们不难发现：
不管是在二十班、三班、补课教室，还是在机房，我有很大概率是最后走的那个——除非那天做清洁的实在太拖沓。
于是“关灯关门关窗”（冬夏季还要关空调）的任务自然就落到我头上了。不管在哪里都一样。以前还算个半吊子班长，这么做算是担责；现在自然也不负什么责任，也没人提醒我做这事。不过就这么拍拍屁股走人，总是良心不安的；回班上以后还可能因此给班上扣分。
所以，我还是默念着“关灯关门关窗”，弄妥当再走吧。
-
「夢は消ぬ」
哼，真是让人啼笑皆非、五味杂陈。
我听了两年半的《傀儡谣》；副标题带《阳炎》的那一首还被我当夜跑踩拍子的音乐，以及逢大考进考场之前“鼓舞士气”的曲子。
不，不对，并不是鼓舞士气，准确来说是让自己紧张起来、认真对待。因为一直以来，我都只看到“夢は消”这三个字——“梦想消逝”，“ぬ”就被我稀里糊涂地判作“了”；于是乎其词义就似乎在警醒我，“要是没考好或者事情没办成，’梦想就要消逝了’”。
结果今天我知道了——此“ぬ”表否定意味。“梦想不会消逝”。
这可是全然相反啊。于是一切都解释得通了：“阳炎”喻指光明，“梦想”不会逝去而“怨恨”终将消散，这特么全部是积极的意象啊？！真亏得我误会了两年半。真操蛋啊。
我对几首《傀儡谣》更具体的理解，会慢慢地整理出来。此处按下不表。