宿舍真他妈傻逼，不过这不重要。
D1
没有参赛。
A. colour
有$n$个求，长$m$的操作序列，每个操作有一个参数$x$，表示把$x$或$x+1$染成一种新的颜色。每次给一个区间求最终的结果有多少种。$n\leq 500,q\leq 2000,m\leq 10^6$。
造个dfa，发现问题是字符集很大，把本质相同的缩成一个即可。
B. binary
C. tree
树，边有边权，每次给两个点和两个系数，求分别以它们为端点选一条链，边权和的带系数和的最大值。$n,q\leq 5\times 10^5$。
相当于我们要在中间选一个点，然后两边各取最长的。
重链剖分，如果两边没有取到同一条重链上，直接做即可。如果两边取到了同一条重链上，一个问题是我们
也可以考虑点分，
cf1764 G3.
注意这里排列是重要的，所以
如果$n$是奇数，我们取$k=2$，那么相当于有一种颜色出现一次而其它颜色都出现两次，要找到出现一次的颜色。考虑我们怎么判断一个区间里有没有$1$，我们知道它的颜色数加上它的补的颜色数应该是
洛谷9393
感觉比较厉害，容易想到三进制状压，但是我们需要二进制，这就需要用一种表示两个。这里考虑把$0$扔掉，因为我们是按位贪心，只需要该有$1$的位置有$1$，不需要该有$0$的位置有$0$。那么注意到在右侧复合看起来比较好，因为一旦确定就不会变了。
那么考虑我们每次是在右侧复合一个操作让它该有$1$的位置要么是$1$要么是$-$，然后是$1$的位置就不用再有$1$了。注意到能减少该有$1$的位置个数则不停操作是不劣的，所以设$dp(S)$表示如果$S$中是该有$1$的位置，不停操作后会剩下哪些位置是$-$，转移也就是找到能进行的任何一个操作进行，不过这个略微麻烦，可以找到所有能进行的操作一起进行，相当于进行了它们的并，这个可以通过法嘛塔求出。复杂度$O((2^m+q)m)$。
cf1693 E.
找到所有最大值，那么我们要选一个分界点，左半边从左边操作，右半边从右边操作。这个最优的分界点是唯一的，也就是次大值左边选择往左，次大值右边选择往右，两个次大值之间的部分选啥都一样。
注意到当前的$\max$和每个数上一次选的时候选了哪一边可以确定每个数是不是$\max$，也就是如果那一边有一个$\max$它必然是，否则要么它没选过，要么必然不是。而每个数这一次选了哪一边我们已经描述过了，可以发现我们总保持左边选择往左，右边选择往右，所以这些东西全都是区间。复杂度$O(n\log n)$。
cf1209 G2.
考虑没有修改怎么做，如果两个颜色相交则必须合并，合并直到不交，每个连通块留一个个数最多的即可。
那么相当于有权值的区间，如果两个区间相交则合并，求每个连通块的$\max$的和。
考虑线段树分治，但是这个要均摊，那么考虑单侧递归线段树。我们在每个左端点处挂以它作为左端点的区间的右端点的值和区间的权值$a,w$，那么相当于从左往右扫$i$，维护$p,v$，如果$a_i>p$则答案增加$v$，$p=a_i,v=w_i$，否则$p=a_i,v=\max(v,w_i)$。
现在开始单侧递归，考虑左边已经有$p,v$了，对$v$的影响会是一个结合的变换$v\leftarrow \max(v,a)+b$，目标是求出这个变换。如果$p$没有盖住左边$a$的$\max$，则维护右边的答案，递归进左边，否则递归进右边。
但是std比较简单，考虑最后的分界线就是没有被覆盖的间隔，求答案可以直接查区间$\max$。那么这玩意居然可以直接在线段树上合并，记录区间最小值和个数，以及两边未完成段的情况即可。
cf1656 G.
考虑其自同构群，发现如果固定了置换后的结果，我们能做的只有同种字符的置换，那么如果两个环包含相同字符，就可以把它们合并成一个，此外做不了啥了。
那么继续考虑交换两种字符的位置，发现这样交换之后必然可以得到两个包含相同字符的环了。
uoj goodbye renyin C. 新年的双区间操作
那么也就是说值越大值越大对吧!这就非常好，考虑一个操作进行的条件其实是初始序列中每个位置有个$\geq$某个数的限制，满足一个它就会被操作。那么我们把初始序列中所有数和进行的操作中的$y$取$\max$就得到了答案。
具体考虑如何复合，这里在左侧复合比较困难，右侧复合，复合一个操作的效果是，如果它进行了也没啥用，那么没有变化，否则会让一个区间的限制对某个数取了$\min$。
D2
100+0+0=100。
A. sequence
大致弱于 22集训队胡策 R14 B. 染色。
B. select
树，链$u\leftrightsquigarrow v$的权值定义为，设这条链长$l$，找到距离这条链最远的点$w$，设这个距离是$d$，则权值是$ld$。求所有链中权值的最大值和最大值个数。$n\leq 5\times 10^5$。
结论是，固定$u,v$，则除非答案是$0$，否则最优的$u,v,w$的y-center是唯一的，因为固定三个点，以距y-center最远的那个点作为$w$是不劣的，而如果有两个不同的y-center，则把$u,v$之一换成某个$w$必然能给出一个更优的解。
从整棵树的center出发考虑也可以得到做法，且不需要这么复杂的观察，但是写起来要复杂。
C. hat
有$n$个有编号的人，每个人戴着一顶帽子，帽子上有一个$0$或$1$，所有人可以看到所有人的编号和别人的帽子颜色，然后所有人同时猜测自己的帽子颜色，要求颜色为$0,1$的人各有至少一半下取整猜对，构造一个策略。$n\leq 18$。
考虑如果有两个情况$x,x+2^k$只有第$k$位不同，那么第$k$个人就需要猜一下了，他只可能在一个情况中猜对，所以给每个情况建两个点$x_0,x_1$表示两种颜色，连边$x_0,(x+2^k)_1$，然后给边定向，指向哪边表示猜对了哪边。然后我们要求每个点入度至少是度数的一半下取整，跑欧拉回路即可。
gdcpc23 ?. Swapping Operation
考虑and只会变化$\log$次。求出从左往右和从右往左的所有关键点。
如果我们换的都不是关键点，那么答案不会变大，而如果初始最优解在$k$分开，那么只需要在$k$的同侧随便换两个就得到答案不变的解了。
如果换的都是关键点，复杂度$O(n\log^2 v)$。
如果一个是一个不是，比如换了左边的关键点，枚举它，先把它删掉重新求关键点，然后答案就不会比这个更大了。
?. ?
是 xviii open cup gp of japan B. Point Pairs 的一部分。
sdcpc23 H. Be Careful
gcj11 R3 D. Mystery Square
收录于 sdptt21 r2。
cts22 回
考虑二维差分，发现变成主对角线$+1$，副对角线$-1$。然后差分成射线，就可以扫描线啦。
kaist22 G. Permutation Arrangement
如果至少有$15$个空位，那么必然有解，贪心填，最后状压dp即可。
?. ?
考虑第一步，我们要设计一个函数$f(x,y)$满足如果$f(x,y)=f(y,z)$，则$x=y$或$y=z$。考虑让$f(x,y)$是$x,y$最高的不同的二进制位，
D3
100+0+0=100。
A. cf37 E. Trial for Chief
B. mex
集合序列，一开始全是空的，支持区间插入一个数(如果在某个集合中已经存在则不改变它)，求区间中所有集合$\mathrm{mex}$的最大值，强制在线。$n\leq 2\times 10^5,q\leq 10^5$。
考虑如果可以离线，倒着做，每次找到哪些区间真的删掉了这个数，就是区间对一个数取$\min$了，而$n$个操作只能产生$2n+1$个区间。
但是不能离线，不过还是可以考虑$\mathrm{mex}$就是不存在的数的$\min$，一开始让每个集合都是全集，每次操作是删一个数，我们还是可以找到哪些区间真的删掉了这个数(而不是之前已经被删过的)。考虑如何查询，如果是单点查询，二分答案$d$，看前$d$个是不是真的删了，那么由于每个位置每个数只会被删一次，只需计算前$d$个数一共被删了多少次。外层值域线段树，内层序列线段树即可，复杂度$O(n\log^2 n)$。
但是是区间求$\max$，这里就比较寄了。
C. cow
多重集，如果两个数和为偶数，可以把它们删掉，把它们的平均数加入(显然这个数一定也是整数)，构造一个方案使得只剩下一个数。$n\leq 10^6$。
一个部分分是所有数都是偶数。考虑两个膜$4$为$0$的数操作还是偶数，为$2$的操作也还是偶数，那么不停这样操作，最后还剩下最多两个数，如果剩下两个那么它们都是偶数。
如果全是奇数也可以这么做。
考虑如果有一个膜$4$为$0$的数，有一个膜$4$为$2$的数，那么必然有解，我们可以把剩下的数胡乱操作，那么最后会剩下一些东西，如果剩下一个偶数那么肯定有解，如果剩下一个奇数，先把这两个数操作然后和它操作，如果不剩啥事没有。如果剩下一个奇数一个偶数，对膜$4$的余数讨论，爆搜即可。
同理可以证明，如果有一个膜$4$为$1$的数，有一个膜$4$为$3$的数，那么还是必然有解。
那么问题是偶数膜$4$余数都相同，奇数膜$4$余数都相同，那么此时奇数和奇数操作
ptzsc21 D3 ?. Eluerian
考虑如果所有点度数都是偶数，那么所有子集度数的和还是偶数，否则有一半子集度数的和是奇数。随机找一个点集，可以用总边数减去它的边数减去它的补的边数的奇偶性求出它的度数和的奇偶性。
ByteDance-Moscow Workshops Camp 2022. Shuffle Contest M. Multiple Communications
如果$a,b$是随机的，我们只要随机取$30$位即可。
如果$a,b$不是随机的，我们随机换个基，然后随机取$30$位即可。这里其实相当于用随机矩阵压缩到$30$位里。
Izborne Pripreme 23 D2 ?. Mapa
拉插。
ptzsc22 D4 ?. Telepathy
注意到B的策略是基于串a的，那么A拿到串b的时候，因为a是随机的，他知道B命中0和1的概率，所以他可以选择撞的概率更大的策略。
考虑怎么才能让期望超过一半，考虑如果只选长$2$的子序列怎么办，搜一下发现有个期望$\frac{5}{8}$的策略。搜一下长$3$的，发现过了。
cts2023 ? ?. 琪露诺的符卡交换
猜测必然有解。
感觉比较厉害了，考虑我们依次看每个人应该拿到什么，考虑直接让每个人从所有人那里各拿到一张卡片，这也就是在一个$n$-正则二分图上求$n$个完美匹配，复杂度$O(n^2\log n)$。
Izborne Pripreme 23 D1 ?. Trokuti
考虑先解出前$5$个点的情况，然后就可以每次加一个点了，但是需要卡卡常，如果问到$2$或$0$则可以直接得到两条边的情况，否则我们还需要把不确定的这些问一圈解出来，shuffle一下就带了一个$\frac{2}{3}$的常数。
xxii open all-siberian pc final D2 ?. Captivating process
如果是树，也就是求一个点满足$a_u-a_x=b_u-b_y$，那么也就是$a_u-b_u=a_x-b_y$，且它在这两条到根的链的交上。对每个$a_u-b_u$开个桶，为了表示链交，重链剖分，枚举两段重链做二维数点，复杂度$O(n\log^3 n)$。但是还是别重链剖分了，反过来考虑贡献，dfs序，一个$u$的贡献是个矩形，扫描线线段树即可，复杂度$O(n\log n)$。
两边都在环上的情况，求出环的交，环交的总长是$O(n)$对吧，那么有交的环对也只有$O(n)$个。如果环长的$\gcd$是$d$，那么有且只有两边的位置差比初始位置差$s$变化$d$的倍数的情况是可达的。所以如果交点$t$分别在$i,j$位，如果存在$k$满足$i-j=kd+s$就可达，否则不可达。枚举$k$进行预处理，把$t$挂到$i-j-kd$这个位置，复杂度$O(n\log n)$。
如果一边在链上一边在环上，
icpc22 naq ?. Stacking Up
如果没有全局$-1$，那就结束了。否则我们倒着做，求出前面进行了多少次全局$-1$，额外凑这么大即可。
ncpc22 ?. Icy Itinerary
归纳构造，考虑新点到原来的分界点。
icpc22 nanjing C. Fabulous Fungus Frenzy
考虑我们可以随便换，所以其实只需要把每种的个数搞对就行了，这样就是有一些 删掉你选择的任意$k$个元素，加入$k$个给定元素 的操作。
考虑倒着做，如果现在这个状态下可以倒着使用某个操作，那么它可以把一些字符变成通配符，这样能操作就操作必然是不劣的。
注意到一个操作必然是某一时刻开始可以用，然后不停用它，直到已经没用了，那么它以后再也没用了。
构造方案比较shaber。
icpc22 nanjing F. Triangles
什么东西😰
D4
0+100+0=100。
出题人是gyr，但是没有我想象中那么劲爆（
A. maxflow
我大样例呢???
基环树，支持修改边权，求如果你可以进行$k$次给一条边$+1$的操作，全图最小割的最大值是多少。$n\leq 5\times 10^5,v\leq 10^6,k\leq 10^{12}$。
二分。发现可以改成bit上二分。
B. shortcut
C. speedrun
平面上有若干竖线段，保证两两不交。极左和极右还有竖的直线。你要选择尽可能多的点，满足删掉任意一条竖线段后，从每个点画横的直线撞到任意竖线段为止，会得到若干横线段，横线段的横坐标两两不交。$n\leq 10^5$。
考虑每个选择只有左右射中的前两条竖线段有用，那么竖着扫，每个选择就是相邻四个竖线段对吧，所以只有$O(n)$种选择。这我为啥没想到啊???
然后可行的转移是一个2-side矩形，直接扫过去bit优化dp即可。复杂度$O(n\log n)$。
abc306 H.
造造dfa，但是可以感觉到这个性质太好了。
考虑看成一张图，我们要给边定向，求缩起无向边之后是个dag的方案数。那么先考虑如果是排列怎么做，我们每次剥掉一个没有入度的点，但是有问题，一个方案可能有很多点可以剥。考虑如果每次剥掉所有能剥的，方案就是唯一的了，那么如果能剥的集合是$S$。有相等的话，可以随便选点集，然后每个连通块内部必须相等即可。复杂度$O(3^n)$。
cf1081 G.
众所周知对若干个序列进行归并排序是把序列按前缀$\max$分段然后把每一段的开头排序。
枚举两个数算作为逆序对的概率，那么如果它俩在同一个不排序的段里，就有$\frac{1}{2}$的概率贡献，因为一段内的相对位置是不会改变的，也就是说长$l$的段内的贡献是$\frac{l(l+1)}{4}$。
如果它俩不在同一段，那么就要看它俩前面那个前缀$\max$的大小关系。注意到如果这两个数分别在段内的$i,j$位置的话，前面那个前缀$\max$就是段内的前$i,j$个的$\max$。这里枚举值就不是很好了，可以直接枚举两段和其中两个数的位置。
现在复杂度还是$O(n^2)$，不同的段长度只有两种，再前缀和一下即可。
1st ucup Ukraine N. No Zero-Sum Subsegment
任何非空子区间和$\neq 0$等价于我们不能两次达到同一个前缀和，那么考虑如果任何时刻两个连续的位置都被经过了，就再也无法穿过这里了。所以大概讨论一下，开头有下去又上来的满的一段，中间就不能出现长度$>1$的拐了，结尾又有上去有下来的满的一段，或者上下颠倒也是可以的。中间的部分，所有的$-1$必须和两个$+2$打包，二项式系数插插即可。
然后就是数学部分了。妈的，不管了。
cf1525 F.
哦哦，原来是dag啊!这是个最小路径划分，但是我们只会用网络流求最小路径划分啊。没关系，网络流就是拆点，删掉入边相当于入点的邻边，删掉出边相当于删掉出点的邻边，那么其实就是相当于删了这个点对吧。
如果某次得分到$0$了，我们必然把所有点都删掉。枚举这一次，然后得分就不会到$0$了。
注意到每次删一个点最大匹配要么$-1$要么不变。劲爆的是必然存在一个点删了它会让最大匹配$-1$，删掉最小点覆盖中任何一个点即可。
所以直接dp就好了，也不用枚举了!
cf1712 F.
这怎么求啊???
考虑两个点之间的距离，要么是直接沿树走过去，要么走到最近的叶子然后走一个$x$。
1st ucup Gomel G. Classical Graph Theory Problem
考虑满足这个条件的最小的图类，我们不停删边，保证删边之后每个点相邻的叶子个数还是$\leq 2$。考虑不能删边的图是什么样的，一个点如果挂了恰好两个叶子，那么它不会让它的邻边不能被删，所以它的叶子之外的邻接点度数必须是$2$，否则这条边就可以被删了，也就是说挂了恰好两个叶子的点之间不会相邻。所以所有的点要么是叶子，要么挂了恰好两个叶子，要么度数是$2$且连接一个点和一个非叶点。所以其实是叶子和挂了恰好两个叶子的点之间由一些度数是$2$的点连起来。度数是$2$的点之间不会相连，否则这条链的两端就都可以断开了。叶子和挂了恰好两个叶子的点之间也不会有度数是$2$的点，因为可以把这俩断下来。所以每个挂了恰好两个叶子的点相邻的都是若干度数是$2$的点和两个叶子。
考虑每次加入一个挂了恰好两个叶子的点$u$和它的邻接点，我们找到和它的邻接点相邻的点$v$们，假设有$c_0$个$v$没选，$c_1$个选了，那么如果$u$选了$v$没选，$u,v$之间那个点就是随意的，如果$u,v$都选了或者都没选，之间那个点就必须相反，那么我们跟$c_0,c_1$中较大的一个选的相反，就可以获得至少一半的调整机会。
D5
A. bfs
$n$个点的有向图，每个连向下一个，还有若干个关键点，每个关键点都连向后面所有关键点。现在每轮随机删一个点，直到删空，求每轮单连通对数的和的期望。$n\leq 2\times 10^6$。
这个数据范围不太够啊!一对点的贡献只和它们之间最近的关键点到它们的距离有关，然后可以法法了，但是还是别法法了，贡献显然d-finite，推一推发现甚至形式非常简单，而两段之间的贡献可以拆拆式子$O(1)$算，不同的段长只有根号种，枚举两种算，然后把算错的部分remake一下，复杂度$O(n)$。
B. mst
图，有一个完全点$0$，支持修改$0$到某个点的边权，求mst边权和。$n,q\leq 5\times 10^5$。
先去掉$0$跑mst。可以发现这个东西可以直接用lct维护，但是lct不好，但是树分治也不太好扔。
考虑可以在树上dp，这个相当于分成若干连通块，每个连通块选一个点连$0$，那么静态lct维护ddp即可。
考虑用kru重构树描述，众所周知kru重构树描述mst合并还是很好用的(sdoi2019 世界地图)，但是我不太知道，这就是菜了。我们选一个点集$S$连$0$，则会把$S$的虚树断掉，
C. match
完全二分图，$n$个左部点$m$个右部点，
BalticOI 11 D2 ?. Tree Mirroring
如果我们知道两个根，从它们出发bfs就能找到树，判定树同构就赢了!
可以发现根其实不是特殊的。
考虑树没有环，我们随便找一个环，那么删掉它之后得到的每个连通块恰好有两个点和它相邻，这俩就是一对对应点。
icpc17 world final ?. Replicate Replicate Rfplicbte
首先构造一个逆，我们让$(i,j)$变成周围$3\times 3$的$ $
BalticOI 22 D1 ?. Uplifting Excursion
https://www.luogu.com.cn/blog/uakioi/nv-knapsack 的第一步。
cerc17 ?. Buffalo Barricades
可以直接用平衡树维护每一块的轮廓，问题是如何点定位，发现一个点所在的区域就是它右上方最早插入的点为右上角的区域。
但是这个题要简单，我们给
cf1616 G. Just Add an Edge
cf1110 G. Tree-Tac-Toe
考虑没有白棋怎么做，发现只有一条链，两边可能挂两个叶子 这种情况可能平局，别的都是白胜，因为如果有四度点，立马就赢了，如果有三度点，且至少两侧高度$\geq 2$，那还是赢了，所以只剩下这种情况了。链只有两边挂叶子可能白胜，如果此时中间那条链长度是奇数则白胜，否则平局。
加白棋的部分就比较离奇了，不过大概可以嗯讨论出来吧。
nwrrc14 ?. Kebab House
$q\leq 5000$。
考虑我们确定所有$0$的位置，设$dp(i,j,k)$表示考虑到第$i$段的位置$j$，这一段有$k$个$0$的方案数，转移直接前缀和，这个是$O(\frac{nq^2}{t})$。好像没啥救啊!
鉴于$t$很小，考虑一次处理一段，只记到上一个$0$的距离，那么
D6
A. 四边形不等式dag定长最短路
B. set
有$n$个数，你要选一些，价值是和的平方除以平方和，求最大价值。$n\leq 80,v\leq 1000$。
把和看成横坐标，平方和看成纵坐标，那么答案是$\frac{x^2}{y}$。$\frac{x^2}{y}=a$也就是抛物线$y=\frac{x^2}{a}$，那么我们要求最大的$a$，就是拿抛物线往里收直到撞到一个点，所以答案必然在凸壳上。用quick hull和最大权闭合子图求出凸壳即可。
C. team
cf364 D. Ghd
随一个数对吧，然后看它的因数，每个数都可以先和它取$\gcd$，然后在它的因数上法嘛塔算每个因数被覆盖多少次。
agc028 D. Chords
这个题好像学校里搬过啊。
发现既然只有相交，环和序列其实是等价的，那么我们还是考虑序列吧。
考虑枚举一个连通块极左和极右的点$l,r$，求出它俩连通且和外面不连通的方案数，然后全部加起来对吧。那么区间内和区间外肯定不能连，然后好像不太会了。考虑容斥，钦点$l$连到的最右的点是$p$，那么$p+1$到$r$内部随便连(当然仍然不能连出去)，$l$到$p$则递归下去。复杂度$O(n^3)$。
cf542 E. Playing on Graph
发现有三元环就不行，进一步地有奇环就不行。
考虑最后那条链每个点都是怎么来的，发现只有链上相邻两个点在被缩起来之前可能有边，别的都不能有边，那么这个是bfs树的性质对吧，求出直径即可。
cf566 E. Restoring Map
考虑叶子看起来比较容易下手。如果有两个点集合相同，它们都是叶子。如果有一个点集合大小是$3$，它必然是叶子。
考虑让交很小看起来也比较容易下手，如果两个集合交的大小是$2$，说明这两个点距离为$3$，然后中间两个点有边。那么我们现在确定了所有非叶结点，问题是每个叶子挂在哪。
首先先把多个相同父亲的叶子合成一个，然后我们要找到哪个是父亲，那么它的集合就是父亲半径为$1$的邻域，对每个点求出半径为$1$的邻域包含哪些点，然后直接判相等即可。但是如果内部结点$\leq 2$个需要特判，此时没必要区分内部结点。
neerc17 Journey from Petersburg to Moscow
考虑枚举第$k$大边权，那么比它大的贡献，小的不贡献，但是这个肯定不对，我们让比它大的贡献减去它的边权，小的不贡献，最后加上它的$k$倍，那么如果我们走的多了答案会变大，走的少了答案还是会变大，非常对对吧。
这谁想的到啊???
cts17 网络
首先两个点一定都在直径上，因为我们走到边上去是为了让环离那边近一点，但是最远的总在直径上。
然后考虑二分答案$l$，考虑端点$s,t$的可能位置。如果直径上两个点$u,v$子树里最深的点深度是$x,y$，它们的距离是$d$，如果$x+y+d>l$，就必须让加的这条边离它们足够近。足够近有个距离，距离带绝对值，不过没有关系，绝对值是$\max$，$\max(a,b)\leq k\Leftrightarrow a,b\leq k$，非常好对吧。然后枚举$s$看是否存在一个$t$即可。都可以双指针，复杂度$O(n\log n)$。
D7
A. 模板 平衡树
B. wisdom
交互题。图，每次可以查一条边是否存在，在$6n$次查询中判定是否存在三个点$u,v,w$，满足$u,v$有边，$v,w$有边，$u$是一度点，$v$是二度点，$w$除了不和$u$有边，和别的点都有边。
先拿随便一个点跟所有点
C. pa20 Tekstówka
收录于 蒙日阵。
scoi2016 萌萌哒
发现这个可以拆对吧，所以我们拆成长$1$的就好做了，那么考虑都拆成长$2^k$的，每层用并查集reduce一下再扔到下一层，在最后一层统计连通块个数即可。那么总共会发生$O(n\log n)$次合并，复杂度$O(n\log n\alpha(n))$。
洛谷5605 小 A 与两位神仙
奇素数幂是为了有原根对吧。求个离散对数，那么问题就是判定是否有$\gcd(x,\varphi(m))\mid y$。
但是我们肯定不能真取对数，注意到$\frac{\varphi(m)}{\mathrm{gcd}(x,\varphi(m))}$是$x$的阶，因为阶是轨道长度，每个数往右边距离$x$的数连一条边，会产生$\mathrm{gcd}(x,\varphi(m))$个平等的轨道，轨道长度都是相等的。阶可以$O(\log^2 m)$求。而判断是否$\mid y$，左边必然是$\varphi(m)$的因数，所以右边也可以跟$\varphi(m)$取$\gcd$，所以其实我们是判断$y$的阶是不是$x$的因数。
18集训队胡策 蒜头的奖杯
scoi2010 连续攻击游戏
在$a,b$之间连一条边，每个连通块如果是树则扔掉最大的那个，否则所有数都可以被选。
Ynoi2013 文化课
发现每个区间只有根号种不同的次数，直接维护出这个多项式即可。
sdoi2018 反回文串
考虑一个回文串会被算多少次，那么就跟它的最小整周期有关，那么当然要用置换群计数那一套，为啥$T\leq 10$呢?波拉德rho对吧!
枚举最小整周期$d$，
洛谷7728 旧神归来
我们只关心每个深度的叶子有多少个，所以选哪个是没啥区别的。问题是要快速模拟这个过程。
考虑设每个深度叶子个数的gf是$F$，那么在深度为$d$的时候，我们做变换$F\leftarrow F-z^d+z^dF=(1+z^d)F-z^d$。这个变换要做很多次，所以考虑让它的形式好一点，它是$(1+z^d)(F-1)+1$，那么也就是说其实是$F-1\leftarrow (1+z^d)(F-1)$。现在可以取$\ln$，那么众所周知加上若干倍的$\ln 1+z^d$是$O(\frac{n}{d})$，所以整个是一个调和数的复杂度。但是还要考虑如何提取最低次项系数，我们要膜$z^{d+1}$做$\exp$得到$z^d$项的系数，可以发现一个$1,…,d-1$次项为$0$的gf，取$\ln$之后也应该$0,…,d-1$次项为$0$，而只有$d$次项的话平方之后就啥也没有了，所以直接提取即可。复杂度$O(n\log n)$。