NGC5457's Site

分类： OI

  • 无题

    （更多…）

  • MOCK PTS 20231127 B 数论题技巧拾贝

    （更多…）

  • 超-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 的博客园

    （更多…）

  • 2023 NOI 春季测试 T2 – 幂次 简略题解

    洛谷题库 P9118 [春季测试 2023] 幂次

    我们有非常易于理解的暴力解法：直接对于 $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$，且一个位置最多被一个子序列占用。求最大匹配数。 （更多…）