鱼
首先如果枚举了\(A\)和\(D\)，则\(BC\)与\(EF\)独立，则可以分别考虑，最后将方案乘起来。
先来考虑\(BC\)。显然三角形\(ABC\)与三角形\(BCD\)都是等腰三角形。平面上的等腰三角形不会很多，实际上是\(O(n^{2.137})\)级别的。因此对于每个点，可以按照其它点到这个点的距离排序，然后暴力枚举等腰三角形。将一条底边统计出左右的顶点，然后统计贡献即可。
对于三角形\(DEF\)，枚举\(D\)，然后按极角序枚举\(A\)，则合法的\(EF\)一定在一个区间中，且区间左右端点可以类似莫队均摊\(O(1)\)维护出来，则当前\(AD\)的值就是每个距离内点数选择两个，这个可以在类似莫队的过程中维护。
那么就做完了，时间复杂度\(O(n^{2.137}+n^2\log n)\)
JOJO
首先考虑没有操作\(2\)的情况，考虑将其复杂度由\(O(nx)\)变成\(O(n)\)级别的。因为保证了相邻不同，因此如果前一个匹配到了某个串的一半，是没有意义的。因此前一个的\(next\)会一直跳，直到长度和字符都一样为止，然后后一个才可以匹配。
然后考虑有回退，显然建立操作树变成撤销。KMP复杂度错误的问题在于是均摊不是严格，如果能搞一个严格的KMP，使其单次复杂度为\(O(\log n)\)之类的就可以了。如果单次border能减半就很好。
如果本来border就小于一半，则直接跳即可。否则因为大于一半所以一定有周期，则可以直接去掉若干周期，就可以剩下小于一半。这样子暴力跳就可以了。时间复杂度\(O(n\log n)\)。
多边形
最终状态肯定是所有点连向\(n\)。
我们先将开始就连向\(n\)的点单独拿出来，然后分成若干个部分，显然这些部分之间不会相互操作，因此独立。而对于每一部分来说，一定有一条边连接两个端点，则下一次操作一定是操作这个端点，增加一条连向\(n\)的边，并分成两部分。这样可以建立一棵树的形式，旋转相当于splay的左旋，则可以单次\(O(n)\)树形dp。
考虑一次旋转的影响，一次旋转影响的只有\(O(1)\)个节点所以可以拿出来暴力，如果这个点没有父亲，则会使答案减一，这个要注意。
时间复杂度\(O(n)\)。
校园旅行
首先有一个\(O(m^2)\)的大暴力，大概就是每次两边扩展一个点。
考虑减少边数至\(O(n)\)，就可以过了。因为这是一个无向图，因此一条边可以反复走。对于\(01\)的边组成的联通块， 一定是二分图，因此只保留一棵生成树不影响答案。对于同色的边组成的联通块，如果是二分图，保留生成树即可，否则需要可以改变奇偶性，则加一个自环即可。时间复杂度\(O(n^2)\)。
白兔之舞
先设\(f_{i}=W^n\)，则白兔走\(i\)步的答案为\(f_i[x,y]\)。
对于每个余数枚举白兔走的步数，有\(ans_t=\sum\limits_{i=0}^{L-1}{C_{L}^{i}f_{i}[x,y][i\bmod k=t]}\)。
看到整除上单位根反演，有
\(=\frac{1}{k}\sum\limits_{i=0}^{L-1}{C_{L}^{i}f_i[x,y]\sum\limits_{p=0}^{k-1}{\omega_k^{(i-t)p}}}\)
消去\(C_{L}^i\)，考虑凑成二项式定理的形式，有
\(=\frac{1}{k}\sum\limits_{p=0}^{k-1}{\omega_k^{-tp}}\sum\limits_{i=0}^{L-1}{C_{L}^{i}\omega_{k}^{ip}f_i[x,y]}\)
\(=\frac{1}{k}\sum\limits_{p=0}^{k-1}{\omega_k^{-tp}}(\omega_k^pW+I)^L\)
则后边是常数，可以分开考虑，不妨令\(A_i=(\omega_k^{i}W+I)^L[x,y]\)
\(=\frac{1}{k}\sum\limits_{p=0}^{k-1}{\omega_k^{-tp}}A_p\)
任意底数的单点求值是Chirp Z-Transform，将\(tp\)拆成\({t+p\choose 2}-{t\choose 2}-{p\choose 2}\)
\(=\frac{1}{k}\sum\limits_{p=0}^{k-1}{\omega_k^{{t\choose 2}+{p\choose 2}-{t+p\choose 2}}}A_p\)
然后减法卷积即可。
最后说一下单位根的问题，因此\(k\mid(p-1)\)，则可以用\(\omega_p^{\frac{p-1}{k}}\)作为模\(p\)意义下单位根。
序列
首先这是一个保序回归问题，但是这个过程显然不是很好维护。因为这个限制在一条链上，所以可以用一个栈维护。
具体的，维护一个栈，如果存在\(A_i>A_{i+1}\)，则\(B_i\)一定等于\(B_{i+1}\)，则这两个数可以合并成一个。因此栈中维护一个单调上升的序列即可。可以做到单次询问\(O(n)\)。
询问之间独立，考虑用前后缀信息拼出来，然后得到整段的信息。首先分治，得到两边的栈。考虑最终的栈的形式，一定是一段前缀和当前的前缀相同，一段后缀和后面的后缀相同，中间一段合并成一段，则二分套二分找到中间两个端点即可。
标签：frac,submission,limits,复杂度,HNOI2019,omega,sum From： https://www.cnblogs.com/275307894a/p/17051224.html