一个明知很荒唐，却又在脑海中挥之不去的念头：
明年也没进队的话，就仗着那辆单车，单骑走天下。“来都来了，总得去看看雄壮的自然力造就的山河、千年的历史积淀成的城邦”，应该是这样想的吧。
不过，就算接下来的十数年里什么都还算如愿，“骑着车环游世界”是一定要做的。在已经老得蹬不动踏板之前。
作者： NGC5457
-
写在前面
既然是“随笔”，那我就写得随便些吧。
稍微处理了一下博客后台，这个分类没法从首页或者其他什么方式找到；链接是访问这里的篇目的唯一方式。如果真的有兴趣读完鄙人每天的胡思乱想，甚至在文章最下面留下一点见解，或者发表些尖锐的批评，我会非常感激的。
（其实上面一段话都改来改去好几回，虽说总是提醒自己注意文法和遣词造句，总有些矫枉过正的感觉。尤其是连“随”笔都要这么改……算了，口水话就口水话吧。）
-
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}
$$ （更多…）