数学很难。
头一次感觉非常罚坐，但是细细思考还是很有收获的。
ARC172F
需要尝试对操作找出一个优秀的描述。
手玩一下操作，偷一张题解的图：
仅看这一段，可以发现我们的操作形如：插入一个字符，然后删除一个字符。
做到这里已经是提高组题目了，令 \(f_{i,j}\) 表示 \(S\) 匹配到 \(i\)，\(T\) 匹配到 \(j\) 的最小步数，于是有转移：
答案即为 \(f_{n,n}-n\)，因为每用一次操作会多一步。
从上到下依次是删除 \(i\) 这个字符，在 \(i\) 前面插入 \(T_j\) 这个字符，直接将两个字符匹配，这样的。
需要限制 \(i\le j\)，因为一定是先插入再删除，这样的。
然后根据 DP 方程构造方案是简单的，值得一提的是这个题的操作不能够互换，一定要保证操作是从前往后操作，因为我们是从前往后 DP，\(O(n^2)\)。
https://atcoder.jp/contests/arc172/submissions/50462209
P4727 / P4128
枚举一个置换 \(x\)，考虑他的每一个置换环，设为 \(p_i\)。
考虑不动点的个数，首先对于某一个置换环本身，会发现它有 \(\lfloor\frac{p_i}{2}\rfloor\) 个不动点，对于两个置换环，会发现他们共有 \(\gcd(p_i,p_j)\) 个不动点。
于是可以在 \(O(n^2)\) 的复杂度内计算某个置换环的不动点个数，使用 burnside 引理即可计算给定群的个数。
考虑到上述计算过程中每个置换只会和置换环的大小相关联，于是可以将置换个数变为 \(O(p_n)\)，需要计算被算重的置换个数，也是容易的。
于是做到 \(O(n^2p_n)\)。
https://www.luogu.com.cn/record/147693830
ARC072E
对于 \(i\) 考虑他的答案，发现假设现在前缀是 \(x\)，我们实际可以将 \(x\) 变成 \([0,x]\) 内的任何数。
考虑后缀的函数，发现直接维护若干个 \(\min(x,|x-d_i|)\) 的复合不可行，但是可以考虑维护其最小的非 \(0\) 点，换句话说就是维护一个全 \(0\) 前缀。
初值 \(f_n=1\)，考虑转移：
- 若 \(f_{i+1}\le d_i/2\)，则没有影响，\(f_{i}=f_{i+1}\)。
- 否则 \(f_{i}=f_{i+1}+d_i\)。
容易 \(O(n)\) 转移 \(O(n)\) 判断。
https://atcoder.jp/contests/arc072/submissions/50473911