由于一些…我也不知道是什么原因吧,似乎 UOJ 现在干活的管理员只剩我和 AwD 了o(╥﹏╥)o,这次正好过年离 WC 比较近,我到家的时候离过年也没几天了,比赛这么鸽还是要道歉 = =
感谢本次救 UOJ 于题不全办不出比赛之中的各位出题人 laofu, matthew99, zhouyuyang, WuHongxun, Picks!
特别感谢将 E 题从 WC 的课件中移到 UOJ 的比赛中的 Picks 老师,牺牲了 WC 第一课堂上大家冬眠的时间,换来了一个超有趣的 E 题!
同时感谢 AwD 一天写出约 1 sdn (1 sdn = 11.7KB, 关于这一单位的来源见【集训队作业2018】蜀道难) 代码的精彩表演!
接下来是这场比赛的题解,这次的 A 题比往常的 Goodbye Round 的 A 题更难一点,这是因为 ABC 三个题都觉得挺好的有点舍不得扔,在 A 前面再加一个题又和传统不太符合。一直担心大家 A 题会出现惨案,不过从比赛中大家通过了 40 人并且大多数人都拿到了可观的分数(>0)这一点来看还是比较成功的!
新年的拯救计划
from laofu, 标程、数据和题解 by whzzt
最早AC: ridiculos (0:14:21)
最短提交: luhong 提交代码
算法一
手玩 $ n = 5, 6 $ 即可通过第一个子任务,期望得分 17 分。
算法二
直接套用求最多边不相交生成树的方法(见李煜东“图连通性若干问题探讨.pptx”),时间复杂度 $ O(n^4) $,期望得分 27 分。
算法三
显然我们会发现构造出的树的数量不超过 $ \lfloor \frac{n}{2} \rfloor $,因为一棵树有 $ n - 1 $ 条边。
咦这个 A 题怎么这么难?咦怎么有个 Subtask 部分分这么多?肯定是用来平衡题目难度造成的平均分下降的,总之就是这个部分分肯定很水!
容易发现,当 $ n $ 是素数时,$ \forall 0 \le k < n, \exists 0, k, 2k, 3k \ldots (n - 1)k $ 在$ \bmod n $ 意义下互不相同。我们可以构造 $ \lfloor \frac{n}{2} \rfloor $ 棵树,第 $ i $ 棵树只考虑满足 $ |u - v| = k $ 或 $ |u - v| = n - k $ 的边 $ (u, v) $,这样我们可以构造出 $ \lfloor \frac{n}{2} \rfloor $ 棵树,达到上界。
期望得分 44 分,结合之前的算法可以获得更高分数。
算法四
我们尝试构造一种恰好为 $ \lfloor \frac{n}{2} \rfloor $ 的方案,这意味着当 $ n $ 是偶数时所有边都会被用上。
如何构造 $ \lfloor \frac{n}{2} \rfloor $ 棵树?可以尝试先构造一棵树 $ T_0 $。接下来对于 $ T_0 $ 中的每条边 $ (u, v) $,我们向 $ T_i $ 中添加边 $ ((u + i) \bmod n, (v + i) \bmod n) $。我们定义一条边 $ (u, v) (u < v) $ 的长度为 $ \min(v - u, u - v + n) $,那么在 $ T_0 $ 中一定恰好包含了 $ 2 $ 条长为 $ 1 $ 至 $ \frac{n}{2} - 1 $ 的边和一条长为 $ \frac{n}{2} $ 的边。
考虑提出那条长为 $ \frac{n}{2} $ 的边,不妨假设其端点为 $ 1 $ 和 $ \frac{n}{2} + 1 $,我们只要让 $ 1 $ 和 $ 2 $ 至 $ \frac{n}{2} $ 之间的点连边,$ \frac{n}{2} + 1 $ 和 $ \frac{n}{2} + 2 $ 至 $ n $ 之间的点连边即可。
当 $ n $ 是奇数,我们可以采用同样的构造,容易发现是合法的。
当然本题的构造方法有多种,一些不同的方法也可以通过 = =
新年的Dog划分
from matthew99, 标程和数据 by matthew99, 题解 by whzzt
最早AC: peehs_moorhsum (1:23:44)
算法一
注意到图是二分图时,若我们将图划分成两个非空部分 $ A $ 和 $ B $,只保留图中 $ A $ 和 $ B $ 之间的边并进行询问,一定有至少一组这样的 $ A $ 和 $ B $ 返回的结果是联通。
考虑返回值为联通的情况。不妨假设最终二分图两侧的点集分别为 $ S $ 和 $ T $,其中 $ S \cap A \ne \emptyset $,若 $ T \cap A \ne \emptyset $,那么 $ S \cap A $ 和 $ T \cap A $ 不可能联通。因此会有 $ T \cap A = \emptyset $,同理 $ S \cap B = \emptyset $,于是有 $ S = A, T = B $。
因此当图是二分图时,我们只要枚举点集进行询问即可。
询问次数 $ 2^n $,期望得分 13 分。
算法二
为了获得最终二分图的两部分,我们尝试获得原图的一棵生成树。
我们可以考虑尝试删掉二分图中所有的边,如果一条可能的边删除后连通性发生了改变,我们就保留这条边,否则删去这条边。最终图中一定会剩下恰好 $ n - 1 $ 条边,它们构成了一个生成树。
于是我们只要将生成树黑白染色就可以得到二分图的一个部分了。
询问次数 $ \frac{n(n - 1)}{2} $,期望得分 37 分。
算法三
刚刚的寻找生成树的方法实在是太暴力了,我们可以对刚刚的方法进行一些优化:二分查找下一次保留边会发生在什么时候。由于这样的事件只会发生 $ n - 1 $ 次,我们只需要进行这么多次二分。
注意到我们找到了原图的一个生成树,只靠这个生成树是可以让原图联通的。那么我们可以保留生成树上的边,删去其它连接二分图两侧的边。如果图不是二分图,那么图中一定存在环,于是一定存在剩余的某条树边删去后仍然连通。
每次二分需要 $ \log(n^2) = 2 \log n $ 左右次查询,因此询问次数 $ 2 n \log n $,期望得分 67 分。
算法四
为了去掉 2 的常数,我们需要将对边二分优化为对点二分。
考虑从 1 号点开始,使用 BFS 进行上述过程,就只要对点二分了。
询问次数 $ n \log n $,期望得分 100 分。
新年的小黄鸭
from zhouyuyang, 标程、数据和题解 by zhouyuyang
最早AC: supy (3:06:13)
算法负二
大胆猜想直接树剖答案最优。
获得$0-5$分好成绩。
算法负一
大胆猜想在子树size过大的时候可以钦定重儿子。
获得$0-20$分好成绩。
算法零
大胆猜想在子树深度和过大的时候可以钦定重儿子。
获得$0-20$分好成绩。
算法一
直接暴力枚举哪些是重边。
时间复杂度$O(2^n\times n^2)$或$O(2^n\times n)$
算法二
假设我们已经知道了你的轻重边划分方案$T$,考虑如何计算答案。
显然如果一条边是轻边我们直接把它扔进$f(x)$里是没有问题的。
如果遇到了轻边,那么在这个轻边父亲节点向上的重链长度显然不会改变,也可以扔进$f(x)$里面
设$h(x,v1,v2)$表示在$x$号节点,已经确定在$f(x)$里的权值为$v1$,向上的连续重链长度为$v2$,子树内的最优解。
转移直接枚举重儿子,并且更新当前状态。
时间复杂度$O(n^4)$或$O(n^3)$
空间复杂度$O(n^3)$
算法三
观察DP状态,我们发现我们可以使用某些技巧干掉$v1$这一维。
我们考虑在产生$v1$贡献的时候,直接在这个节点将他的贡献算进答案,而不是在子树上每个节点上计算答案。
这样子直接设$h(x,v2)$表示在$x$号节点,向上的连续重链长度为$v2$,子树内的最优解。
转移仍然直接枚举重儿子。
时间复杂度$O(n^2)$
空间复杂度$O(n^2)$
算法四
继续观察DP状态,我们发现我们可以尝试只存下来$log_2v2$的值,这样子状态就变成$O(nlogn)$了。
转移我们枚举在$x$所在重链上第一个满足$f$的值不同于他的父亲节点的点,或者是叶节点,设其为$y$
观察算法三中的DP转移方程,不难发现在钦定重儿子的时候转移方程形如$h(y,v2+1)+\Sigma h(x到y路径上所有的轻儿子,0)+自己的权值 \to h(x,v2)$
因为在转移的重链上的点$f(x)$相同,所以我们可以假设这些点有点权,为$v(x)=\sum h(x父亲除了x之外的所有儿子)+自己附带的权值$
此时转移方程就可以看成路径点权和加上$y$子树的权值(如果$y$不是叶节点,否则为$0$)
对于叶节点的情况,我们可以维护$logn$颗动态开点线段树维护深度在某一范围内的叶节点的点权和最大值。
对于非叶节点的情况,不难发现合法转移只有$O(nlogn)$种,直接找到所有可能出现的情况,暴力转移。
非叶节点的点权和可以在确定$dfn$序之后使用树状数组维护。
时间复杂度$O(n\log^2n)$
空间复杂度$O(n\log^2n)$
算法五
出题人卡内存怎么办???
考虑通过一些操作把$log_2v2$拆开,使得他在他的$1$代祖先,$2$代祖先,$\dots$ ,$2^k$代祖先的地方恰好被算一次。
此时我们每个点的点权就唯一了,线段树就只需要一颗了。
其于基本同算法四。
时间复杂度$O(n\log^2n)$
空间复杂度$O(n\log n)$
算法六
from: matthew99
算法四,五我听不懂怎么办?
考虑对于每一个节点x维护一个分段函数表示$f[x]$
我们可以发现分段函数的段数的上界是$O(子树大小\times \log n)$的。
直接启发式合并维护即可。
时间复杂度$O(n\log^2n)$
空间复杂度$O(n\log n)$
算法七
from: matthew99
在审题的时候@whzzt说分段函数段数$O(子树深度\times \log n)$的。
此时在算法六的基础上套长链剖分,暴力合并,时间复杂度可以做到$O(n\log n)$
但是因为出题人 zhouyuyang和审题人whzzt太咕咕咕了,没有实现过这个算法,也没有想过算法细节。
时间复杂度$O(n\log n)$
空间复杂度$O(n\log n)$
新年的族谱树
from WuHongXun, 标程和题解 by AwD, 数据 by whzzt
whzzt: (;´д`)ゞ因为懒得写 spj 加了个权值,为了让问题描述看起来更合理一点加了一大堆废话= = 似乎大家没怎么看懂的样子
算法一
枚举族谱树所有的形态,找一个字典序最大的输出来。
时间复杂度不明。
算法二
怎样的老家族集合是合法的?
最终选择的集合确定了一棵有根树,选出的集合作为有根树的子树,两两之间要么是包含的,要么是分离的。
要求字典序最大的方案,也就是要尽量选择权值大的老家族的集合。
按照套路,显然可以得到一个简单的贪心:沿权值降序依次考虑每个集合,若它与之前选择的集合没有冲突,则选择该集合。
一共有 $O(nk)$ 个集合,每次判断合法性的时间复杂度为 $O(n^2)$ 。
使用 bitset 可以将判断合法性的复杂度优化至 $O(\frac{n^2}{w})$
时间复杂度为 $O(n^3k)$ 或 $O(\frac{n^3k}{w})$。
算法三
在后文中,我们将会把一类有根树称作族谱树 —— 族谱树的叶子节点都是元素,非叶节点都是一个包含了其子树中的元素的集合,每个非叶节点至少有两个孩子。
由于族谱树它真的是一棵树,因此并不用依次检测当前集合 $S$ 与树上的所有集合是否有冲突 —— 当 $S$ 合法时,考虑族谱树上最小的包含它的集合 $T$, $T$ 的每个孩子 $W_i$ 要么是 $S$ 的子集,要么与 $S$ 分离,并且是 $S$ 子集的孩子的并恰好是 $S$。
于是就可以提高判断合法性的效率了:
首先,找到包含 $S$ 的最小集合 $T$ —— 找到 $S$ 中的任意一个节点 $a$,考虑节点 $a$ 到根的链,一定是一串 $S$ 包含的集合接着一串包含 $S$ 的集合,因此可以简单的二分出 $T$。
对于 $S$ 中的每个元素 $a$,找到是它祖先也是 $T$ 的孩子的集合。这些集合显然就是 $W_i$ 了,由于这些集合两两不交,因此只需要看看它们的大小之和是否为 $|S|$,就知道它们的并是否为 $S$ 了。
于是就可以在 $O(n \log n)$ 的时间复杂度下检测一个集合是否合法。(使用长链剖分可以做到 $O(n)$,然而并没有什么卵用)。
当合法的时候,大力重建族谱树。
时间复杂度为 $O(n^2k \log n)$ 或 $O(n^2k)$。
算法四
在上一个算法中,第一步的时间复杂度可以做到 $O(\log n)$ —— 可以直接以集合大小作为关键字二分。瓶颈在第二步上。显然,通过枚举 $S$ 中每个元素的方法得到 $W_i$ 过于缓慢,我们需要更快的做法。
在静态的树上维护动态的树是很困难的,不妨在动态的树上维护静态的树。
不失一般性的假设 $S$ 来源于老族谱树 $a$ 上的子树 $b$ ,对于子树 $W_i$ ,如果 $W_i$ 是 $S$ 的子集,$W_i$ 中所有节点在树 $a$ 中的 LCA 就是节点 $b$ 的孩子了。显然,只有当所有 $W_i$ 要么是 $S$ 的子集要么与 $S$ 分离时,LCA 是节点 $b$ 的孩子的 $W_i$ 的大小之和才恰好为 $|S|$,不然一定会小于 $|S|$,因为那些不合法的元素并不会被统计到。我们可以通过这个来判断 $S$ 是否合法。
具体来说,对于每个族谱树中的集合 $T$,按子树的 LCA 的 DFS 序号,一共以 $k$ 种顺序维护 $T$ 的孩子。当询问老族谱树 $a$ 上子树 $b$ 构成的集合 $S$ 的合法性时,只需要先找到 $T$,再看看 LCA 是 $T$ 的孩子的大小之和是否为 $|S|$ 即可。这些孩子在第 $a$ 个顺序上是一个区间,二分找到这个区间即可。
于是检测一个集合是否合法的复杂度就降到了 $O(\log n)$。
瓶颈成了每次修改族谱树,理论上应该能做到 $O(nk)$。
时间复杂度为 $O(n^2k^2)$。(好像变慢了 …… )
算法五
考虑修改族谱树的过程 —— 我们只是增加了一个节点,并将该节点父节点的一些孩子移动给了它。这个操作在第 $a$ 个顺序上是很容易完成的,需要移动的孩子是个区间(就是算法四中判断合法性的区间),只需要将这个区间 split 出来就行了。然而对于其他顺序来说,需要移动的节点是无序的。
平衡树启发式合并 $n$ 个元素的时间复杂度是 $O(n \log n)$ 的,类似的,平衡树启发式分离 $n$ 个元素的时间复杂度也是 $O(n \log n)$ 的。于是可以直接跑个启发式分离 —— 如果需要移出来元素少于一半,则直接依次删除并把删掉的元素重新建一棵树,不然就依次删除不需要移出来的元素同样建棵树就行了。
这个东西实现出来就是 $k$ 棵 LCT 上套 splay。($k$ 棵 toptree ?)
插入节点的时候需要知道集合的 LCA 的序号,因此在 toptree 上还需要维护一个子树的 LCA。当然,这里并不需要强上一个 $O(1)$ LCA,可以仅仅维护子树 DFS 序的最小值与最大值。当真的需要 LCA 的序号时,再去通过最小值与最大值计算 LCA,这样常数应该会小一点 ?
时间复杂度为 $O(nk \log n)$。
为什么 $k$ 这么小?动态开空间多麻烦啊 ……
新年的A+C Problem
from Picks, 标程和数据 by whzzt, 题解 by Picks
本题中的模型其实是来源于量子计算的模型。题中可使用的门是三元可逆逻辑门,而在真实的量子计算中是Hilbert空间中的线性变换,其中可逆逻辑门可以在量子计算中实现。
题目的任务是求对于长度为l的输入整数a进行加常数c的可逆电路,其中可利用的资源有三类额外位:
- 泄露位:初始为0,输出可以为任意值的位。由于可逆运算中信息是守恒的,当输出为任意值时,输入的信息会泄露到这些额外位中。当有人获取了额外位的输出,是可能获得额外位的信息的。
- 干净位:初始为0,输出时也为0的位。这些位可以视为一个资源池,从中取出时是0,放回时也是0。
- 脏位:初始时不知,输出时需要还原为初始状态的位。这些位可以从系统的任意无关位置取出,在过程中利用完之后放回原位。
显然这三类额外位存在支配关系,泄露位的利用严格容易于干净位,干净位的利用严格容易于脏位。
子任务一、二
有许多泄露位可以利用时,有很多种做法都可以解决这个问题。
最简单的方法是从低到高枚举每一位,用一位存下当前的进位。但由于 $ 0 + 1 = 1 + 0 $ 会造成不是一个一一映射,我们可以利用一个泄露位(值一定是0)来解决这个问题。
根据实现的不同需要 l 左右个泄露位。
子任务三
当我们有 $ 2l $ 个干净位可以利用时,我们考虑实现一个加法器 $ (A,B,q)→(A+B+q,B,q) $,其中 $ q $ 是一个干净位,我们用来向后传递信息。
注意到我们无法绕开进位,我们不妨使用 $ q $ 位置来传递进位信息。对于 $ A,B $ 的对应位 $ a,b $ ,我们设计可逆门 $ \mathrm{MAJORITY}:(i,j,k)\rightarrow(i\oplus k,j\oplus k,\mathrm{MAJ}(i,j,k))$,其中 $\mathrm{MAJ}(i,j,k)$ 表示的是 $ i,j,k $ 中存在至少两个的逻辑值,逻辑关系为 $ \mathrm{MAJ}(i,j,k)=(i\ \mathrm{and}\ j)\mathrm{or}(i\ \mathrm{and}\ k)\mathrm{or}(j\ \mathrm{and}\ k) $,可以验证这是一个可逆门。
同时,当我们用 $a,b,q$ 表达当前位与进位时,它们的多数值即为进位。使用一个依此从低位到高位的操作序列,我们可以在过程中获得临时进位,并将临时进位信息递归传给后方变量操作。当递归结束时,我们可以将之前的门取反(即输入输出对调)来将操作取消,额外添加 $ \mathrm{TRIXOR} $ 门 $(i,j,k)\rightarrow (i\oplus j\oplus k,j,k) $,来得到当前位的答案。
即如下过程:
fixpoint adder(a[i], b[i], q) :=
MAJORITY(a[i], b[i], q);
adder(a[i+1], b[i + 1], q);
reverse(MAJORITY)(a[i], b[i], q);
TRIXOR(a[i], b[i], q).
回到问题,我们一开始将常数 $ c $ 写入变量 $ b $ 中,调用加法器,再将变量 $ b $ 中的 $ c $ 擦除即可。
子任务四
此时我们只有 $ l $ 个额外干净位,不过好在 $ c = 1 $,我们仍能比较简单地解决。
在上一个子任务中,我们发现最关键的问题即是进位问题,我们考虑如何比较好地解决进位问题。注意到 $ c=1 $,则第 $ i $ 位的进位实际上是输入变量前 $ i $ 位进行与操作的结果。我们只需要利用额外的 $ l $ 个干净位依此计算逻辑与 $ (i,j,k)\rightarrow(i,j,k\oplus(i\ \mathrm{and}\ j)) $ 即可。实际上我们只需要 $ l-2 $ 个额外位来存储每一位的进位信息,因为最后一位无作用,第一位无需存储。计算出进位之后我们可以利用 $(i,k)→(i\oplus k,k)$ 来获得答案,之后将计算逻辑与的过程取消掉即可。
子任务五
该子任务中我们仅有 $ l $ 个额外脏位,此时难度显著上升了。
这时我们需要利用一个补码的性质:在模 $ 2^l $ 的意义下,整数 $ b $ 逐位取反的结果即是 $-b-1$。
我们利用一个技巧来处理加 $ 1 $ 操作。考虑加法器 $ (A,B,q)→(A+B+q,B,q) $,如果我们将 $ B $ 取反,我们可以计算得到 $ (A,B,q)\rightarrow (A-B-1+q,-B-1,q) $。将之串在一起并将B还原,可以得到 $ (A,B,q) \rightarrow (A+2q-1,B,q) $ 过程。但 $ q $ 同样是脏位,如果 $ q=1 $,则我们计算完成。如果 $ q=0 $,我们实际上计算了 $ A-1 $ 的结果,那此时我们预先将 $ A $ 取反,在其后再次将 $ A $ 取反,则实际完成的仍是 $ A+1 $ 的计算。那么我们只需要在上述过程前后均加上由 $ q $ 操控的 $ A $ 取反过程。对应到位上即是门 $ (a,q)\rightarrow (a\oplus q\oplus 1,q) $。
粗略观察,此时我们使用了 $ l+1 $个额外脏位。但是注意到 $ B $ 的最高位其实可以不使用,将其取出用作进位 $ q $ 即可。
子任务六
现在我们仅有一个额外位了。我们先考虑一些可能的子任务。
你需要对利用计算过程 $P:(A,y)\rightarrow(A,y\oplus f(A))$ 的一位结果 $f(A)$ 来控制一个对 $B$ 变量的操作 $O:B\rightarrow g(B)$,其中$g(g(B))=B$,但除 $A,B$ 外你仅有 $ 1 $ 个额外脏位 $ q $ 。
我们可以构造如下过程:
Definition dirtyControl(P, O, A, B, q) :=
controlled(O)(q, B);
P(A, q);
controlled(O)(q, B);
reverse(P)(A, q).
注意到当 $ f(A) $ 是 $ 1 $ 时,$ \mathrm{controlled}(O)(q, B) $ 仅作用了一次。反之,则作用了 $ 0 $ 次或 $ 2 $ 次,均不影响变量 $ B $ 的值。
当你有 $l$ 个额外脏位,还有一个输入位 $p$ 存有 $0$ 或者 $1$,你需要计算 $ a + p $。
这个与子任务五非常相似。我们提供两种方法来完成。
一种是非常粗暴的方法,即使用 $ p $ 作为控制变量去控制是否进行子任务 $ 5 $ 的加 $ 1 $ 操作。只需要将子任务 $ 5 $ 中的所有门额外加一个控制变量 $ p $,当且仅当 $ p=1 $ 时执行门操作即可。对于二元门,扩展成三元门是容易的。对于三元门,添加额外控制变量变为四元门之后需要将三元门进行分解。分解方法是取一个额外的脏位(随意找一个无关位即可),将前两位的信息利用小问题1中的方法存储在脏位中,再将后两位与脏位一起运算得到结果。
另一种是灵巧一点的方法,我们考虑子任务五中 $ 1 $ 的来源,实际上是 $ B $ 的取反操作。那我们使用输入位 $ p $ 控制 $ B $ 的取反操作,当 $ p = 1 $ 时才进行该取反即可。
当你有 $ l-1 $ 个额外脏位 $ Q $ ,你要获得 $ a+c $ 的最高进位,输出在干净位 $ s $ 中。
还是利用小问题1中的方法,我们用第 $ i $ 个脏位来储存第 $ i $ 个进位的信息(即若第 $ i $ 位进位为1,则对应脏位取反)。逻辑形式为:
Fixpoint dirtyAdd(a[i], c[i], q[i]) :=
If c[i]=1 then ( (controlled(NOT)(a[i], q[i])); NOT a[i]. )
controlled(controlled(NOT))(q[i-1], a[i], q[i]);
dirtyAdd(a[i-1], c[i-1], q[i-1]);
controlled(controlled(NOT))(q[i-1], a[i], q[i]);
即当更低位的脏位不变时,该位进位由 $ a[i], c[i] $ 控制,否则联合控制。同样的,最高位不需要存储进位,故只需要 $ l-1 $ 个脏位。注意最低位和最高位需要特殊处理,最低位不需要低位进位的控制,最高位运算的结果存入 $ s $ 中。
现在我们利用一个额外干净位 $ s $ 来计算 $ a+c $。首先我们将输入 $ a $ 均分成两半 $ p,q $,若总长度是奇数则使 $ p $ 比 $ q $ 长。
我们先利用小问题3,视 $ q $ 为脏位,计算出 $ p $ 部分加上对应的部分 $ c $,结果的最高进位,存储在额外干净位 $ s $ 中。然后我们利用小问题2,视 $ p $ 为脏位,将 $ s $ 中的值加到 $ q $ 中去。最后重复第一步,将 $ s $ 中信息擦除。此时我们发现,输入的两部分不再产生关联了,只需要递归下去分别解决 $ p $ 和 $ q $ 的计算问题即可。
子任务七
此时额外位是一个脏位g。我们再次利用小问题1中的方法来解决这个问题。 最终的方法为:
Fixpoint addC(a, g) :=
Let p, q as described;
P2(g, q, p);
controlled(allNOT)(g, q);
P3(g, p, q);
P2(g, q, p);
P3(g, p, q);
controlled(allNOT)(g, q);
addC(p, g);
addC(q, g);
扩展
如果我们不局限于三元逻辑门,而是可以使用量子门,则额外的一个脏位也是可以省去的。参见参考资料【3】。
参考资料
- Craig Gidney. Constructing Large Increment Gates. http://algassert.com/circuits/2015/06/12/Constructing-Large-Increment-Gates.html
- Thomas Häner, Martin Roetteler, Krysta M. Svore. Factoring using 2n+2 qubits with Toffoli based modular multiplication.
- Craig Gidney. Trouble Adding Constants into Qubit Registers. http://algassert.com/post/1701