多边形

首先要知道终止态是所有边都指向了 (n) 号节点。
那么我们如果每一步都让 (n) 的度数 +1 那一定是最优的，显然可以办到。
那么可以从与 (n) 相邻的边分割出若干个独立的部分求解。
对于一个部分，每次我们一定是选一个最高的边进行 ( ext{rotate})，然后分成两个独立的部分。

对于一个 ( ext{rotate}(a,c))，二分找到 (lt c) 的最大的与 (a) 有边的就是 (b)。

注意到这个形成一个二叉树结构。
根据森林的拓扑序计数 (res={n!over prod size_i}) 答案只跟树上节点的 (size_i) 有关，可以直接计算。
考虑 ( ext{rotate}) 一次的影响，根据下图：

只有 (x) 这个点的 (size) 变化，更新一下即可。
时间复杂度 (O(nlog n)) 或者 (O(n))。

白兔之舞

首先知道两个数组循环卷积相当于 DFT 以后点值相乘再 IDFT 回去。

[c_i=sum_{j=0}^{n-1}sum_{k=0}^{n-1} a_jb_k[j+k=imod n]\ ={1over n}sum_{j=0}^{n-1}sum_{k=0}^{n-1} a_jb_ksum_{d=0}^{n-1}w^{d(j+k-i)}\ ={1over n}sum_{d=0}^{n-1}w^{-di}A(w^d)B(w^d) ]

考虑算一个数组的 DFT

[f_i=A(w^i)=sum_{j=0}^{n-1}a_jw^{ij}\ =sum_{j=0}^{n-1}a_jw^{{i+jchoose 2}-{ichoose 2}-{jchoose 2}} ]

mtt 即可。
考虑算一个数组的 IDFT，reverse 处理即可。

鱼

鱼身和鱼尾是两个独立的部分，分开做并且预处理出来。

考虑对于 (AD) 统计 (BC), 可以先枚举所有 (BC) 把它挂在 (BC) 的垂直平分线上，然后在线段 (AD) 处在直线 (AD) 所对应的 ( ext{vector}) 里面二分这个区间。
垂直平分线的条件是充要的，为了方便用斜截式 (y=kx+b) 来表示直线，二元组 ((k,b)) 均为化简的分数（此题严重卡精度、卡 int64 溢出）。
对于 (y_p eq y_q) 的点对，垂直平分线斜率存在，把中点横坐标插入 vector 中；
对于 (y_p = y_q) 的点对，垂直平分线斜率不存在，用唯一确定的横坐标 (x_p+x_qover 2) 表示这一类直线，把中点纵坐标插入 vector 中。

考虑对于 (AD) 统计 (EF)，考虑先枚举 (D) 再枚举 (A) 的话，然后所有点关于 (D) 点极角排序，(angle ADQ in (0.5pi, 1.5pi)) 的 (Q) 可以作为 (E/F) 点。
双指针扫描，类似莫队一样维护以 (dist(D,Q)) 为下标的 map 即可算出点对个数。

话说这个要取中点于是一开始坐标统一 ( imes 2)，然后极限的 (dist=(4 imes 10^9)^2+(4 imes 10^9)^2) 爆了 unsigned long long。。。

枚举 (A)、(D) 把 (BC) 方案跟 (EF) 方案乘起来即可，因为有序的，最后还要乘 (4)。
时间复杂度 (O(n^2log n))。

序列

直接二次函数可以证明一个连续段如果用同一个 (b_k) 那一定是取平均数。
(50pts) 做法看了就会了而且是我校 tgz 模拟赛。
考虑单调栈弹栈的过程，对于一个前缀，已经插进去的左端点过会还可能没了，但已经没了的左端点再也不会出现。
后缀也是同理，考虑一个 (i) 维护 (i-1) 的前缀单调栈和 (i+1) 的后缀单调栈，最终答案一定是取若干个完整的前缀栈栈顶 + (i) + 若干个完整的后缀栈栈顶拼接成中间一个连续段，然后两个栈内剩下来的不动，作为最终的答案序列。

定义 (push) 操作为把 (i) 或者 ([l,r]) 插入到前缀栈中，然后调整到这个栈单调的操作。

一个暴力做法是我们 (push(i))，然后判断左边栈顶是不是 (le) 右边栈顶，否则我们尝试把右栈栈顶整个区间 (push) 了，弹掉，当第一次满足条件的时候停止，大致如下图。这个做法是对的，因为这个是单调的，往右做一次的话左栈顶应该减小了而右栈顶变大了。

直接按上面那么做，复杂度 (O(n^2))，实际得 (100) 分。
因为有单调性我们可以二分这个右端点（只能是栈中元素的右端点），把这段区间一起 (push) 了，找最靠左的 (mid) 即可。
复杂度 (O(nlog^2n)) 实际得 (100) 分。
还有那个后缀栈的问题，我们可以先从 (n) 往 (1) 做出来这个栈，然后再逐位撤销操作。（询问离线下来）
可持久化线段树也可以。

校园旅行

首先 (30pts) 的暴力 bfs 必须会，就是往队列里面插入单个点以及相邻的同色点，每次向两头扩展相同的颜色，更新答案。
时间复杂度 (O(m^2))。

(sum_{u,v} ext{degree}_u imes ext{degree}_v = O(m^2))

考虑缩图，定义0->0为黑边,1->1为白边,0->1/1->0为桥边。
那么一条回文路径可以表示为
黑边<-桥边<-白边<- ... o ... ->白边->桥边->黑边

现在约定：走黑白边必须一次性走 1e9 / 1e9 + 1 条，桥边必须一次性走 1e9 + 1 条。
那么与原问题等价。

考虑一个黑连通块，若 u->v 只能走出一种奇偶性，那么仅保留一条路径也无妨。
否则我们还要保证 u->v 能走出两种奇偶性。

对于第一种情况，缩出一棵树即可；第二种我们造一个自环。

考虑桥边，环是没有意义的，黑色 (P) 点可以到达白色 (Q) 点则一定能走出长度为 1e9 + 1 的路径。
直接删去这样的环边即可。

JOJO

这个题太难了，写了一天，要写的内容好多，先鸽了。