ARC 板刷记录

暂时停更。

记录难度 的题，因为再高我就算看题解也不会或者耗时较长性价比不高。部分没有价值的题或者神秘 poly 题会直接跳。可能以后会补一些 的题。

大部分都是口胡，因为我迫真有时间写。

难度来源：https://kenkoooo.com/atcoder/#/table/

个人认为有启发意义的题目会打上“深刻”标签，很难以理解的题目会打上“被爆”标签。

免责声明：写博客的人是蒟蒻，经常不会做，因此下面给出的讲解可能与网上某些题解有相似或一致之处。

如果侵犯了原作者的利益，请联系我，我会立刻删除此部分内容。

ARC162

C-Mex Game on Tree

有一棵 个结点以 为根的树，有些结点初始有数有些没有，现在 A，B 轮流向所有未填数结点填数，最后如果有一个结点的子树 为 则 A 胜否则 B 胜。求两人绝顶聪明的情况下谁胜。

。

首先 B 可以直接通过在某个位置放置 使得它到根的路径上所有点都废掉，因此 A 只有一次机会。如果子树已经满足条件或者只有一个空缺且值域 也只有一个空缺那么 A 胜否则 B 胜。

[被爆]D-Smallest Vertices

给出 与长为 的数组 ，保证 ，表示一棵树需要满足结点 恰有 个儿子。对于任意树中的任意点 ，若 子树内编号最小值为 则称 是好点。

现在你要对于所有满足度数限制的树求出所有好点的编号和。对 取模。

。

E-Strange Constraints

你有一个长为 的数组 ，问有多少值域在 内的数组 满足条件：

• 在 中的出现次数不超过 。
• 在 中的出现次数不超过 。

。对 取模。

这个题目描述比较的抽象，我们换一个描述。

设 表示 中 的出现次数，则可以重新描述为

• 在 处可以填一个 使得 。

容易发现 越小可以选择的位置越多，因此考虑按照 从大到小 DP。

设 表示只考虑出现次数不小于 的数有 个，总共出现了 次的方案数。

当从 转移到 时，考虑枚举 出现了 次。设 ，则有 种选取数的方案，而排列方案数是 ，于是有转移 由于 的上界为 ，因此时间复杂度其实是 。

F-Montage

给定 ，求有多少 矩阵 满足：对于任意 都有 。对 取模。

。

考虑转化题目限制。我们发现对于任意矩形等价于如果左上角与右下角为 则左下角与右上角为 ，进而推出：如果矩形左上角与右下角为 ，那么整个矩形都必须是 。

此外我们还发现如果一整行/列都是 则不会有任何影响，因此我们可以枚举有多少行/列是 ，计算都不是 的结果，然后乘上组合数即可。

因此我们发现删除整行/列的 后 在每一行都必须是连续的一段，且从上到下左界与右界单调不增（也就是：从左上角到右下角画两条最短的折线要求不能相互穿过，中间夹的那一部分涂 ）。考虑 DP。

定义 表示前 行，目前左界为 右界为 的方案数。

这个东西前缀和优化一下就好了。时间复杂度 。

ARC161

这场创意很好。

被 F 创似了跳了。

C-Dyed by Majority (Odd Tree)

你有一棵树保证度数均为奇数，要求给每个结点都染色为黑/白，然后每个结点同时变换为与之相连的所有点颜色的众数，使得每个点最终变为指定的颜色。给出一组解或报告无解。

。

考虑初始时每个叶结点直接染色成其父亲的颜色就好了（不影响其他结点），而它们的父亲的颜色已经确定。

然后每次把这些点删掉后肯定还是一棵树，用广搜重复这个过程即可。

D-Everywhere is Sparser than Whole (Construction)

题意：你要构造一个 个点 条边的图，满足其任意子图中边数与点数之比小于 。

首先 时无解，然后发现每个点向后面连 条边时一定合法。解决。

[深刻]E-Not Dyed by Majority (Cubic Graph)

你有一个 个结点 条边的无向简单图，每个结点的度数均为 ，要求给每个结点都染色为黑/白，然后每个结点同时变换为与之相连的所有点颜色的众数。请构造一个所有结点的颜色序列，使得无论原图如何染色，在经过一次操作后都不可能变为该颜色序列。

且是偶数。

打表可得随机一组解有不大于 的概率不合法，于是我们就随机几次判断是否合法就好了。

考虑如何判断不合法，一个点连出去的边中最多只能有一个和它本身的颜色不同，于是就可以用 2-SAT，对于每对 有 “要么 和 的颜色相同，要么与 相连的另外两个点颜色与 相同”，于是直接 2-SAT 即可。

ARC160

A-Reverse and Count

题意：有一个长为 的排列 ，定义 为将区间 翻转后的 。求出所有 中字典序第 小的那个。

。

Sol：只要我们能找到 比较两个 的方法，我们就可以用 的代价找出第 小的那个（std::nth_element）。

我们设要比较 与 。

• 若 ，则答案为 。
• 否则若 ，则答案为 。
• 否则答案为 。

时间复杂度 。

B-Triple Pair

题意：求正整数三元组 的个数，满足其任意两项之积不大于 ，即

， 组数据。

Sol：根分。

当 时，无论 取何值都合法。

当 中有一个大于 时，不妨设 （最终答案乘三），则 。由于 ，数论分块求即可。

时间复杂度 。

[深刻]C-Power Up

题意：你有一个多重集，每次操作可以取出两个 然后添加一个 ，可以随时停止操作，问可能得到的可重集数量。

答案对 取模，。

Sol：不妨设我们总是从最小的数开始合并，这样可以确保统计不会重复。

DP，定义 表示目前合并到 这个数， 这个数有 个的方案数，则

状态数是 的，考虑优化。

修改状态为： 表示目前合并到 这个数， 这个数有 个的方案数，则

然后做一个差分前缀和就好了。

状态数是 的，因此时间复杂度 。

[深刻]D-Mahjong

题意：对长为 、和为 的数列 执行若干次操作，每次选取一个位置减 或选择长为 的子区间每个元素减 ，求有多少种数列满足存在方案把数列每一项都减为 。

对 取模。。

Sol：逆向做成单点加 和区间加 。如果所有元素和不是 的倍数则无解；否则一定是进行了 次操作。

每个元素必定是被单点加了若干次并/或被区间加了若干次。由于区间加 次等价于单点加一次，我们考虑钦定所有元素被区间加的次数都小于 次，这样每个合法的操作序列就会对应唯一的数列。

我们设 表示 被区间加的次数， 表示 被单点加的次数，那么就是要求满足下列条件的 数：

• 。
• 。
• 。

考虑对条件三容斥，每次钦定有至少 个 不合法剩下随便，则相当于把 分到 个元素，考虑经典插板答案即为

暴力计算组合数即可，时间复杂度 。

ARC159

B-GCD Subtraction

题意：给定整数 ，每次把 减去它们的 GCD 直到其中一个为 ，求操作次数。

。

Sol：根据 GCD 辗转相加相减的性质， 的 GCD 只增不减且每次至少加倍，那么可能 GCD 的取值只有最多 种。

考虑每次计算减多少次 GCD 后 GCD 会变大。

设 ，则 。

设要求的答案为 ，则 。辗转相减后，。

枚举 的所有因数，找出每个因数对应最小的 即可。

时间复杂度 。

C-Permutation Addition

题意：你有一个长为 的数列 ，每次操作可以指定一个长为 的排列 ，使得 ，问是否存在长度在 以内的操作序列使得 的每个数都相等，有的话输出任意一种方案。

。

Sol：首先考虑是否有解。

设原数列和为 ，则进行若干操作后数列和为 。

为奇数时，原式写作 ，则 。

为偶数时，原式写作 ，则 或 。

接下来考虑如何构造。

我们发现先加上 再加上 后 的差分不变，而为了使得 减小 ，我们令其他项不变，而在第二次加 时将 与 交换，即可达成效果。

这样最多会做大约 次，足以通过。时间复杂度 。（？

D-LIS 2

题意：最开始有一个空的序列，进行 次操作，每次把 依次加到序列的结尾，求最终序列的严格 LIS 长度。

。

Sol：无聊套路，定义 为以区间 结尾的 LIS 长度，则

然后非常套路的两棵线段树分别维护 和 即可。时间复杂度 。

ARC158

B-Sum-Product Ratio

题意：在给定的集合里选三个数 ，分别输出 的最大值和最小值。

。

Sol：我们设已经确定了 ，，，则加入 的贡献为 因此我们总是要选 的三个最值。排序即可。

[深刻]C-All Pair Digit Sums

题意：定义 为 在十进制下每一位的和，例如 。

现在给出 个数 ，求 。

Sol：我们观察到每发生一次进位会导致 减小 。设 表示 中发生进位的次数，则答案即为 前面是容易的，考虑如何快速求 。

我们从低到高按十进制位考虑。在只考虑第 位上的进位时，我们发现任意两个数想这里进位需要满足 。

因此对于每一位，按照 升序排序，统计有多少 满足 ，直接 two-pointer 即可。

时间复杂度 。

[深刻]D-Equation

题意：给出下列三元方程的任意一组解： 。

Sol：

我们随机 ，只要 ，左边任意一项都不为零，则一定存在 满足 由于左边是 次多项式，右边是 次多项式，而由质数可知 在模 意义下一定存在逆元，因此我们解出 ，然后给每一项都乘上 ， 即为答案。

[被爆]E-All Pair Shortest Paths

题意：给你一个 的网格图，每个格子上有权值，一条路径的长度为其经过格子的权值和，求所有点对之间最短路的长度之和。

对 取模，，权值为正。

Sol：究极麻烦题。只看懂分治做法，扫描线做法太神秘了看不懂。

考虑分治，设分治区间为 ，现在考虑两个点 满足 在 且 在 的贡献。

由于点权为正，容易证明最短路一定不会走回头路（否则可以直接抄近道），因此可以线性递推出任意一个点到区间中点的最短路。

我们设点 到 的最短路长度为 ， 到 的最短路长度为 。 同理。

那么 到 的最短路长度即为 。

我们考虑当 时，相当于每个 都对一个 做了 的贡献（答案要乘二）。

移项，得到 。

考虑把所有 和 混在一起排序，维护集合 表示当前 ，然后从小到大考虑：

• 当前值来自右区间时，我们在 中插入 。
• 当前值来自左区间时，对答案的贡献为 。

因此只需要记录 的大小和总和即可。

情况类似，不再赘述。

时间复杂度 ，瓶颈在排序。

ARC157

B 是简单分讨题，跳了。

C-YY Square

题意：一个 的 矩阵 ，从左上角出发向下或向右走直到抵达右下角。

将路径上经过的所有数字排成长为 的序列 ，此路径的权值为 。

求所有可能路径的权值的平方和。

，答案对 取模。

Sol：套路 DP 题。

先考虑如果只求线性和怎么做，显然 DP：定义 表示从 走到 的所有方案权值和，则 然后上处理高次求和的套路之完全平方公式展开，会发现第 个符合条件的邻项贡献为 。

定义 表示从 走到 的所有方案权值和，则： 时间复杂度 。

D-YY Garden

题意：一个 的 矩阵 ，可以横向或纵向沿边线切割（必须切到底）。

求所有切割方案中满足每个连通块和为 的方案数。

。

Sol：

如果整个矩阵和不为偶数则无解；否则一定是形成了 个连通块。设它为 ，那么我们枚举 的因数 ，则一定是横向切了 刀，纵向切了 刀。

在钦定了横向连通块 个纵向连通块 个后，那么每一个横条和为 ，竖条和为 。

从上往下扫，记录上一次切的地方，因此这一次切的地方必定满足和上一刀围成的矩形内和为 。竖条统计同理。

注意可能有全 的行/列，如果这一行/列在被切的地方的周边则这一刀就拥有了自由活动空间，方案数更多。

预处理二维前缀和即可，时间复杂度 。

E-XXYX Binary Tree

题意：给一棵有根真二叉树，你需要给每个结点的值 赋为 或 ，满足对于所有 有

• 出现了 次。
• 出现了 次。
• 出现了 次。
• 没有出现过。

你只需要判断解的存在性。保证 。

多组数据，。

Sol：由于真二叉树的性质，所有非叶结点中 一定出现了 次。

我们分讨根的值。

• 根值为 时，那么恰好有 个 ，其中有 在叶子结点上。
• 根值为 时，那么恰好有 个 ，其中 个在叶子结点上。

容易发现只要满足上述条件就一定能构造出符合条件的树。

我们做一个树形背包： 表示在 子树内选 个叶结点，自己选/不选，最多能选的最大非叶结点数。直接转移即可。

时间复杂度 。

ARC156

B-Mex on Blackboard

题意：你有一个大小为 的多重集 。你需要执行 次操作，每次选取 ，然后在 中插入 ，表示 内最小没有出现过的自然数。问最终 有多少种可能的结果。

答案对 取模。。答案对 取模。

Sol：如果我们希望插入 ，那么 中应当已经出现 。

考虑枚举最后集合的最大值为 。假设为了插入 内的所有数用了 次操作，则剩下的问题就变成了 次操作，每次给一个数的出现次数加一问最后有多少不同的多重集，直接插板即可。

时间复杂度关于值域线性。

C-Tree and LCS

题意：有一棵 个结点的树，你需要构造一个长为 的排列 ，使得下面这个值最小：

• 在树上选取任意一条简单路径 ，令 ， 和 的 LCS 的最大长度。

Sol：

我们可以用下面这个方式构造出一个答案不大于 的解：

• 首先把所有叶结点压到一个队列里。
• 随意取出两个叶结点 ，然后使 ，然后删掉这两个结点。
• 重复直到原树被删完。如果还剩一个结点 ，使 。

现在我们证明这个答案不大于 。

• 当 ，答案为 。
• 否则我们随便选择被同时删掉的两个点 ，则一定不存在一条同时包含 且答案大于 的路径。转移到 。

证毕。

[深刻][被爆]D-Xor Sum 5

题意：给一个长为 的数组 ，求出 ，其中 为异或， 满足 。

。

Sol：当一个 出现偶数次时这个 就没有贡献。

对于一个 设 出现了 次，则贡献为

拆一下组合数：

由 Lucas 定理：

由于在模 意义下只有 的结果是 ，也就是说对于所有 ， 的二进制位应当完全包含 。容易发现只有当 的每一个为 的二进制位都被分到恰好一个 时满足条件。

考虑 DP。

定义 表示已经决定了从低到高 位，当前 的和在二进制右移 位后的二进制结果为 的方案数。那么当 是奇数且 是奇数时，会对答案有一个 的异或贡献。

表示 的前 位的 popcount。

时间复杂度 。

ARC155

C 是大分讨跳了。

A-ST and TS Palindrome

题意：给定字符串 ，问能否构造 使得 与 均为回文串。

，

小力分讨一下。

Case 1:

由题意可得 的前缀与后缀都需要是 的反串，当 时只需要暴力判断重叠部分是否符合条件就好。

Case 2:

同理此时 的前缀和后缀都是 的反串，直接判就好了。如果中间有未重叠部分需要单独判断这部分是否回文。

时间复杂度 。

B-Abs Abs Function

题意：维护一个二元组 的集合 。 次操作包含加入一个二元组或询问

小力分讨一下，得到

用 std::set 维护 与 ，然后调用 set::lower_bound 查询即可。

时间复杂度线性对数。

D-Avoid Coprime Game

题意：有一个 个元素的多重集 与一个变量 初始为 。两人轮流操作，每次从多重集中选取一个元素 满足 ，删除 并 ，不能操作者输。

对于多重集内的每个数判断当这个数作为第一次被选择的数时两人都采取最优策略的情况下谁会获胜。本题中 。

。

首先考虑 每次操作后都变小的情况。

设 表示 时先手的胜负。。

现在我们不强制要求 变小，那么如果当前是必败局面（即后继状态均为先手必胜），可以出一张 +2 选择一个 的倍数转移到后手。

设 表示多重集中 的倍数个数，容易发现当前还剩奇数个倍数时必胜，偶数个倍数时必败。

因此加一维表示当前操作次数的奇偶性。当后继状态均为先手必胜时，。

时间复杂度 。

ARC154

C-Roller

题意：你有一个环状数组 ，可以进行若干次操作，每次把一个位置的数赋为它的后继。问能否通过操作把 转化为 。

，

把元素相等的子串压成一个块，操作等价于把一个块长度减 并把它的下一块长度加 。由于所有块的相对位置不变，因此直接枚举起点暴力扫一遍即可。

D-A + B > C ?

题意：交互题，猜一个长为 的排列 ，每次可以给出三个数 （可以相同），系统返回 。

，交互次数不超过 。

由于 对任意 均不成立，我们可以找到 的位置。

由于 ，于是我们就可以用归并排序，每次比较的时候询问一次即可。这样总交互次数是 级别的。

ARC153

B 是平衡树板子跳了。

[深刻]C-± Increasing Sequence

给定 和数组 ，，要求构造长度为 的严格上升数组 ，满足 ，或报告无解。

。

首先令 ，如果不符合要求则开始调整。容易发现如果对于一个前缀减或对一个后缀加则满足要求。

令 。

时，我们找到一个位置使得其前缀和为正/后缀和为负，然后对这里做前缀减/后缀加即可。 反之。

时间复杂度线性。

D-Sum of Sum of Digits

定义 表示 在十进制下各位的和。

给定数组 ，求自然数 使得 最小。

定义 表示从低到高第 位上发生了 次进位，这 位的数字和的最小值。

每一位转移之前把数组按照 升序排序，然后枚举 的第 位的值计算要进位多少次即可。

如果使用基数排序，时间复杂度 ，。

注：双倍经验，区别是换成了二进制，但是一个蓝一个黑非常抽象

ARC152

B 是无聊结论跳了。

C-Pivot

有一个数组 ，可以进行若干次操作（也可以不操作），每次选取序列中的一项，令其为 然后执行 ，要求操作完后序列非负，求最后序列中最大值的可能最小值。

我们考虑排序后把数组画到直线上，操作相当于选取一个点翻折，于是无论怎么操作直线的形状都不会变（只会斜率变负），也就意味着 不变。

我们考察两个端点的变化，设选择的是 ，那么连续两次操作都选择 会导致整条直线下移 ，则单次移动的单位为 的 。

D-Halftree

题意：你有一个 -indexed 的 个结点的图初始为空，再给定 ，每次可以在任意 之间连一条边，但同时也会在 连边，给出一种将图连成树的方案或报告无解。

首先 为偶数必定无解，现在证明 为奇数时有解。

考虑从每个点 都向 连边，则会形成 个环（忘了叫啥定理了）。由于 是奇数，则 是奇数，那么环长也是奇数，那么我们就可以形成若干长为 的链，且它们的链头为 ，然后发现把这些也串起来就好了。

[被爆]E-Xor Annihilation

在数轴上有 个点在 处，每个点有点权且所有点权构成 的排列，现在你要在正无穷与负无穷处都放一个点权为 的点，然后接下来除了刚刚放置的点每秒会向异或和较大的那一侧（如果它左侧的点权异或和大于右侧则向左，如果右侧点权异或和大于左侧向右），如果相等则不动，两个点碰到一起会合并成一个点且点权为两点异或和。

求有多少 满足所有点最终会停下来。

。

ARC151

C 是神秘博弈论跳了。

B-A<AP

给定长为 的排列 ，求有多少长为 的数组 满足 且 的字典序小于 。

。

字典序更小可以描述为

这样就可以得到若干个相等关系，枚举 并用并查集维护连通块即可。

[深刻]D-Binary Representations and Queries

你有一个长为 的 -indexed 数组 。 次操作，每次给出 ，表示对于所有从低到高第 位为 的数 ，使得 （如 时 ）。

求操作完成后的数列。对 取模。

。

考虑两个操作 ，则当 时这两个操作可以交换顺序而不影响答案（可自行验证），这样我们可以先依次执行 的操作，再执行 的操作。

考虑到对于一个固定的 执行一次操作可以用下列变换来表示：

其中 ， 的第 位是 。

因此每次我们只需要计算出所有乘起来的矩阵的结果即可。

设 ，时间复杂度 ，其中 。

[深刻]E-Keep Being Substring

你有一个长为 的数组 ，给出它的两个子串 ，每次操作可以在 的头尾增删任意元素，但是必须时刻保证 是 的子串。求把 变为 最小操作次数。

当 有公共子串时，设长度为 则答案为 。这部分直接上 Hash+二分+Hash 表（或者 SA）即可。

当 没有公共子串时，必定是把 杀到只剩一个字符后再经过若干次加一个字符再删一个字符的操作后使出现了 的子串后最优。

因此我们考虑建图，，则问题变为在 中枚举留下的元素问最少多少步走到 中有的元素（走一步代表加一个元素再删掉之前的元素）。然后发现这个东西一遍 BFS 就解决了。

时间复杂度 。

ARC150

B-Make Divisible

对于 找出最小的 ，使得 整除 。

。

考虑枚举 ，则 。

对 整除分块，每次取块的最小值即可。

时间复杂度 。

[深刻]C-Path and Subsequence

你有一张 结点的有向图，点有点权。再给出一个数组 ，求是否所有 到 的路径上的点权序列一定包含 作为子序列。

。

考虑如何匹配最短子序列。发现对于一个点我们总是选择入边中的最短匹配长度，因此跑 Dijkstra 即可。

时间复杂度 。

D-Removing Gacha

一棵树最开始都是白点，每次随机选择一个到根路径上有白点的点涂黑，求把整棵树涂黑的期望次数。

。取模 。

单独考虑每个结点的期望染色步数，答案为每个点期望之和。

设结点 深度为 ，路径上目前有 个点未染色，则抽到一个未染色的结点期望次数 ，而又有 的概率抽到 ，因此每次有 的概率抽到，因此答案为 。

ARC149

被 E 撅了跳了。

C-Avoid Prime Sum

构造一个 且 的数恰好都出现一次的矩阵，满足相邻两项和都不为质数。

。

显然的方式是把奇数和偶数各放一边，只需要考虑 个分界点的和必须不是质数。在范围 内随机一些奇数 ，如果不是质数就只需要在分界线上方放 下方放 就好了。容易发现质数密度一定不会大于 ，所以随机个 次几乎必定能找到一个合适的奇数。 是奇数时可能还要多判一下 和 都不是质数，但是这个概率还是非常小。

[深刻]D-Simultaneous Sugoroku

数轴上有 个点，有 次操作，每次把所有点向靠近原点的方向移动 单位长度（如果已经在原点则不动），求出最后哪些结点在原点，对于在原点的结点求出第几次操作到达原点，对于不在原点的结点求出最终坐标。

。

考虑移动原点。对于一次操作，在 处与在 处的操作实际上是对称的，所以可以把对称位置上的点记一下和什么点对称。

容易想到只需要把被原点截断的两部分中较短的一部分的每个结点都对称到另一部分，用树维护对称关系，最后 DFS 一遍即可。

或者我在这里放一张官方的图会好一些？

ARC148

C-Lights Out on Tree

你有一棵树， 组询问，每次给出一个点集 内的点为 其余 ，一次操作可以子树异或 ，求最少操作次数使得整棵树变 。

。

首先考虑暴力，设结点 的值为 ，每次询问从根开始 DFS，如果当前结点是 则操作次数 并反转。容易发现访问到一个点时，当前结点的颜色 取决于 当前到根路径操作次数的奇偶性 与 的异或值。

然后发现当某个结点的颜色与父亲结点不同时，必定需要加一次操作次数（一次操作必定无法解决）。所以答案就是这个。

D-mod M Game

有 个数 ， 轮流行动（ 先手）每次取一个数，最终若 取的数和与 取的数和模 同余则 胜否则 胜。问谁有必胜策略。

大胆猜想当且仅当所有数出现次数都是偶数时 胜，然后发现 的时候 也胜（ 选 则 选 ， 选 则 选 ）。此时发现如果同时有偶数对 满足 时也有解，然后发现貌似剩下都无解。

[深刻]E-≥ K

给你一个长为 的数组 ，问有多少种重新排列的方式使得任意 有 。

。

发现条件转化为：

• 不能出现两个相邻 的数。
• 若 相邻，，则 。

直接排列是比较难的，考虑按照 降序后 降序排序，用类似排列 DP 的方式插入数，这样可以保证插入时一定不会出现第二种情况。

实时维护一下还有多少个位置可以放 的位置设其为 ，分讨一下当前 的值，设出现了 次，则：

• ：选 个位置放即可，方案数为 ，然后 。
• ：相当于把这 个数划分成 段（允许为空）然后把每一段都填到原先的一个空位，于是方案数 ，然后 。

时间复杂度 。

ARC147

C-Min Diff Sum

求 其中 。

[深刻]D-Sets Scores

你要构造 个集合 ，满足所有集合元素都是 内的整数，且对于 有 与 相差恰好一个元素。记一种集合的构造方案的权值为 （其中 为在所有集合中的出现次数），求所有满足条件的构造方案的权值和。

一开始还以为是啥神秘容斥，结果发现被骗了，哈哈。

由于转移到下一个位置的集合时要么加一个元素要么减一个元素，我们考虑把每一次发生变化的那个元素记下来，这样得到了一个长度为 的序列 。由于这个绝妙的定义，所有长为 且 的所有序列都是合法的。

此时只需要确定 即可。考虑 包含的元素，定义 分别表示 与 时 在所有集合内的出现次数。我们发现， 在 中每出现一次，就代表它在集合中的状态翻转一次。由于 包含/不包含 是两种相反的初始情况，因此无论出现多少次，在两种初始情况下都不可能出现某次翻转后 在两边的两个集合的出现状态相同，进而推出 ，也就是说对于 确定的情况，每一种 都贡献 的出现次数，则这一部分的答案为 。又有 一共有 种，因此答案为 。

E-Examination

你有 个二元组 ，你可以进行任意次交换两个二元组的 的操作，求使得所有 的操作次数的最小值或报告无解。