「AGC060C」Large Heap
这个题赛时只做了 15min，而 B 做了快 1.5h。。。
发现到 \(U,V\) 的路径是一条向左延伸，长度为 \(A\) 的链，和一条向右延伸，长度为 \(B\) 的链。记 \(f(i,j)\) 表示，左侧的链长为 \(i\)，右侧长为 \(j\)，路径上的点均比两端点小的概率。
转移系数为 \(\frac{2^{n-i+1}-1}{2^{n-i+1}+2^{n-j+1}-2}\) 与 \(\frac{2^{n-j+1}-1}{2^{n-i+1}+2^{n-j+1}-2}\)，这容易看出。
时间复杂度 \(O(AB)\)。
「AGC059C」Guessing Permutation for as Long as Possible
为什么我赛时不会这个题？？？为什么我现在还是不会这个题？？？
每次询问相当于给边 \((a_i,b_i)\) 定向，而在询问之前知道大小关系，就相当于存在一条 \(a_i->b_i\) 或者 \(b_i->a_i\) 的路径。
事实上，我们只需要考虑路径上恰有三个点的情况（因为存在其他的限制）。这相当于每个元素有两种状态，每次限制要求某两个元素的状态相同，求所有合法的元素状态数。
使用并查集求解，时间复杂度 \(O(n^3logn)\)。
「AGC060D」Same Descent Set
牛逼题。
记 \(F(S)\) 表示大于号集合为 \(S\) 的排列个数，则答案为 \(\sum_SF(S)^2\)。
同时有小于和大于的限制，我们一般把大于号容斥成小于和无限制。记录 \(G(S)\) 表示无限制的集合为 \(S\)，所有合法的排列数。有 \(F(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}G(T)\)。于是
记 \(P(S)=\frac{(-1)^{|S|}G(S)}{2^{|S|}}\)，则答案又等于
这是一个可以 \(O(n^3)\) 求解的形式（\(G(S)\) 可以通过组合数计算）。
以上是我自己想出来的部分，后面的优化我怎么也想不到啊。。。
考虑 \(T_1\cap T_2\) 的本质，它将原来的序列划分成了 \(|T_1\cap T_2|+1\) 段，这些段内的每个位置，两个限制中至少保留一个；而中间的分割点，两个限制均不保留。记 \(A(x)\) 表示长度为 \(x\) 的序列，满足要求的生成函数。答案就是 \((n!)^22^{n-2}[x^n]\frac{1}{1-2A(x)}\)。
使用多项式求逆解决，时间复杂度 \(O(nlogn)\)。
「AGC058D」Yet Another ABC String
容斥哪些位置是一个不合法子串的开头，注意到两个相近的位置可以合并，于是考虑所有极长段，这是经典的。
由于所有模 \(3\) 余 \(2\) 的极长段的容斥系数为 \(0\)，所以我们只需枚举所有模 \(3\) 余 \(0\) 和 \(1\) 的段的个数就可以做到 \(O(n^2)\)。
但我们可以只枚举模 \(3\) 余 \(1\) 的段，剩下的可以通过推组合数式子优化。
时间复杂度 \(O(n)\)。
「AGC054C」Roughly Sorted
每次的操作肯定是选一个这样的位置：不满足题意，且向前交换可以使逆序对减少。
那终止状态中，以其为结尾的逆序对数量恰为 \(k\) 的位置才可能是被交换而来的。而这些位置放在其后继的任意位置也都满足题意。
时间复杂度 \(O(nlogn)\)。