UOJ Logo ljt12138的博客

博客

一个有趣的问题和其扩展

2019-06-03 20:18:09 By ljt12138

在监考十二省联考的时候,我们发现排座位是一件非常麻烦的工作。由于主办单位需求的不同,例如成绩较好的靠前、同一学校的分开、成绩较好的分开、保证一定的随机性等等,我们需要用非常复杂的逻辑安排座位。事实上我们使用了一个简单的爬山,每次随机选择两个学生,如果交换可以使得代价函数降低就交换。

之后为了应付某图论应用技术报告我考虑了一个简化的问题,如果在 $n\times m$ 的网格图上分配座位,有 $n\times m$ 个选手来自 $k$ 个学校,其中第 $i$ 个学校有 $a_i$ 人,该如何分配座位使得任意相邻的两人都来自不同的学校。其中一个座位和其前后左右至多四个座位相邻。这个问题的证明是相对容易的,不过稍加改进便可以推广到任意维立方体的情景。

Theorem. 当且仅当 $\max\{a_i\}\le \lceil \frac{n\times m}{2} \rceil$,存在合法的座位安排方案。

Proof. $(\Leftarrow)$ 容易构造出使用尽可能多的 $1\times 2$ 的骨牌覆盖棋盘的方案,使得要么每个位置都被覆盖,要么仅存在一个单独的位置。整个棋盘被划分为了 $\lceil \frac{n\times m}{2} \rceil$ 组。如果一个学校人数超过一半,根据鸽巢原理,必然有一组中存在两个该学校的人,因而不存在合法的座位安排方案。

$(\Rightarrow)$ 我们希望说明一旦人数最多的学校人数不超过一半,就必然存在合法的座位安排方案。考虑直接构造。首先,若仅有两个学校,由于两者的人数都不超过 $\lceil \frac{n\times m}{2} \rceil$,因此他们必然分别具有 $\lceil \frac{n\times m}{2} \rceil$ 和 $\lfloor \frac{n\times m}{2} \rfloor$ 位选手。将棋盘黑白染色,我们可以将一个学校的人安排在黑色点,另一个学校的人安排在白色点,从而任意两个同校选手必然不相邻。

当学校个数超过 $2$ 时,我们先将所有选手分成人数相等(或差1)的两组,使得仅存在不超过一个学校,满足其选手被分到了两组中。若这样的学校不存在则证完了,否则不妨设这个学校编号为 $i$。由于我们可以将人数最多的学校分配到组 $A$,将人数第二多的学校分配到组 $B$,因此 $i$ 号学校至多是人数第三多的学校,从而其人数不超过 $nm/3$。另一方面,学校 $i$ 被分配到组 $A$ 的人数 $p$ 不超过 $nm/4$,被分配到组 $B$ 的人数 $q$ 也不超过 $nm/4$。

不妨设组 $A$ 有 $\lceil \frac{n\times m}{2}\rceil$ 人,组 $B$ 有 $\lfloor \frac{n\times m}{2} \rfloor$ 人,$(0,0)$ 是黑色点。我们只需将学校 $i$ 的 $p$ 人分配到黑色点,将另外 $q$ 人分配到白色点,使得任意两人不相邻,那么将 $A$ 中的其余人任意分配到黑色点上,$B$ 中的其余人任意分配到白色点上便完成了构造。

考虑这样的构造方案,我们首先从 $(0, 0)$ 开始,逐行逐列将 $p+q$ 人依次分配到黑色点中,然后将最后 $q$ 人向下移动一行。一旦满足:

$$ \frac{(n-1)m}{2} \ge p+q $$

这样的方案就一定可行。而这成立只需:

$$ \frac{(n-1)m}{2} \ge \frac{nm}{3} \iff n \ge 3 $$

根据对称性,一旦 $n\ge 3$ 或者 $m\ge 3$ 便立刻有合法的分组方案,因而也有构造方案。而 $n,m\le 2$ 的情景是平凡的,这就完成了证明。

Theorem. 当 $n\ge 144$ 或存在 $x_i\ge 3$ 时,对于 $x_1\times x_2\times x_3\times \dots \times x_n$ 的超立方体,存在合法的座位安排方案当且仅当:

$$ \max\{a_i\}\le \left\lceil \frac{\prod_i x_i}{2} \right\rceil $$

Proof. 稍加改进便可以知道,如果人数最多的学校人数超过一半仍然不存在方案,并且一旦某个 $x_i\ge 3$,之前的证明仍然成立。下面只需证明 $x_i = 2$ 的情况成立即可。

不妨将所有的位置映射到长度为 $n$ 的 $01$ 串,我们仍然希望将学校 $i$ 的 $p+q$ 个人合理安排,使得 $p$ 个人和另外 $q$ 个人不相邻。考虑这样的构造方案,将 $2^n$ 个不同的位置按照其中 $1$ 的个数分组,分为了大小分别为:

$$ {n\choose 0}, {n\choose 1}, \dots, {n\choose k}, \dots, {n\choose n} $$

的 $n+1$ 组。不失一般性我们设 $p\ge q$,于是前 $p$ 人从前向后选择具有偶数个 $1$ 的组,后 $q$ 人从后向前选择具有奇数个 $1$ 的组。我们只需说明,他们选择的组之中一定存在一个“分割”,保证他们不会选择相邻的组,从而更不会仅相差 $1$。下面用反证法。如若他们“触碰了”,即分配到 $A$ 组的 $p$ 个人占用了组:

$$ {n\choose 0}, {n\choose 2}, {n\choose 4}, \dots, {n\choose i} $$

而分配到 $B$ 组的 $q$ 个人占用了组:

$$ {n\choose i+1}, {n\choose i+3}, \dots {n\choose n-1} (or\ {n\choose n}) $$

那么一定有:

$$ \begin{align} \frac{2^n}{3}\ge p+q &\ge {n\choose 0} + {n\choose 2} + \dots + {n\choose i-1} + 1 + 1 + {n\choose i + 4} + {n\choose i + 6} + \dots + {n\choose n-1}(or\ {n\choose n})\\ &\ge {n\choose 0} + {n\choose 2} + \dots + {n\choose i-1} + 1 + 1 + {n\choose i + 5} + {n\choose i + 7} + \dots + {n\choose n}(or\ 0)\\ &\ge 2^{n-1} - 2\times \frac{2^n}{\sqrt{n+1}} \end{align} $$

要有这一点至少有:

$$ \frac{2^n}{3}\ge 2^{n-1} - 2\times\frac{2^n}{\sqrt{n+1}}\iff n\le 143 $$

thx

lkmcfj 提供了第一个定理证明中构造放置方案的方法(另一种简单的构造方案只能给出$m\ge 6$的界),CommonAnts 指出了第二个定理证明中构造放置的方案的方法。

hack

程序似乎写错了,现在 $n\le 12$ 这样的方案不一定能保证有解,但是原问题对 $n\le 4$ 都是有解的。

似乎后一个问题的证明完全有问题...找时间修一下吧orz

fix: 现在只能保证 $n\ge 144$ 是没有问题的..所以还是不知道小的情景怎么说明。

feat: 使用计算机改进第二个定理对组合数的估计可以说明,$n\ge 91$ 总是有解的。

RMQ标准算法和线性树上并查集

2019-02-17 17:29:30 By ljt12138

Stage0

某天深夜水群的时候给小朋友普及Tarjan算法求LCA的时间复杂度,被老鸽们指正应当是$O(n+q)$而非$O(n+\alpha(q))$。最近阅读了一下wiki上指出的论文 https://core.ac.uk/download/pdf/82125836.pdf 学习了一下。

先放结论:RMQ问题和LCA问题的最优复杂度都是$O(n)-O(1)$的,线性复杂度的Tarjan需要做一些操作。

Stage1 : RMQ标准算法

通常我们所说的RMQ问题,即区间最值问题被描述为:给定一个数组和若干询问,每次询问一段区间中最小值/最大值。我们常常使用ST表或线段树来解决这样的问题,复杂度分别是$O(n\log n)-O(1)$和$O(n)-O(\log n)$。$O(f(n))-O(g(n))$表示预处理时间复杂度为$O(f(n))$,每次询问时间复杂度为$O(g(n))$。事实上,存在$O(n)-O(1)$的RMQ算法,这样的算法通常称为RMQ标准算法。

RMQ标准算法有三个步骤:

  1. 建立序列的笛卡尔树,将RMQ问题转化成LCA问题
  2. 通过树的欧拉序列,将LCA问题转化为±1 RMQ问题
  3. 通过分块ST表解决±1 RMQ问题

为了方便,我们之后所有的讨论都为求区间最小值。

建立笛卡尔树

序列的笛卡尔树被定义为:最小值所在的位置作为根,其左侧区间的笛卡尔树作为左孩子,右侧区间的笛卡尔树作为右孩子的一棵树。假设我们拥有了一个序列的笛卡尔树,一个很明显的自顶向下寻找$[u, v]$区间最小值的算法如下:

  1. 如果第一个点在当前节点左侧,第二个点在当前节点右侧,则根节点就是区间最小值
  2. 如果在同一侧,则递归到该侧查询

我们事实上是在求$u,v$在笛卡尔树上的LCA。那么,$[u,v]$之间的区间最小值的位置,就是$u, v$在笛卡尔树上LCA所表示的位置。

笛卡尔树可以被线性的建立。我们每次在序列右端新增一个节点,并维护笛卡尔树最右端的点$rm$。对于每个节点$u$,我们维护其父亲$fa[u]$和其左右儿子$lc[u], rc[u]$。新增一个节点$nd$时,我们将其设为$rm$的右孩子。之后,利用平衡树的旋转操作,不断向上旋转,直到$nd$的父亲的值比其小为止,最后将$rm$设为$nd$。由于将$nd$向上旋转不会破坏序列的左右顺序,也不会破话除$nd, fa[nd]$两个节点之外父子的大小关系,最终得到的一定是原序列合法的笛卡尔树。

我们称$nd, rc[nd], rc[rc[nd]], ...$为笛卡尔树最右端的链,由于最右端的链长每次最多增加1,而每次向上旋转会使得其长度减小$1$,那么旋转的总次数是$O(n)$的,因而建立笛卡尔树的复杂度也是$O(n)$的。

转化为±1 RMQ问题

一个常见的求LCA的算法是转而求解树的欧拉序列上的RMQ问题。所谓欧拉序列,就是对树做dfs,每当访问一条边$(u,v)$时,就在序列上加入$v$。特别的,序列上一开始只有根节点。设每个节点$nd$出现的第一个位置为$pos[nd]$,那么,两个节点$u, v$的LCA,就是$[pos[u], pos[v]]$中最浅的节点。

欧拉序列良好的性质在于,任何两个相邻元素之间深度相差必然为$1$。那么问题便被转化为了,给定一个序列,任意两个元素之间相差为$1$,并给定若干个区间,求区间内最小的数。

±1 RMQ问题的线性解法

线性解决±1 RMQ问题的关键在于,由于相邻两个元素之差为1,那么长度为$n$的本质不同的数列只有$2^n$个。

考虑将序列按照长度为$\frac{\log(n)}{2}$分段,我们可以认为$\log(n)\le w$,$w$是计算机的字长(假设我们在随机储存器计算模型下)。长度为$\frac{\log(n)}{2}$的本质不同的数列只有$O(\sqrt{n})$个,我们可以枚举所有可能的情况,并枚举左右端点。这可以在$O(\sqrt{n}\log^2(n))$的时间复杂度内完成。一个数列长度为$n$的数列可以用二进制串编码,其第$j$位为$[a_j < a_{j+1}]$。

对于分成的$O\left(\frac{n}{\log(n)}\right)$段,使用ST表维护区间最小值。这样可以做到$O(n)$时间的预处理和$O(1)$时间的询问。

考虑一个区间询问$[u, v]$,可以看成一些整块和一些零散部分。对于整块,可以用ST表上$O(1)$询问最小值;对于零散部分,通过查表求出答案。这样,总共的询问时间复杂度是$O(1)$的,而所有预处理的复杂度都是$O(n)$的。因此,我们给出了$O(n)-O(1)$求解一般RMQ问题的解法。

Stage2 : 线性树上并查集

将Tarjan优化到线性的技术来源于线性树上并查集。树上并查集是并查集的一个特殊情况:给定一棵树,每次操作形如将一个节点合并到父亲,每次询问形如查询一个点已合并的祖先。

其一个更特殊的情景是当树退化成序列的情景:例如经典题目《花神游历各国》https://www.lydsy.com/JudgeOnline/problem.php?id=3211 的一个做法是利用并查集维护向右下一个不是$1$的元素。这可以看成一个以最右端节点为根的链上的并查集。

树上线性并查集的做法分为三步:

  1. 将树分为大小为$O(b)$的块,且块的个数是$O(n/b)$的
  2. 对于每种本质不同的块的本质不同的状态,预处理每个点的答案
  3. 对块间维护并查集

将树分块

正如题目《王室联邦》https://www.lydsy.com/JudgeOnline/problem.php?id=1086 中指出,我们可以对树在线性时间内分块,使得每一个块的大小在$[b, 3b]$之间,且每一个块有一个“根”。满足每个块$B$都与其根联通,且$B$在其根的子树内。

使用一个dfs过程可以将树分块。在dfs所有子树后,我们将子树中剩下的节点($\le b$个元素的零散块)合并,剩下至多一个零散块。这样可以保证,除了根节点可能有一个大小为$2b < size\le 3b$的块,其他的块大小都在$[b, 2b]$之间。

预处理

考虑本质不同的树至多有多少个,一棵树可以被父亲数组$parent[nd]$唯一确定,而$parent$数组可以被编码到长度$(b-1)\times \log b$,那么本质不同的树的上界就有$2^{(b-1)\log b}$种。对于每种本质不同的树,每一个节点可以被操作过,也可以没有被操作过,本质不同的状态有$2^b$个,那么每种本质不同的状态中每个节点的答案一共有:

$$2^{(b-1)\log b}\times 2^b\times b$$

如果我们取$b=\log\log n$,那么上式是$O(n)$的。

对块间维护并查集

我们对块间,即所有的“根”维护并查集。由于并查集的节点数只有$O(n/b)$,当我们取$b=\log\log n$时,总复杂度是$O(n/b\alpha(n)+q)=O(n+q)$的。

对于一个将节点合并到父亲的操作:可以$O(1)$修改块状态完成。

对于一个查询操作:如果当前块内已经合并到块的根了,向上查询。如果一个节点是某个块的根且合并到了其父亲,使用一个并查集合并上去。

这样,我们就在$O(n)-O(1)$的时间复杂度内解决了树上并查集问题!自然,Tarjan算法和花神游历各国的并查集部分都被加速到了线性。

Pollard-rho算法简要分析

2018-05-19 19:58:59 By ljt12138

Pollard-rho算法简要分析

标签(空格分隔): 数论


概述

Pollard-rho算法是质因数分解的一种有效的蒙特卡洛算法,可以在期望$O(n^{1/4})$的复杂度内找到合数的一个因数。其核心思想就是随机的选取$x\lt n$,试图找到一个$x|n$。但直接利用反复随机的方法是行不通的,为了提高效率,Pollard-rho算法依靠“生日悖论”来找到一个因数。

“生日悖论”

生日悖论是指$k$个人两两生日不同的概率,随着$k$的增长下降的非常快。如果在$n$个数中随机选取$k$个,其两两之差全不为一个常数$c$的概率为$O(\frac{1}{n^{k^2}})$,因而如果通过两两之差去“碰”一个数,只需要期望$k = O(\sqrt n)$次。考虑如果一个数$n$的最小质因子是$O(\sqrt n)$,其小于$n$的倍数有$\Omega (\sqrt n)$个,如果我们随机选取$k$个数,两两作差寻找,碰到的概率为$\Omega(\frac{1}{(\sqrt n)^{k^2}})$,这样只需要期望$k = O(n^{1/4})$次就可以找到一个因数。

弗洛伊德判环

考虑如何在$O(1)$的附加空间内沿着环走一周,考虑用两个指针,一个每次移动一步,一个每次移动两步,其位置差每次增加$1$,直到位置差为环长即两个指针相遇,则他们刚好绕环一周,且他们取遍了每一种可能的位置差。

Pollard-rho算法

Pollard-rho算法的核心是构造一个“随机的”函数:

$$f(n) = f(n-1)^2+1$$

我们要用这个函数生成随机数去“碰”一个质因数的倍数,设这个集合为$S$。

注意到$f(x)$在模$n$意义下必然会形成一个环。考虑$f(x)-f(y)=f^2(x-1)-f^2(y-1) = (f(x-1)+f(y-1))(f(x-1)-f(y-1))$,有一个$f(x-1)-f(y-1)$因子。因而如果$f(x-1)-f(y-1)\in S$,就有$f(x)-f(y)\in S$。而根据欧几里得算法$\gcd(x, n)=\gcd(n,x\bmod n)$说明了如果一个数与$n$有公因子,那么模$n$后也有。因为形成环,立刻可以得到对于任意的$x_1, y_1, x_2, y_2$,如果满足$|x_1-y_1| = |x_2-y_2|$,即他们在环上的位置差相等,那么$|f(x_1)-f(y_1)|\bmod n\in S \iff |f(x_2)-f(y_2)|\bmod n\in S$。

换言之,环上的二元组被其之间的距离划分为了若干个$O(k)$个等价类,$k$为环长。那么这显然可以用弗洛伊德判环快速的完成,事实上,弗洛伊德判环每一次移动,都相当于进行了$O(k)$次两两比较。因而最终复杂度就是$O(n^{1/4})$。

算法流程就是,每次随机一个初始解$f(0)$,通过$x=f(x), y = f(f(y))$进行弗洛伊德判环,直到$\gcd(|x-y|, n)\ne 1$找到一个约数,或者$x=y$算法失败。如果找到一个约数,递归的分解两边。为了防止大素数导致时间退化,需要先用$Miller-rabin$素数测试判断是否是素数。

update: 5.21

复杂度分析被hack掉了...详情见评论orz

经过一些实验,看起来使用偶数次多项式同余做$f(x)$要比使用奇数次多项式优秀得多,前者约为$n^{1/4}$,后者约为$n^{1/2}$

ljt12138 Avatar