ZR20220816

T1、T3没人会，感觉很没必要

T2：有意思的 dp

题目本质上就是要求一个排列，使得操作次数最少，状压暴力是 $O(2^m m^2n + 2^mm^2)$ 的，考虑可以均摊一下复杂度，发现其实转的次数就是夹在两个元素之间的元素，因此就可以记一个 $O(m^3)$ 的状态，cnt[i][j][k] 表示夹在 夹在i,j中间的k总共有多少个 ，然后每次从 f[s1][x] 转移至 f[s2][y] 就暴力计算 $\sum$ cnt[x][y][] ，然后就发现时间复杂度是 $O(m^3n+2^mm^3)$ 的，大概就是一个均摊的思想，更进一步，发现从 $i$ 转到 $j$ 的值就是 (pos[j]-pos[i])%m ，因此我可以记录 $\sum$ pos[i] 、$\sum$ pos[j] 与 总共有多少 $(i,j)$ 满足在排列中 $j$ 在 $i$ 前，然后dp的时候动态维护这几个数组就行了。