按照值从小往大考虑。设 f_{i, j} 表示考虑到 i，< i 的数一共换了 j 个 i，< i 的数的方案数。则状态总量为 \mathcal{O}(n)，转移是前缀加，差分即可。
时间复杂度 \mathcal{O}(n)。
D
若 k \nmid m 则答案为 0。以下令 m \leftarrow \frac{m}{k}。
众所周知，一个方案合法，则必然存在一种顺子和刻子的分配方案，使得从每个位置开始的顺子不超过 k 个。
先放顺子，设 f_i 表示一共放了 i 个顺子的方案数，容斥可得
f_i = \sum_j (-1)^j \binom{n - k + 1}{j} \binom{i - jk + n - k}{n - k}
加上刻子，答案为
\sum_i f_i \binom{m - i + n - 1}{n - 1}
如果要求 f 没有高效简单的做法。但是如果我们把两个式子写到一起，并把 j 提到最外层
\sum_j (-1)^j \binom{n - k + 1}{j} \sum_i \binom{i - jk + n - k}{n - k} \binom{m - i + n - 1}{n - 1}
注意到 i 是没有范围限制的。根据恒等式
\sum_i \binom{a + i}{c} \binom{b - i}{d} = \binom{a + b + 1}{c + d + 1}
可以得到答案为
\sum_j (-1)^j \binom{n - k + 1}{j} \binom{m - jk + 2n - k}{2n - k}
时间复杂度 \mathcal{O}(n^2)。
E
我们的目标是对于每个非叶子结点，都存在一条新加的边跨过它。
如果叶子个数为偶数，经典地，按照 \rm dfn 序分成两半，前一半匹配后一半即可。
如果叶子个数为奇数，我们需要选择一个的叶子连其他的点，剩下的叶子前后匹配。对于叶子 u，设 v 为 u 深度最小的祖先，满足 v \to u 的路径上除了 u, v 的其它点都只有一个儿子，则若选择 u 连其他的点，可以选的点为除了 v \to u 这条路径上的点外的任意点。枚举叶子贪心即可，不难证明正确性。需要注意的是，这时我们必须选定一个 \deg = 3 的结点作为根才能保证上述做法的正确性，显然 \deg = 3 的点在叶子个数为奇数的时候必然存在。
时间复杂度 \mathcal{O}(n \log n) 或 \mathcal{O}(n)。
F
看了 10min 就会了，但是因为前四题花了长达 100min 导致赛时没过 /cf
经典地，对于一个排列 p 和 i = 0, 1, \cdots, n，依次找出 p 中 \le i 的所有位置，这样会形成 n + 1 个 01 序列 s_0, \cdots, s_n。一种操作方案能将 p 排序当且仅当其能将 s_0, \cdots, s_n 排序。
首先来考虑维护哪些 01 序列是好的。称操作 i 有效，当且仅当存在一个 01 序列 s，使得 s 经过前 i - 1 次操作后和经过前 i 次操作后不同。注意到共有 2^n 个序列，并且每个序列最多进行 n^2 次操作，所以有效操作的数量为 \mathcal{O}(n^2 2^n)。我们维护有效操作集合，如果当前操作有效，则更新其生效的每个 s 的状态，并判断其是否变为好的，并且更新有效操作集合。这一部分实现精细可以做到 \mathcal{O}(n^3 2^n)。
然后来考虑统计路径数。设 f_s 表示 (0, 0, \cdots, 0) \to s，除了 s 以外都是好位置的路径数；g_s 表示 s \to (1, 1, \cdots, 1)，除了 s 以外都是好位置的路径数。加入一个好的序列 s 时，先用 f_s \times g_s 更新方案数，再更新 s 超集的 f 和子集的 g 即可。这一部分实现精细可以做到 \mathcal{O}(n 3^n)。