图论 / 数论 / 比赛日志

MOCK PTS- 20231122 B – 迷失 – 强连通图所有环长度之最大公约数

题意简述

给定不含重边的有向图 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)+1−dep⁡(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,b−a)\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⁡(nlog⁡n)\operatorname{O}(n\log n) 的时间内求出所有环环长之 gcd⁡\gcd。 （更多…）

More
  • 2023年11月22日
数据结构 / 比赛日志

MOCK NOIP 20231027 T2 – 缺金木 – 线段树的“双半群”模型

题意简述

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

  • 给定 l,r,xl,r,x，将 ai,l≤i≤ra_i,l\leq i\leq r 全部加上 xx；
  • 给定 l,r,xl,r,x，将 ai,l≤i≤ra_i,l\leq i\leq r 全部乘以 xx；
  • 给定 l,r,xl,r,x，若这是第 kk 次操作，则保护 ai,l≤i≤ra_i,l\leq i\leq r 直到第 k+xk+x 次操作（含），这期间操作 1,21,2 对 aia_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,m≤2×105n,m\leq 2\times 10^5。

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

（更多…）

More
  • 2023年10月27日
数论 / 题解

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

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

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

不过，我们注意到若有正整数 xx，满足 x>1,x=a0b0  (a0,b0∈N)x>1,x=a_0^{b_0}\ \ (a_0,b_0\in \mathbb N)，且 ∀a,b∈N,a0≠ab\forall a,b\in\mathbb N,a_0\neq a^b（即底数 a0a_0 不可再开根），那么 ∀b,b∣b0,x=(a0b0/b)b\forall b,b\mid b_0,x=(a_0^{b_0/b})^b。这意味着假如不去重地暴力添加 ⌊nb⌋\lfloor\sqrt[b]{n}\rfloor 到答案中，上文中 xx 将被算 ∣{b∣b0≡0(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)=∑b∣b0f(b0)g(b)=\sum_{b\mid b_0}f(b_0)，故 f(b0)=∑b0∣bg(b)μ(b/b0)f(b_0)=\sum_{b_0\mid b}g(b)\mu(b/b_0)。显然，当 b>log⁡2nb>\log_2 n 时仅有 a=1a=1 满足 ab≤na^b\leq n，故我们只需计算 ⌊log⁡2n⌋\lfloor\log_2 n\rfloor 个 bb，最后特判 a=1a=1。预处理出 μ\mu 的值，暴力求取反演式，复杂度为 O⁡(log⁡2n)\operatorname{O}(\log^2 n)。

其实并不需要这么麻烦。我们根本不需要反演：根据 g(b)=∑b∣b0f(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)−∑b∣b0,b0>bf(b0)f(b)=g(b)-\sum_{b\mid b_0,b_0>b}f(b_0)。由 bb 从大往小计算即可，复杂度相同。

More
  • 2023年3月10日
多项式 / 算法

再探 FFT – DIT 与 DIF，另种推导和优化

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

离散傅里叶变换

我们计算数列 {an}\{a_n\} 的离散傅里叶变换 DFT⁡(a,n)k=∑j=0n−1aje−2π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+q≡k(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+m−1n+m-1 位的 DFT⁡\DFT，点值相乘后 IDFT⁡\IDFT 即可得到 ck=∑i+j≡k(modn+m−1)aibj=∑i+j=k0≤i<n0≤j<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=0n−1aiω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日
数论 / 比赛日志

MOCK quasi-PTS 20230209 日志

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

A – 单调

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

题意简述

给定长为 n  (n≤105)\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\rangle 或 ⟨3,2,1⟩\langle 3,2,1\rangle，且一个位置最多被一个子序列占用。求最大匹配数。 （更多…）

More
  • 2023年2月9日
组合数学 / 题解

洛谷题库 P6031 Cards 加强版 – 题解与思路重现

洛谷题库 P6031 Cards 加强版

对于每一轮对局的 m!m! 种排列，对于编号为 aa 的牌，恒有 (m−1)!(m-1)! 种是以牌 aa 为首的。因此一轮可以归为 mm 种情况，首张为王牌的概率为 1m\frac{1}{m}。

这是某场模拟考试给出的部分分： SubtaskConstraintsPointsDependencies1n,m,k≤522k=123k≤5000101,24m≤1001015n≤k56k≤105101,2,37k≤5×106201,2,3,68411∼7 \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} （更多…）

More
  • 2023年1月31日
数据结构 / 算法

高维莫队

我们可以将莫队算法从一维扩展到更高维度。

考虑正在维护 kk 维结构的信息，且每一维的大小分别为 n1,n2,⋯ ,nkn_1,n_2,\cdots,n_k。为了下文叙述方便，我们将维度大小序列复制一份，得到 nk+1,⋯ ,n2k(ni=ni−k)n_{k+1},\cdots,n_{2k}\quad(n_i=n_{i-k})。我们同时维护 2k2k 个指针，第 i  (i≤k)i\ \ (i\leq k) 个指针维护第 ii 维左端点，第 i  (k<i≤2k)i\ \ (k<i\leq 2k) 个指针维护第 i−ki-k 维右端点。按询问处理顺序依次移动到每个询问对应的位置上。 （更多…）

More
  • 2023年1月24日
字符串 / 数据结构 / 比赛日志

MOCK quasi-PTS 20230102 日志

又来了，要不然差临门一脚要不然是编译器出锅悬置指针导致了看似非常不合理的 undefined behavior。这已经不是简单的 frustration 了，要是考场上遇到这种根本没办法查出来的语言相关问题，不就三年 OI 一场空了么？

不过，正是因为考试前从没“用过”悬置指针，才会诱发这样的问题。这再次提醒我们，考场上千万不要使用不熟悉的语法糖，使用平时经大量验证的写法，纵使排版稍欠美观、或代码量增长少许，也是稳定而完备的。

不得不说，这几场“主题模拟赛”的题面中，唯这一场是最上心的。既将足球相关术语用平易近人的方式融合进题面里，又不使其过分冗长而消磨选手耐心。 （更多…）

More
  • 2023年1月23日
成都外国语学校高二 OIer。喜欢搞些杂七杂八的小项目。常去骑车。复健中，脚力已不如前。

一言(ひとこと)

暫し空に祈りて 愛を断て

分类