题集

一些杂题，主要是贪心（模拟费用流）和构造，以及一些思维题。（部分来自 zzz 课件）

Bohater

有 $n$ 只怪物，为了打败第 $i$ 只怪物，你会下降 $d_i$ 的血量。击败怪物后，会掉落回复 $a_i$ 生命值的血药。任何时刻血量都不能小于等于 $0$ 。问是否存在一种打怪顺序使得自身不死掉。

数据范围： $n \le 10^5$ 。

简单贪心，我们把怪物分为两种类型：击败后加血和击败后扣血。对于第一种怪物，我们可以采取先打 $d_i$ 小的，因为我们需要攒血量去打 $d_i$ 大的怪物。对于第二种怪物，我们倒着考虑。我们这样就可以发现，倒着看时， $d_i$ 为血药， $a_i$ 为减小的血量，为了使得血量不小于 $0$ ，我们需要把减少的血量小的放前面，在原顺序中也就是把 $a_i$ 小的放后面。

不离

有 $2$ 个属性 $x$ 和 $y$ 以及 $n$ 件装备，第 $i$ 件装备需要在 $x \ge a_i, y \ge b_i$ 时才能穿上，穿上后会使 $x$ 加上 $c_i$ ，使 $y$ 加上 $d_i$ 。如果想让所有装备都穿上，最初的 $x$ 最小应该是多少。在 $x$ 最小的前提下， $y$ 最小是多少。

数据范围： $n\le 10^5$ 。

我们先考虑 $x$ 。我们可以先把装备按 $a_i$ 排序，一件一件穿。当 $x$ 无法达到 $a_i$ 时，我们就提升初始的 $x$ ，把这段差值补上。这样就求出了最小的初始 $x$ 。

我们再考虑 $y$ 。既然有了初始的最小 $x$ ，我们就可以模拟穿装备的过程。一件一件穿，当力量值大于 $a_i$ 时，我们把这件装备扔到按 $b_i$ 排序的堆里。当力量值小于 $a_i$ 时，我们再从堆里一件一件拿装备穿，过程和求 $x$ 的过程一样。由于 $x$ 是我们求出的最小解，因此一定有解。

专业网络

有 $n$ 个人，可以花费 $b_i$ 元和这个人成为朋友，也可以在朋友数超过 $a_i$ 时和它成为朋友。询问和这些人成为朋友的最小花费。

数据范围： $n\le 2\times 10^5$ 。

我们考虑能够最多节约多少钱。我们先把所有人按照 $a_i$ 排序，这时我们发现正着考虑不太好，因为我们花钱一定是买 $a_i$ 更大的，因此我们从后往前考虑。我们先认为所有人都是花钱买的，我们遇到一个人先把它扔到堆里，同时把他的钱节约下来，让他成为不通过花钱交上朋友的人。如果我们发现当前 $a_i$ 要大于现在买的人数，那我们就取出堆顶，把他买下来。这样就完成了。

排列鞋子

有 $n$ 双鞋子，分左右鞋，放在编号为 $0\sim 2n-1$ 的位置上。我们要求最终的序列为：编号 $2i$ 位置上的鞋子是左鞋，编号为 $2i+1$ 的位置上的鞋子是右鞋，并且编号 $2i$ 和 $2i+1$ 的位置上的鞋子的大小相等。每次可以交换相邻的两只鞋子，问最少交换多少次可以满足上面的条件。

数据范围： $n\le 10^5$ 。

我们可以从右往左扫这个序列，遇到没有用过的鞋子就在它左边找到和它配对的，把那只鞋子移过来即可。我们来证明一下这个算法的正确性。

首先，如果我们要把这两只鞋子移动到一起，如果最终移动到的位置在这两个鞋子之间，那么操作次数不变。我们考虑对其他鞋子的影响。首先对左半部分的鞋子不会有影响，它们的位置不变。而对于在这两个鞋子之间的鞋子 $x$ ，如果与它配对的鞋子在最终移动到的位置的右边，则操作数不变，如果在最终移动到的位置的左边，则操作数会增加。则我们需要尽可能减少这样的情况出现。而移动到最右端时这样的情况就会变为 $0$ 。因此这样是最优的。

这样就可做了。用一个树状数组统计答案即可。

Buy Low Sell High

已知接下来 $n$ 天的股票价格，每天你可以买进一股股票，卖出一股股票，或者什么也不做。最终最多能赚多少钱。

数据范围： $n\le 3\times 10^5$ 。

~~模拟费用流开始~~

本题很容易建出费用流模型。见下图。

其中源点向每天连流量为 $1$ ，费用为 $-c_i$ 的边，每天向下一天连流量为 $+\infty$ ，费用为 $0$ 的边，每天向汇点连流量为 $1$ ，费用为 $c_i$ 的边。每新加进来一天就会多增加三条边。我们考虑增加了这三条边会对网络产生什么影响。见下图。

（图二中为将负环消掉，也是费用流中的一个算法）

我们可以发现，新一轮增广只会选择之前没有选择的一天来买股票，或者反悔掉之前卖出的一股股票来现在卖。这样就可以开一个堆维护了。

数据备份

长度为 $n$ 的序列，要求选 $k$ 个数，要求这 $k$ 个数不能相邻，求选出的数最大总和。

数据范围： $n\le 10^5$ 。

本题也是比较经典的模拟费用流例题。我们先把费用流模型建出来，见图一。

我们这里把数字与数字之间的间隙看作点，把数看作边。我们考虑一次增广的情况，见图二。可以发现，单次增广会把一段区间的状态全部取反，同时这段区间必须满足 0 101...101 0，即两边都不选，并且中间选和不选交替。我们还能发现，这样一次增广后，会把三段区间变为一段区间。用堆和链表维护即可。

我们也可以从贪心的角度来说明这个结论。每次的决策必然是选择最小的，或者是最小值的两边的值。我们可以先选择上最小值，然后删除这三个数，加入值为 $a_{i-1}+a_{i+1}-a_i$ 的数。这样如果下次再选择到这个数，就代表着我们反悔了。代码和上面的做法完全一样。

另外，由于本题建出了费用流模型，我们可以用 wqs 二分来解决，这里不再说明。

Olympiad in Programming and Sports

有 $n$ 个学生，每人有两种技能，分别是 $a,b$ 表示编程能力和运动能力。你需要将他们分为两个团队分别参加编程比赛和体育比赛，编程团队有 $p$ 人，体育团队有 $s$ 人，一个学生只能参加其中一项。每个团队的力量是其成员在对应领域能力总和，两个团队的实力和最大是多少。

数据范围： $n\le 3000$ 。

本题依旧可以建出费用流模型。

图一即为网络。图二、三、四都为单次增广可能的路径，我们可以选择一个没有被选择的人来让他选择编程或者运动，或者是让它顶替掉一个选择过别的运动的人。我们可以按照这个想出反悔贪心策略：开三个堆来维护 $a_i, b_i, b_i-a_i$ 。一开始先选择编程能力最大的，然后每轮不断取出最大的 $b_i$ 和最大的 $a_i+(b_i-a_i)$ ，重复 $s$ 轮即可。

Raffles

有 $n$ 个奖池，第 $i$ 个奖池有 $p_i$ 元奖金，已经有 $l_i$ 张彩票押在上面。现在有 $t$ 张彩票，你要把这些彩票押到奖金池中，并且在每个奖金池中你押的彩票数不能超过原有的彩票数。如果你在第 $i$ 个彩票池押了 $t_i$ 张彩票，你中奖的概率就是 $\frac{t_i}{t_i+l_i}$ ，中奖会获得该彩票池的所有奖金。一共有 $q$ 次事件，每次事件会使一个彩票池中 $l_i$ 加一或减一。每次事件后输出获得奖金的最大期望值。

数据范围： $n, q, t\le 2\times 10^5$ 。

我们考虑往某个池子里放一个彩票增加的期望钱数。

\begin{aligned} \frac{t_i+1}{t_i+1+l_i}-\frac{t_i}{t_i+l_i} &=\frac{(t_i+1)(t_i+l_i)-t_i(t_i+1+l_i)}{(t_i+1+l_i)(t_i+l_i)} \\ &=\frac{l_i}{(t_i+1+l_i)(t_i+l_i)} \end{aligned}

我们再考虑如果没有修改操作如何求出答案。我们只需要维护两个堆，一个存放当前的决策，一个存放下一次的决策（就比如当前池子里押了 $x$ ，下一次决策即为 $x+1$ ）。每次拿出下次决策收益最大的，循环 $t$ 次即可。

当有修改时，我们可以先将其在堆中的信息更新一遍，然后从下一次决策中取出最大的和当前决策进行比较，如果更大就替换。这样复杂度其实是对的，因为我们每次重新跑一遍只会引起一张彩票的变化。

Cardboard Box

$n$ 个关卡，对每个关卡，你可以花 $a_i$ 代价得到一颗星，也可以花 $b_i$ 代价得到两颗星，也可以不玩。问获得 $w$ 颗星最少代价。

数据范围： $n\le 3\times 10^5$ 。

我们考虑从有 $i$ 颗星变为 $i+1$ 颗星的方法：

直接选一个之前 $0$ 颗星的关卡增加一颗星，代价 $a_i$ 。
选已经选了一颗星的关卡变为两颗星，代价 $b_i-a_i$ 。
让之前一颗星的关卡变为零颗星，一个零颗星的关卡变为两颗星，代价 $b_i-a_j$ 。
让之前两颗星的关卡变为一颗星，一个零颗星的关卡变为两颗星，代价 $b_i-b_j+a_j$ 。

我们分类讨论完就可以直接开五个堆分别维护 $a_i,b_i, -a_i, b_i-a_i, -b_i+a_i$ 。每次从上面的决策中选择最大值即可。

序列

给定两个长度为 $n$ 的正整数序列 $\{a_i\}$ 与 $\{b_i\}$ ，确定两个长度为 $K$ 的序列 $\{c_i\}, \{d_i\}$ ，其中 $1 \leq c_1 < c_2 < \cdots < c_K \leq n , 1 \leq d_1 < d_2 < \cdots < d_K \leq n$ ，并要求 $\{c_1, c_2, \cdots , c_K\} \cap \{d_1, d_2, · · · , d_K\}\geq L$ 。目标是最大化 $\sum^{K}_{i=1} a_{c_i} +\sum^{K}_{i=1} b_{d_i}$ 。

数据范围： $n\le 2\times 10^5$ 。

我们建出费用流模型。

可以发现，只要弧 CD 有流量，那么一定会去选择流它。当弧 CD 没有流量后，我们有如下选择：

选择相同下标的数字。
找一个可用的左部点和一个左部点被选择的右部点。
上面的对称情况。

模拟即可，同时当我们第二或第三种情况后某个点的左部点和右部点都被选择，则可以为弧 CD 增加一点流量。也就是上图中的图四。

Raper

你需要生产 $k$ 张光盘。每张光盘都要经过两道工序：先在 A 工厂进行挤压，再送到 B 工厂涂上反光层。

你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 $n$ 天时间，每天可以先送一张光盘到 A 工厂（或者不送），然后再送一张已经在 A 工厂加工过的光盘到 B 工厂（或者不送），每家工厂一天只能对一张光盘进行操作，同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。求生产出 $k$ 张光盘的最小花费。

数据范围： $n, k\le 5\times 10^5$ 。

我们建出费用流模型。

我们先用 wqs 二分消去 $k$ 的限制，这时，我们的模型就变为了最小费用可行流（即花费最小的费用跑出来的流，只需要不断增广至单次费用大于 $0$ ）。我们就可以像前面的一道题一样开始模拟费用流。

~~所以为什么加个 wqs 二分就能上黑~~

IIIDX

Konano 接到了一个任务，他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有 $n$ 首曲目，每首曲目都会有一个难度 $d$ ，游戏内第 $i$ 首曲目会在玩家 Pass 第 $\left\lfloor \frac i k \right\rfloor$ 首曲目后解锁（ $\left\lfloor x \right\rfloor$ 为下取整符号）若 $\left\lfloor \frac i k \right\rfloor = 0$ ，则说明这首曲目无需解锁。Konano 的工作，便是安排这些曲目的顺序，使得每次解锁出的曲子的难度不低于作为条件需要玩家通关的曲子的难度，即使得确定顺序后的曲目的难度对于每个 $i$ 满足 $d_i \geq d_{\left\lfloor \frac ik \right\rfloor}$ 。同时保证最终字典序最大。

数据范围： $n\le 5\times 10^5$ 。

本题如果所有数都互不相同，那么很好做，只需要贪心地往最小的子树内放最大的就行。而当有重复时，这个做法就行不通了，我们需要换新的思路。

我们先把 $d$ 排序离散化了，设 $f(x)$ 为大于等于 $x$ 的数的个数，一个位置能被填上 $x$ 当且仅当 $siz_u \ge f(x)$ 。而当它填上 $x$ 后， $1\sim x$ 这些位置都会减去 $siz_u$ ，这个操作可以称作预定。由于要求字典序最大，我们可以编号从小到大考虑，每次在线段树上二分出第一个 $siz_u\ge f(x)$ 的位置，将前面的位置全部减去 $1$ 。

这里有一点要注意，就是进入子树时，我们需要将父亲的更改撤销掉，而再新加上子树的修改。这样也很好理解，就是你的父亲已经给子树全部占了座了，但是到你该坐的时候座位还是被占着的，这样就不行了。

没有题目

大小为 $n$ 的 01 矩阵 $A$ ，满足 $A^k = 0$ ，求 $A$ 里面最多有多少个 $1$ 。

数据范围： $n \le 10^{18}, k \le 1145141919810$

我们可以把矩阵看作邻接矩阵，这样就可以变成一个图论问题。我们思考邻接矩阵的幂次是什么意义：经过 $k$ 条边后从 $i$ 走到 $j$ 的方案数。为了让它全为 $0$ ，我们只需要构造一张 DAG，其中最长链不超过 $k$ 即可。

具体点说，我们可以把所有点均匀分成 $k$ 部分，部分内部不连边，剩下的边全部连上。这样就满足了边数最多且最长链不超过 $k$ 。

Complicated Computations

求一个数列的所有连续子序列的 mex 值的 mex。

数据范围： $n\le 10^5$ 。

考虑枚举 $\mathrm{mex}$ ，观察是否该值满足在所有不出现它的区间内的 $\mathrm{mex}$ 不为它。如果对于所有的区间都是这样，我们就可以判断它是 $\mathrm{mex}$ 。

我们可以维护一个 $lst_i$ ，表示该值在我们扫描的过程中上次出现的位置。当我们扫到 $x$ 时，我们检查是否有 $\min_{i=1}^{x-1}\{lst_i \}\le lst_x$ 。如果成立，则证明 $x$ 在该区间不为 $\mathrm{mex}$ 。这样就能标记出所有的值。

时间复杂度 $O(n\log n)$ 。

阿狸和桃子的游戏

阿狸和桃子正在玩一个游戏，游戏是在一个带权图 $G=(V, E)$ 上进行的，设节点权值为 $w(v)$ ，边权为 $c(e)$ 。游戏规则是这样的：

阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。
为了保证公平性，节点的个数N为偶数。
经过 $\frac{n}{2}$ 轮游戏之后，两人都得到了一个顶点集合。对于顶点集合 $S$ ，得分计算方式为

\sum_{v \in S}w(v) + \sum_{e=(u,v)\in E \land u,v\in S}c(e)

由于阿狸石头剪子布输给了桃子，所以桃子先染色。两人都想要使自己的分数比对方多，且多得越多越好。如果两人都是采用最优策略的，求最终桃子的分数减去阿狸的分数。

数据范围： $n\le 10000, m\le 100000$ 。

由于最终要求的是分数之差，因此我们可以把边权拆成两半分到点权上。这样做的话，当两个人分别选了一条边的两个点时，做差之后边权下放到的点权就抵消了。而当一个人选了一条边的两个点时，边权由于算到两个点里了，也会加上边权。因此拆边权后贪心模拟即可。

东兴保卫战

有一颗 $n$ 个节点的树，一开始每个节点都没有军队。现在 $A, B$ 两个人轮流选择一个没有放置军队的点放军队，直到所有点被占领。设 $a$ 为 $A$ 人所占领的点形成的连通块数量， $b$ 为 $B$ 所占领的点形成的连通块数量。 $A$ 先手， $A$ 想要让 $a-b$ 最大， $B$ 想让 $a-b$ 最小。求都采用最优策略的情况下， $a-b$ 的最小值。

数据范围： $n\le 100000$ 。

我们考虑一个结论：在树中，设 $t$ 为连通块数，则 $|V|-|S|=t$ 。有了这个结论，我们就可以按照上一题的思路，点权设为 $1$ ，边权设为 $-1$ 即可。

Boxes

$n$ 个数字 $a_i$ （顺时针给出）构成一个环，每次可以从一个起点出发顺时针给这个环依次 $-1$ 、 $-2$ … $-n$ 。问是否存在一种方案使得能把所有数恰好都减成 $0$ 。

数据范围： $n\le 10^5, a_i\le 10^9$ 。

我们考虑区间加等差数列这个操作，这样会导致差分数组中有一个数减去 $n-1$ ，剩下的数全部加 $1$ 。我们设 $c=\frac{n(n+1)}{2}$ ，即每次操作减少的值，显然一个存在方案的必要条件是： $\sum a_i \bmod c = 0$ 。

我们再设 $M=\frac{\sum a_i}{c}$ ，即一共操作的次数， $m_i$ 为该点进行减 $n-1$ 操作的次数， $d_i$ 为差分数组，则有：

\begin{aligned} d_i & = (M-m_i)-(n-1)m_i\\ m_i&=\frac{M-d_i}{n} \end{aligned}

当 $m_i$ 为非负整数时有解。

Decrementing

黑板上写着 $n$ 个整数。第 $i$ 个整数是 $a_i$ ，它们的最大公约数为 $1$ 。

A 和 B 将使用这些数来玩一个游戏。A 在这个游戏中是先手，他们将轮流进行以下操作（以下两步相当于一次操作）：

选择黑板中大于 $1$ 的一个数，将其减 $1$ 。
此后，将黑板上所有数全部除以所有数的最大公约数。

当黑板上的数全部为 $1$ 时，不能再进行操作的人就失败了。两人都选择最好的方式行动，请求出哪边会最终胜利。

数据范围： $1\le n\le 10^5, 1\le a_i\le 10^9$ 。

首先没有除以 $\gcd$ 的操作时，我们可以通过奇偶性来判断谁胜。而带上除以 $\gcd$ 操作时，可能就会翻盘。由于只有除以偶数的 $\gcd$ 才可能会改变和的奇偶性，我们肯定要对奇数和偶数下手。下面进行一个分类讨论：

当出现 $1$ 时，就相当于没有第二个操作了，直接判断奇偶性。如果场上有奇数个偶数，则先手必胜，否则后手必胜。
当场上有奇数个偶数时，先手只需要保持住当前的局面即可。先手可以取走一个偶数的 $1$ ，而后手无论如何取也会使得偶数的数量回归奇数。先手必胜。
当场上有偶数个偶数，且奇数的数量大于 $1$ 时，上面的情况就会转到后手，因此后手必胜。
而当场上仅有一个奇数，有偶数个偶数时，先手就可能可以翻盘。先手可以取走奇数，这时所有的数都会除去一个偶的 $\gcd$ ，剩下的摊子就留给后手去管。

这样前三个操作都是直接结束，最后一个操作会使所有数除以至少 $2$ ，求 $\gcd$ 的复杂度为 $O(\log n)$ 。因此复杂度为 $O(n\log^2 V)$ 。

Modulo Matrix

构造一个 $n\times n$ 的矩阵. 要求:

所有元素互不相同。
满足 $a_{i,j}\leq 10^{15}$ 。
对于任意两个相邻的数字， $\max(x,y)\bmod \min(x,y)$ 都相等，且均为正整数。
可以证明方案一定存在。

数据范围： $n\le 500$ 。

由于是相邻的数字去取模，我们可以先构造斜线中填的数字，最后构造填数字后中间的数字。一个想法是周围四个格子中全部放质数，中间的格子放旁边质数的 $\operatorname{lcm}+1$ 。但是这样出现的值的级别是 $O(n^8)$ ，无法通过。

我们考虑优化填数。我们可以这样填：一部分质数从左下到右上填，一部分从右下到左上填，交叉的部分就填乘积。可以看下图：

这样就能把填的数字控制在 $O(n^4)$ 级别，再调整一下质数的顺序即可通过。

Distance Sums

给出 $n$ 个互不相同的数 $d_i$ ，表示树上的节点 $i$ 到其他所有点的距离和。请判断是否存在这样一棵树，其中每条边的长度均为 $1$ 。若存在请输出一种方案，否则输出 -1。

数据范围： $1 \leq n \leq 10^5$ ， $1 \leq d_i \leq 10^{12}$ 。

显然的一个结论是： $d_i$ 最小的点为重心， $d_i$ 最大的点是叶子。我们就可以从叶子开始构造，首先先找出最大的点，它的 $siz$ 显然是 $1$ 。根据树形 dp 的公式： $d_v=d_u+n-2siz_v$ ，我们就可以反推出它父亲的 $d$ 值，查询即可。同时记得给父亲加上它的 $siz$ 。这样循环 $n-1$ 次即可构建出整颗树。

但是这样我们算的只是 $d$ 的差值，我们还需要检验 $d$ 是否和题目中给出的相同。直接从重心跑一遍 $dfs$ 比较即可。

赶路

给定二维平面内的一些点，要寻找一个排列 $p$ 使得按照这个排列走，形成的线段不会相交。其中 $p_1=1, p_n=n$ 。

数据范围： $n\le 500$ 。

有意思的题。

我们假设一定有解。设 $solve(l, r)$ 为走 $[l, r]$ 这段区间的点的方案。我们随机选择一个点 $k$ ，和 $l$ 连个线，把平面分成两半，我们可以沿着一半走到 $k$ ，然后再从另一半走到 $r$ 。而至于怎么走，交给剩下的，因为我们假定一定有解，而分成的两半又不相交。

Double Knapsack

给你两个可重集 $A, B$ ， $A, B$ 的元素个数都为 $n$ ，它们中每个元素的大小 $x\in [1,n]$ 。请你分别找出 $A, B$ 的子集，使得它们中的元素之和相等。

数据范围： $n\leq 10^6$ 。

北京高考考 *3000 是吧

我们可以把集合中的子集和看作是一段序列的子段和，我们通过下面的证明我们可以证明这样做是一定有解的。

我们设 $A$ 集合的前缀和为 $suma$ ， $B$ 集合的前缀和为 $sumb$ 。我们先假设 $sumb_n\ge suma_n$ ，那么对于所有 $0\le i\le n$ ，我们都可以找到一个恰好小于等于 $sumb_i$ 的 $suma_{i'}$ ，这里的恰好小于等于的意思就是 $suma_{i'}\le sumb_i< suma_{i'+1}$ 。

由于 $a_i$ 都是小于等于 $n$ 的，那么我们就可以得到 $0\le sumb_i-suma_{i'}\le n-1$ ，一共有 $n$ 种可能，但是我们的 $i$ 的取值一共有 $n+1$ 种。由于鸽巢原理，我们可以得到一定会存在一组 $(i, j)$ 满足 $sumb_i-suma_{i'}=sumb_{j}-suma_{j'}$ 。

我们移项可以得到 $sumb_{i}-sumb_{j}=suma_{i'}-suma_{j'}$ ，也就对应着一段区间的和，至此构造完成。

Swedish Heroes

有一个长度为 $n$ 的序列，你要进行恰好 $n-1$ 次操作，每次操作你需要选择连续的两个数 $a_i,a_{i+1}$ ，然后从序列中删掉这两个数，并将 $-(a_i+a_{i+1})$ 插回到原位置。你需要让所有操作结束后序列剩下的唯一一个数最大，输出这个值。

数据范围： $n\le 10^5$ 。

一个比较显然的性质是：答案一定是 $a$ 序列所有数加加减减得到的，更严谨地说， $a$ 序列中每个数对答案的贡献取决于它在答案中的正负号。

因此我们可以考虑什么样的正负号排列才是合法的。我们统计一下 - 的数量 $p$ , + 的数量 $q$ ，我们可以发现一个规律： $2p+q \equiv 1 \pmod{3}$ 。

证明：显然对于 $n=1,2,3$ 的情况都成立，考虑当长度为 $n$ 时的情况：

每个情况一定都是两种合法情况的组合，那么：

\begin{aligned} -[(2p_1+q_1)+(2p_2+q_2)] &\equiv -(1+1) \pmod{3} \\ &\equiv 1 \pmod{3} \end{aligned}

但是还有一种情况：+-+-+-+-......。这种情况是不合法的。所以我们还要考虑上这点。

想到这个性质之后我们就可以开始 dp 了，我们设 $f[i][j][k][u]$ 表示当前考虑到第 $i$ 个数， $2p+q$ 在模 $3$ 意义下为 $j$ ，上一个符号为 $k$ ，是否出现了两个相同符号相邻 $u$ 。

状态设计出来后就可以开始 dp 了。

f[i+1][(j+2)\bmod 3][0][u|(k==0)]\leftarrow f[i][j][k][u]-a_{i+1}

f[i+1][(j+1)\bmod 3][1][u|(k==1)]\leftarrow f[i][j][k][u]+a_{i+1}

时间复杂度 $O(n)$ 。

AquaMoon and Wrong Coordinate

有 $n$ 个人和 $k$ 个间隔相同时间的时刻，每个人都向正方向做匀速直线运动。给出每个时刻（ $0 \sim k - 1$ ）的所有人的坐标集合（无序），在这 $nk$ 个数中有一个数是错误的，找出这个错误的数并将其改正。

数据范围： $5 \le n \le 1000$ ， $7 \le k \le 1000$ 。

我们可以考虑所有人的速度都是不变的，因此每个时间刻之间的坐标和之差是一定的。形式化的，我们可以写成下面的式子：

设 $f_t=\sum \limits_{i=1}^n(x_i+v_it)$ ，则

\begin{aligned} f_{t+1} &= \sum \limits_{i = 1}^n(x_i+v_i(t+1))\\ &=\sum \limits_{i=1}^n(x_i+v_it)+\sum \limits_{i=1}^nv_i\\ &=f_t+\sum \limits_{i=1}^n v_i \end{aligned}

我们就可以用这个性质找到哪一列出现了问题。但是这无法定位到哪个数。因此我们需要再次动用人类智慧。

我们设 $s_t=\sum \limits_{i=1}^n (x_i+v_it)^2$ 。那么我们再次作差，展开就可以得到下面的式子：

s_{t+1}+s_{t-1}-2s_t=\sum \limits_{i=1}^n 2v_i^2

然后枚举即可。时间复杂度 $O(n)$ 。

Largest Smallest Cyclic Shift

你有 $a$ 个 a， $b$ 个 b， $c$ 个 c。要求用这 $a+b+c$ 个字母拼接成一个字符串，使得这个字符串的最小表示法在所有能拼成的字符串中最大。

数据范围： $a+b+c \le 50$ 。

算法流程比较简单：

将所有字符串存下来。
找到这些字符串中最小的和最大的，拼接到一起后插入，然后删除原来的两个字符串。
重复 2 操作，直到只剩一个字符串为止。

证明：考虑数学归纳法，假设当你有三个字符串 $s_1, s_2, s_3$ （假设 $s_1 < s_2 < s_3$ ）时，拼接的最优方案为 $s_1 s_2 s_3$ 成立，那么当我们有一个串 $s_1s_2\cdots s_k$ 时，有一个另外的字符串 $s_{k+1}$ （ $s_1<s_2<\cdots < s_{k+1}$ ），那么我们把后面 $s_2s_3\cdots s_k$ 看作一个整体，即为 $s$ ，那么易知 $s<s_{k+1}$ 。那么我们可以得到最大的字符串即为 $s_1 s_{k+1} s$ 。

而当最小的情况（ $1$ 个 a，b，c）时，易证该情况成立。

因此我们上面的算法正确。

当然这里还有一点漏洞，就是我们必须保证集合中的所有字符串都为最小表示法。而我们的算法中最小和最大拼接的时候就可以保证这一点性质。因此可以这么做。

用 multiset 就可以做。时间复杂度 $O((a+b+c)\log (a+b+c))$ 。

Strange Sorting

对一个长度至少为 $d$ 的字符串（下标从0开始），定义 d-sorting 的排序方式为，循环 $i$ 从 $0$ 到 $(d-1)$ ，将字符串中下标 $\bmod\ d$ 为 $i$ 的字符按原顺序取出来依次加到末尾。

给定长度为 $n$ 的字符串， $m$ 次操作，每次将所有长度为 $k$ 的子串按左到右的顺序进行一次 d-sorting，每次操作后输出当前串。

数据范围： $m\times n\le 10^6$ 。

我们发现一次操作我们相当于是固定一个长度为 $k$ 的滑动窗口向右划，同时在窗口内进行一次 sorting。我们可以把 sorting 的过程看作是一个置换。我们发现每次向右移动窗口太麻烦，我们考虑把窗口固定，让字符串移动。

我们可以再定义一个置换来让字符串向左移动一位。这样我们只需要把 sorting 的置换和这个左移置换复合，然后循环做 $n-k+1$ 次即可。最后别忘了消除左移的影响。

时间复杂度 $O(n\log n)$ 。

Similar Sets

对于两个序列 $A,B$ ，如果存在两个不同的整数 $x,y$ 满足 $x,y\in A$ 且 $x,y\in B$ ，就说 $A,B$ 是“相似”的。

给定 $k$ 个序列，输出一对“相似”序列，或告知无解。

数据范围： $\sum n\le 2\times 10^5$ 。

我们先从暴力入手。很容易就可以想到两个暴力：

固定一个序列，看其他的序列是否有和它有两个相同的元素。时间复杂度 $O(n\times k)$ 。
枚举二元组 $(u, v)$ ，看是否有两个序列会产生相同的二元组。时间复杂度 $O(\frac{n^2}{k})$ 。

我们直接进行一个根号分治。我们让长度大的序列进行第一个暴力，长度小的序列进行第二个暴力即可。阈值取 $\sqrt n$ ，时间复杂度 $O(n\sqrt n)$ 。

Minimum Path

给定一个包含 $n$ 个点， $m$ 条带权无向边的图，保证这个图没有自环与重边。点编号为 $1$ 到 $n$ ，第 $i$ 条边连接编号为 $u_i,v_i$ 的点，有权值 $w_i$ 。

我们规定若一条路径所包含的边边集为 $E$ ，那么这条路径的权值为 $\sum_{i\in E}w_i-\max_{i\in E}w_i+\min_{i\in E}w_i$ 。

现在你需要求出对于所有整数 $i$ 满足 $2\leq i\leq n$ ，从编号为 $1$ 的点到编号为 $i$ 的点所有路径权值的最小值。

数据范围： $2\leq n\leq2\times10^5,1\leq m\leq2\times10^5;$

我们发现我们要求的是一个最小值，我们考虑放缩一下。我们把减去 $\max w_i$ 放缩为在这条路径上删去一条边，加上 $\min w_i$ 变为在这条路径上再加上一条边的权值。我们发现如果减去/加上的边不是最大/最小值的话，我们得到的结果一定不是最优的。

因此我们建分层图，一个点 $(u, 0/1, 0/1)$ 表示当前在 $u$ 这个点，是否减去一条边，是否加上一条边，然后跑分层图最短路即可。

k-Maximum Subsequence Sum

长度为 $n$ 的数列，支持两种操作：

修改某个位置的值
询问区间 $[l,r]$ 里选出至多 $k$ 个不相交的子段和的最大值。

数据范围： $n, m\le 10^5, k\le 20$ 。

我们先考虑单次询问怎么做。我们建出费用流模型。

我们可以直接开始模拟费用流，每次选出最大的子段，然后将这些边取反即可。就可以直接用线段树来维护，重复 $k$ 轮即可。

维护的东西比较多，可以重定义运算符减少码量。

时间复杂度 $O(nk\log n)$ 。

Game On Tree

crimson000 和 rain 在玩一个游戏。他们有一棵由 $n$ 个结点组成的树。一开始，rain 有 $k$ 个卡片，其中第 $i$ 个卡片位于结点 $a_i$ （注意：所有的结点都是唯一的）。在游戏开始之前，crimson000 将在这棵树的一个结点上放置一个卡片。

这个游戏由一些回合组成。每个回合都将有以下事件发生（完全按照以下顺序）：

crimson000 可以把她的卡片移到相邻的结点，或者不移动；
对于 rain 的每一张卡片，他可以把这张卡片移到相邻的结点，或者不移动。注意：每个卡片的选择都是独立的。

当 crimson000 的卡片与 rain 的任意一张（或多张）卡片在同一结点时，游戏结束。（rain 自己的多张卡片可以置于同一结点上）

crimson000 希望游戏回合越多越好，rain 则相反。

如果某回合中间游戏结束（即 crimson000 把卡片移到了有 rain 卡片的结点上），这回合依然算入总回合数。

对于每个结点，计算 crimson000 一开始将卡片放在该结点时游戏将持续的回合数。

数据范围： $n\le 2\times 10^5$ 。

我们先让被追者停在原地不动，看在每个点它存活的时间，我们记为 $f_u$ 。被追者的策略就是：走到一个能走到的 $f_u$ 最大的点，然后停在原地等死。

现在我们就要找到能走到的 $f_u$ 最大的点 $v$ 。我们考虑点分治。设当前分治中心为 $x$ ，显然这个点 $v$ 一定满足 $f_v>dep_u+dep_v$ ，我们稍微推下式子可以得到： $f_v-dep_v-1\ge dep_u$ ，我们设 $a_i$ 为 $f_v-dep_v-1=i$ 的点的 $f_v$ 的 $\max$ ，那么当前的决策就是 $\max_{i=dep_u}^{+\infty} a_i$ ，对 $a$ 做后缀 $\max$ 即可。

时间复杂度 $O(n\log n)$ 。

Gregor and the Two Painters

给定两个长度分别为 $n,m$ 的序列 $a,b$ 和一个参数 $x$ 。生成一个 $n\times m$ 的黑白矩阵， $(i,j)$ 为黑当且仅当 $a_i+b_j\leq x$ 。求矩阵内黑色四连通块数

数据范围： $n,m,a_i,b_i\leq 2\times 10^5$ 。

我们进行一个钦定代表元。我们钦定一个连通块的代表元为其 $a_i+b_j$ 最小的那一个。我们只需要对这个代表元计数即可。

我们考虑一个点如何成为代表元。只有可能是 $a_i+b_j$ 更小的点与其不连通。我们固定 $j$ ，考虑 $a$ 如何让它和更小的不连通。我们设 $la_i$ 为 $i$ 左侧第一个小于等于它的位置， $ra_i$ 为 $i$ 右侧第一个小于等于它的位置，那么 $la_i, ra_i$ 和 $i$ 不能连通，也就是 $\min(\max_{j=la_i}^i a_i, \max_{j=i}^{ra_i}a_i)+b_j>x$ ，我们记前面那堆为 $ma_i$ ，同理我们对 $b$ 也做相同的事情，就能得到一个点 $(i, j)$ 成为代表元的条件： $a_i+b_j\le x, ma_i+b_j>x, a_i+mb_j>x$ 。直接二维数点，树状数组即可。

时间复杂度 $O(n\log n)$ 。

Nim Cheater（gym103119I）

crimson000 和 Flandre 正在玩小石头！

每天他们都会玩 Nim 游戏，Flandre 先手。crimson000 想要通过作弊取胜，因此他可以花 $a_i$ 元钱来移除编号为 $i$ 的这堆石子。每天玩完过后移除的石子会重新放回来。在第 $0$ 天一堆石子也没有，在接下来 $n$ 天每天会发生一个事件，包括在最右边加入 $b_i$ 个石子（需要 $a_i$ 元移除）和在最右边删除石子。对于每一天求出 crimson000 想要获胜所需的最小钱数。

数据范围： $n\le 40000, a_i<2^{15}$ 。

空间限制： $8$ MB。

我们离线把操作树建出来，那么我们就可以进行一个 dp：设 $f_{u, k}$ 为在 $u$ 这个节点所有石子数异或为 $k$ 的最小代价，转移显然为：

f_{u, i}=\min(f_{fa_u, i\otimes a_u}, f_{fa_u, i}+b_{u})

我们发现这样的空间复杂度是 $O(na)$ 的，必然过不去。考虑优化，我们可以发现如果我们遍历一个点的子树，遍历到最后一颗子树时，我们只要更新完这个点的 $f$ 之后就不再需要这个点的 $f$ 了。基于这一点，我们进行一个类似 dsu on tree 的思路，我们先把所有轻儿子遍历一遍，到遍历重儿子的时候我们把这个点的 dp 值销毁掉。

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

United in Stormwind（gym103202M）

一张问卷有 $m$ 个问题，每个问题有 AB 两个选项。现在有 $n$ 个人填写了这个问卷。我们称一个问题的集合为可区分的，当且仅当有至少 $k$ 对人的这些问题的回答不一样。求有多少个可区分的问题的集合。

数据范围： $n\le 2\times 10^5, m\le 20$ 。

我们先把一个人看成一个 01 串，那么两个人不同答案的问题即为他们异或起来。如果异或的这一位为 $1$ ，那么就会给所有包含这一个问题的集合贡献一对不同的答案。那么我们就有一个很暴力的做法：枚举问题的集合 $S$ ，再枚举两个人，看 $a_i\otimes a_j$ 是否和 $S$ 有交。这样复杂度是 $O(n^22^m)$ 的，必然过不去。

我们考虑先把这个 $O(n^2)$ 给干掉。我们设 $num_i$ 为 $a_j=i$ 的 $j$ 的数量，再设 $F_i$ 为有多少对异或起来为 $i$ ，那么显然：

F_i=\frac{1}{2}\left(\sum_{j\otimes k=i}num_j\times num_k -[i=0]\times n \right)

这个求和就是显然的 FWT 了。

我们再设 $G_S=\sum_{T\cup S\not=\emptyset} F_T$ 。那么答案就是 $\sum [G_S\ge k]$ 。但是我们发现这个 $G$ 不好算，考虑容斥。

G_S=\sum_{T\cup S=\emptyset} F(T)=\sum_{T\subseteq (U-S)}F(T)

这就是显然的一个子集求和了，我们直接进行一个 SOSdp，就能做到 $O(m2^m)$ 了。

时间复杂度 $O(m2^m)$ 。

Degree of Spanning Tree（gym102992D）

给定一张 $n$ 个点 $m$ 条边的连通图，询问是否存在一棵生成树满足其不存在一个度数大于 $\left \lfloor \frac{n}{2} \right \rfloor$ 的点。

数据范围： $n\le 5\times 10^5$ ，

我们先求出一颗生成树，如果当前这棵树不包含度数大于 $\left \lfloor \frac{n}{2} \right \rfloor$ 的点就可以直接输出即可。如果包含，那么我们进行调整。

先把这个度数大的点拿出来作为根节点。由于整棵树的度数之和为 $2n-2$ ，因此只会存在一个这样的点。我们如果把这个点删掉，会出现一堆连通块。如果我们连上一个连通块内部和另一个连通块内部的边，那么我们就可以删掉根节点的一条边。

我们用并查集维护即可。

时间复杂度 $O(n\alpha(n)+m\log m)$ 。

Paimon’s Tree（gym103470G）

Koishi 在她的左口袋里发现了一棵树，最初有 $(n + 1)$ 个白色顶点。

Koishi 将为您提供长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$ 。首先需要选择树中的一个顶点并将其涂成黑色。然后执行以下操作 $n$ 次。

在第 $i$ 个操作中，选择一个通过边直接与黑色顶点 $y_i$ 连接的白色顶点 $x_i$ ，将该边的权重设置为 $a_i$ ，并把 $x_i$ 变为黑色。经过 $n$ 次操作后，我们得到一棵带边权的树。

如果我们最优地选择染色顺序，树的直径的最大长度是多少。

数据范围： $n\le 150$ 。

我们先考虑如果指定了直径的两个端点我们该怎么做。我们把整棵树按照这两个点拽开，这个链上可以进行区间 dp。每个点除了链之外的子树可以当作一个垃圾桶，如果我们不想要一个权值就可以扔到垃圾桶里。

具体的，我们设 $f[l, r, t]$ 为已经合并完 $[l, r]$ 这段区间的点，我们放了 $t$ 个权值。转移就考虑往垃圾桶放还是向两边扩展即可。时间复杂度 $O(n^5)$ 。

我们考虑直接在树上进行区间 dp。我们还是设 $f[u, v, t]$ 为 $u\to v$ 这条链为直径的一部分，放了 $t$ 条边。但是发现这样无法获取垃圾桶的大小，于是再加两维来表示扩展的方向。

设 $f[u, v, t, 0/1, 0/1]$ 表示 $u\to v$ 这条链为直径的一部分，放了 $t$ 条边，和 $u$ 相连这条边是否放过权值，和 $v$ 相连这条边是否放过权值。转移同上。

时间复杂度 $O(n^3)$ 。

ARC132E

有 $n$ 个方块排列在一排。每个正方形都有一个向左或向右的脚印或一个洞，以 <，>，. 表示。

crimson000 将重复下面的程序，直到没有洞为止。

以相等的概率随机选择一个有洞的正方形。
填上所选正方形的洞，站在那里，并以相同的概率随机面向左边或右边。
沿着面对的方向一直走，直到踩到一个有洞的方块或离开这排方块。

这里，方块和方向的选择是相互独立的。

当 crimson000 踩到一个方块（没有洞）时，该方块在他行走的方向上会有一个脚印。如果该方块已经有了一个脚印，那么它就会被抹去并被一个新的脚印取代。

当 crimson000 完成这些操作时，求向左的脚印数量的期望值。

数据范围： $n\leq 10^5$ 。

不难发现最终这个脚印序列一定形如：<<<<=>>>>，其中 = 为一开始就有，且全程没有动过的一块。

那么就可以枚举中间没有动过的这一部分，计算其不被踩到的概率，乘上贡献即可。只考虑左半部分，不被踩到当且仅当每次选择都不选到最右边这个点并且向右走。那么设 $f_i$ 为 $i$ 个点都变为 < 并且不影响到其它点的概率，发现除了上面说的这种情况之外其余情况都为 $f_{i-1}$ 的子问题，得到转移为：

f_{i}=(1-\frac{1}{2i})f_{i-1}

由于左右对称，可以直接拿来用。

复杂度 $O(n)$ 。

CF1610H

给定 $n$ 个节点的数， $m$ 条路径，要求选择一些点，使得对于所有路径，都存在一个点 $x$ ，满足 $x$ 到这条链的最短距离小于 $x$ 到这条链两个端点的距离。求出最少选择多少个点。

数据范围： $n, m\le 3\times 10^5$ 。

考虑链怎么做：把区间按照右端点排序，如果区间内没有选点就选择右端点。

转化到树上类似，如果只存在直上直下的链（也就是链的两个端点为祖先后代关系），可以贪心的选择这条链上最靠上的非端点的点，我们称其为关键点。由于会出现链之间交叉的情况，可以进行 dp。设 $f_u$ 为所有关键点在 $u$ 子树内的直链都能被满足时最少放置的方案数，如果 $u$ 为关键点，那么可以有这样的转移： $f_u=f_y+1$ ，其中 $y$ 为 $u$ 所在链的末尾。但是由于 $u$ 以及其所在链可能会挂上其他的子树，所以还需要一种转移： $f_u=\sum_{v\in son_u}f_v$ 。两者取 $\text{max}$ 即可。

但是上面只考虑了直链的情况，如果出现了拐弯，其实可以直接选择根节点来满足所有的曲链。但是问题出在不知道是否选择过根节点，也不知道所有的链是否被满足过。那么可以对所有的曲链都进行如下操作： $ans\leftarrow \max(ans, f_u+f_v+1)$ 。意思就是处理完两端子树内后再在根节点放一个，如果全程都是 $ans\ge f_u+f_v+1$ ，就意味着所有的曲链都被满足了。

时间复杂度 $O(n)$ 。

CF1446D2

给出 $n$ 个元素组成的序列 $a$ ，求最长的子段使得其中有至少两个出现次数最多的元素。

数据范围： $n\le 2\times 10^5$ 。

首先给出一个结论：两个出现次数最多的元素中有一个为整个序列的众数。证明就考虑调整法，如果两个都不是众数，那么可以扩张区间使得众数的出现次数和其中一个出现次数相同。

那么就可以枚举另一个数 $x$ ，看哪些区间 $x$ 的出现次数和众数一样多了，时间复杂度 $O(na)$ 。

考虑根号分治，按照出现次数来分治，上面的过程只枚举出现次数大于 $\sqrt n$ 的数，因此最多会枚举 $\sqrt n$ 个数。而对于出现次数小于 $\sqrt n$ 的数，枚举出现次数，然后双指针一下即可求出最长的区间。

时间复杂度 $O(n\sqrt n)$ 。

soytony 的博客里说可以加强到 $2e7$ ，但我不会。

AGC035D

有一个由 $n$ 张牌组成的牌堆，每一张牌上都写有一个非负整数。自顶部开始，第 $i$ 张牌上的数字为 $a_i$ 。

crimson000 将重复以下操作，直至牌堆里只剩两张卡为止：

从牌堆里选择三张连续的卡。
把三张卡中位于中间位置的卡吃掉。
把剩余的两张卡上的数字加上被吃掉的卡的数字后按照原来的顺序放回牌堆。

请找出最后剩下的两张牌上所写的数字之和最小是多少。

数据范围： $n\le 18$ 。

显然最终剩下的两张牌是 $a_1$ 和 $a_n$ 。考虑一个数会被计算到答案里几次，因此可以设 $f(l, r, xl, xr)$ 为在 $[l+1, r-1]$ 这段区间内选数，其中左端点会被记录到答案中 $xl$ 次，右端点会记录 $xr$ 次。转移就枚举选择哪个数删掉，因此转移为：

f(l, r, xl, xr)=\max_{k=l+1}^{r-1}(f(l,k,xl, xl+xr)+f(k,r,xl+xr,xr)+a_{k}\times (xl+xr))

时间复杂度据说是 $O(n^22^n)$ ？

可以把贡献直接放到状态里。

AGC034E

给你一颗 $n$ 个节点的树，一些节点上有棋子（恰好一颗）。可以进行若干次操作，每次操作可以将两颗距离至少为 $2$ 的棋子向中间移动一步。问能否通过若干次操作使得所有的棋子都在一个点上，如果能，输出最小操作次数，如果不能，输出 $-1$ 。

数据范围： $2 \leq n\leq 2000$ 。

枚举以哪个点作为最终所有棋子都在的点上，设 $s_u$ 为 $u$ 子树内棋子数， $g_u$ 为 $u$ 子树内所有棋子一开始到 $u$ 的距离之和， $f_u$ 为 $u$ 子树内所有棋子在经过操作后到 $u$ 的距离之和最少是多少。

考虑转移， $f$ 的转移可以看作是下面这个问题：有一些集合，每次可以选择不同集合中的两个数消除，求最终剩下的数的个数。设集合大小之和为 $sum$ ，最大集合大小为 $maxn$ ，当 $2\times maxn\le sum$ 时，会剩下 $0$ 个数；否则会剩下 $2\times maxn-sum$ 个数。

在这里，为了让消去的 $f$ 最多，可以让子树内所需最多操作次数的那个子树选择让其当前棋子的状态为 $f$ 当前的状态，其余的不变，最大化其它的操作次数来让这颗子树内的距离和尽可能减少的多。可以得到转移：

当 $u$ 存在一颗子树 $v$ 满足 $f_v+s_v>g_u-g_v-s_v$ 时，让其他子树内的棋子都和 $v$ 配对， $f_u=f_v+s_v-(g_u-g_v-s_v)$ 。否则 $f_v=g_u\bmod 2$ 。

由于一次操作会让 $g_{rt}$ 减二，因此最少步数为 $\frac{g_{rt}}{2}$ ，只需要通过 $f$ 判断是否有解即可。

时间复杂度 $O(n^2)$ ，可以换根实现到 $O(n)$ 。

CF1070L

给一个 $n$ 个点 $m$ 条边的无向图，你需要将这 $n$ 个点划分为 $r$ 个集合，满足条件：每个点集的导出子图中所有点度数均为偶数。

求出最小的 $r$ 并输出任意一种划分方案。

数据范围： $n\le 2000, m\le 10000$ 。

首先判断 $r$ 是否可以为 $1$ 。

如果 $r=2$ ，那么只有两个集合，考虑进行高斯消元求出在哪个集合。设 $x_u$ 表示 $u$ 所属的集合。如果 $x_u=1$ ，那么它周边需要有偶数个 $x$ 为 $1$ ，否则需要按度数分类讨论。分类讨论后可以得到矩阵构造方法： $a_{i,i}=a_{i,n+1}= deg_i\bmod 2$ ，其余都为邻接矩阵，解方程即可。

猜测一个结论： $r$ 只能为 $1$ 或 $2$ 。证明如下：

如果方程无解，则说明有几列异或起来为 $0=1$ ，右边为 $1$ 表示有奇数个度数为奇数的点，左边为 $0$ 表示所有点都出现过偶数次，奇数度数的点会在自己的方程出现一次，那么在这些点的导出子图中，奇数点连接了奇数条边，偶数点连接了偶数条边，总的度数会变为一个奇数。而无向图度数和总是偶数，矛盾。

高斯消元即可，时间复杂度 $O(\frac{n^3}{w})$ 。

CF1034E

值域 $[0, 3]$ 做子集卷积，对 $4$ 取模。

数据范围： $n\le 21$ 。

设 $f(i)=\text{popcount(i)}$ 。

考虑设 $\{s_i\}=\{a_i\times 4^{\text{f}(i)}\}, \{t_i\}=\{b_i\times 4^{\text{f}(i)}\}$ ，那么对 $s, t$ 做 OR 卷积得到 $c$ ，那么 $ans_i\equiv \frac{c_i}{4^{\text{f}(i)}}\pmod 4$ 。

证明就考虑 $\frac{4^{\text{f}(i)}\times 4^{\text{f}(j)}}{4^{\text{f}(i\text{ or }j)}}$ 在 $i\text{ and }j=0$ 时会有 $1$ 的贡献，其余情况在 $\bmod\ 4$ 情况下都是 $0$ 。

开 ll 其实就能过，因为是相当于在 $\bmod 2^{64}$ 意义下做，最终只需要除以 $4^{21}$ 。

时间复杂度 $O(n2^n)$ 。

未完待续，持续更新