从 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}\)
需要手玩，如果画成柱状图大概是
发现分布很有规律，有连续的单调的段，长度 \(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+，原因是我是唐，在写可撤销并查集时路径压缩了。