OI

扩展欧拉定理揭示了对于任意模数 nn,有 abmodn={ab,b<φ(n)abmodφ(n)+φ(n),otherwise. a^b\bmod n=\begin{cases} a^b,&b<\varphi(n)\\ a^{b\bmod \varphi(n)+\varphi(n)},&\text{otherwise} \end{cases}.

我们又知道若分解质因数 x=picix=\sum p_i^{c_i},则 φ(x)=x(pi1)/pi\varphi(x)=x\prod (p_i-1)/p_i。则若 x>1x>1,若 2x2\mid xφ(x)x/2\varphi(x)\leq x/2;否则,2φ(x)2\mid\varphi(x)。记 φ(k)(x)=φ(φ(φ(k layersx)))\varphi^{(k)}(x)=\underbrace{\varphi(\varphi(\cdots\varphi(}_{k\text{ layers}}x)\cdots)),则 O(logn)\newcommand\bigO{\operatorname{O}}\bigO(\log n) 级别的 kk 就能使其收敛到 11

因此对于 Z/nZ\mathbb{Z}/n\mathbb{Z} 上的超-4运算 a1a2a3a_1^{a_2^{a_3^{⋰}}},结合扩展欧拉定理得到,在指数塔的 O(logn)\bigO(\log n) 层就将得到 modφ(1)+φ(1)1\bmod\varphi(1)+\varphi(1)\equiv 1 的指数。从而它是收敛的。 (更多…)

More
  • 2023年11月30日

维护连通块

现有一棵 nn 个节点的树。我们构建一最小的连通块 S(l,r)S(l,r),包含编号在 [l,r][l,r] 中的所有节点。多次询问,每次对于任意一对 [l,r][l,r],询问关于这连通块的信息。

如果可以离线/可持久化,此类问题有一通用思路:用扫描线维护“rr 固定时不同 ll 构成连通块的信息”。若 [p,q][l,r][p,q]\subseteq[l,r],则 S(l,r)S(p,q)S(l,r)\supseteq S(p,q);对于一固定的 rr,我们维护 ll 分别取 r,r1,,1r,r-1,\cdots,1(向左拓展)时,连通块的增量。对于点 xx,我们记录 tr(x)t_r(x) 表示 rr 固定时使得 xS(l,r)x\in S(l,r) 的最大的 ll。假设已经对于 rr 维护好了;现在拓展到 r=r+1r’=r+1

x{r,r+1}x\notin \{r,r+1\},则 tr+1(x)tr(x)t_{r+1}(x)\neq t_{r}(x)

  • xxrrr+1r+1 的简单路径上,且
  • tr+1(x)=rt_{r+1}(x)=r

的充分必要条件。

考虑任意 ll。由于 SS 是极小的,故将 r+1r+1“加入”S(l,r)S(l,r) 得到 S(l,r+1)S(l,r+1)需找到 r+1r+1 和连通块在树上最接近节点之间的路径,将路径上所有点加入连通块;由树的性质,此路径是通向 [l,r][l,r] 中任意节点的必经之路,也即 r,r+1r,r+1 的最短路径的某一前缀。又当 l=rl=r 时,S(l,r+1)S(l,r+1) 就是该路径本身;再有 [p,q][l,r]S(l,r)S(p,q)[p,q]\subseteq[l,r]\Longrightarrow S(l,r)\supseteq S(p,q),故本命题得证。

因此,我们需将整条路径上的点的最大出现时间整体覆盖tr+1(x)=rt_{r+1}(x)=rr+1r+1 本身除外,它是 tr+1(r+1)=r+1t_{r+1}(r+1)=r+1)。可以使用珂朵莉树和树剖维护连续的 t(x)t(x) 相同的一段。设 ΦΦ 表示连续段个数。每次覆盖操作会对 O(logn)\newcommand\bigO{\operatorname{O}}\bigO(\log n) 条重链执行“删除若干连续段,加入 O(1)\bigO(1) 个连续段”的操作。又 ΦnΦ\leq n,则 ΦΦ 的总变化量是 O(nlogn)\bigO(n\log n) 的。因此若用对数级别有序关联式容器(如 std::map),总时间复杂度为 O(nlog2n)\bigO(n\log^2 n)(更多…)

More
  • 2023年11月30日

题意简述

给定不含重边的有向图 GG,设其邻接矩阵为 AA,定义其元素的“加”为逻辑或,“乘”为逻辑与。问 Ac,c=1,2,A^c,c=1,2,\cdots 在何时出现循环节(c=kc=k),以及最小循环节长度 dd(即,Ak=Ak+dA^k=A^{k+d}k,dk,d 均最小)。

题意转化

在原图上,从 uu 出发,可用恰 bb 步走到 vv,则在 bb 次迭代后的图上有有向边 (u,v)(u,v)。问最少迭代多少次后图的形态出现循环节。

强连通图的所有环环长的最大公约数

任意找一点 uu,只需考虑经过 uu 的所有环。

考虑有一不经过 uu 的环,其长为 aa;另有一经过所有点的环(本图强连通),其长为 bb。则有 gcd(a,b,a+b)=gcd(a,a+b)\gcd(a,b,a+b)=\gcd(a,a+b)

我们任意找一棵本图的搜索树。设其根为 uu。设节点 vv 的深度为 dep(v)\newcommand\dep{\operatorname{dep}}\dep(v)。设某经过 uu 的有限长度的环依次经过了非树边(横叉边、返祖边) (v1,w1),(v2,w2),,(vt,wt)(v_1,w_1),(v_2,w_2),\cdots,(v_t,w_t)。那么其环长在答案中可以被 gcd(dep(vi)+1dep(wi),i{1,2,,t})\gcd(|\dep(v_i)+1-\dep(w_i)|,i\in\{1,2,\cdots,t\}) 取代。

可得 wiw_i 一定是 vi+1v_{i+1} 的祖先。我们删去 (v1,w1)(v_1,w_1),得到另一个环;这环与原来环的长度差为 dep(w1)dep(v1)1\dep(w_1)-\dep(v_1)-1。这两环均在答案中作出贡献;又由于 gcd(a,b)=gcd(a,ba)\gcd(a,b)=\gcd(a,b-a),则我们将原来的环长等价替换为两个数:其一即 dep(w1)dep(v1)1|\dep(w_1)-\dep(v_1)-1|,其二为现在的环长。再继续删除 (v2,w2),(v_2,w_2),\cdots,便等价地换为 t+1t+1 个数。

因此我们遍历一遍搜索树,就可以在 O(nlogn)\operatorname{O}(n\log n) 的时间内求出所有环环长之 gcd\gcd(更多…)

More
  • 2023年11月22日

题意简述

给定长为 nn 的序列 aa。要求支持以下操作:

  • 给定 l,r,xl,r,x,将 ai,lira_i,l\leq i\leq r 全部加上 xx
  • 给定 l,r,xl,r,x,将 ai,lira_i,l\leq i\leq r 全部乘以 xx
  • 给定 l,r,xl,r,x,若这是第 kk 次操作,则保护 ai,lira_i,l\leq i\leq r 直到第 k+xk+x 次操作(含),这期间操作 1,21,2aia_i 无效。若 aia_i 已经被保护到 x,x>k+xx’,x’>k+x,则这一保护不会失效。
  • 给定 l,rl,r,输出 i=lrai\sum_{i=l}^{r} a_i,对 109+710^9+7 取余。

n,m2×105n,m\leq 2\times 10^5

半群、双半群模型——线段树到底能维护怎样的信息?——caijianhong 的博客园

(更多…)

More
  • 2023年10月27日

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

我们有非常易于理解的暴力解法:直接对于 b=3,4b=3,4\cdots,求出所有可以当作底数的 aa,计算 aba^b 后放入数据结构/排序去重;特别处理 b=2b=2 的情况即可。在此不再赘述。

不过,我们注意到若有正整数 xx,满足 x>1,x=a0b0  (a0,b0N)x>1,x=a_0^{b_0}\ \ (a_0,b_0\in \mathbb N),且 a,bN,a0ab\forall a,b\in\mathbb N,a_0\neq a^b(即底数 a0a_0 不可再开根),那么 b,bb0,x=(a0b0/b)b\forall b,b\mid b_0,x=(a_0^{b_0/b})^b。这意味着假如不去重地暴力添加 nb\lfloor\sqrt[b]{n}\rfloor 到答案中,上文中 xx 将被算 {bb00(modb)}|\{b\mid b_0\equiv 0\pmod b\}| 次。

于是这就变成莫反的模板题了:记 g(b)g(b) 表示“能被 aba^b 表出的 xx 之数量”,f(b0)f(b_0) 表示“恰能被 x=a0b0x=a_0^{b_0} 表出,不可被 x=ab,b<b0x=a^b,b<b_0 表出的 xx 的数量”。易得 g(b)=bb0f(b0)g(b)=\sum_{b\mid b_0}f(b_0),故 f(b0)=b0bg(b)μ(b/b0)f(b_0)=\sum_{b_0\mid b}g(b)\mu(b/b_0)。显然,当 b>log2nb>\log_2 n 时仅有 a=1a=1 满足 abna^b\leq n,故我们只需计算 log2n\lfloor\log_2 n\rfloorbb,最后特判 a=1a=1。预处理出 μ\mu 的值,暴力求取反演式,复杂度为 O(log2n)\operatorname{O}(\log^2 n)


其实并不需要这么麻烦。我们根本不需要反演:根据 g(b)=bb0f(b0)g(b)=\sum_{b\mid b_0}f(b_0),假若 b0,b0>b,f(b0)\forall b_0,b_0>b,f(b_0) 都已经计算完成,那么我们直接得到 f(b)=g(b)bb0,b0>bf(b0)f(b)=g(b)-\sum_{b\mid b_0,b_0>b}f(b_0)。由 bb 从大往小计算即可,复杂度相同。

More
  • 2023年3月10日

本文将简单推导两种方式进行的离散傅里叶变换,用另种视角解释并优化算法。参考了 Seniorious yhx-12243 的 NTT 到底写了些什么(详细揭秘) 一文、OI Wiki 快速傅里叶变换 条目 和 rushcheyo 转置原理及其应用 讲稿。

离散傅里叶变换

我们计算数列 {an}\{a_n\} 的离散傅里叶变换 DFT(a,n)k=j=0n1aje2πinkj \newcommand\DFT{\operatorname{DFT}}\DFT(a,n)_k=\sum_{j=0}^{n-1}a_j\mathrm{e}^{\frac{-2\pi\mathrm{i}}{n}kj}

卷积定理循环卷积得到,我们对同样长为 nn 的数列 {bn}\{b_n\}DFT\DFT,并令数列 ck=DFT(a,n)kDFT(b,n)kc_k=\DFT(a,n)_k\DFT(b,n)_k,则有 IDFT(c,n)k=j+qk(modn)ajbq \newcommand\IDFT{\operatorname{IDFT}}\IDFT(c,n)_k=\sum_{j+q\equiv k\pmod n}a_jb_q

于是我们可以利用该原理实现常规意义下的数列卷积:有长为 nn 的数列 {an}\{a_n\},长 mm 的数列 {bm}\{b_m\},则将 a,ba,b 高位补 00,分别作 n+m1n+m-1 位的 DFT\DFT,点值相乘后 IDFT\IDFT 即可得到 ck=i+jk(modn+m1)aibj=i+j=k0i<n0j<maibjc_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=i=0n1aiωnik\DFT(a,n)_k=\sum_{i=0}^{n-1}a_i\omega_n^{ik} 的定义,其中 ωn=exp(2πi/n)\omega_n=\exp(2\pi\mathrm{i}/n),即 nn 阶单位根。 (更多…)

More
  • 2023年2月23日

近一个月来第一次赛时通过一道题。真是可喜可贺。

A – 单调

一开始以为与网络流相关;后来考虑 DP;结果是个贪心或者乱搞。

题意简述

给定长为 n  (n105)\newcommand\bigO{\operatorname{O}}n\ \ (n\leq 10^5) 的序列 ai,ai{1,2,3}\langle a_i\rangle,a_i\in\{1,2,3\}。匹配尽可能多的子序列,每个子序列均为 1,2,3\langle 1,2,3\rangle3,2,1\langle 3,2,1\rangle,且一个位置最多被一个子序列占用。求最大匹配数。 (更多…)

More
  • 2023年2月9日