AGC028 C Min Cost Cycle

首先，我们把这个改成，从到连两条边，一条是，一条是。那么我们选一条边连即可。这个问题与原问题等价。

对于每个点，我们根据它的边被选择的状态分类。它的入边的边权可能是，也可能不是；出边边权可能是，也可能不是。这样就分成了 4 类点。我们记表示不是，表示是，那么每个点的状态可以表示为二元组的形式。

对于所有点的二元组，显然和的总个数的相等的，都等于。有了这些二元组我们显然可以方便地求出答案。

如果二元组中没有和，那么必然所有的二元组要么是，要么是。如果同时出现显然会在某个点冲突。

否则，二元组中必然存在相等数量的和。剩下的就是若干个和。注意到我们可以这样构造一个方案：因此我们钦定了一个的状态后，其他的就可以随便选了。

于是我们分以上两种情况统计最小值即可。

时间复杂度。

代码

AGC028 D Chords

考虑计算每一种连通块的贡献。设表示只考虑中的点的所有连接情况，满足最大编号为 j，最小编号为 i 的连通块出现的次数。

显然，只有在长度为偶数，且不存在从连出去的边的时候，DP 值才不为 0。

设表示个点连条边的方案数。显然有

那么我们假设中仍未匹配的点有个。如果是奇数那么。否则区间总共就有种连边方案。但是我们要减掉不合法的。

不合法的相当于存在一个，使得与不相交。那么设里未匹配的点数为（显然是偶数），那么减掉的方案就是。

一个 DP 值对答案的贡献就是，其中表示不在的未匹配点的个数。

时间复杂度。

代码

AGC027 D Modulo Matrix

构造一个的矩阵，满足如下性质：

  1. ；
  2. 所有的互不相同；
  3. 存在一个正整数，满足对于任意两个行相邻或列相邻的元素，有都是。

，保证有解。

我们贪心地让。

我们考虑把矩阵黑白染色。那么黑色的格子是互不相关的。我们把白色的格子填成四周的格子的 lcm 加 1 即可。

考虑怎么把黑色格子填成互不相同的数？我们把黑色格子分两个方向的对角线。每一条对角线上我们乘一个质数上去。这样每个格子就是两个质数的积，且互不相同。第 1000 大的质数是 7919，因此可以过。

注意的时候要特判。

时间复杂度。

代码

AGC027 E ABBreviate

设，那么我们证明，一个字符串能变成字符，仅当以下任一条件满足：

  1. 。
  2. 的权值和与的权值在模意义下同余，且中存在两个相邻相同字符。

显然可以归纳法证明。

那么考虑第二个推论：一个字符串能变成字符串，仅当我们可以贪心地把的一个前缀划分成段使得每一段都能变成的一个字符，且剩余的那段后缀的权值和模余。那么我们把这个剩下的一段并到第段后面即可。

因此我们贪心地在当前串后面构造，设表示贪心匹配能转移到的方案数。答案显然是合法的的和。对于的情况要特判。其他的情况都无所谓。

可能会关心当第段和剩下的一段里都没有连续相同字符的时候，我们咋办？其实分析可以发现，我们可以合理安排合并的顺序使得能变成。只要中有两个相邻相同字符就行。

时间复杂度。

代码

AGC026 F Manju Game

我们把一行黑白染色，假设黑色是奇数的格子，分值和为，白色是偶数的格子，分值和为。

考虑是偶数。

那么我们可以证明，先手得分的上界和下界都是。

证明下界：先手可以选择左端点或者右端点，得到所有的黑色分值或者所有的白色分值。

证明上界：后手显然会让先手尽可能得到少的分值。由于先手的下界是，因此后手的上界是。我们因此可以证明，后手一定能达到上界。当先手选择一个格子后，后手会选择一个方向来获得主动权，然后就可以选择与先手反色的格子，来得到所有白 / 黑色格子的分值，因此后手可以达到上界。

于是是偶数就可以直接输出和。

考虑是奇数。

容易证明，如果先手第一次选择了黑色的格子，那么后手的下界就是，那么先手的上界就是。另一方面，先手的下界也是（直接选择一个端点），于是这样的答案就是。

那么如果先手第一次选择了一个白色格子呢？

先手第一次选择了一个白色格子，那么后手在选择左边或者右边的格子后，主动权仍在先手。先手可以继续选择白色格子，然后后手 ban 掉左边或者右边的部分，继续做。而如果先手打算转而选择黑色格子，根据刚才的证明，先手的得分就加上当前剩下的所有黑色格子值，后手得分就加上剩下的白色格子值。

你发现，先手决定了每次的决策点，而 ban 掉哪一边则由后手决定。换言之，我们设先手的基础分值是。那么最后会出现一个区间，先手的基础分值就减掉这个区间的白色分值，加上这个区间的黑色分值。

假设我们确定了每次的决策点（假设先手选了次白色格子），这个决策点把整个序列就分成了部分。在做了次博弈后会剩下一个区间，而这个剩下的区间是由后手决定的！换言之，后手会找到一个区间，使得这个区间的白色分值减黑色分值尽可能大。这样先手就会减掉尽可能多的分值。

这是一个可二分的问题。我们二分这个最大的分值，那么为了让先手赢，我们就要这个最大值尽可能小。于是相当于判定是否存在一种划分方案，使得划分后每一段的白色减黑色的分值都小于等于这个答案。这里的段数是没有规定的，只要你能划分出来即可（因为权值可能是负数，因此不要把它想成一个傻逼问题）。

思考发现，我们记录一个前缀最大值即可在的时间内判定。

因此总复杂度。

代码

AGC027 F Grafting

首先我们可以钦定一个点不动，让这个点当作根，变成有根树。

然后一次 DFS 可以求出哪些点不用动。

剩下的点我们要动，那么有动的先后关系。在 A 树上父亲比儿子后动，在 B 树上父亲比儿子先动。那么拓扑排序检查关系是否有环即可判断是否合法。

还有一种情况，就是所有点都要动。那么我们枚举第一个动的点的方案，然后把这个点当作根即可。

总时间复杂度。

代码

AGC025 F Addition and Andition

考虑做一次 and 的加法操作，我们实际上是从高位到低位循环，遇到（即两个数的这一位都是 1），就把这两位置为，然后再正序循环进位。进位的状态也是一个二元组，表示第一个数的进位，第二个数的进位。我们可以通过二元组的进位与否来完成这个过程。

然后我们把这个过程做次。但其实我们直接考虑每个进位进了多少次即可。具体地，在上述过程中，我们在正序循环进位的时候，如果又遇到了的状态，我们就又把它置为，然后做进位的操作。这样做次，如果第次遇到了的状态就不去动它，直接退出循环。因为我们的进位次数最多为。

为啥这样是对的？主要原因是，前一个进位肯定追不上后一个进位。

那么我们显然可以优化这个过程。我们把一段连续的相同二元组缩成一段。这样在进位的时候就可以快速转移。比如一个的进位状态加在的状态上，相当于我们分出一个的状态，然后变成了把的进位加在上，那么相当于把变成，然后把的进位加载下一个三元组上。

我们用链表维护上述过程，每次在表头插入，如果遇到就维护进位的过程即可。注意进位的次数不超过。

复杂度使用势能分析，为。

代码