由于一些…我也不知道是什么原因吧，似乎 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$ 是素数时，$\mathrm{\forall }0\le k<n,\mathrm{\exists }0,k,2k,3k\dots (n-1)k$ 在$modn$ 意义下互不相同。我们可以构造 $\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)modn,(v+i)modn)$。我们定义一条边 $(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 \mathrm{\varnothing }$，若 $T\cap A\ne \mathrm{\varnothing }$，那么 $S\cap A$ 和 $T\cap A$ 不可能联通。因此会有 $T\cap A=\mathrm{\varnothing }$，同理 $S\cap B=\mathrm{\varnothing }$，于是有 $S=A,T=B$。

因此当图是二分图时，我们只要枚举点集进行询问即可。

询问次数 $2^n$，期望得分 13 分。

算法二

为了获得最终二分图的两部分，我们尝试获得原图的一棵生成树。

我们可以考虑尝试删掉二分图中所有的边，如果一条可能的边删除后连通性发生了改变，我们就保留这条边，否则删去这条边。最终图中一定会剩下恰好 $n-1$ 条边，它们构成了一个生成树。

于是我们只要将生成树黑白染色就可以得到二分图的一个部分了。

询问次数 $\frac{n(n-1)}{2}$，期望得分 37 分。

算法三

刚刚的寻找生成树的方法实在是太暴力了，我们可以对刚刚的方法进行一些优化：二分查找下一次保留边会发生在什么时候。由于这样的事件只会发生 $n-1$ 次，我们只需要进行这么多次二分。

注意到我们找到了原图的一个生成树，只靠这个生成树是可以让原图联通的。那么我们可以保留生成树上的边，删去其它连接二分图两侧的边。如果图不是二分图，那么图中一定存在环，于是一定存在剩余的某条树边删去后仍然连通。

每次二分需要 $\log (n^2)=2\log n$ 左右次查询，因此询问次数 $2n\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状态，我们发现我们可以尝试只存下来$lo{g}_{2}v2$的值，这样子状态就变成$O(nlogn)$了。

转移我们枚举在$x$所在重链上第一个满足$f$的值不同于他的父亲节点的点,或者是叶节点,设其为$y$

观察算法三中的DP转移方程，不难发现在钦定重儿子的时候转移方程形如$h(y,v2+1)+\mathrm{\Sigma }h(x\mathrm{到}y\mathrm{路}\mathrm{径}\mathrm{上}\mathrm{所}\mathrm{有}\mathrm{的}\mathrm{轻}\mathrm{儿}\mathrm{子},0)+\mathrm{自}\mathrm{己}\mathrm{的}\mathrm{权}\mathrm{值}\to h(x,v2)$

因为在转移的重链上的点$f(x)$相同，所以我们可以假设这些点有点权,为$v(x)=\sum h(x\mathrm{父}\mathrm{亲}\mathrm{除}\mathrm{了}x\mathrm{之}\mathrm{外}\mathrm{的}\mathrm{所}\mathrm{有}\mathrm{儿}\mathrm{子})+\mathrm{自}\mathrm{己}\mathrm{附}\mathrm{带}\mathrm{的}\mathrm{权}\mathrm{值}$

此时转移方程就可以看成路径点权和加上$y$子树的权值(如果$y$不是叶节点，否则为$0$)

对于叶节点的情况，我们可以维护$logn$颗动态开点线段树维护深度在某一范围内的叶节点的点权和最大值。

对于非叶节点的情况，不难发现合法转移只有$O(nlogn)$种，直接找到所有可能出现的情况，暴力转移。

非叶节点的点权和可以在确定$dfn$序之后使用树状数组维护。

时间复杂度$O(n{\log }^{2}n)$

空间复杂度$O(n{\log }^{2}n)$

算法五

出题人卡内存怎么办？？？

考虑通过一些操作把$lo{g}_{2}v2$拆开，使得他在他的$1$代祖先，$2$代祖先，$\dots$ ，$2^k$代祖先的地方恰好被算一次。

此时我们每个点的点权就唯一了，线段树就只需要一颗了。

其于基本同算法四。

时间复杂度$O(n{\log }^{2}n)$

空间复杂度$O(n\log n)$

算法六

from: matthew99

算法四，五我听不懂怎么办？

考虑对于每一个节点x维护一个分段函数表示$f[x]$

我们可以发现分段函数的段数的上界是$O(\mathrm{子}\mathrm{树}\mathrm{大}\mathrm{小}\times \log n)$的。

直接启发式合并维护即可。

时间复杂度$O(n{\log }^{2}n)$

空间复杂度$O(n\log n)$

算法七

from: matthew99

在审题的时候@whzzt说分段函数段数$O(\mathrm{子}\mathrm{树}\mathrm{深}\mathrm{度}\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^{3}k)$ 或 $O(\frac{n^{3}k}{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^{2}k\log n)$ 或 $O(n^{2}k)$。

算法四

在上一个算法中，第一步的时间复杂度可以做到 $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^2{k}^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的可逆电路，其中可利用的资源有三类额外位：

1. 泄露位：初始为0，输出可以为任意值的位。由于可逆运算中信息是守恒的，当输出为任意值时，输入的信息会泄露到这些额外位中。当有人获取了额外位的输出，是可能获得额外位的信息的。
2. 干净位：初始为0，输出时也为0的位。这些位可以视为一个资源池，从中取出时是0，放回时也是0。
3. 脏位：初始时不知，输出时需要还原为初始状态的位。这些位可以从系统的任意无关位置取出，在过程中利用完之后放回原位。

显然这三类额外位存在支配关系，泄露位的利用严格容易于干净位，干净位的利用严格容易于脏位。

子任务一、二

有许多泄露位可以利用时，有很多种做法都可以解决这个问题。

最简单的方法是从低到高枚举每一位，用一位存下当前的进位。但由于 $0+1=1+0$ 会造成不是一个一一映射，我们可以利用一个泄露位(值一定是0)来解决这个问题。

根据实现的不同需要 l 左右个泄露位。

子任务三

当我们有 $2l$ 个干净位可以利用时，我们考虑实现一个加法器 $(A,B,q)\to (A+B+q,B,q)$，其中 $q$ 是一个干净位，我们用来向后传递信息。

注意到我们无法绕开进位，我们不妨使用 $q$ 位置来传递进位信息。对于 $A,B$ 的对应位 $a,b$ ，我们设计可逆门 $\mathrm{MAJORITY}：(i,j,k)\to (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)\to (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)\to (i,j,k\oplus (i\mathrm{and}j))$ 即可。实际上我们只需要 $l-2$ 个额外位来存储每一位的进位信息，因为最后一位无作用，第一位无需存储。计算出进位之后我们可以利用 $(i,k)\to (i\oplus k,k)$ 来获得答案，之后将计算逻辑与的过程取消掉即可。

子任务五

该子任务中我们仅有 $l$ 个额外脏位，此时难度显著上升了。

这时我们需要利用一个补码的性质：在模 $2^l$ 的意义下，整数 $b$ 逐位取反的结果即是 $-b-1$。

我们利用一个技巧来处理加 $1$ 操作。考虑加法器 $(A,B,q)\to (A+B+q,B,q)$，如果我们将 $B$ 取反，我们可以计算得到 $(A,B,q)\to (A-B-1+q,-B-1,q)$。将之串在一起并将B还原，可以得到 $(A,B,q)\to (A+2q-1,B,q)$ 过程。但 $q$ 同样是脏位，如果 $q=1$，则我们计算完成。如果 $q=0$，我们实际上计算了 $A-1$ 的结果，那此时我们预先将 $A$ 取反，在其后再次将 $A$ 取反，则实际完成的仍是 $A+1$ 的计算。那么我们只需要在上述过程前后均加上由 $q$ 操控的 $A$ 取反过程。对应到位上即是门 $(a,q)\to (a\oplus q\oplus 1,q)$。

粗略观察，此时我们使用了 $l+1$个额外脏位。但是注意到 $B$ 的最高位其实可以不使用，将其取出用作进位 $q$ 即可。

子任务六

现在我们仅有一个额外位了。我们先考虑一些可能的子任务。

你需要对利用计算过程 $P:(A,y)\to (A,y\oplus f(A))$ 的一位结果 $f(A)$ 来控制一个对 $B$ 变量的操作 $O:B\to 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】。

参考资料

1. Craig Gidney. Constructing Large Increment Gates. http://algassert.com/circuits/2015/06/12/Constructing-Large-Increment-Gates.html
2. Thomas Häner, Martin Roetteler, Krysta M. Svore. Factoring using 2n+2 qubits with Toffoli based modular multiplication.
3. Craig Gidney. Trouble Adding Constants into Qubit Registers. http://algassert.com/post/1701