分类： 数论
-
超-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$ 的指数。从而它是收敛的。 （更多…）
-
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$。 （更多…）
-
2023 NOI 春季测试 T2 – 幂次 简略题解
我们有非常易于理解的暴力解法：直接对于 $b=3,4\cdots$，求出所有可以当作底数的 $a$，计算 $a^b$ 后放入数据结构/排序去重；特别处理 $b=2$ 的情况即可。在此不再赘述。
不过，我们注意到若有正整数 $x$，满足 $x>1,x=a_0^{b_0}\ \ (a_0,b_0\in \mathbb N)$，且 $\forall a,b\in\mathbb N,a_0\neq a^b$（即底数 $a_0$ 不可再开根），那么 $\forall b,b\mid b_0,x=(a_0^{b_0/b})^b$。这意味着假如不去重地暴力添加 $\lfloor\sqrt[b]{n}\rfloor$ 到答案中，上文中 $x$ 将被算 $|\{b\mid b_0\equiv 0\pmod b\}|$ 次。
于是这就变成莫反的模板题了：记 $g(b)$ 表示“能被 $a^b$ 表出的 $x$ 之数量”，$f(b_0)$ 表示“恰能被 $x=a_0^{b_0}$ 表出，不可被 $x=a^b,b<b_0$ 表出的 $x$ 的数量”。易得 $g(b)=\sum_{b\mid b_0}f(b_0)$，故 $f(b_0)=\sum_{b_0\mid b}g(b)\mu(b/b_0)$。显然，当 $b>\log_2 n$ 时仅有 $a=1$ 满足 $a^b\leq n$，故我们只需计算 $\lfloor\log_2 n\rfloor$ 个 $b$，最后特判 $a=1$。预处理出 $\mu$ 的值，暴力求取反演式，复杂度为 $\operatorname{O}(\log^2 n)$。
其实并不需要这么麻烦。我们根本不需要反演：根据 $g(b)=\sum_{b\mid b_0}f(b_0)$，假若 $\forall b_0,b_0>b,f(b_0)$ 都已经计算完成，那么我们直接得到 $f(b)=g(b)-\sum_{b\mid b_0,b_0>b}f(b_0)$。由 $b$ 从大往小计算即可，复杂度相同。
-
MOCK quasi-PTS 20230209 日志
近一个月来第一次赛时通过一道题。真是可喜可贺。
A – 单调
一开始以为与网络流相关；后来考虑 DP；结果是个贪心或者乱搞。
题意简述
给定长为 $\newcommand\bigO{\operatorname{O}}n\ \ (n\leq 10^5)$ 的序列 $\langle a_i\rangle,a_i\in\{1,2,3\}$。匹配尽可能多的子序列，每个子序列均为 $\langle 1,2,3\rangle$ 或 $\langle 3,2,1\rangle$，且一个位置最多被一个子序列占用。求最大匹配数。 （更多…）
-
AtCoder ARC148D – mod M Game 题解与思路重现
AtCoder Regular Contest 148 D – mod M Game
鲁莽的尝试？
一个非常显然的 Bob 的必胜局面是：对于任意 $x\in \{0,1,\cdots,M-1\}$，在这 $2N$ 个数中的出现次数均为偶数。由此 Bob 可以选择与 Alice 上一轮选的相同的数而获胜。
那……其他局面就一定是 Alice 必胜么？
我们只依靠该结论交一份代码。不出意料，没有通过。不过它只错了两成的测点！看来大体方向是正确的。
正解
-
AtCoder ABC236G – Good Vertices – 题解 – 矩阵乘法优化DP
昨晚参与AtCoder ABC 236时认为G题似乎可做，直到看到数据范围才发现事情没有那么简单。
由于最近学习离线数据结构，又见识过一道题意接近的题目，故想到整体二分，二分每一个节点第一次能恰好经过$L$条边到达的时间，然后考虑DP求解。设计状态$f(i, x)$表示在该图上经过恰好$i$次转移能否到达点$x$。但很快发现每一次二分时均要重新在图上运行DP，时间复杂度无法承受。况且DP递推转移的次数$L$高达$10^9$，甚至不可能是线性的复杂度。
今天查看题解，发现有几个重要的，从未考虑过的trick：
- 既然要求能够经恰好$L$次转移到达的最早的时间点，则我们将每条边的边权$w$设为其加入图中的时间，则可以转化成恰有$L$条边的最小瓶颈路。
- 发现$L$很大，所以考虑通过矩阵乘法加速递推，也即所谓倍增优化DP的一种。