我要破防了啊啊啊啊啊啊！？！！！！$%%&-526互联

从 2023-07-05 开始更新。
flag: $\mathrm{TEE \ge 1e5.5}$，希望不要反复破防了。

$\mathbb{ARC \ 155 \ F}$

E, F 先咕着，做一些多项式题，这篇题解是我人工翻译的

[1] Double Counting 双重计数
考虑从叶子节点开始，用唯一的方式（如果有的话）来构造出一棵满足条件的树。因此，我们可以对一棵每个节点度为 $D_i$ 的有向有标号树来代替无向树进行计数。

常用的对有标号树计数的方式是双重计数，设 $A$ 是原问题的答案，$B$ 是这棵有根树的数量，其中

树根是 $N$ 个节点中任意一个。
从节点 $i$ 连出的 $D_i$ 条边用 $1$ 到 $D_i$ 标号。

那么，$B=A \times N \times \prod_{i=1}^{N}D_i!$ 。

[2] Construction of the rooted trees 有根树的构造有根树可以按照一下方法构造，此外对于所有的树，按以下方式都有唯一构造。

确定与根相连的节点集合 $S$ 。
对于 $S$ 中的节点，从 $D_i$ 中选择一条指向根，并给其他的边选择指向的节点。
确定其他边的终点。

考虑在完成了第一步和第二步之后，执行第三步的方式有多少，让我们按节点编号的升序，边的升序来开始考虑，可以选择没有父节点且与当前起点不在一个连通块里的点作为终点。在一开始，有 $n - \mid S \mid$ 个节点没有父节点，所以有 $(n - \mid S \mid - 1)!$ 种方式，特别地，这一步的方案数和上一步无关。

接下来，来计算第二步的方案数。这里有 $\prod_{i \in S} D_i$ 种方式选择指向根的边，对于其他边的终点的方案数，观察可以得到这个方案数等于 $N$ 个节点 $\mid S \mid$ 条边组成森林的方案数。

现在，我们把选出来的 $S$ 忽略掉，从 $N$ 个节点和 $0$ 条边开始，重复以下操作 $\mid S \mid$ 次，形成一个有根森林。将一个节点 $u$ 与另一个在其连通块之外的没有父节点的 $v$ 连接。这里有 $\prod_{i = 1}^{\mid S \mid} N \times (N - i) = N^{\mid S \mid} \times \frac{(N - 1)!}{(N - \mid S \mid - 1)!}$ 来选择 $u$ 和 $v$ ，然后消序得到 $N^{\mid S \mid} \times \frac{(N - 1)!}{\mid S \mid!(N - \mid S \mid - 1)!}$ 种方案。对称地来看，其中一共有 $N^{\mid S \mid} \times \frac{(N - 1)!}{\mid S \mid!(N - \mid S \mid - 1)!} \times \frac{1}{N^C \mid S \mid} = N^{\mid S \mid}(N - \mid S \mid)$ 种方案满足所选出来的父节点集合为 $S$ 。

因此，在第一步钦定了 $S$ 之后，这里有 $N^{\mid S \mid - 1} \times (N - \mid S \mid) !\times \prod_{i \in S} D_i$ 棵满足条件的有根树可以被构造出来。

[3] Using convolution 使用卷积
故而，我们定义 $f(x) = \prod_{i}^{N}(1 + D_ix)$，我们有 $B = \sum_{k = 0}^{N - 1}N^{k - 1} (N - k)[x^k]f(x)$ 。于是就可以用多项式直接做了。

$\mathbb{AGC \ 043 \ D}$

需要手玩，如果画成柱状图大概是

AGC043D

发现分布很有规律，有连续的单调的段，长度 $len \in [1,3]$，并且每段的开头放在一起单调不降，长度为 $2$ 的段数量永远小于长度为 $1$ 的段。
考虑为啥会出现这种情况，对于原序列一段 $A_1, A_2, A_3$，如果 $A_1 > A_2$ 或者 $A_2 > A_3$，那么这三个数会有两个连续被取出；如果 $A_1 > A_2$ 并且 $A_1 > A_3$，这三个数会一起取出。
上述一起取出来的数一定会被扔进一个单调的块里面，因为大小为 $2$ 的块和大小为 $1$ 的块都会成对出现，所以大小为 $2$ 的块的个数一定小于等于大小为 $1$ 的块的个数。
于是定义 $dp_{i, j}$ 表示现在长度为 $i$，大小为 $1$ 的块的个数减大小为 $2$ 的块的个数为 $j$ 的方案数，可以直接转移。

$\mathbb{ARC \ 163 \ C}$

~~我是肯尼迪，我脑洞非常大。~~
这题是真抽象，但是我想到了就更抽象。
有个东西叫裂项相消，就是说 $1 + \sum_{i = 2}^{n} \left(-\frac{1}{i} + \frac{1}{i}\right) = 1$，换个写法 $\frac{1}{2} + \sum_{i = 2}^{n - 1} \left(\frac{1}{i} - \frac{1}{i + 1}\right) + \frac{1}{n} = 1$，于是这道题就会做了。
然后这样就会WA，对于 $n = 6$ 会得到如下方案 $2, 6, 12, 20, 6$，出现了两个 $6$。显然不对。
如何避免呢？对于 $n = (i + 1)i$ 的形式，可以先拆一个 $2$ 出来，然后再裂项一下凑出剩下的 $\frac{1}{2}$。

$\mathbb{ARC \ 163 \ D}$

不会竞赛图性质，GG。
现在会了，这里指 将一个竞赛图缩点之后形成的 DAG 是一条单链，证明方式考虑依次加点进图即可。
然后还是不会计数，听说是套路，但是真的不会。
难点在于去计算所有强连通块个数的和。考虑换一种方式去描述强连通块个数？
结合到性质，发现对于一张固定的图，对它缩点，劈开这条单链使其成为两个非空集合的方案数等于强连通个数减一。
更具体地来说，如果缩点后图变成 $scc_1 \to scc_2 \to scc_3 \to \dots \to scc_n$，将其划分成 $A,B$ 两个集合，满足 $A \cup B = scc, A \cap B = \varnothing, \forall u \in A, v \in B, \exists e = u \to v$。
于是达到了切换主体的目的，定义 $dp_{i, j, k}$ 表示考虑了前 $i$ 个点，$\mid A \mid = j$，有 $k$ 条小连大的边，$\Theta(n^4)$ 转移即可。

dp[0][0][0] = 1;
for (int i = 0; i < n; i++) {
  for (int j = 0; j <= i; j++) {
    for (int k = 0; k <= m; k++) {
      if (!dp[i][j][k]) continue;
      for (int l = 0; l <= j; l++) dp[i + 1][j + 1][k + l] = (dp[i + 1][j + 1][k + l] + (dp[i][j][k] * binom(j, l) % Mod)) % Mod;
      for (int l = 0; l <= (i - j); l++) dp[i + 1][j][k + j + l] = (dp[i + 1][j][k + j + l] + (dp[i][j][k] * binom(i - j, l) % Mod)) % Mod;
    }
  }
}

$\mathbb{ARC \ 164 \ D}$

发现这个东西和括号匹配很像，但是一开始想偏了，想成把 + 看成左括号，把 - 看成右括号了。
其实这样非常不对，比如 +--++-。
正确的想法是要把每个球的移动方向看成左右括号。考虑算贡献，本来这个非常套路，但是当时降智了，以为要去枚举匹配的两个点计算，其实这个贡献非常好拆，一对匹配的点 $(x, y)$ 的贡献为 $y - x$，拆成单点，如果方向往左，贡献为正，方向往右，贡献为负。
因为左边的序列定了，右边的序列也能定，所以枚举左边有多少个 ? 变成了 +，以此来判断当前小球的移动方向，即可计算贡献了。

$\mathbb{ARC \ 159 \ D}$

哈哈，我是傻逼。
首先观察得到性质，如果选了一个区间 $[l_i, r_i]$ 中的 $x$，那么一定会去选 $[x, r_i]$，证明非常显然，但是我没想到。
于是分类讨论即可，记 $dp_i$ 表示以第 $i$ 个区间结尾， LIS 的最大长度。
如果 $r_j < l_i$，$dp_i = \max\{ dp_j \} + (r_i - l_i + 1)$；如果 $r_j \ge l_i$，$dp_{i} = \max\{ dp_j - r_j \} + r_i$。

$\mathbb{ARC \ 159 \ C}$

哈哈，我是傻逼。
比较厉害的一点在于如何把对所有元素的操作通过叠加使其变成对两个元素的操作。
首先做一遍 $1, 2, 3, \dots, n$ 然后再做 $n, n - 1, n - 2, \dots, 1$ 相当于啥都没做，于是在第二次操作时交换相邻两个数，那就实现了一个数加一，一个数减一，这样就能构造答案了。

$\mathbb{AGC \ 001 \ D}$

比较有意思的构造题，值得思考的点在于转换这个问题。
算是积累一个技巧，看到回文的限制注意到可以把对应的两个点之间建立边一类的联系。
这道题就充分体现了这个玩意。因为大条件是 $\sum{a_i} = \sum{b_i} = n$，需要做的是在把 $a$ 这边的限制刻画完之后把 $b$ 拼上去。
然后我来偷两张图（/bx command_block）。

这个构造非常自然，一个是 $a_i$ 为奇数一个是 $a_i$ 为偶数的情况。但是也注意到了如果 $a$ 中出现了大于两个奇数，这个是 Impossible 的。
然后按图模拟即可，注意特判 $m = 1$ 的情况。

$\mathbb{AGC \ 001 \ E}$

我先猜一手，这道题应该从 $a_i, b_i$ 的值域大小出发并转组合意义去做。
注意到 $\binom{a_i + a_j + b_i + b_j}{a_i + a_j}$ 的组合意义是从 $(0, 0)$ 出发走到 $a_i + a_j + b_i + b_j$ 的方案数。
但是这样有点问题，我需要去记录每种情况的 $a_i + a_j + b_i + b_j$ 是多少，相当于这个组合意义并没有起到作用。思考这样做的问题在于组合意义是对于 $(a_i, b_i), (a_j, b_j)$ 这两个点对而言的，复杂度与 $(a_i, b_i), (a_j, b_j)$ 这样的点对数量有关，如果要降复杂度，需要拆单点贡献。
修改一下组合意义，把起点从 $(0, 0)$ 挪到 $(-a_i, -b_i)$ 上去。于是转化为求两两点对之间的路径数，这样复杂度非常对，因为这样做的复杂度与 $a_i, b_i$ 的值域相关，总的复杂度是 $\Theta(ab + n)$，需要注意减去 $i = j$ 的情况后答案应该除以 $2$。

吐了， atcoder 模数居然不是 $998244353$。 /tuu

$\mathbb{AGC \ 001 \ F}$

先放一波我的错误思路。

看起来不是很好处理，先变形一下这个限制？
$i, j$ 能够交换必须满足 $\mid i - j \mid \ge nk, \mid a_i - a_j \mid = n$ 那么 $i$ 和 $j$ 能够换。
发现上面这个转化不是等价的，只是一个必要条件。
怎么办？这说明了从条件出发并不是一个好的方向。那从问题出发，要是字典序最小，不难想到有这样一种方式去交换。
$p1 < p2 < p3$，且 $p1, p2$ 之间距离大于等于 $k$，$p2, p3$ 之间距离小于 $k$，$a_{p2} = a_{p1} + 1 = a_{p3} + 2$。
那么我做 swap(p1, p2) 后接一个 swap(p2, p3) 就变成了 $p3, p1, p2$ 这样就非常优秀。
能不能推广？能不能月下无限连？

不能。

问题在于我需要去刻画三个点的关系，并且在不断弱化的我限制，这样是非常不优秀的。
并且值得注意的是在这种有限制的交换关系求方案思路重点一般在限制上，但是我从一开始弱化了这个限制导致不可做。

这道题解法就很牛逼了，题目着重刻画的是下标和值的关系，正解是把这两个玩意儿反过来。
~~这显然不是人类能够想出来的东西~~，但是也有其合理性。
记反过来之后的排列是 $q$，$i, j$ 能交换的条件是 $i,j$ 相邻，且 $\mid q_i - q_j \mid \ge k$。为什么这样会更好下手？下标相邻这样的限制是非常强的，它是由 $\mid a_i - a_j \mid = 1$ 这个限制转化过来的。这就提示在有对偶（姑且称之为）的两个限制下，尽量把强限制（等于）放在更好刻画的位置（下标），把若限制（偏序关系）放在比较能用某些结构刻画的位置（值域）。

下一步继续用更强的限制刻画偏序关系，当 $\mid q_i - q_j \mid < k$ 时他们的相对顺序不会发生改变，因为交换是相邻的，当存在交换使 $i, j$ 相邻时他们会因为值的限制卡住动不了。

然后对这样的点对 $i \rightarrow j$ 建边。

最后把这个边建回原图，对于 $p_i, p_j$ 如果 $\mid i - j \mid < k$，则要求他们的大小关系不变，如果要求 $p_i < p_j$ 就建边 $i \rightarrow j$。
运用一下拓扑字典序原理解决这个问题，注意不能直接贪心，应该建反图后从大往小贪（典中典）。

然后想了一下发现我剩下的几步还是不会（纯纯废物了）。
考虑 $i$ 能向 $\{ j : \mid i - j \mid < k, p_j < p_i \}$ 这个集合里面的点连边，$i$ 的入度为 $0$ 的充要条件是 $p_i$ 是 $[i - k, i + k]$ 这个区间里面的最大值。那么用一个大根堆去维护目前出度为 $0$ 的点即可，然后用线段树维护区间最大值，在删除 $i$ 时，查看 $[i - k, i), (i, i + k]$ 中最大值编号，如果入度为 $0$ 就塞进大根堆。

$\mathbb{AGC \ 002 \ D}$

忘了整体二分怎么做了，完蛋啦，哈哈。
没啥好说的，直接整体二分拿并查集连连就好，然后我调了2h+，原因是我是唐，在写可撤销并查集时路径压缩了。?

$\mathbb{AGC \ 002 \ F}$

换个方式去刻画题目，考虑到所有颜色都是等价的（把涂白的球记为 $0$），那么题目变成要求第 $i$ 种颜色的球出现在第 $i$ 个白球之后，最后的方案总数乘 $n!$ 即可。发现可以把白球出现这个事件拎出来以此对整个过程分段。定义 $dp_{i, j}$ 表示放了前 $i$ 个白球，前 $j$ 种彩球都放了 $k - 1$ 的方案数。

千万不能把每种彩球分开处理，原因很简单，分开处理后需要记录每种彩球出现了多少个，而这种开销是无法接受的。相反把每种彩球都分在一起可以更有效地去计数。

转移分成两种

放一个白球，这样一定合法，方程是 $dp_{i + 1, j} = dp_{i + 1, j} + dp_{i, j}$
放一种彩球，满足的要求是 $j + 1 \le i$，注意到要先放一个在最靠前的空位上，于是剩下了 $k - 2$ 个球，有 $\binom{nk - i - (k - 1)j - 1}{k - 2}$ 种放法，于是方程是 $dp_{i, j + 1} = dp_{i, j + 1} + dp_{i, j} \times \binom{nk - i - (k - 1)j - 1}{k - 2}$。

需要特判 $k = 1$。

$\mathbb{AGC \ 003 \ D}$

从考察一个数是否是完全立方数出发，一个数如果是完全立方数，当且仅当它的所有质因子的次数都能被
$3$ 整除。
一个很 naive 的思路是分解每个质因数，按模 $3$ 的余数分类，一个类和恰好另一个类对应乘积是完全立方数。
但是这个数据范围着实分解不了质因数。首先把 $(1, s^{\frac{1}{3}}]$ 内的质数除掉，这样剩下的性质就只能是 $p, p^2, p_1p_2$，注意到 $p^2$ 需要再补上 $p^{3k + 1}$ 才会变成完全立方数，因为已经超过了 $s^{\frac{1}{3}}$，所以补上的一定是 $p$，而 $p_1p_2, p$ 必须补上 $p^2, p_1p_2$ 才行。
于是我们调了一下上界获得了和暴力一样的做法。

$\mathbb{AGC \ 003 \ E}$

神仙东西。
首先去除一堆没用的 $n_i$，得到的序列是严格递增的。这个操作是在干嘛？
是把原序列复制几遍并接上一个前缀，记 $P_i$ 为操作了 $i$ 次之后的序列，$dp_{i, j}$ 表示 $j$ 在 $P_i$ 中出现的次数。
令 $t = \lfloor \frac{n_i}{n_{i - 1}} \rfloor$，那么 $P_i$ 就由 $t$ 个 $P_{i - 1}$ 和 $P_{i - 1}$ 的前 $n_i \mod n_{i - 1}$ 个字符组成，于是先将 $dp_{i, j}$ 初始化为 $dp_{i - 1, j}$。
然后前缀怎么办？？？

现在重新想一下上面的思考是怎么来的，首先淡化 $P_i$ 和 $P_{i - 1}$ 之间的转移。改成 $P_i$ 从 $P_{pre}$ 转移过来。
那么有

\[\begin{aligned} P_i = \lfloor \frac{n_i}{n_{pre}} \rfloor P_{pre} + P_{pre}[1, n_i \ \mathrm{mod} \ n_{pre}] \end{aligned} \]

$pre$ 的寻找自然是最后一个小于 $n_i$ 的 $n_{pre}$，然后抛弃掉 $n$ 个表示，把 $n_i \ \mathrm{mod} \ n_{pre}$ 和 $n$ 放在同一位置，那么这就是个子问题，递归下去处理即可。
复杂度反而不是重点。
反思为什么想不到这种方法，因为一般的题目强调的都是两两状态之间的转移，在想题的时候就陷入了如何从 $P_{i - 1}$ 到 $P_i$ 的陷阱里面。要想到泛化，泛化，泛化。

$\mathbb{AGC \ 003 \ F}$

你说得对，但是连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数做完了。

没有，注意可以直接矩阵乘法加速。

$\mathbb{AGC \ 004 \ E}$

物理原理，相对移动。
固定机器人不动就变成了挪动出口去救机器人，假设把出口挪动了 $(p_x, p_y)$，那么以 $(x_0, y_0)$ 为左下角到以 $(x_0 + p_x, y_0 + p_y)$ 为右上角的这个矩阵里的所有机器人可以被救。
于是直接 $\Theta(n^4)$ 定义 $dp_{w, s, a, d}$ （含义看键盘可知）暴力转移即可。

$\mathbb{AGC \ 004 \ F}$

大分类讨论题。
非常神了，看到 $m \in [n - 1, n]$，不难想到分成树和基环树的情况讨论。

首先讨论树的情况，每一次都会改变两个点的颜色，一个点必须被改变奇数次，所以当总点数为奇数时直接判无解。
那么偶数时怎么计算最小步数呢？能不能形象一点？改变颜色一类的题目要想到把改变颜色变成移动颜色之类的更好计算的方式。
因为树是二分图，于是把整棵树都黑白染色，现在改变一下操作，变成颜色不同的两个点可以互换颜色，不难发现一个点被操作奇数次的结果是颜色反色。于是把黑色看成有棋子在上面，把白色看成空，操作就是移动棋子，使得每个棋子最终落在一开始没有棋子的地方。
也容易发现当棋子和空白点数不同时是无解的。
对于一个节点 $u$，假设子树内有 $x$ 个棋子，总共点数有 $siz_u$ 个，可以猜想到经过 $u$ 这个节点的棋子数目下界是
$x - (siz_u - x)$ 步，意思是能够内部消化的就内部消化，不能内部消化的都要经过 $u$ 离开这颗子树，于是所有点被经过的次数就是需要移动的总步数（注意一下取绝对值），多单位移动的步数问题可以转化为考虑每一个节点被经过的次数问题。

然后是基环树的情况，次数需要讨论环的奇偶性。
当环是偶环时，先抠出来一条边变成树，是否无解和树的情况一致，考虑多出来的这条边能给我们带来什么？
显然某些情况下直接通过这条边要比在环上绕一大圈更优，于是现在单独考虑这条边要被经过多少次。
把环上的点拉出来为 $p_1, \dots, p_l$，这条边连接了 $p_1, p_l$，记棋子为 $1$，空格为 $-1$，子树和为 $a_i$，如果这条边被经过了 $x$ 次，那么最后的答案是 $\sum_{i \in left} \mid a_i - x \mid + \sum_{i \in right} \mid -a_i - x \mid + \mid -x \mid$。（初一数学问题）。
最后是奇环情况，此时这个环两边的点是同色的，操作一次增加或减少 $2$ 个棋子。
那么断开这条边，只要黑白点数的差是偶数就可以利用这条边调整至有解，于是先调整有解，然后跑树的做法就可以了。

$\mathbb{AGC \ 005 \ D}$

~~我一眼秒了，然后看题解发现推错了一步，题解是wgy在两年前写的。~~
第一步先容斥，记 $f(i)$ 表示至少 $i$ 个地方填冲突的方案数，于是得到

\[\begin{aligned} res = \sum_{i = 0}^{n} (-1)^{i} (n - i)! f(i) \end{aligned} \]

考虑怎么算这个 $f(i)$，因为我组合数学撇，所以先建图，建出来 $k$ 条链，相当于在这 $k$ 条链上选出来 $i$ 条边，有一个 $\Theta(n^2)$ 的 dp 可以直接做。

$\mathbb{AGC \ 005 \ E}$

感觉很神奇，趁还没被题解定式思维，先写一下我自己的想法。
可以观察到答案一定是偶数，最后一步一定是 B 去抓住 A，A 不可能自己撞上去，因为他选择停一步会更优。
所以应该是从最后结束或是结束不了的情况入手，分析两个人的策略。
首先排除掉无解的情况，即是 B 永远抓不到 A，利用样例 4，看到这种情况下 A 可以反复横跳，即是说对于 A 树里面直接相连的 $i \rightarrow j \rightarrow k$，如果 B 树中直接连接 $i, j, k$ 的只有 $1$ 条边，那么 A 可以利用这个链一直跳。
那么反过来如果不存在这种情况 B 的策略就应该是一直朝着有 A 的子树里面走，A 跑到离 B 最远的点等死就好了？

看了题解，题解的描述更具体，如果一条红边连接了在蓝树上两个距离大于 $2$ 的点，那么只要 A 跑到了这两个点任意一个，游戏就不会停止。否则就很好想了，此时不存在一条红边连接了蓝树上距离大于 $2$ 的点，根据最先的观察，A 最理想的情况一定是跑到蓝树上离 B 的初始点最远的点然后等 B 来找他。

于是这是一个对于先手的单手游戏了，对于先手一定需要保持在第 $i$ 步走到的节点 $p_i$ 满足 $dis(p_i, B) > i$ 才能保证不被抓住，这样 $\Theta(n)$ 就能做了。

很牛逼啊，为啥最后做法这么简单，因为无解的情况自带性质，如果有解那么必定使无解的条件不成立。提示是从无解情况出发，用无解的性质当条件做题。

$\mathbb{AGC \ 005 \ F}$

这是什么套路？我完全不会。
看起来很 dp，所以用湘妹儿思考法我来切换主体。
考虑一个点 $u$ 对询问 $i$ 能造成啥贡献？
枚举块的大小得到下面的式子

\[\begin{aligned} f_u = \sum_{i = 1}^{n} \left( \binom{n}{i} - \sum_{v \in son_u} \binom{siz_v}{i} \right) \\ \end{aligned} \]

哈哈，我就会这个 $\Theta(n^2)$ 的暴力。???
哈哈，切换主体之后换不回来了。
重新定义 $f$ 把 $f_i$ 的下标改成连通块大小。

\[\begin{aligned} f_i &= \sum_{u = 1}^{n} \left( \binom{n}{i} - \sum_{v \in son_u} \binom{siz_v}{i} \right) \\ &= n\binom{n}{i} - \sum_{u = 1}^{n} \sum_{v \in son_u} \binom{siz_v}{i} \end{aligned} \]

然后把 $siz$ 相同的子树视为一个整体。记子树大小为 $i$ 的子树个数为 $cnt_i$，改写上面的式子

\[\begin{aligned} f_i &= n \binom{n}{i} - \sum_{siz = 1}^{n} cnt_{siz} \binom{siz}{i} \\ &= n \binom{n}{i} - \sum_{siz = 1}^{n} \frac{cnt_{siz} siz!}{i!(siz - i)!} \\ &= n \binom{n}{i} - \frac{1}{i!} \sum_{siz = 1}^{n} cnt_{siz} \cdot \frac{siz!}{(siz - i)!} \\ \end{aligned} \]

记 $F = \sum cnt_{siz} siz!, G = \sum \frac{1}{(siz - i)!}$ 反转一下 $G$ 的下标
发后面一坨是具有 juanable 的性质。

现在写完了，我觉得说得对，没什么困难的地方。
?扯淡。那为啥我做不来。

$\mathbb{AGC \ 006 \ C}$

真聪明，置换快速幂。?
这个期望一眼吧。。。
难点在于需要很快找到换了 $k$ 次之后的位置，然后发现这个映射和次幂有着相同优美的性质。
于是可以 $\Theta(n \log k)$ 做了。

$\mathbb{AGC \ 006 \ E}$

这个东西是？魔方？？？不让我求步数那我是不是真的可以当魔方做？
? 好复杂，先放了。

$\mathbb{AGC \ 006 \ F}$

既视感过于强烈以至于我觉得这就是道傻逼题。
没有手玩能力的我什么时候才会做这种题？？？?
《手玩一下》发现可以三染色。
为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手？
当 $x + 1 \equiv y \pmod 3$ 时 $x,y$ 之间会有连边，于是三染色，如果染色失败，就说明这张图会变成任意两点之间会有连边，贡献是 $2^{siz}$。
如果只有两种颜色，那啥也干不了。
否则记每种颜色点数为 $c_0, c_1, c_2$ 贡献是 $c_0c_1 + c_1c_2 + c_0c_2$。

$\mathbb{AGC \ 007 \ E}$

首先二分答案出 $mid$，转成判定问题，判定能不能使所有叶子之间的路径权值都小于 $mid$。
结合到题目给出的树的特定的形态思考路径有哪些性质？对于 $u, v$ 是兄弟节点，在访问了其中一个之后一定会马上访问另一个，因为每条边只能经过两次，更进一步地，发现这是在模拟深搜的过程。
考虑把 $dfn$ 序拉出来，记 $dfn$ 的反序列为 $p$，只保留叶子的信息为 $p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_k$。
在二分出 $mid$ 的情况下这个序列合法当且仅当 $\forall i \in [1, k), \mathrm{dist}(p_i, p_{i + 1}) \le mid$，考察这个序列的生成方式，如果叶子节点存在兄弟节点，那么这一对将会连续加入序列，否则单独加进去。那么对于以 $u$ 为根的子树内一定会存在一条跨过左右子树的路径，思考这条路径怎么去计算，令 $son_0, son_1$ 分别为 $u$ 的两个儿子，$leaf_0, leaf_1$ 分别为左子树内最后访问的叶子节点和右子树里最先访问的叶子节点，那么这条路径 $l = \mathrm{dist}(leaf_0, son_0) + \mathrm{dist}(son_0, u) + \mathrm{dist}(u, son_1) + \mathrm{dist}(son_1, leaf_1)$。拆一下，中间的 $\mathrm{dist}(son_0, u) + \mathrm{dist}(u, son_1)$ 是定值，所以决定这条路径的是 $\mathrm{dist}(leaf_0, son_0) + \mathrm{dist}(son_1, leaf_1)$，所以现在可以有一个初步的状态为 $dp_{u, l, r}$ 表示对于以 $u$ 为根的子树内第一个访问到 $l$，最后一个访问到 $r$ 的过程中路径的最大值，转一下

\[\begin{aligned} dp_{u, l, r} = \min\{ \max\{dp_{son_0, l, k_1},dp_{son_1, k_2, r}, \mathrm{dist}(u, k_1) + \mathrm{dist}(u, k_2)\} \} \end{aligned} \]

然后写成判定形式

\[\begin{aligned} dp_{u, l, r} = dp_{son_0, l, k_1} \& dp_{son_1, k_2, r} \& [\mathrm{dist}(u, k_1) + \mathrm{dist}(u, k_2) \le mid] \end{aligned} \]

发现这个状态很蠢。怎么优化？？？不会了。

问题在哪里？在于我的状态后两维记录的是叶子节点的编号，导致我很难看出关键之处，换一下把叶子节点编号直接改成到该叶子节点的距离。

\[\begin{aligned} dp_{u, l, r} = dp_{son_0, l, k_1} \& dp_{son_1, k_2, r} \& [ k_1+ k_2 \le mid] \end{aligned} \]

突破口在状态本身，减少状态数的最直接方法是去掉不必要的状态。也就是说如果存在 $l_1 < l_2, r_1 < r_2$，那么对于 $dp_{u, l_1, r_1}$ 来说 $dp_{u, l_2, r_2}$ 这个状态是没有意义的。
这部就有单调性了吗，对于 $l$ 升序排，那么对应的 $r$ 必定是降序。对于 $dp_{x, l, r}$ 来说在另一棵子树内能和它合并的状态一定是一个前缀，直接双指针就能做到 $\Theta(n \log^2n)$，状态数不难分析得到。

$\mathbb{AGC \ 007 \ F}$

拿到这种题完全没有思路。。。开始不了啊。。。
注意可以从特殊情况开始思考，首先判掉 $S = T$。
算是长脑子，记住这种生成序列一类的题可以从被生成序列和原序列之间（点对点、区间对区间）的关系入手。
这题最重要的性质在于将被生成元素和原元素之间连边后所有的边都不相交，且一定是一个字符对应一个区间，这是由这道题特殊的生成方式决定的，重点在于要动手多玩。

得到一个初步的策略，对于一个点，先尽量往右走，走到需要被覆盖的左端点处，然后一路复制下来，最后一步覆盖掉整个区间。
说得非常抽象，具体操作？

看了一圈题解感觉抽象。放个代码。

int up = n - 1, down = n - 1;
while (down >= 0) {
  while (down && t[down - 1] == t[down]) down--;
  while (up >= 0 && (up > down || s[up] != t[down])) up--;
  if (up < 0) return printf("-1"), 0;
  while (!que.empty() && que.front() - (int)que.size() >= down) que.pop();
  if (up != down) que.push(up);
  res = Max(res, (int)que.size() + 1);
  down--;
}