分类： 数学
-
超-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$ 从大往小计算即可，复杂度相同。
-
再探 FFT – DIT 与 DIF，另种推导和优化
本文将简单推导两种方式进行的离散傅里叶变换，用另种视角解释并优化算法。参考了 Seniorious yhx-12243 的 NTT 到底写了些什么（详细揭秘） 一文、OI Wiki 快速傅里叶变换 条目 和 rushcheyo 转置原理及其应用 讲稿。
离散傅里叶变换
我们计算数列 $\{a_n\}$ 的离散傅里叶变换
$$
\newcommand\DFT{\operatorname{DFT}}\DFT(a,n)_k=\sum_{j=0}^{n-1}a_j\mathrm{e}^{\frac{-2\pi\mathrm{i}}{n}kj}
$$由卷积定理和循环卷积得到，我们对同样长为 $n$ 的数列 $\{b_n\}$ 作 $\DFT$，并令数列 $c_k=\DFT(a,n)_k\DFT(b,n)_k$，则有
$$
\newcommand\IDFT{\operatorname{IDFT}}\IDFT(c,n)_k=\sum_{j+q\equiv k\pmod n}a_jb_q
$$于是我们可以利用该原理实现常规意义下的数列卷积：有长为 $n$ 的数列 $\{a_n\}$，长 $m$ 的数列 $\{b_m\}$，则将 $a,b$ 高位补 $0$，分别作 $n+m-1$ 位的 $\DFT$，点值相乘后 $\IDFT$ 即可得到 $c_k=\sum_{i+j\equiv k\pmod{n+m-1}}a_ib_j=\sum_{\substack{i+j=k\\0\leq i<n\\0\leq j<m}}a_ib_j$。
为行文方便，下文采用 $\DFT(a,n)_k=\sum_{i=0}^{n-1}a_i\omega_n^{ik}$ 的定义，其中 $\omega_n=\exp(2\pi\mathrm{i}/n)$，即 $n$ 阶单位根。 （更多…）
-
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$，且一个位置最多被一个子序列占用。求最大匹配数。 （更多…）
-
洛谷题库 P6031 Cards 加强版 – 题解与思路重现
对于每一轮对局的 $m!$ 种排列，对于编号为 $a$ 的牌，恒有 $(m-1)!$ 种是以牌 $a$ 为首的。因此一轮可以归为 $m$ 种情况，首张为王牌的概率为 $\frac{1}{m}$。
这是某场模拟考试给出的部分分：
$$
\begin{array}{cccc}
\text{Subtask}&\text{Constraints}&\text{Points}&\text{Dependencies}\\ \hline
1&n,m,k\leq 5&2&\\
2&k=1&2&\\
3&k\leq 5000&10&1,2\\
4&m\leq 100&10&1\\
5&n\leq k&5&\\
6&k\leq 10^5&10&1,2,3\\
7&k\leq 5\times 10^6&20&1,2,3,6\\
8&&41&1\sim 7
\end{array}
$$ （更多…） -
AtCoder AGC058D – Yet Another ABC String – 题解
AGC058D – Yet Another ABC String
将 $\mathtt{A,B,C}$ 换成 $0,1,2$。记 $a,b,c$ 是题面中 $\mathtt{A,B,C}$ 的数量，$n=a+b+c$。我们称位置 $i$ 不合法，当且仅当 $S_{i-2}+2\equiv S_{i-1}+1\equiv S_i\pmod 3$。将其视为两条边 $(i-2,i-1),(i-1,i)$，那么所有不合法的位置造成的连边将会形成若干条链。
考虑容斥。直接钦定指定数量的位置不合法，其方案是难以计算的。又因为容斥系数是 $(-1)^c$，$c$ 为钦定的非法位置数量，那么将整个串分成若干个部分分别计算方案，带上容斥系数相乘后累加，结果不变。故而尝试从上文的链入手：易得对于固定长度的一条链，能够连成它的非法位置集合不变。设 $f(l,0)$ 表示“大小为偶数，且能够连成长度恰为 $l$ 的链”的非法位置集合数量；$f(l,1)$ 则是大小为奇数。染色方案与位置集合方案是独立的；则设整个串按顺序被分成了链 $(l_1,l_2,\cdots,l_s)$（此处的“链”长度均不小于 $3$），答案即为
$$\sum_{(l_1,\cdots,l_s)}\operatorname{染色方案数}\left((l_1,\cdots,l_s)\right)\prod_{i=1}^s\left((-1)f(l_i,1)+f(l_i,0)\right)$$ （更多…） -
MOCK quasi-PTS 20221214 日志
NOIP+？准省选难度？已经到了能力的边缘么？
但有点奇怪的是，这三道题的思考方向全部正确，T1 甚至只差临门一脚了；可惜部分分给得不那么让人舒服。
另外，这种“为了卡常而卡常”的时间限制着实令人不适；尤其是当 CWOI 的评测机本身配置落后的情况下。不过这也反过来使得我重新开始关注更底层的常数优化。
简略题解
A – 种花
-
CF1747E – List Generation – 题解
这道破题拖了我整整一天。
代数推导
转化为容斥模型
题目所给限制可以表述为，$a$ 和 $b$ 均为单调不降的序列，长度相等（记为 $k$），且 $a_1=0,a_k=n,b_1=0,b_k=m,\nexists i\in[2,k],a_i=a_{i-1}\land b_i=b_{i-1}$。
考虑差分序列 ${a_i}’=a_i-a_{i-1}\quad(i\in[2,k])$，${b_i}’$ 同理，它与原序列形成双射。于是不存在 ${a_i}’={b_i}’=0$ 的差分序列合法。考虑 $\sum_{i=2}^{k}{a_i}’=n$，也就是和为 $n$ 的 $k-1$ 元线性方程组的一组非负整数解；$b’$ 同理。容易计算“钦定至少有 $c$ 个位置不合法”的方案数——利用容斥原理即可得到长为 $k$ 的合法序列对个数为
$$\sum_{c=0}^{k-2}\binom{k-1}{c}\binom{n+(k-1)-1-c}{(k-1)-1-c}\binom{m+(k-1)-1-c}{(k-1)-1-c}(-1)^c$$ 答案累加上式结果 $\times k$。 （更多…）