XIX(2018~2019)
Zhejiang
A. Automorphism
考虑给一棵树，怎么算自同构数。
考虑只有两棵同构的子树才能换，并且两棵同构的子树可以随便换。于是答案就是 每个父亲相同并且子树同构的等价类大小的阶乘 乘起来，我们称这个关系是 等价。
注意到挂一个叶子最多会增加$\log$对等价关系，因为每次等价子树大小都会翻倍。但是如何找到这些等价关系?
考虑这个性质可以更强，每次出现两棵大小相同的子树，从这里向上走子树大小都会翻倍，而大小相同才有可能同构。如果有很多大小相同的子树，考虑做某种树剖，一个点子树大小严格大于一半则作为重儿子，那么只有轻儿子可能和它的兄弟同构，而我们可以做一个树hash。可以用平衡树维护链支持跳top，这是弱化的动态重链剖分。
现在问题如何支持挂叶子，计算子树hash值。考虑每层用一个不同的$\prod (a_ix+b)$的集合hash，可以用树ddp维护，这个树ddp可以直接在我们的动态重链剖分上维护，实际上它甚至并不能算是ddp，就是直接维护一下。最后开一个dfs序BiT统计答案。
但是这玩意怎么写啊?
B. Border
01串，求每个子串的最长非平凡border长度之和。
哦串是随机的啊（
border的期望长度只有$\log$。
我们枚举长度$k$，然后找到所有长$k$的子串，对于每个串考虑它的出现位置，选两个就可以得到一个border是这个串的子串。
注意到枚举到一个串的最长border之后，它的更短的border就都确定了，可以算出次长border来减去多余的贡献。复杂度也许是一个$\log$，也许是两个$\log$吧。
我认为这个应该作为$n=\sum_{i=1}^n 1$的例题。
C. Convolution
直接使用 任意模数二项卷积。
介绍一下做法。crt，然后只考虑膜$m=p^k$的情况。我们要计算$C=AB$。我们定义$p$-阶乘为$n!_p=p^{\nu_p(n!)}$，也就是$n!$中$p$的部分，反$p$-阶乘为$\overline{n!_p}=\frac{n!}{p^{\nu_p(n!)}}$，也就是扔掉了所有的$p$。显然反$p$-阶乘在膜$p^k$下可逆。
定义$\overset{\frown}{a}_n=\frac{a_n}{\overline{n!_p}}$，类似定义$\overset{\frown}{b}_n,\overset{\frown}{c}_n$，则有
\[\overset{\frown}{c}_n=\sum_k\frac{n!_p}{k!_p(n-k)!_p}\overset{\frown}{a}_k\overset{\frown}{b}_{n-k}\]这样的。根据kummer定理，那个奇怪系数不超过$n$，所以如果不取膜，结果的每一项不会超过$n^2m^2$，一般可以使用四个1e9级别的模数计算，而换成别的模数之后就可以求逆然后呐塔塔了。
D. Decomposition
显然dp。
这个好像也是板子。如果转移的这一段没有一个非平凡整周期，那么可以前缀和算，而有非平凡整周期的转移可以用runs来算，具体一点就是我们对于每个run $(l,r,p)$，把它push_back到$[l+2p-1,r]$中的每个位置，然后需要对每个膜$p$的等价类开一个前缀和，这个run开的前缀和长度是$\min(p,r-l+1-2p)$。总复杂度$O(n\log n)$。
E. Edit
dp。设$dp(u,v,i,j)$表示希望把$u$子树操作成$v$子树，目前已经用$u$的前$i$个儿子搞出$v$的前$j$个儿子的最小代价，$dp(u,v)$表示$i,j$分别是$u,v$儿子个数时的值，对于第二棵树设$s(u)$表示从空开始搞出$u$子树的代价，对于第一棵树设$t(v)$表示删光。$(v,j)$的对数是$O(n_2)$，所以复杂度是$O(n_1^2n_2)$这样的。
一开始是这么想的，但是这个有问题，因为可能会把一些儿子合并起来变成对应点的一个儿子，也可能会把一个儿子分裂开变成对应点的一些儿子，然后可能会裂两层合一层这样的，所以就很复杂了。
考虑使用括号序，发现这个操作就是加入一对匹配括号或者删除一对匹配括号，于是设$dp(u,i,l,r,0/1)$表示只考虑$u$的前$i$个儿子，用括号序上$l,…,r$这一段搞出$u$子树，最外面是对原来就有的括号做一次relabel得到，还是通过插入得到 的最小代价。转移枚举新的儿子
F. Flow
看起来很有趣。
考虑一个单位流量从$s$到$t$的过程，发现把这无限张图拍起来，它所做的事情是在一个环上走。我们不搞什么二分图，而是对于给出的边直接在一张$n$个点的图中连边$u\rightarrow v$，那么猜测答案就是图中的最大循环流。感性理解一下，一个环对应于每条边的一单位流量，而这些流量在这张无限的图上转来转去之类的。使用scaling或者network simplex即可。
G. Good Game
当你看到这个题，你知道这场你已经Good Game了/jy
首先用经典的容斥dp，可以转化成$m^2$次计算两个点之间的路径数。
这个题是雅礼集训2017 D11 path。考虑建立一个杨表，我们令$a_{i,j}$是第$i$维到达$j$的时间，那么这就是一个标准斜杨表，可以用标准斜杨表计数的Aitken公式。
那么这个公式是什么呢?我们用杨表每一行的长度组成的序列来描述一个杨表，用$\lambda/\mu$表示从$\lambda$中挖去$\mu$得到的斜杨表，则这样的斜杨表个数为
\[\left(\sum_i \lambda_i-\mu_i\right)!\det\left(\begin{bmatrix}\frac{1}{(\lambda_i-i-\mu_j+j)!}\end{bmatrix}_{i=1,j=1}^{\vert\lambda\vert}\right)\]，其中$\frac{1}{a!}$在$a<0$的时候是$0$。
H. Hamilton Path
MiracleFaFa : This one is my favorite problem in the problem set. Thank you for sharing your solutions.
考虑这个东西要求很多边都不能存在。我们把所有$p_i\rightarrow p_j$都删掉之后，这个图甚至变成了一个dag，所以限制看起来非常强。
考虑爆力怎么做。先枚举一个起点，然后如果它有两条出边，那么我们就完蛋了，因为其中一条必然会成为前向边。于是除了终点，每次走到的点连向未走过的点的边数恰好为$1$才有可能，模拟即可。
考虑怎么批量处理很多个这样的东西。我们维护若干条链，从所有点都是孤立点开始，每次尝试把一条链向后扩展一个点，这可行当且仅当链尾连向的点有且仅有一个不在链中。如果扩展到的点是一个链头，那么很好，否则路径的最后一个点必然是 两条链上在这个扩展到的点前面的那个点 之一，我们可以在反图上尝试两种可能。
于是现在所有的扩展都是扩展到一个链头，那么最后如果我们没有得到唯一一条链，则必然不行，否则还可能有多个答案。考虑如果没有一条链尾连向链头的边，那么必然没有多个答案了，否则我们得到一个哈密顿回路，答案必然在上面，而每条回路外的边会ban掉一个起点的区间，差分-前缀和维护即可。
I. IOI Problem Revised/Post Office 5
这个题在apio2021的课中讲到了。
破环成链之后，每个起点开始的路径不会互相穿过，或者说对于任意两个起点开始的最优解，我们选的区间们不会有一个包含另一个。
于是先求一个从$1$开始的最优解，接下来问题就是在每个这个最优解选择的区间里选一个点，然后串成一个环。设最优解选了$k$个区间，考虑我们选择其中长度最短的区间作为环的开始，它的长度不超过$\frac{n}{k}$。对其中每个位置，以它为起点跑一个最优解，方法是把每个区间看成一行，竖着排，那么解是不会互相穿过的。取第一行中点，在每层跑smawk得到一个最优解，这把这个形状切成两部分，分开递归下去，复杂度$O(n\log n)$。如果用决策单调性分治就是俩$\log$，再加上wqs二分就是仨了。
一个问题是怎么求一个最优解。这是一个经典做法。如果答案在一条线段的中间，那么我们可以跑两个dp，一次尽可能多选，一次尽可能少选，从而得到线段两个端点$l,r$的方案。然后我们要从两个端点的方案出发构造中间任意一点的方案，做法是找到一个点$i$，然后取$l$方案的前$i$个分段点和$r$方案$i$之后的分段点，由于这个是连续的，我们知道必然存在一个$i$可以构造出我们所要的$k$的答案。
为了证明这样构造出来必然是最优的，可以注意到如果左边取$r$的方案，右边取$l$的方案，则得到$l+r-k$的方案，而$l+r-k$也在这条线段上。设答案是$f$，直接把四边形不等式代入我们的构造，可以知道$f(l)+f(r)\geq f(k)+f(l+r-k)$，而由于在一条线段上，设斜率是$t$，我们知道$f(k)\geq f(l)+t(k-l),f(l+r-k)\geq f(l)+t(r-k),f(r)=f(l)+t(r-l)$，合起来就得到$f(k)=f(l)+t(k-l)$。
J. Jump Jump Jump
考虑我们只需要算出不管前面，走到$(i,i)$的概率，就可以用法法塔算一个容斥来搞定了，实际上这个容斥可以用多项式求逆表示。
设$A=\frac{1}{k}\sum\limits_i x^{dx_i}y^{dy_i}$，那么$\frac{1}{1-A}$就是走到每个位置的概率。
结论 如果$F(x,y)$是有理分式，那么它的对角线$[z^n]G(z)=[x^ny^n]F(x,y)$是代数的。
所以它是整式递推的，我们可以爆力高消出它的递推式，然后递推即可。
证明可以看 https://www.luogu.com.cn/blog/your-alpha1022/chu-li-bgf-diagonal-di-jing-dian-fang-fa ，感觉我比较智障。这里面也给出了推导的方法。
K. Knight
考虑如果$r+c$是奇数，那么这个就是二分图。如果$r+c$是偶数，那么直接染色之后黑格子和白格子是独立的，我们先只考虑黑格子，于是把这个东西转一转，那么$r+c$就可以缩成$\frac{1}{2}$，最后必然可以缩成奇数，于是它还是一个二分图。
于是既然是二分图了，我们考虑它和自己的笛卡尔积，那个限制就是不能走到笛卡尔积上走过的点。这个笛卡尔积也是二分图，于是所有环都是偶环，于是我们知道如果撞到了走过的点，必然是后手撞上了，也就是说先手只会被逼死而输，而不会撞上走过的状态而输。那么先手输当且仅当两个人在同一个连通块，并且这个连通块是树，并且一开始两个人的距离是奇数。
L. Link Cut Digraph
时间分治。
scc合并只会发生最多$n-1$次。
我们递归左边，加入左边的边跑scc，然后递归右边。注意到跑scc的时候复杂度是$O(n+m)$，而$n,m$都可能很大，这就很难受。感觉上不是很好优化。
考虑我们转而计算边，对于每条边考虑它的端点进入同一个scc的时间，求出这个之后就可以直接并查集合并。考虑整体二分，现在要处理边集$S$，它们被缩起来的时间在$[l,r]$内。令$d=\frac{l+r}{2}$，那么我们就希望知道加入$1,…,d$这些边之后，$S$中哪些边被缩起来了。注意到被缩起来的scc中所有边，被缩起来的时间是一样的，所以我们实际上只需要加入$l,…,d$这些边。复杂度$O(m\log m)$。
不是很理解这个东西本质上是什么。
Udmurtia
A. Equal Digits
状压dp。设$dp(i,S)$表示考虑前$i$个，当前有的数位是$S$的方案数，转移考虑$i$是删了还是没删，如果删了那么可以从前面和$i$相同的位转移过来，前缀和即可。复杂度$O(n2^\Sigma)$。
B. Remove the Tree
dp。设$dp(u,0/1/2)$表示 :
-
$0$ : $u$的父边被上面搞掉了，也就是不一定存在包含$u$的链
-
$1$ : $u$的父边被$u$搞掉了，并且包含$u$的是一条祖先-后代链
-
$2$ : $u$的父边被$u$搞掉了，并且包含$u$的链随意
的最小操作次数。三个转移 :
-
$0$ : 如果没有包含$u$的链，从儿子们的$2$转移；否则也就是$dp(u,2)$$
-
$1$ : 枚举连向哪个儿子或者不连向任何儿子，剩下的选择$0$$
-
$2$ : 枚举连向哪两个儿子，剩下的选择$0$，这个可以直接选择$dp(v,1)-dp(v,0)$的最小值和次小值
，复杂度$O(n)$。
C. Unseen Segments
考虑每个纵坐标，这些纵坐标分成$O(n)$段，每一段的贡献只和$l+r$有关。直接前缀和即可。
D. Road Connectivity
注意到只有$10$条边，也就是只有$2^10=1024$种情况。但是这个有点多了，发现其实我们只需要考虑无标号图，这样的图只有$c=34$个。
矩阵快速幂。我们倍增到左端点，然后换一个只保留不连通的情况的转移矩阵倍增到右端点，复杂度$O((c+q)c^2\log v)$。
为了优化，这是一个线性递推。
E. Binary String
看起来太离谱了。
考虑我们对于前一半的数，问$[i,n],[i,n-1],[i,n-2],…$，后一半问$[1,i],[2,i],…$这样的，然后错误的时候得到错误的合理答案的概率就是$\frac{1}{n}$级别。
F. Fair Competition
排序题。
也就是排好序之后分成左右两边，左边只回答自己右边的，右边只回答自己左边的。左边的右数第三，第二和第一个是$1,2,3$，其中$1$是哑巴，$2$只说自己比$3$小。
好消息是，只要我们得到了回答，答案就是真的。
注意到除了$(1,2),(1,3)$，两个人总是可以用两次比出来的，如果随机一个顺序的话是$1.5$次。
使用二分插排，维护左右两部分，最后会剩下$1,2$可能插不进去，但是$3$必然可以插进去，如果我们哪次比较出了问题就把出问题的都拿出来，否则就正常做，最后把出问题的拿出来再二分进去。二分插排的比较次数大概是8500，所以期望比较次数大概不到1.3e4，差的还是很多的。
归并也是可以的，但是归并的比较次数是9000左右。
G. Token and Dice
人类智慧题。感觉可以机器学习出来。
H. Convex Region
感觉很复杂。不会。
SPb
A. Create the Best Pet
其实就是让你求出Salt。
先用gene搞出一个很小的范围，然后爆力即可。为了跳过前面调用的8e4次random，我们可以爆力算出这个变换。
B. Graph and Machine
也就是判断两个可以随机访问的自动机是否同构，如果不同构则找到一组反例这样的。
考虑随。不知道正确率，感觉可以把自动机构造出一个特判这样的。
考虑拼一些必要条件。称三个特殊点分别是$s,1,2$。
首先对于任意一条到$1$的路径，每条边都必须出现过，否则我们改了没出现的边答案会改变，但是自动机不知道。
继续考虑，发现如果一个点可以到$1$，那么$s$到它的所有路径都必须处理了相同的边集，并且此时每个点邻边权值和奇偶性的状态是唯一的，否则就不满足上一个观察。所以我们可以直接用集合hash算这个，保留可以到$1$的点然后toposort即可。这样就可以保证走到$1$的图真的是$1$。如果出了问题，那么对于有边没有出现过的情况容易构造，对于状态不唯一的情况也容易构造，也就是取两个不同的状态，其中必然有一个会是错的这样的，模拟即可。
现在问题是有可能一个图应该是$1$，但是自动机认为它是$0$。这么说我们已经完成了问题的一半了（
继续考虑可以到达$1$的点，刚才我们说明了到达它们的时候状态必须是唯一的。考虑我们从一个这样的点走到一个不能到达$1$的点的时候，状态也必然是唯一的，并且任何一个被判定为$0$的图必然经过这么一条边。接下来问题就是我们需要给剩下的边分配一下使得它实际上是$1$，可能这样做当且仅当对于每个剩下的边形成的连通块，其中有偶数个点的剩余的$c$是$1$，可以用dfs树那一套给出构造。从$1$出发dfs，用可撤销并查集维护连通块即可，复杂度$O(n\log n)$。
有点牛逼了。
C. Clique Festival
$k$只有$18$。立刻可以考虑我们在每个团中只会走最多一条边。
然而这个不是很好用。考虑按照每个点属于哪些团来把点分成$2^k$类，答案只和每一类的个数相关。
考虑如果两个点同属于任何一个团，那么一步就可以走到。但是两步不一定比一步劣。
考虑两步看起来是什么样的。感觉上就是选择一个$u$中存在的团，选择一个$v$中存在的团，然后如果这两个团有交，那么可以沿这两个团走过去。
于是我们知道，$k$步走过去就是选择一个$k$个团的链，相邻两个有交，或者说选择一个点的序列，相邻两个的状态有交这样的。
考虑先求出两个团之间的距离$d(i,j)$，也就是我们给团建一张图，站在一个点表示刚才从这个团里面的某个点沿着这个团的边走了一步，那么从团$i$走到团$j$需要付出$a_j$的代价，如果两个团没有交则不能走。于是从$u$到$v$的最短路就是枚举$u$所在的团$i$和$v$所在的团$j$，求各$a_i+d(i,j)$的$\min$。于是设$f(i,j)=a_i+d(i,j)$。
考虑怎么批量算这个。有很多想法。简单想法是，我们枚举两个团$i,j$，求$u\in S(i),v\in S(j)$，并且$f(i,j)$是$u,v$的最短路的$u,v$的对数。
显然从小到大枚举$f(i,j)$，然后问题是找到满足$u\in S(i),v\in S(j)$并且$u,v$还没被处理过的$u,v$的对数，然后我们要把它们都处理掉。由于这里有$n^2$对，并且这并不能表示成很少个矩形，所以我们考虑如何描述 还没处理过。发现看起来没有什么好方法描述它。一个可能的方法是它不包含在前面任何一对团的笛卡尔积中，这给出这样的式子 :
\[f(i,j)\left\vert S(i)\times S(j)-\bigcup_{f(i^\prime,j^\prime)<f(i,j)}S(i^\prime)\times S(j^\prime)\right\vert\]考虑这个笛卡尔积看起来就不是很好，因为它太大了。我们折半一下，先枚举一个点$u$，然后再枚举第一步走到哪个团求出$u$到每个团$j$的最短路$g(u,j)$，按照$g(u,j)$从小到大给团$j$排序，此时枚举$j$，没有被处理过的$v$就是不属于前面任何一个团的$v$。于是答案就是
\[\sum_{j=1}^k g(u,j)\left\vert S(j)-\bigcup_{t<j}S(t)\right\vert\]考虑这个怎么批量算。设$c(S,j)$表示$t<j$的$t$组成集合$S$时后面那个东西，显然只需要算出$c$就可以了。
发现这个计算的就是所在团的状态中$j$位是$1$而$S$中的位是$0$的点的个数，那么我们外层枚举$j$，内层法嘛塔即可。复杂度$O((2^k+n)k^2)$。
D. Distance in Crosses
稍微转一下，然后就变成两个十字之间的曼哈顿距离了。
E. Lui and Lines
百分法。
然而我们可以发现它是二维单谷的，所以就三分三分就行了。
然后可以直接求偏导搞定。/fn
F. Dominating Subarray
考虑这个序列必然是完全相同的，否则如果两个相邻位置不同，我们把这个区间平移一下，左边或者右边就会出问题。
于是如果存在一个区间只包含最大值，那么这个就是答案。
然后wa了。考虑啥时候会出问题，发现如果它是前缀或者后缀，我们可能不能平移。于是就爆力check一下前缀和后缀的情况即可。
G. Least Number
bfs。
H. Galactic Governments
也就是一个$k$维超棋盘上有$n$个超矩形，找到一个不在任何矩形中的格子。
考虑我们二分这些维拼起来的值，然后爆力容斥来查这个点左下方有多少被覆盖的格子，这样就可以知道是不是有一个空格子，需要使用int128。复杂度是$O(2^nk\log v)$。
I. Multiplication
有点牛逼了。考虑我们取$n$个随机奇数，然后我们拿到的数不知道是哪一个乘$x$了，就尝试每一个乘$x$，这样会得到若干个可能的$x$。尝试每个这样的数，得到的可能的$x$取一个交，就可以得到答案。由于是随机的，期望$\log$次就可以得到答案。
J. Guess Two Strings
连续查询100次，然后考虑每一位是什么情况。如果这一位只有很少次是不一样的，比如不到25次，那么说明两个串在这一位相同，否则不同。如果有至少两个不同的位，那么我们需要合并一下，对四种可能求出其中最可能的。然后好像就模拟就行了。
另一个想法是，我们枚举两个串作为$s,t$，然后对每个串按照到这两个串距离哪边更小来分成两组，每一组再对每一位找到出现次数更多的字符。然后我们check一下是不是每个串到$s$或$t$的距离是15，如果是那就输出，否则就换两个。
考虑一组不正确的串被check认为正确的概率。发现这个概率非常小，所以我们就认为它是对的好了。但是其实我并不会分析这个正确率。
K. Beautiful Tables
直接消。
L. Three Balls
考虑找到球心们所在的平面，然后它就被分成若干段，然后我就数学水平有限了，还是大力simpson吧。
Eurasia
A. Trampler
模拟。
B. Video buffering
一眼看上去感觉很离奇。
每个任务在缓冲区里是一个时间区间，具体一点是三个时刻，它的开始，完成和离开时间，而开始和完成相差$a_i$。
注意到确定顺序之后，同时只能做一个 表示的是某种依赖 前面的做完才能做后面的，也就是前面的完成时间$\leq$后面的开始时间。
考虑按照I或P分成若干段，每一段内部都是B，那么这些B肯定是从前往后做。于是如果不考虑缓冲区，左端点的顺序肯定是第一段的起点，第二段的起点，第一段里面，第三段的起点，第二段里面，这样的。
观察样例，猜测如果考虑缓冲区，也是按照这个顺序。感性理解一下挺对的。于是我们只需要模拟出每个任务的进出时刻，然后就可以直接求被覆盖最多的那个点。
然后这些限制的具体效果大概就是，后面的离开时间会限制前面的完成时间从而限制开始时间，后面的完成时间会限制前面(它所依赖的)的离开时间。
注意到我们知道最后一个任务的右端点必然是$(n-1)d$，所以倒着做就好了。
C. Package
考虑网络流。我们给每个包建一个点，每个版本是一条边，每个冲突是一个点，跑包的完美匹配即可。
D. Vasya’s graph
加入一条边的时候，如果是加到同一个连通块，啥事没有。如果是不同的连通块，那么我们查询是否有不允许这两个连通块合并的限制，如果没有的话，其中一个连通块需要改名，此时我们启发式合并就好了。
E. Quadratic equation
。
F. Alignment
容易考虑dp，设$dp(a,b,c,d)$表示四种各有$a,b,c,d$个的答案。复杂度$O(n^4)$。
G. Rocket
又重又贵的东西我们是不要的，然后由于有两种合金，画到平面上就是线段，线段上方的也是不要的，所以这是一个左下凸壳。
考虑看出凸壳之后怎么办。闵和即可。所以我们可以知道，最多只会用一种合金，不知道这个有没有什么用。
可以作为模板 凸函数闵和。
H. Cabbage
直接二分答案。
I. Segments
动态二维数点。为了做到1log，我们可能需要利用数据随机。
想了一年发现我是智障，一段的期望长度是
\[1+\int_{\frac{1}{n}}^{1}\frac{1}{x}\mathrm{d}x\]，其中前面是随出来$>n$的部分。显然它的值是$\ln n+1$，所以直接在每个整点开一个vector，然后每次插入把这一段push_back到段中每个整点和段两边第一个整点。统计答案的时候，注意到所有点被覆盖期望$n(\ln n+1)$次，所以每个点被覆盖期望$\ln n+1$次，所以我们只需要在两边的vector里硬找到这些覆盖即可。
J. Civilization
题意大概是，六边形棋盘，六连通，每个格子有地形和地表两个属性，地形包括平原，丘陵，山地，地表包括草原，森林，沼泽，而两个相邻格子的边界可能有河流。每回合你会得到$m$体力，然后进行任意次移动，其中山地不能走，过河直接耗尽体力，走进森林和沼泽花费2体力，其它移动花费1体力，体力不能$<0$。求最小的回合数。
dij。比较两个状态，只需要以回合数为第一关键字，剩余的体力为第二关键字。这个也告诉我们，只要距离是有序的，就可以最短路。
K. Ecliptic
计算几何。
Korea
A. Coloring Roads
直接lct维护一下。
B. Dev, Please Add This!
经典题。考虑每条极长的横线或者竖线，所有的移动都是从一条这样的线上的一点移动到一个端点，那么我们给每条线建一个点，它表示在这条线上的任意一点，然后就可以跑一个scc。
注意到每个星星必然被经过它的二者之一收集到，那么它被收集的状态就是一个bit的pair，缩完scc之后每个scc就表示一个bit的pair的序列，问题是在缩完之后的dag上选一串scc使得它们or起来之后每个pair至少有一个1。
dag上的路径 不是很好处理，我们考虑把它转化成 两两可比的集合。于是可以使用2-sat :
-
对于一个星的横竖线所在的两个scc，如果一个没选，则必须选另一个
-
对于两个互不可达的scc，如果选了一个，则另一个不能选
于是直接跑就好了。点数是$O(hw)$，边数是$O((hw)^2)$，总复杂度$O((hw)^2)$。
C. Dstorv
考虑最后手在极左，花在极右，并且必然是一个前缀的一部分手和对应的后缀的一部分花最后留了下来。于是我们枚举这个前缀，设$l(i,j)$表示前$i$个手，剩下恰好$j$个，并且$i$剩下了的概率，$r$是对应的，然后答案就是$\sum l(i,a)r(i+1,b)$这样的。
考虑$l$怎么算，发现不是很好算，于是我们需要一个好算的东西。重设$l(i,j)$表示有$j$个手跨过$i,i+1$这个间隔往左飞，而最后有$b$个飞出去了，那么转移考虑如果这个是手，则它往左飞；如果这个是花，那么考虑它撞掉了多少右边来的，可以前缀和优化一下。复杂度$O(n^2)$。可以理解为某种线头dp。
D. Dumae
我们可以得到一个dag，然后需要给每个人分配一个位置。进行类似于toposort的过程，如果$i$能到的点已经都分配掉了，并且分配到$l_i$个人，则把$i$加入一个堆，堆中按$r$从小到大排序，每次取出$r$最小的即可。
然后发现这个会死掉，原因是一个人的$r$可能受到确定在他后面的人的限制。于是每个人的$r$和后面的人的$r-1$取$\min$即可。
E. Electronic Circuit
判定广义串并联图。
做法是，一个图是广义串并联图，当且仅当可以通过若干次删一度点，缩二度点，叠合重边把它变成空的。叠合重边就是把重边合成一条。
F. Fake Plastic Trees
看起来是$2\lg n+O(1)$。
考虑我们要凑一个$n$，必然要凑出$\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil$，那么可以注意到这些东西不管怎么取整都是某个$\lfloor\frac{n}{2^k}\rfloor$或$\lceil\frac{n}{2^k}\rceil$，然后就结束了。
G. Fascination Street
设$dp(i,0/1/2,k,a,b)$表示前$i$个，上一个选了这个/上个/上上个，用了$k$次交换，有$a$个接头是要选的，$b$个是不选的，转移考虑这个是不动，留一个接头还是接一个接头，并且这个位置是选还是不选，复杂度$O(nk^3)$。据说被卡了。
考虑怎么砍一维。注意到如果这个位置要选，那么跟一个要选的位置换是没有用的。如果这个位置不选，那么跟一个不选的位置换是没有用的。然而这个只是减少了四个case。
发现不选的接头和要选的接头不会同时出现，所以就结束了。复杂度$O(nk^2)$。
H. Fractions
发现Suneung分数只有很少，所以直接做即可。
I. Game on Plane
考虑这个不能相交说的就是画线的时候不能在端点处相交，因为如果交了那么对面一手就把你干掉了。画一条线会分成两个凸多边形，递推sg值即可。
J. Histogram Sequence
也就是求区间$\min$第$l,l+1,…,r$小的区间。
考虑笛卡尔树，直接算出每个$\min$出现多少次，然后就结束了。
K. Interesting Drug
容易想到$n^2$ dp，也就是设$dp(i,j)$表示现在在$i,…,j$，走到$1,…,n$的答案。
注意到只有$O(n)$个转移是有权值的，所以我们可以考虑对没有权值的批量转移。我们的方程是$dp(i,j)=\max(dp(i-1,j)+[c_{i-1}=j-i]d_{i-1},dp(i,j+1)+[c_{j+1}=j-i]d_{j+1})$，也就是相邻两项取$\max$，并且有若干个位置需要特殊处理。
考虑这个 相邻两项取$\max$还是挺复杂的，不过好像也没有那么复杂。用平衡树维护连续段，每次大的段会吃一口小的，边上也会吃掉一个，于是可以算出每一段何时被吃空，用一个堆维护这些事件即可。
这个太复杂了。考虑一个更加简单的想法，我们不要搞这么多状态，而是只考虑那$O(n)$个特殊的状态，转移是二维偏序，对一维分治之后对另一维一边归并一边转移即可。
L. Faster Sorting
对每个位置预处理从它开始极长连续上升或下降段的长度，然后就直接跳即可，复杂度是调和数的$O(n\log n)$。
M. Utilitarianism
wqs二分，然后树dp。复杂度$O(n\log n)$。
Poland
A. Drone With a Camera
直接做。
B. Fibonaccis’ vouchers
也就是求$k$个fib数的和中的严格第$n$小。$n$非常大。
猜测很少个fib数就可以表示出1e18以内所有数。然而发现还是不少的，可能需要大概40个?
注意到除了比$k$小的数，如果它的Zeckendorf表示不超过$k$个$1$，那么就可以用恰好$k$个fib数的和表示，也就是不停把最高位拆成两个之类的。于是问题变成找到Zeckendorf表示不超过$k$个$1$的第$n$个数。
注意到Zeckendorf表示是唯一的，所以对它先dp一遍，然后从高到低确定每一位即可。让我们来听一听无敌王卷王是怎么说的 :
这个分解类似于二进制分解，我们先确定下第$n$大的数的最高位在哪里，然后相当于把最高位删掉再在剩下的位置上找第$n-x$大的数在哪里，类似于迭代下去，直到全部迭代完毕。
因为只用大约40个数就表示出来了，相当于只用80位就能确定下来，时间复杂度没有问题。
实际上复杂度是$O(\log^2 n)$。
C. Chinese Remainder Theorem
对于每个方程考虑使它成立的$m$，发现它就是$a_i-b_i$的因数，于是只需要计算各$a_i-b_i$的gcd。
D. Road
找到上一次推平最近的时间。
E. Evaluation
爆炸oj Mst拼上一个 货车运输。
F. Baking Pans
。
G. Taste in Art
牛逼了。考虑给每个数按照除掉所有$2,3$之后剩下的东西分组，每一组把$2,3$的个数作为两维画到平面上，那么问题变成不能选择一个拐，轮廓线dp即可。
H. Hobby
。
I. Grade Book
这是某种路径划分。斜过来看，你会发现它是最小不上升子序列划分，于是它等于最长上升子序列长度。
J. Identical Scarves
我一开始认为题意是每次可以把两个接起来或者把一个分裂开/fn，但是它实际上是每次可以给一个$\pm 1$。
注意到我们必然是把一个值域区间都变成中位数，所以双指针扫一扫就好了。
K. Pocket Money
如果你使用机翻，可能会看不懂。它说的是，维护一个每天给的零花钱的数量，然后每天会给你这个数量，并且更新这个数量。
对于最大值，我们塞满+，直到后面全填-也不够了，就(可能要先填一个0再)开始填-。
对于最小值，我们塞满-，如果遇到一个-的时候前面没有足够的+了，就前面最近的-变成0，或者如果没有-了，把最近的0变成+，如果还没有就完蛋了。
L. Lines
行，列，对角线都在相互影响，让我们很难处理。于是考虑容斥，我们钦点若干行，列，对角线被同一种棋子覆盖，那么可以发现如果钦点的同时有三种中的至少两种，或者$n$为奇数的时候同时钦点了两条对角线，那么所有钦点的棋子都是同一种。如果只钦点了若干行或若干列或若干对角线，那么钦点的每一部分都是独立的。
注意到大部分情况是简单的，可以根据 行/列/对角线和(列/对角线)/(行/对角线)/(行/列)交于恰好一点 算出剩下多少格子。然而一行，一列和一条对角线可能同时交于一点，所以就出问题了。考虑dp，我们从外往里dp，每次决策四条对角线是否选，它们交于四个点，用$dp(i,j)$表示考虑了前$i$圈，目前钦点了$j$个格子的方案数即可。复杂度$O(n^3)$。
M. Magical Maze
牛逼了。
做法是，考虑删掉所有起点不能到的点和不能到终点的点，然后枚举第一个点，那么第二个点可以是它能到的任意一个点。为了算出这样的点的数量，直接dag dp看起来并不可行。考虑一个牛逼想法，这是一个平面图，所以我们分别扶左右墙走，走出来的区域就是可达的区域，然后这个东西就可以加加减减dp出来。
Siberia
A. Product
。
B. Driving the Gnu
。
C. Crazy minesweeper
每走一步，对每个位置尝试如果它是雷，能否推出矛盾，如果它不是雷，能否推出矛盾。然后这个看起来就很复杂。
可以注意到它把随机数生成器给你了，为什么要把随机数生成器给你呢?因为其实并不需要玩扫雷，我们可以对所有种子跑出来这个地图，然后尝试确定种子。由于踩雷代价很大，我们每次找到最不可能有雷的地方，踩一脚，然后看哪些地图的情况不对，就把它排除掉。
D. Error in code
看起来就是没有算$n$这个点。所以就把它算进去就好了。具体做法就是把这个东西复制三份，分别把三个循环的开始改成$w,u,v=n$这样的。
E. Birthday
可能可以想到bfs树，它只在层内和相邻层间有非树边，不过我没有想到。现在问题是要求一个点，从它出发的bfs树高度$\geq k$，使用bitset从每个点出发bfs就好了。复杂度$O(\frac{n^3}{w})$。
F. Gas penalties
也就是求全源最短路。
考虑每到一个点必然要加油，否则可以不到。并且每次加油，要么恰好加到下一个点，要么一直加满。
考虑走的过程是什么样，以邮箱空了把这个过程分成若干段，每一段都是加满，加满，加满，加满，……，恰好加到下一个点。
所以枚举一个起点$s$，为了线性的状态数，直接设$f(u)$表示站在$u$加满了的最短路，$e(u)$表示站在$u$没油的最短路，那么看起来有四种转移 :
-
$e(u)+Vp_u\rightarrow f(u)$，没有限制
-
$f(u)+d(u,v)p_v\rightarrow f(v)$，要求$d(u,v)\leq V$$
-
$e(u)+d(u,v)p_u\rightarrow e(v)$，要求$d(u,v)\leq V$$
-
$f(u)+(d(v,w)-(V-d(u,w)))p_v\rightarrow e(w)$，要求$d(u,v)\leq V,V-d(u,v)\leq d(v,w)\leq V$。
由于有第四种转移，直接做的话对于每个起点是$O(n^3)$，就完蛋了。考虑如何优化，注意到对于$u,w$，我们选择的$v$是和起点无关的，所以可以预处理出来。于是每次就是$O(n^2)$了，总共是$O(n^3)$。
G. Level check
相当于把所有w挖掉，然后看起点的连通块是否包含m。直接分治即可，也就是相当于一个动态图连通性，一开始加入所有边，然后每组查询会把一些边删掉，然后查询若干次一个点在不在起点的连通块，最后把这些边加回去这样的。容易做到俩$\log$。
能不能一个$\log$啊?
H. Intersection Graph
模拟。
I. In search of the chair
球面计算几何/xia
不会。太离谱了。
J. Office
JKL在boj上顺序是错的。
模拟。
K. Recursive circuit
题意看起来很复杂，不过好像直接模拟就行了。
L. Subsequences
瞬间就秒了，然后发现我所做的是求所有方案的本质不同子序列个数之和。
考虑怎么计算本质不同子序列个数。这是 模板 子序列自动机，但是它的转移不够局部，看起来不是很好。考虑能不能搞点局部的，我们直接设$dp(i,c)$表示考虑前$i$个字符，结尾为字符$c$的子序列个数，为了方便处理空串，设$f(i)$表示答案。
考虑往后加入一个字符$s_i$的时候，我们可以给$f(i-1)$中任何一个串后面接上一个$s_i$，也就是$dp(i,s_i):=f(i-1)$；同时$f(i):=f(i-1)-dp(i-1,s_i)+dp(i,s_i)$，因为$dp(i-1,s_i)$中的串都在$dp(i,s_i)$被统计到了。第二个式子等价于$f(i):=f(i-1)-dp(i-1,s_i)+f(i-1)$，注意我们所求的是膜$2$的值，所以相当于$f(i):=dp(i-1,s_i)$，也就是说这个转移实际上是交换了$dp(i-1,s_i)$和$f(i-1)$。一开始只有$f(0)=1$这一个$1$，所以后面还是只有一个$1$，于是状态只有$27$种。预处理每种的转移即可。
Dolgoprudny
A. Color Numbers
意思是，如果两个数一个是另一个的子集，并且大小之差$\geq k$，就连一条边，最后求色数。
可以注意到这是一个偏序关系，所以这是可比图，而我们知道它的一个perfect order就是按popcnt从小到大，所以按这个顺序贪心即可。问题是我们要求一个奇怪的东西的mex，不会啊，怎么办?
可以发现由于这是可比图，求mex等价于求max，并且容易知道一个点的颜色不比它的子集小。考虑从小到大处理，对每个点求一个子集的颜色max，以及取到这个max的最小popcnt，如果这个popcnt比当前这个点的popcnt小了至少$k$，那这个点的颜色就是max+1，否则是max这样的。然后由于max是幂等的，我们可以直接枚举一位进行转移，做到$O(2^mm)$这样的。
B. Guess Matrix
牛逼题。
考虑我们先猜出每一行，然后考虑随便找一行开始往下走，也就是枚举另一行接上去，这样试$n$次可以接上一行，然后试完了一个方向再试另一个方向就好了，这个一共是$n^2$次。
然后一开始考虑的是可以直接在所有长$n$的串构成的trie上dfs，但是这样会搜到一些行后缀，然后这些行后缀就没法往后扩展成为一行了，这会产生很多无用状态，我们就失败了。
考虑类似于把行拼起来的做法，我们每次从空出发往两边扩展。但是为了保证扩展出来的是新的一行，我们不能从空，而是需要从一个不是之前已经得到的任何一行的子串的串出发。
考虑一个 不是之前任何一行的子串的串 必然可以由一个 是之前某一行的子串的串 向前或向后扩展一个字符得到。我们对已经得到的行建立多串sam，然后在上面尝试进行扩展。
所以需要说一说怎么建多串sam/kx，首先注意到这里只需要匹配，所以可以加分隔符来建。然后我需要学习一下。
C. Array
考虑如果$\min$只出现一次，那么答案就是$\min$。否则答案$<\min$。
考虑这相当于我们要选一个序列出来，使得答案$<\min$，然后就可以拿它对所有数取膜，答案就可以是它了。
注意到我们只需要考虑那些发生了取膜的数。先考虑一个多项式复杂度做法，我们把数从大到小排序，设$dp(i)$表示结尾于$i$的可能值的bitset，复杂度$O(n^3)$。注意到可以维护前缀or，并且在把bitset折起来的时候可以按照$a_i$的倍数分成若干段，那么一共要做$O(n\log n)$次总长$n^2$的bitset or，复杂度是$O(\frac{n^2}{w})$。
呃，是不是就过了啊?但是很遗憾std::bitset不支持 剪一段 这么牛逼的功能，所以可能需要手写。这里直接实现 截取 会比较困难，阳间一些的方法是实现 把一个bitset的一个区间or到另一个bitset的一个区间上。
D. Modular Knapsack
注意到大小有很多相同的。如果是最小化，我们猜测只需要保留很小的一些，并且是随机数据所以很可能很对。但是这里是最大化，不过可以发现一个好消息，我们先全选上，问题就变成最小化删掉的权值和了。所以我们爆力加入最小的一些直到接近tl，来求解最小化问题即可。
存在不依赖随机的做法，原题naipc 16 Jewel Thief。如果之后要做naipc，可能会把这个题解迁移过去。
背包。$n\leq 10^6,m\leq 10^5,w\leq 300,v\leq 10^9$，其中$w$是重量，$v$是价值。10s。
考虑对于一个重量，我们肯定选价值最大的一些，所以考虑类似于多重背包的做法，设$dp(i,j)$表示前$i$个重量的物品，重量之和恰好为$j$的最大价值，此时枚举$t=j\bmod{i}$，重设$g(j)$表示重量之和恰好为$ij+t$的最大价值，那么转移就是$g(i)=\max\limits_j(g(j)+f(i-j))$，其中$f(i)$是前$i$大的价值和。
为了优化这个，考虑$f$的性质，显然它是上凸的，那么这玩意就有类似于lightning conductor的决策单调性，直接分治即可。复杂度$O(mw\log m)$。
那么我们回来解决这个问题。这里带了一个取膜，所以需要稍微改一改。假设现在处理到重量为$i$的物品，考虑每个环，如果物品数量足够绕着环走两圈，那么我们必然先选一圈，然后物品个数就不超过两圈的长度了，可以破环成链直接跑上面的东西。复杂度$O(p^2\log p)$。
应该可以smawk砍$\log$。
E. Tower Defense
也就是一块钱可以扩展$k$。
考虑点分，直接算出每个点的答案。考虑如何计算分治中心的子树间的贡献，发现这个贡献只和深度有关，看起来可能是$\lceil\frac{\max(\mathrm{dep}(u)+\mathrm{dep}(v)-r,0)}{k}\rceil$，我们对每种贡献求出它有多少个，那么在dfs过程中，每次移动只需要处理一次$\max$的变化和一次上取整的变化，总复杂度$O(n\log n)$。
F. String Product
枚举$a$的长度，1e6以内最大的$d$是$240$。然后每这么多个字符分成一段，判断各段的差分是否相同。
G. Automaton
经典trick题。
考虑统计每个点的最长串，在$s$的sam上一个串$t$是最长串，当且仅当它的$\mathrm{endpos}$和所有$ct$的$\mathrm{endpos}$都不同。
注意到$\mathrm{endpos}$是一个匹配位置的问题，于是考虑kmp，我们爆搜$t$的$\mathrm{border}$集合，这个东西的数量是 https://oeis.org/A005434，可以知道它还是很小的。但是我们显然不能对$t$和所有$ct$存这个，不过可以发现如果存在$\mathrm{endpos}(t)=\mathrm{endpos}(ct)$，那么$c$是唯一的，所以转而计算$\mathrm{endpos}(t)=\mathrm{endpos}(ct)$的总数即可。枚举$c$，爆搜$t,ct$的$\mathrm{border}$集合，这个数量也不是很多，据说只有1e4，然后dp即可。dp具体就是border集合给出自动机，然后在上面跑就行了。
现在问题是怎么搜这个border集合。一个板子题是gym100958I substring pairs。一个简单做法大概是，根据弱周期引理，我们知道如果$x<y<z$是三个相邻的$\mathrm{border}$，那么要么有$z>2y$，要么有$z-y=y-x$。这样搜的复杂度，简单分析一下是$O(n^{\lg n})$，实际上很可能更小。搜出来之后可以用并查集计算方案数，然后发现不是很对，如果一个方案的$\mathrm{border}$被另一个方案包含，我们还要让前者的的方案数减去后者，然后发现这样居然就对了。那么至于如何搜$t,ct$的$\mathrm{border}$集合，我们搜出$t$的，然后模拟一轮kmp求出所有可能的向左扩展，这样搜出来的东西数量是$O(n^{\lg n+1})$。
H. Handsome multisets
请注意这个是不区分两个相同的数的。
请注意你可以自选膜数是明示取膜并不会发生。
考虑什么样的集合是好的。我们从小到大加入每个数，那么如果一个数加入的时候不超过前面所有数的总和，它必须和上一个数相同，否则不合法。如果它比前面所有数的总和大，它必须是这个和$+1$。
考虑是这个和$+1$的情况只会出现$\log$次。然后这个看起来不是很能直接用。
注意到如果现在总和是$x$，然后我们选择了$k$个$x+1$，那么总和会变成$(k+1)(x+1)-1$。然后又选了$l$个$(k+1)(x+1)$，总和会变成$(l+1)(k+1)(x+1)-1$。也就是说总和是每一段个数$+1$的乘积再$-1$。所以问题是枚举个数$k$，把$n+1$分解成$k$个非$1$数的乘积，pr一下，然后1e16内最大的d是41472，爆力dp是$O(d^2(n))$，看起来不是很行，不过是不是也许过了。
发现这个东西看起来有点积性。为了方便令$n:=n+1$，考虑如果$n$的dgf是$F$，问题相当于$\frac{1}{n^z}^k$，而$F$是每一维的乘积，所以我们二项式定理展开，然后只需要对每个素因数$p^e\parallel$算$[z^e]\left(\frac{1-z^{e+1}}{1-z}\right)^k$即可，把括号里替换成$\frac{1}{1-z}$没有影响，于是这个就是一个组合数。复杂度$O(\sqrt[4]{n})$。
I. Fence
考虑设$f_0,f_1$表示为$0,1$的概率，然后转移就是乘上$(1-p+pz)$，这里膜$z^2-1$。考虑差分-前缀和，但是多项式膜$z^2-1$可能不可逆，所以我们分解为$(z+1)(z-1)$然后crt得到答案，复杂度线性。这里需要对$1-2p=0$的情况特殊处理，因为此时它膜$z+1$得到$0$，直接记录它的出现次数即可。任何题目给出的多项式膜$z-1$都是$1$。
我们尝试了用矩阵来做这个，看起来是一样的。
然而这里这个东西看起来很掉精度，所以我们直接线段树维护吧。
J. Polynomial
请注意odd是指系数为奇数而不是次数为奇数。
弱于 zjoi2017 多项式，然后我就去学了一下，虽然多项式这个题太强了，但是还是写在这里。$n-1$次多项式$f$，查询$f^m$的一个区间中，给定的长$k$的串$t$出现多少次。$n\leq k=18,m\leq 10^{16}$。
先考虑总和怎么算。
考虑快速幂，快速幂就是 平方 或者 平方并乘$f$。
考虑平方，注意到膜$2$，所以平方的时候交叉项全杀了，相当于次数都乘了$2$。也可以考虑经典结论$f^2(x)\equiv f(x^2)\pmod{2}$。
所以看起来难度瓶颈是平方并乘$f$。考虑我们直接维护每种长$k$的子串的出现次数，那么发现平方之后每个子串长度都变成了$2k-1$，而很巧的是乘最多$k-1$次的$f$之后$k-1,…,2k-2$次的值必然还是正确的，所以这些都可以转移，只需要特殊处理两边，额外维护最低的和最高的若干位即可。
然后如果是区间和，考虑拆成后缀和，我们只要在倍增的时候，每次把后面截掉一个或者不截，来倍增出那个后缀的位置即可。复杂度$O(2^k\log m)$。
现在回来考虑这个问题。直接做即可。
看一看rng_58和um_nik的讨论。rng_58给出了一个更为简单的做法。考虑设$c(n,p)$表示计算$f^np$的系数和($p$是一个多项式)，那么类似于快速幂，如果$n$是偶数，那么我们考虑$g=f^{\frac{n}{2}}$，根据刚才的结论有$f^n(x)=g(x^2)$，所以$f^n(x)p=g(x^2)p$。考虑把$p$改写成$q(x^2)$的形式，那么就可以递归了，显然把奇偶次项分开，写为$p(x)=r(x^2)+xs(x^2)$，于是$f^n(x)p(x)=g(x^2)r(x^2)+xg(x^2)s(x^2)$。显然这两项的$1$的位置不会有重合，于是我们知道$c(n,p)=c(\frac{n}{2},r)+c(\frac{n}{2},s)$。如果是奇数，那么$c(n,p)=c(n-1,fp)$，那么因为快速幂最多减一次就会折半，偶数位置的第二维长度不超过$n$，可以状压。复杂度还是$O(2^n\log m)$。
Peterhof
A. Alice and Path
模拟过去，然后倒着模拟回来。
一个牛逼想法是，如果方向发生了改变，那么重复$\gcd(2,3)=6$次这个过程必然会回到起点，也就是说你只需要把输入再输出五遍。如果方向没变，你将沿一个方向走下去。注意到长度为奇数的序列总可以改变方向，所以我们补最多一个就好了。
B. John and the Magic Box
也就是你可以用$4n$次进行预处理，$4(k+1)$次完成一个长$k$的询问。
显然长$k$的询问把序列分成$k$段，然后我们用$k-1$次合并起来，那么说这个题弱于$4n$预处理$3$查询区间半群信息。$3$查询区间半群信息就是四区间合并结构，发现$2000$的$\lg^\ast$看起来当然小的可怜，所以我们考虑能不能$4n$次建一个四区间合并。算一算发现常数好像很大。
那么考虑四区间合并结构本来是维护半群信息，而这里是交换半群，这有啥好处呢?发现交换半群相比半群，最大的特点就是它交换，那么既然它交换，它就交换了。有个锤子用。
考虑换个想法。发现这个题的输入方式(ban一些数)以及交换的性质很适合我们shuffle一下，然后可以用那个分块的trick，也就是在一个询问左右端点在同一块的概率是$\Theta(\frac{1}{\sqrt{n}})$，而此时爆力需要$O(\sqrt{n})$。我们每一块处理前后缀和，块间使用二区间合并结构即可。等会啊，你发现不太对啊，这里是要排序的，排序之后相邻的在同一块的概率会更大，所以就很恐怖了。
回来考虑四区间合并，因为可以看到很多人强行构造过了。感觉上可以砍掉很多常数，比如每个叶子啥也不需要计算，二区间合并结构建的时候也不需要算所有东西，看起来可以砍掉很多$n$。本机调调参，shuffle一下，感觉就过了。
C. Anti-Distance
bfs一下然后观察。
图片来自 https://codeforces.com/blog/entry/63881?#comment-477035 的 Spoiler1。
考虑左边那一部分，发现我们把四个横着的看成一段，形式就变得简单起来。所以问题是计算在哪一段，发现这个是简单的，然后我们转四次做即可。
D. Machines on the Moon
这是一道通信题，但是yandex不支持通信式的交互，所以这个题让你造两个图灵机，spj模拟它们的运行。多少有点……
题意是有一张公开的图，A得到了一个团，B得到了一个独立集，判定它们是否有交。你可以使用$(\lceil\lg n\rceil+1)^2$个bit，并且每次发送一个bit，对方都可以立即收到，这个在这个图灵机的spj里面实现为它们共享内存。
我们能发的信息有点太少了，大概是如果每次传过去一个点，传回来一个bit，那么你只能传$\lg n+1$次。
所以考虑二分。考虑一个公共点有啥性质，发现它和A持有的所有点有边，和B持有的所有点没有边。
考虑一个简单想法，我们让A找到团中度数最小的点，如果这个度数不超过$\frac{n}{2}$，就可以排除一半的点，让B找到独立集中度数最大的点也是一样的。但是如果这个点度数超过了$\frac{n}{2}$，此时考虑由于团中每个点的度数都超过了$\frac{n}{2}$，独立集要想和这个团有交，交点的度数也超过$\frac{n}{2}$，也就是独立集中度数最大的点的度数超过了$\frac{n}{2}$，所以还是可以排除一半的点。也就是每一轮，A发送一个度数不超过$\frac{n}{2}$的点的编号或者$0$，如果B收到$0$则发送一个度数超过$\frac{n}{2}$的点，然后显然双方此时都知道了一个点，把它们的邻接点都删掉并进行下一轮。
E. Coin Tournament
模拟。
F. Fizz and Buzz
模拟。
G. Game on Tree
注意到B只可能往下走，因为回到之前某个位置必然不优。
考虑dp，类似于超现实数的想法，设$dp(u)$表示要让对手到达$u$的时候(也就是对手走了一步到$u$，此时该你走)必败，至少需要在他到达之前在$u$子树内花费多少步。转移是$dp(u)=\max(\sum dp(v)-1,0)$这样的。为了找到第一步要操作的点，从根出发不停往下寻找一个$dp>0$的点，如果找不到了那么随便输出一个即可。
H. Jack and Jill
每次选择多的一边。
I. Laws
能除就除。
J. Cubic Path
搜。
K. Red-Black Tree
dp，设$dp(u,i,0/1)$表示$u$子树，黑高是$i$，$u$是红/黑是否可行，转移枚举儿子的颜色。
Xi’An
A. Exotic Ancient City
边权很小。考虑kru，注意到我们计算边权为$2$的边用了多少条的时候，可以把$\leq 2$的都当成$1$加进去，然后再减去$\leq 1$的条数，所以问题是边权都是$1$怎么做。
考虑每次加入一列。可以发现由于这一列只和上一列有边，加的边也只和上一列的连通性有关，所以我们只需要维护相邻两列。考虑$i-1,i$的连通性和$i,i+1$的连通性有啥区别。
发现考虑前$i$列，第$i$列的连通性包含于考虑前$i+1$列，第$i+1$列的连通性(当然，把点重标号)，这个可以简单归纳证明。类似地我们也知道，$i-1,i$的连通性包含于$i,i+1$的连通性，我们来证一下 : 如果两个不在同一列的点$u,v$连通，那么说明$u$所在的连通块和$v$所在的连通块有边，那么往后移动一列，连通块不会变小，所以这个边仍然存在。
那么既然连通性是不降的，我们知道一条边会在一个前缀被加入，然后它就再也不被加入了。所以考虑求出每条边在哪个前缀是有用的。
考虑如果一条边加入时，是合并了右边的一个点和左边的一个连通块，那么这条边将会一直有用。但是这个看起来并不充要。考虑什么样的边以后会没用，发现如果它连通了两个连通块，但是这两个连通块都包含左边的点，那么当左边的部分本来就连通了的时候，它就不再有用了，否则它还有用。所以如果一条边加入的时候，它所连的两个连通块都包含左边的点，那么把它称为有效的，容易知道有效的边一共只会加$O(n)$次，而无效的边加进去不会让连通性变强。所以我们爆力维护有效的边即可，并查集需要支持查询是否有左边的点，随便维护一下就好了。复杂度$O((n+m)w\alpha(n))$。
B. Mysterious Host
模板 析合树计数。
C. Heretical Möbius
爆搜题。
$\mu^2$是$0$当且仅当有平方因数，那么我们从小到大检查每个素数，每次会删掉很多可能的位置，递归到最后(crt出来模数$\geq 10^9$)可能的位置将会很少，爆力检查即可。
一个重要的剪枝是，可以发现大素数平方贡献的$0$往往很少，所以如果剩下的$0$比小素数所能贡献的$0$多了不少(看起来这个数也许是$5$)，那么可以直接return。
D. Deja vu of Go Players
输出$[n\leq m]$。
E. Immortal Universe
考虑怎么判定两个序列行不行，发现如果我们可以找到两个$-1$，使得它们前面的和是$0$，那么就可以不行。
注意到这个和是连续变化的，所以如果有一个$\leq 0$的，那么必然有一个$0$，所以问题是能不能找到两个$-1$使得前面的和$\leq 0$。那么我们就把两个串的min加起来，如果它$\leq 0$那么就可以不行。考虑dp，设$dp(i,j,k)$表示前$i$个，当前和为$j$，最小的和为$k$的方案数，复杂度$O(n^3)$，倒着做就省掉了$j$，复杂度$O(n^2)$。
F. Interstellar Fantasy
计算几何。过球心和两点连线画一个平面，它和球的交是一个圆，最短路是沿着切线走到这个圆上，然后沿着圆弧走一段，然后沿着另一个点的切线走过去。或者可能线段和球不交，那就啥事没有。
G. Omnipotent Garland
选出$m$对最后相邻的B，那么我们需要把每一对之间的C都选走。注意到如果$km=n$，那么最近的两个B之间C的个数不超过$k-2$，我们选择外面的$k-2$个C。否则我们第一次选尽可能大的即可。
H. Saintly Coins
/fn
I. Misunderstood Missing
注意到后两类操作的效果只和后面的某些东西有关，爆力dp，设$dp(i,j,k)$表示考虑后$i$个，选了第一类操作的位置有$j$个，它们的和为$k$的答案，复杂度$O(n^4)$。
J. Philosophical Balance
先建st。先二分答案$d$。
感觉了一下发现二分答案好像不是很有用。
考虑答案不可能超过$1$，因为对方选择长为$1$的后缀你就没了。然后发现类似的想法啥用没有。
考虑dp，设$dp(u)$表示只考虑$u$子树的答案，转移类似于 srm817 Div.1 C. Hager。复杂度线性。
K. Desperate Fire Survive
考虑对于一个$k$，如果一个位置比$k$小了$\lg n$，或者比$k$大，那么直接删了就行了。所以有可能有用的数总数是$O(n\log n)$。
枚举一个$k$，考虑dp，设$dp(k,i)$表示从$i$开始的最短区间，使得可以合并出一个$k$，转移就先拼一个$k-1$，再拼一个$k-1$。转移需要进行$n\log n$次二分，查询需要两次二分，复杂度$O(n\log^2 n)$。
L. Eventual Journey
同一部的是$1$，相邻的是$1$，剩下的是$2$。
Gomel
gp of t宝。
A. One Goal
考虑爆力怎么做。枚举一个点，考虑它的贡献。重心的充要条件是没有一棵子树选了超过$\frac{k}{2}$个点，但是编号最小的重心呢?
重心唯一，当且仅当存在一个点，它的任何一棵子树都选了$<\frac{k}{2}$个点，否则往$=\frac{k}{2}$的走一步，就得到另一个重心，所以可以直接卷一卷，注意到两个点还是只会贡献一次，所以是$n^2$的。如果重心不唯一，它在虚树的一条边上，此时两边点数必然相等，我们枚举这条边(对应原树的一条链)，然后两边就可以随便选了，但是需要保证以这条链为根，两边选的点的lca是这两个点，减去全都选在一棵子树的即可。总复杂度$O(n^2)$。
考虑在边上的情况，点分治，贡献是一个min卷积，如果归并地离散化，复杂度$O(n\log n)$，但是这部分不是瓶颈。
考虑是一个点的情况。用gf来描述，考虑大小为$c$的子树，其egf为
\[F(cz)=\sum_{i=0}^\frac{k-1}{2}\frac{(cz)^i}{i!}\]现在我们要把一些这样的东西卷起来，提取$k![z^k]$，然后带系数地加起来。这玩意看起来很复杂。
考虑换一个想法，我们减去存在一棵子树大小$\geq\frac{k}{2}$的情况，这样的子树最多只有两棵，有一棵的情况是我们所要的，而有两棵的情况刚才算过了，把它加回来即可。重新设大小为$c$的子树，其egf为
\[F(cz)=\sum_{i=\lceil\frac{k}{2}\rceil}^\infty\frac{(cz)^i}{i!}\]那么一个点$u$的贡献就是
\[u(n^k-k![z^k]\sum_ce^{(n-c)z}F(cz))\]其中$c$枚举以它为根的一棵子树的大小。设$G(cz)=e^{-cz}F(cz)$，把常数扔掉，$e^{nz}$提出来，问题变成求一堆$G(cz)$的线性组合，然后只要把它和$e^{nz}$卷起来。
考虑这是线性组合，所以每一项是独立的，这就非常好。考虑设$c=i$时的系数是$a_i$，那么线性组合的$j$次项系数就是$[z^j]G(z)\sum\limits_{i}a_ii^j$。
考虑怎么求这种东西啊?我们还是写一个gf $T=\sum\limits_{i,j}a_ii^jz^j$，那么化一化发现它居然是$\sum\limits_i\frac{a_i}{1-iz}$，这让人想起来怎么求若干次数和1e5的多项式的乘积之类的，我们还是分治法法塔，分开维护分子和分母，然后合并的时候直接通分就好了。复杂度$O(n\log^2 n)$。
B. Two Teams
结论是，我们必然是让一个队通过罚时，而另一个队通过题数取胜。也就是说，我们让两个队轮流赢，一个队每次让题数比对方更多，而罚时从大到小选让对方尽可能只需要一题来反超，另一个队则每次让题数和对方相等，除非他们的罚时太大，此时也需要让题数更多了。
C. Three Indices
考虑怎么$n^2$，我们枚举一个区间$[i,j]$，然后看它和$[j+1,j+1+(j-i)]$是不是最多相差一个位置，如果是的话，$[j+1,j+1+(j-i)]$开始的所有方案都可以接到$[i,j]$后面。为了判断这个，直接维护有多少不同的。
经典地，对于所有区间长度，可以转移的位置是总共$O(\frac{n}{L})$个区间。可以看看 重写平方串，润和琳墩串。
考虑转移在每个$\bmod{L}$等价类内部进行，考虑一个可以转移的区间，其中每个$\bmod{L}$等价类的大小要么是$\lfloor\frac{x}{L}\rfloor$，要么是$\lceil\frac{x}{L}\rceil$这样的，并且按余数从小到大考虑所有等价类，这些值形成最多三个区间。直接考虑从小到大扫余数，用set维护序列上的连续段，那么总变化量是$O(\frac{n}{l})$，每次操作是一个$\log$，总复杂度$O(n\log^2 n)$。
D. Four Elements
容斥，减去选重了的，这部分很容易小常数$O(n^3)$，现在允许重复选一个数。考虑这个东西是若干个$\frac{cz^a}{1-z}$加起来然后四次方，考虑折半，我们先平方一下，得到的东西形如$\frac{P}{(1-z)^2}$，分子有$O(n^2)$项，大概是6e5吧。
接下来我们枚举一边的$\frac{z^i}{(1-z)^2}$，对于另一边的$\frac{z^j}{(1-z)^2}$，它们贡献$[z^s]\frac{z^{i+j}}{(1-z)^4}=\binom{s-i-j+3}{3}$。为了使$i,j$独立，我们使用范德蒙德卷积，得到$\displaystyle\binom{s-i-j+3}{3}=\sum_{t=0}^3\binom{s-i+3}{t}\binom{-j}{3-t}$，提出$t$之后就可以直接算了。主要问题是需要排序去重，或者你可以直接用map，这部分$O(n^2\log n)$。容斥看起来直接一样做也是$O(n^2\log n)$的，不过没有什么必要。
E. Five Points
考虑两个点怎么做。样例告诉我们答案是$\frac{3}{4}$。考虑A发出了一条射线，它和射线AB的夹角是$\alpha$(角取绝对值)，那么B发出射线和AB的夹角$<\alpha$，或者和A发出射线不在同侧则不会相交。不在同侧是$\frac{1}{2}$，而在同侧时有一半的概率更小，所以是$\frac{1}{4}$，加起来得到$\frac{3}{4}$。
考虑五个点怎么做。类似于某个agc题，我们发现角具体是多少不重要，只有若干个角的大小关系重要，具体一点就是每条射线和每条直线的夹角。这样的角一共有$20$个，爆搜一个排列，我们就得到一个至少能算出来的做法。如果能够剪掉一些不可能出现的情况，那么是不是就过了啊。
不是很懂。rng_58的做法是，所有$\frac{1}{2}n(n-1)=10$条连线，将极角分成$20$部分，枚举每条射线在哪个部分，然后可以判断是否相交，如果有必然相交的那么就相交了，否则对于一个有$k$条线的极角区间，有$\frac{1}{k!}$的概率它们两两不交，可以理解为当且仅当按照向无穷远处投影的顺序来排的时候才不交。
F. Six Words
线图中的点表示原图中的边，边表示原图的边的相邻关系，所以线图的线图中的点表示原图的一对有公共端点的边，边表示两对包含同一条边，边权是这个同一条边的边权。线图的线图的一条边，也就是原图的包含同一条边的两对有两种情况，也就是所有边都有一个公共端点，或者没有，前者对应于原图的一个点，后者对应于原图的一条边，不妨称为第一/二类边。
考虑先把第一类连起来。发现如果一个点度数是$c$，在线图的线图上对应$\binom{c}{2}$个点，把它们包含的两条边的边权排名作为坐标画到平面上会形成一个三角形，然后我们会给一行连行对应的边权，一列连列对应的边权。考虑kru，我们首先会把第一列全连起来，然后会把第二列连起来，并把第二列和第一列之间连起来，依此类推，我们知道贡献的系数是$c-2,c-2,c-3,…,1$这样的。
考虑第二类，发现一个点邻接的最短的第二类边必然比最短的第一类边要长，所以考虑kru的过程，我们必然会把第一类边加满，此时原图每个点对应的线图的线图上的点形成了一个连通块，而块之间只需要加第二类边变成树，所以直接并查集即可。需要注意原图的一度点不对应线图的线图上的点。
G. Seven Nevers
处理每个点作为结尾和开头的lis长度$f,g$，那么我们想把左边的一个$f$和右边的一个$g$拼起来，拼是一个一维偏序。注意到如果左边的$i,j$满足$f_i\geq f_j,a_i\leq a_j$，那么$j$就没有用了，于是两边各只有一个单调栈有用，而单调栈总变化量是$O(n)$，数据结构维护即可。这个和t宝说的线段树做法是一致的。
H. Eight Sins
也就是我们不一定会问中点了。
考虑可能的序列有$\binom{k}{n}$种，算一下大概是2464个bit。考虑我们让分出来的两边的方案数尽可能平均，这个可以二分一下，用斯特林近似来估计，然后就结束了。
I. Nine Judges
好像完全看错了数据范围。考虑任意两个题都是可比的，所以这是竞赛图，我们在缩点之后不停选择没有出度的scc中的点，如果选完了就选下一个scc即可。
考虑如何快一点。注意到我们直接归并排序，就能保证每个scc都在上一个后面，然后发现这个其实是求了一条哈密顿路。直接用sort好像也可以。复杂度$O(kn\log k)$。
J. Ten Ranges
十进制下素数的Minimal Set是$2,3,5,7,11,19,41,61,89,409,449,499,881,991,6469,6949,9001,9049,9649,9949,60649,666649,946669,60000049,66000049,66600049$，如果一个数不包含其中任何一个，那么它是secondary的。爆力数位dp，复杂度是$O({\huge L}\log n)$，其中${\huge L}=2935341711360$是状态数。
猜测其实能到的状态数很少。写一发，发现这一维其实只有$149571$。先dfs到所有可能到的状态，把它们的转移处理出来，然后直接dp即可。
使用dfa最小化，只剩下好像$19$个状态。
也可以每次合并两个，然后最小化。就不需要搜出可能到的状态了。
K. Eleven Problems
枚举一个排列。
Belarus
A. Alien Invasion
请注意点是按顺序排列的。否则我认为这个题不可能做。
考虑我们先问所有点，那么有一些凹的部分需要砍掉。我们枚举每个点删掉它，看它是不是在凸包上，如果不是那么就不是了，然后我们会得到一些凹的区间，对每个区间和它两边的在凸包上的点爆力递归下去处理。这些区间构成的多边形可能还是凹的，如果这样我们要继续递归。
考虑询问次数，第一次至少有三个点在凸包上，接下来每次至少有一个点在凸包上，所以递归层数不超过$n-4$，第$i$层不超过$i-3$个点可能不在凸包上。然后对于每个点它还需要付出一次不删的查询，所以看起来就差不多了。
B. Bus Stop
考虑如果所有$d$相等，那么我们知道min的期望是$\frac{d}{n+1}$。
注意到这个时间必然在$\min$以内，所以不妨从小到大排序。枚举一个在$\min$以内的子集，剩下的在$\min$以上，设$f_i$是$i$个车在$\min$以内的概率，发现它就是一车$(p_iz+q_i)$乘起来，分治法法塔即可，复杂度$O(n\log^2 n)$。
C. Calculating Average
平均值是$\frac{s_r-s_l}{r-l}$这样的，经典地，把$i$看成一个点$(i,s_i)$，那么这是一个斜率。维护每个前缀的下凸壳和每个后缀的上凸壳，在一个上进行三分，另一个上二分，复杂度$O(n\log^2 n)$。
这个是求凸壳公切线。https://www.luogu.com.cn/blog/user19567/guan-yu-ologn-qiu-chu-liang-tu-qiao-gong-qie-xian 即可。
D. Data Structure Problem
这玩意看起来就很有均摊，发现xor的时候我们只需要打全局标记，and/or的时候，建一个trie，如果一位同时有01并且被拍了，我们就trie合并一下，然后把0变1/1变0即可，由于此时已经没有0或者没有1了，还是可以当成xor标记。直接用一个数组维护每一层哪些点同时存在两个儿子，复杂度大概是$O(n\log v)$。
E. Expected Cost
这个东西在重心取得。一棵树可能有一个或者两个重心，两者都归结为求$n$个点的有标号有根树，所有点深度和的期望。注意到删掉根，深度和必然减少$n-1$，所以这就是$F=\exp F+A$之类的，看起来可以做到$O(n\log n)$。
或者对边进行考虑，每条边的贡献是两边点数的$\min$，那么总贡献的期望就是这些的期望加起来，也就是一个的期望的$n-1$倍。直接枚举两边的大小合并即可。
F. Fractional XOR Maximization
模拟竖式除法求出循环小数，然后从高到低贪心，不停递归，直到当前的情况和之前某一个同构，或者当前的情况已经可以直接计算答案。细节看起来很复杂。
为了把循环小数转化成分数，可以直接等比数列求和。
循环节可能很长，所以需要使用python。
G. Go West
绳子必然形成一个弧。需要考虑我们会使用多长的棍子，设出来求导即可。
H. Humongous String
离奇题。放zimpha翻译的题解。https://github.com/zimpha/problem-editorials/blob/master/opencup/2018-2019/grand-prix-of-belarus.md#h-humongous-string
I. Intellectual Prefix Maxima
草，没有修改啊。
那就直接leafy的全局平衡二叉树，每个点开$O(n)$的信息就好了。复杂度$O(n\log n+q\log^2 n)$。离线双指针就一个$\log$了，并且甚至可以线性空间。
看起来std好像是点分。
J. Jimp Numbers
请注意是唯一的方案。
$k=c^2-a^2-b^2$。设公差是$d$，那么也就是$k=(a+2d)^2-a^2-(a+d)^2=-a^2+2ad+3d^2=-(a-d)^2+(2d)^2=(a+d)(3d-a)$。
考虑一个数何时具有这样的分解。我们设$t=a+d$，那么$3d-a=4d-t$。考虑$k=t(4d-t)$。由于$a,d$都是正的，需要$t>d$。
考虑我们知道固定$k,t$，有$d=\frac{1}{4}\left(\frac{k}{t}+t\right)$，然后我们考虑$t>d=\frac{1}{4}\left(\frac{k}{t}+t\right)$，也就是$t>\sqrt{\frac{k}{3}}$。所以问题转化成数多少$k$有且只有一个因数$t$同时满足$t>\sqrt{\frac{k}{3}},4\mid \frac{k}{t}+t$，这两个式子不妨称为条件A和B。
考虑对$k\bmod{4}$讨论。
-
如果$k\bmod{4}=2$，那么$t,\frac{k}{t}$一定是一个奇数一个$\bmod{4}=2$的数，所以不可能满足B。
-
如果$k\bmod{4}=3$，那么$t,\frac{k}{t}$膜$4$应该一个是$1$另一个是$3$，所以任何一个因数都可以满足B，那么问题变成它有且只有一个因数满足A，$k$自己是一个平凡解，所以$k$是jimp number当且仅当$k$是素数或$1$，也就是它是$\bmod{4}=3$的素数。
-
如果$k\bmod{4}=1$，那么$t,\frac{k}{t}$膜$4$应该是$1,1$或者$3,3$，所以不可能满足B。
-
接下来考虑$k\bmod{4}=0$。尝试考虑$t,\frac{k}{t}$膜$4$，可以知道如果$2^3\parallel k$，那么$t,\frac{k}{t}$膜$4$必然一个是$0$一个非$0$，所以不行。继续拼一拼，发现如果$2^5\mid k$，那么也不行，因为$t=\frac{k}{4},t=\frac{k}{8}$是两个平凡解。所以考虑$2^2\parallel k,2^4\parrllel$。
. 如果$2^2\parallel k$，那么$t,\frac{k}{t}$膜$4$必须都是$2$，所以对于$\frac{k}{4}$的任何一个因数，它乘上$2$就可以满足B，$\frac{k}{4}$自己是一个平凡解，于是要求$\frac{k}{4}$是素数或$1$。
. 如果$2^4\parallel k$，那么$t,\frac{k}{t}$膜$4$必须都是$0$，所以对于$\frac{k}{16}$的任何一个因数，它乘上$4$就可以满足B，$\frac{k}{16}$自己是一个平凡解，于是要求$\frac{k}{16}$是素数或$1$。
其中每一部分都可以打表发现。所以这个题是一个打表题。柯洁说的好，当你不知道干什么的时候你就打个表。
剩下的就较为简单了，问题是求$n$以内$4k+3$型素数个数，$\frac{n}{4}$以内奇素数和$1$的个数，$\frac{n}{16}$以内奇素数和$1$的个数，然后加起来。使用min_25筛，复杂度$O(\frac{n^{\frac{3}{4}}}{\log n})$，或者直接分段打表。
K. K-Triangles
考虑怎么求三角形和，发现可以斜着递推一下，每次是减去一行加上一列这样的。
考虑怎么求答案，发现不交相当于每次ban了一个梯形或者三角形，它可以被一些斜着的前缀和和两个矩形拼出来。复杂度$O(n^2)$。
L. Long Game
请注意题意。如果存在逆序对，输出$n$的奇偶性，否则输出Bob。
Bytedance
wow , what an amazing confidence you have . Just by seeing the submission you reached conclusion that if someone is able to solve that problem , then i could also .
great .
petr单杀所有人。
A. Algorithm Was Applied
请注意$a<b<c$。
观察discuss，发现这个题可以$O(m\alpha(n))$。
也就是两个点最后有边，当且仅当它们一开始有边，或者存在一个编号比它们小的点和它们都有边。然后这个等价于两个点之间存在一条编号比两个点都小的路径，必要性显然，充分性考虑不停把路径上编号最小的点挖掉，把它两边接起来。
一个图要想做什么染色计数之类的，一般来说要么非常稠密，要么非常稀疏，要么它跟某几类极为特殊的图有什么关系。
考虑编号最小的点，它的邻接点连成一个完全图。然后把它删掉，考虑编号次小的点，它的邻接点连成一个完全图。这样进行完所有点，我们就得到了一张图。
发现最后一个点周围编号比它大的点形成一个团，所以这是一个弦图，编号是一个完美消除序列。考虑这有啥用，我们按完美消除序列的倒序染色，那么加入每个点的时候，它的邻接点颜色必然不同，而剩下的颜色都是可用的，所以设$f(u)$表示最后$u$邻接点中编号比它大的个数，那么答案就是$\prod(n-f(u))$。
考虑如何计算$f$，我们从小到大加点，加入一个点之后，它的$f$就是它连通块邻接的还未加入的点数。考虑直接对每个连通块维护邻接的还未加入的点数，合并的时候线段树合并或者hash table启发式合并，复杂度$O(m\log n)$。
考虑能不能再快一点啊。jiangly指出，考虑每个点$u$的贡献，建立kru重构树，这里kru重构树是加入一个点的时候把它邻接的连通块作为它的儿子。考虑一个点的贡献，它的一个编号比它小的邻接点会从某个地方被加入，然后往上合并，直到遇到这个点的时候贡献消失，也就是说所有的贡献形成一个叶子个数$O(\mathrm{deg}(u))$的连通块，它可以拆成$O(\mathrm{deg}(u))$条链。那么我们直接建这个虚树，然后树上差分-前缀和一下，复杂度瓶颈在并查集。然后并不需要建出虚树，用类似sa求后缀trie点数的做法进行容斥即可，然后这里lca可以用tarjan lca，看起来居然还能写。当然并不能和启发式合并拉开很大的差距。
B. Balanced Rainbow Sequence
观察discuss，发现这个题可以$O(n\log n)$。
考虑dp，设$dp(i,j,k)$表示前$i$个，lime和blue的前缀和是$j$，gray和blue的前缀和是$k$，最少改多少次。复杂度$O(n^3)$。
考虑点性质。经典地，对于每种颜色，一定是把一个前缀的若干个右括号改成左括号，一个后缀的左括号改成右括号，直接枚举三种分别改了哪些，确定了blue的两种之后，gray和lime就只剩一个自由度了，并且两者是独立的，复杂度$O(n^4)$。
所以先枚举blue的总和(左括号减右括号)，然后三者的一个前缀或者一个后缀就都必然要改了，做完这些我们在blue上我们从外往里改，相当于每次给一个区间$+1$，然后求lime和gray的答案，线段树支持区间加全局min，然后双指针即可。复杂度$O(n^2\log n)$。
考虑如何砍一个$n$。我们直接模拟一遍求出每种情况下每个位置的值，然后每个位置就是一个限制，那么我们从左往右扫序列，问题是有多少次操作覆盖了这个位置，然后就$O(n)$单次了。关于这个限制，具体一点，直接设三个序列的操作次数分别是$l,m,r$，当前扫到的位置分别被$c_l,c_m,c_r$次操作覆盖，那么每个限制是$\min(l,c_l)+\min(m,c_m)\geq x,\min(m,c_m)+\min(r,c_r)\geq y$之类的，每个限制可以拆成四个，最后变成$l,m,r,l+m,m+r$分别$\geq$某些数的限制，我们要最小化$l+m+r$，手动simplex枚举构成某个顶点的限制即可。
考虑如何做到$n\log n$。发现我们从小到大枚举blue的总和，那么每次是各$O(1)$个区间的$c,x,y$变化了$1$，合并限制的时候是维护一些东西的$\max$，可以直接线段树。
C. Called Convergient
可以感受到答案和$2$的幂有些关系。但是我完全没感觉。
由于方案是连续的，我们的简单想法是，给出一个上界，然后构造达到这个上界。
petr指出，打表发现当$x=\frac{t}{2^k}$，其中$t$是奇数也即它是既约的时，最优策略是选择$\frac{1}{2^k}$。显然答案是单调的，而$\frac{t}{2^k}$是稠密的，所以我们可以尝试逼近给出的$x$，这相当于求一个有理数的二进制表示，它必然会循环，所以我们找到一个循环节之后就可以求出答案。
为了大概地证明这个结论，猜测对于任意策略，答案$f(x)$大概是超鞅(期望比当前值小)，因为如果它是严格亚鞅(是亚鞅而不是鞅)，我们不停赌当前值的一半似乎就赢了(虽然题目要求你不能赌的比上一次小，但是这个仍然让人觉得不太可能)。超鞅也就是说$f(x+k)p+f(x-k)q\leq f(x)$，其中$q=1-p$。如果$f$能够全部取得等号，就无敌了(我们知道$f(0)=0,f(1)=1$，而$f(l),f(r)$可以推出$f(\frac{l+r}{2})$，这样可以逼近任意实数)，打表发现那个策略真的取到了，所以就赢麻了。
现在求$\frac{t}{2^k}$的答案。dp，设$dp(i,0/1)$表示考虑前$i$位，后面进了一个$0/1$的胜率，转移是如果$a_i=1$，那么$dp(i,0)=qdp(i-1,0)+pdp(i-1,1),dp(i,1)=dp(i-1,1)$，否则$dp(i,0)=dp(i-1,0),dp(i,1)=qdp(i-1,0)+pdp(i-1,1)$。现在我们已经可以处理有限小数了。对于无限小数，这个dp的转移是一个线性变换，所以我们算出循环节的线性变换复合$A$，然后考虑这一变换无限进行下去会收敛于哪。怎么算矩阵的无穷次幂?
google一下，你会发现这个矩阵是row stochastic matrix 行马尔可夫矩阵。我们希望求$A^n$，可以考虑jordan分解$A$为$PDP^{-1}$，其中$D$是对角的，那么$A^n=PD^nP^{-1}$，而$D^n$容易计算。wiki说根据Gershgorin circle theorem有row stochastic matrix的特征值的绝对值都$\leq 1$。它有一个特征值是$1$，并且爆力代入我们知道$A$全零时$-1$才是它的特征值，这个不太可能，所以$D^\infty$必然只剩下一个$1$。为了求出$P$，我们已经知道$1$是一个特征值，那么给特征多项式除掉一个$x-1$，就得到另一个特征值了，所以代入求解特征向量即可。然后发现结果的式子非常简单，以至于petr直接看组合意义看出来了。
妈的，bytedance哪来这么多这么离奇题啊。
D. Doesn’t Contain Loops or Multiple Edges
请注意loop指的是self-loop 自环。
题面强调了 恰好一个，于是考虑如果有一个点的颜色可以调大或者调小，那么调一下就好了。
如果没有这样的点，说明每个点周围的点都是满的，也就是每个点和它的邻接点都包含了所有颜色。猜测此时必然无解，然后过了。
考虑证明，尝试证明如果有解，只需要调一个点的颜色。考虑全都调大了的情况，发现我们可以只调颜色变化的点中变得最大的那个点，剩下的点并不需要动。
E. Equal Adjacent Elements
考虑相当于分配了一个排列作为删除时间，那么如果两个相同的数，中间的数都删了它们还没删，那么就完蛋了。也就是端点同色的区间，端点的$\min$要比区间内(不含边界)的$\max$小。然后好像不是很会啊。
柯洁说的好，不知道干什么你就容斥一下，这个条件反过来就独立了，所以看起来就很好。我们钦点若干个要么不交要么包含的端点同色的区间(相交而不包含必然不合法)，让它们比区间内的数删的都晚，发现我们钦点若干个不交的，然后向每个区间递归，进行区间dp即可，而钦点若干个不交的这一步可以用另一个dp完成，复杂度$O(n^3)$。
然后看起来有更简单的做法啊。考虑最后一个被删的数，它两边的数不可能相遇，于是还是递归下去了。复杂度$O(n^3)$。感觉我好像有点智障啊。
F. Formally, You Choose Three Integers
感觉这个操作看起来就很自由。猜测$n$足够大则同构就有解。但是假了，搜一搜发现$n=10$的时候只有$7200$种置换。
观察搜出来的这些置换，发现奇数总是在奇数位，偶数总是在偶数位，所以这样的置换只有$5!^2=14400$种，那么看起来就是说我们可以凑出其中一半。考虑能凑出来的和凑不出来的的区别在哪，根据某个agc题的经验，猜测和逆序对有关，我们再搜一下，发现逆序对数总是偶数。
于是几乎就结束了。如果$n\leq 5$，好像需要爆搜，否则我们分别看奇偶位是否同构，如果同构，如果有两个数相等那么必然可以把逆序对数调对，否则看一下这个置换是啥，跑一个逆序对。
逆序对数可以四毛子做到线性。
G. Game
同时是cf1710 E。为什么才2400啊，尽管是大原题?
感觉上这个$10^{228}$可能是有用的。
看看每个样例都说了什么。样例4看起来比较有趣，但是好像还是没啥用。
考虑一个牛逼想法，我们排序，然后二分答案，那么两个数和$\leq d$的状态可以双指针扫出来，画到平面上，称一个状态是白的当且仅当$\leq d$，否则是黑的。两个状态有边当且仅当在同一行或者同一列。如果轮到先手的时候，正在白的状态，那么先手就回家了，后手同理。每个位置拆成$10^{228}-1$个点，每个点只能走一次，那么这个问题就比较经典，删掉起点不可达的点，然后后手要寻找一个不包括起点的完美匹配，然后先手走到一个点，后手就走到它的匹配点。
计算是否存在一个不包括起点的完美匹配的话，考虑加上起点算一遍，去掉起点算一遍。注意到它和每层一个点是等价的，因为我们只删了一个点，只会影响第一层。算最大匹配的话，这里考虑konig定理(居然不是hall定理)，二分图的最小点覆盖等于最大匹配，我们考虑这张图的最小点覆盖，继续转而考虑最大独立集，那么我们让行，列的各一个前缀选黑色，剩下的部分选白色，然后一个黑点选了当且仅当它同时在行和列的那个前缀里面。
考虑枚举列前缀$i$，那么答案关于行前缀$j$是两个凸函数的和，所以可以三分。进一步地，从小到大枚举$i$，那么最优的$j$也越来越大，所以双指针即可。总复杂度$O(n\log v)$。
H. Hat With An Integer
我还以为是一个环。
这是一个经典问题，定义两个序列的距离是不同位置的个数，那么答案等于所有不可能出现的序列到实际序列距离的最小值。
现在我们考虑如何求这个。考虑如果第$i$位是$j$，那么下一位在$[j+b_i,j+c_i]$之间，也就是说每次可以走到一个区间，然后要尽可能和实际序列相同。这玩意类似一个lis，直接dp，设$dp(i)$表示考虑前$i$位，第$i$位和实际序列相同的答案，那么枚举上一个相同的位，中间可以用前缀和算出可以走多远，大概是$j$能转移到$i$当且仅当$a_i-sb_i\geq a_j-sb_j,a_i-sc_i\leq a_j-sc_j$，于是它就变成三维lis了，直接分治BiT即可。
也可以做到一个$\log$。我们希望消去一个维度。注意到$b_i\leq c_i$，否则答案是-1，于是$sb_i-sc_i$是单调下降的，然后我们把上面可以转移的那两个式子相减，得到$sb_i-sc_i\leq sb_j-sc_j$，也就是说满足这个的话，$i$必然在$j$后面。所以下标这一维就扔掉了，一个lis即可。
I. Intersect With Other Balls
没太懂这个题在干啥。
how u come up with such type of solutions?
J. J The Attacker Has
考虑怎么判断一个状态是不是必胜。如果守方的一张牌比攻方的一张牌大，我们就在这两张牌之间连一条边，那么如果存在一个守方的完美匹配，攻方不管打什么牌，守方都可以打匹配的牌，守方就无敌了。
然后由于攻方必须打出现过的数字，那么如果一个数字的子集有完美匹配，攻方第一手打在这里面，守方还是会赢。所以我们要求有哪些数字的子集存在完美匹配，那些不包含在任何一个子集中的数字就都是可以打的。
考虑如何求出一个完美匹配。如果你玩过任何一个牌类游戏，我们知道应该用尽可能小的牌去打败对方。所以贪心，数字的大小只在花色内有用，所以相同花色内匹配完后剩下哪些并不重要，所以我们把每种花色看成一个括号序列，考虑匹配剩下的部分即可。然后如果攻方剩了王牌，守方就输了，否则看一下守方剩的王牌和攻方剩的非王牌哪个多即可。复杂度$O(2^mnm)$。
考虑如何做到$O(2^m(n+m))$。对于每种花色dp一下，转移取个lowbit即可。复杂度$O(2^mn)$，空间可以做到$O(2^m)$。
K. K Integers
先尽可能选a，然后尽可能选b，然后尽可能选c，直到接下来必选的那个字符-1，选那个字符并继续考虑下一个必选的字符这样的。
L. Labeled Connected Graphs
类似于某个agc题，在$1$出发的最短路dag上dp，每次决策一层。设$dp(i,j,k,0/1)$表示$i$个点的图，最远的点距离是$j$，有$k$个的方案数，那么我们都知道层内可以随便连，层间只有相邻的层可以连，并且每个点都要连到上一层的某个点，胡乱选选就好了。为了计算答案，我们可以随时钦点一个点作为真正的$2$，然后让剩下的随便选。复杂度$O(n^3)$。
M. Moves You Need to Make
考虑一个多项式复杂度做法，枚举换了哪两个数，那么肯定会先把它们换过来这样的，然后再算这个的逆序对数。和这俩相关的逆序对数好算，并且关于它俩是独立的(我们必然是把大的往后换)，所以都算出来就随便统计答案了。
N. Number Of Vertices
相当于给边定向了，然后判有没有欧拉回路。
America
A. Piece of Cake
考虑两个点作为相邻的点被选的概率，看起来组合数选一选就好了。然后乘上它们之间减去的面积直接贡献给答案。
B. Busy Board
这个题在naipc的时候首杀是88min/jy
注意到有元素被操作过的行/列，最后最多有一个X。先判定是不是一开始就一样了。然后考虑如果一个位置最后是它所在行/列中唯一的X，那么操作它不劣。注意到如果我们操作了一个位置，那么接下来不管我们要操作什么别的位置，都可以把一个O塞过去然后操作，然后也可以干掉任何一个位置的X。但是我们不能在任意位置生成一个X，所以定义一个最后是X的位置是可以操作的，当且仅当它是所在行/列唯一的X，那么如果一个位置操作后只会影响到可以操作的X，那么它也是可以操作的，只要找到是否有可以操作的位置一开始是O，然后判断不会被操作的位置是否正确就行了。
C. Cost of Living
实数实在是太恐怖啦。
直接把通胀率和修正都设出来，然后爆力解即可。复杂度$O(c^3)$。
D. It’s a Mod, Mod, Mod, Mod World
类欧。
E. Monotony
考虑序列上怎么做，直接dp即可。
然后我们好像不是很会。爆力怎么做?考虑大力dp，我们枚举选了哪些行以及这些行分别是升还是降，然后对列dp。
注意到存前面两列就可以知道是升还是降了。预处理一下升降的情况，复杂度$O(2^nn^3)$，据说直接冲了。
考虑如何砍一个$n$。注意到，我们知道上一个可以知道升降的情况，知道第一个也可以，此时枚举选的第一列$s$，转移大概是$dp(i)=\sum\limits_{f(s,i)=f(s,j)}dp(j)$，其中$f$是状态。发现这个看起来只和每个$f$的个数有关，直接爆力统计即可。
F. Heaps of Fun
考虑把每个点的值分成$k$段，猜测答案是关于$k$的$n$次多项式，插出来求极限即可。但是很可惜它并不是。
考虑把数轴按$b$分成若干段，那么如果一段里有$k$个，其中某一个最小的概率就是$\frac{1}{k}$。dp，设$dp(u,i,j)$表示$u$子树，$u$在$i$这一段，这一段共有$j$个数的答案。
G. Intersecting Rectangles
边界重合也算/jy
没有相交，等价于没有同向线段相交(包括端点)，并且没有不同向线段相交(不包括端点)。前者排序，后者扫描线set/线段树之类的。
H. Rocket Powered Hovercraft
我们会先转，然后冲。轨迹是一个圆，尝试直接画，如果目标点在圆内则先转一段然后一边转一边冲过去，否则直接一边转一边冲到目标点到圆的切线，然后沿着切线直接冲。
I. Cutting Strings
还是贪心。一开始把所有东西都切掉，那么每次相当于用一次的代价选一段，开头结尾可以不花费代价。我们先尝试选择最大的字母，如果可以全选出来那么递归到这些字母之后的后缀，否则贪心地选取最长的连续段，如果当前长度不能都选完，则选一个后缀字典序最大的作为最后选的那个，这个可以用类似于最小表示/最小后缀的做法，而不需要sa。在boj上拿了最优解和最短解。
J. Subsequences in Substrings
考虑$n^2$，我们枚举左端点，那么往右匹配$t$，第一次匹配到的位置之后都可以作为右端点。那么从右往左在线建立子序列自动机就可以$O(nm)$了。
K. Knight of the Tarot Cards
关于一张牌能张出啥来，唐队长认为这是一个经典问题。先约掉$\gcd$。结论是，如果$a,b$奇偶性不同，它等价于$(1,0)$的牌，否则等价于$(1,1)$的牌，这两种情况分别称为A类和B类。证明考虑类似于某个经典题的做法，以及一个简单构造 :
-
如果$a,b$同为奇数，那么黑白染色一下，肯定走不到$(1,0)$，我们可以转一下递归到$\frac{a+b}{2},\frac{a-b}{2}$，注意到$\gcd(a+b,a-b)=\gcd(a+b,2b)\leq 2\gcd(a+b,b)=2$，所以这俩必然仍然互素。同时膜$4$讨论一下，可以知道这俩奇偶性必然不同，否则$b$必然是偶数。
-
否则我们首先证明可以走到$(1,1)$，直接考虑我们可以走到$(a+b,a+b),(a-b,a-b)$，而$\gcd(a+b,a-b)=\gcd(a+b,2b)$，左边是奇数而右边是偶数，所以可以把那个$2$扔了。于是我们也可以走到$(2,0)$，那么我们构造一个纵轴上没有距离，横轴上距离是奇数的方案，然后不停用$(2,0)$往回走即可。发现$b(b,a)+a(a,-b)=(a^2+b^2,0)$是可以的，所以就证完了。
主要难度在于你不会想到要这么构造。
接下来考虑两张牌会发生什么。此时我们有四个向量，如果两张牌类型相同，那么取个$\gcd$就行了。如果类型不同，设一个是$(a,0)$，一个是$(b,b)$，那么此时$(\gcd(a,b),\gcd(a,b))$必然可达，类似上面考虑，约掉$\gcd$，我们还是尝试到达$(1,0)$。如果$a$是奇数，那么我们显然可以得到$(a+b,b),(b,a+b)$，然后根据前面的结论可以到$(1,0)$。如果$a$是偶数，那么还是必然到不了，所以就结束了。
接下来我们有不超过$nd(v)$个状态，预处理出来然后从大到小dp即可，复杂度$O(nd(v)(n+\log v))$。
L. Planes, Trains, but not Automobiles
最小链覆盖。考虑建出经典的二分图匹配，我们每次要让一个点必然是链头，也就是把它的入点删掉，然后求最大匹配，那么也就是求它的入点是否必然在最大匹配中。这是一个经典问题，从每个不在最大匹配中的点出发搜交替路，能走到的点就可以不在最大匹配中。
M. XOR Sequences
考虑在trie上走，如果左右子树都非空，那么这一位是$1$的$i$，$p_i$必然在$0$子树这样的；如果左右子树有一个空了，那么全都递归到另一个。这个东西复杂度看起来是$O(n^2)$的，但是我们直接大力猜测它不是，发现如果一个数递归到了两棵子树，那么必然无解，所以复杂度是$O(n^{\lg 3})$。继续发现我们递归到左边和右边方案数是一样的，所以复杂度是$O(n)$。
China
A. Array
我们要让这个最小，那么必然希望$c$变小。如果改成前面出现过的一个数，改成啥关系不大，我们要求出到前面出现过的一个数的最小距离，set即可。如果改成后面才出现过的一个数，我们在被改成的那个数第一次出现的位置统计，这里带了一些别的东西，看起来需要两个BiT。
B. Chiaki Chain
dragoon: What’s the easy way to code B?
-is-this-fft-: To give up.
-is-this-fft-: (Seriously, fuck that task.)
找到每个环，然后每个点对应的链上的点几乎可以是它往上第一个三度点，但是如果没有三度点，此时$k=0,1,2$，特判一下。如果有三度点，有可能主链头上挂了一个子链，那么主链在哪就不清楚了，所以如果往上找到第一个三度点发现它已经挂了一个环，那么我们退一步把它挂到上一个点。然后找到最远的两个挂过的点，它们之间的任意路径必然是主链了，然后检查除了主链和各子链，是否有剩下的部分。
C. Cut The Plane
草，为什么是整数点。
如果不是整数点，我们只要画竖线就行了，或者可能需要让它稍微斜一点点点点点点点点，然后你就会了。
看了一眼题解，完全没懂这题在干啥。
D. Edges Counting
dp。需要统计$n$个点的基环树环大小和，那么我们枚举环的大小然后插上树就行了。
感觉不是很会$n\log n$啊。
吓死我了，我还以为膜数也是变化的。
E. Equanimous
这个题甚至是21年集训队论文 浅谈有限状态自动机及其应用 的例题。
堪比noi D2B，不过还差一点，因为noi D2B是可以手动构造的（
F. Fighting Against Monsters
看起来很背包。注意到如果boss很厚，各种策略基本上只差很少轮。
考虑如果boss在1e18级别。如果先杀死boss，那么小怪接下来一刀秒了。如果先杀死一个小怪，然后杀死boss，然后杀死另一个小怪，那么发现我们可以在尽可能短的时间内杀死第一个小怪，并且对它造成的伤害刚好是它的血量，因为我们可以用$1,…,k-1$拼出$1,…,k$的每个数。如果最后杀死boss，那么小怪必然很早就死了，设$dp(i,j,k)$表示前$i$轮，小怪的血量分别是$j,k$，主角最少掉了多少血，如果小怪死了则记一个负数，这样可以知道boss被砍了多少。小怪必然在前101轮死掉，在此之后直接模拟即可。
G. Mysterious Triple Sequence
打表发现好像找不到啥规律。那么直接猜测循环节来的很快，但是看起来这个很容易构造掉。
然后开题解。第一步直接吓死我，原来这个序列是硬凑的题面啊，不得不说你凑你妈呢，如果谁还能切这个我只能how mind works或者我有一个波特朋友。设$f_0=0,f_1=1,f_n=2f_{n-1}+f_{n-2}$，那么有$a_k=f_{2^k+1},b_k=f_{2^k},c_k=f_{2^k-1}$。我们直接把循环节中所有出现爆力bsgs找出来，然后直接把这些位置全求个离散对数即可。
H. Inner Product
经典问题。在第一棵树上点分，第二棵树上建虚树，问题变成每个点有一个点权，边有边权，然后要求所有有用的点对的距离乘上点权和的和。换根dp即可。
可能那个时候past glory ds水平还不太行（
I. Counting Polygons
也就是求有多少个不循环同构的长$m$，和为$n$的序列。polya，转$i$次的置换有$\gcd(n,i)$个环，然后组合数选出环之间，枚举$\gcd$，发现$\sum_{i=1}^m[\gcd(m,i)=d]=\varphi(\frac{m}{d})$，分解之后直接枚举就结束了。
但是我们还需要减掉有一条边至少是一半的情况。如果有两条边至少是一半，只有一种情况。否则它只在转$0$次的置换中被统计到一次，减掉就好了。枚举最长的边的长度，剩下的组合数选出来，这里是一个上指标求和，可以$O(n)-O(1)$。总复杂度$O(n+\frac{T\sqrt{n}}{\log n})$。
J. Square Graph
还是很牛逼啊。
考虑如果$i,j>i$之间有边，那么边权必然是$w_{j-i}$这样的。考虑什么时候有边，定义$f(k,i)=[a_i=a_{i+k}]$，那么$i,j$有边当且仅当$i$属于$f(j-i,…)$的一个长至少$j-i$的连续段。类似于gp of gomel C. Three Indices，我们发现和$i+k$有边的$i$构成$O(\frac{n}{k})$个区间，可以用sa找到它们。然后就变成了区间到相邻的区间连边(点对点)，求mst。考虑别乳卡，发现困难。考虑kru，好像也不是很容易。
发现显然其实有很多的边是没有用的，因为mst只有$n-1$条边。考虑如果固定一个长度，那么我们可以干这么一件事，我们只连每个区间对的第一条边，如果第一条边都连不上，那么这一对显然不可能有用了，因为它必然跟别的第一对对上了。这样只剩下$O(n)$个区间对。考虑把每个区间拆成长$2^k$的两个区间，然后我们按$k$从大到小处理，每层跑一个kru，就赢麻了。
K. Three Dimensions
数位dp。虽然结束的很容易，但是结束的很困难。
Moscow
A. Anatoly Shalyto
感觉一下，我们直接选择$a_1,a_n,a_{n-1}$，如果$a_n=a_{n-1}$则找到第一个不同的；反过来，选择$a_1,a_2$，以及最大的出现至少两次的数这样的。显然答案不可能更大。
B. Basirovich Maxim
钦点一个顺序，然后可以写出线性规划。然后发现这个太离谱。
仔细看了一眼啊，发现我是智障，我们实际上只需要考虑$S_0$中的位置，剩下的必然选满。也就是说序列分成若干段，每一段是相邻两个$S_0$中位置(左闭右开)，然后它对各$d$有一些贡献这样的。
经典地，考虑一开始先满上，然后每个位置可以把一个后缀减去一些，并且选的总量不能超过$c_0$，不妨钦点$c_0=1$。经典地，二分答案，然后转化成各$d_p-kd_0\geq 0$。那么此时相当于有若干个操作可以选，每个可以给各$d_p-kd_0$加上一个数，求是否有可行解。注意到这些操作张成的东西就是凸包，然后限制相当于求它和$x\geq a,y\geq b,z\geq c$是否有交。注意到交中存在一个点由最多三个点生成，所以我们会$O(n^3)$了，也就是枚举三个点爆力simplex。
柯洁说的好，当你不知道干什么的时候你就对偶一下。直接对偶，然后变成三个变量一堆限制，因为半空间交也是凸的，我们三分然后三分即可。
可以使用随机增量做半空间交。
C. CTAHKEB** ANDREW
感觉上直接做的话不是很可做。
考虑一个间隔何时最优?我们尝试移动一步，发现如果第一个元素是$x$，那么有$x-1$个数比$x$小，$n-x$个数比$x$大。所以会增加$n-x$对，减少$x-1$对，这和剩下的数在哪完全无关。所以将每个数置为$n-2x-1$，求最小的前缀和的位置即可。
D. Dr. Bill Poucher
考虑这个策略是啥。考虑样例2，第一个人说和第二个人相反的，第二个人说和第一个人相同的。如果实际上第一个人和第二个人相同，第二个人和第一个人相反，那么就矛盾了。所以我们猜测这和xor有些关系，猜测存在环则必然有解，方法是一个人和前面相反，剩下的人都和前面相同。
E. Elena Andreeva
总是选择$x=0$，然后猜测的次数是$\lg n$，也就是$\operatorname{lcm}$超过$n$所需的次数。
F. Filipp Rukhovich
考虑枚举一对相等的，计算它们在多少子序列中对称地出现，可以选一选。对一个二项式系数对称之后是一个范德蒙德卷积，合完之后拆一拆变成了差卷积。法即可，复杂度$O(n\Sigma\log n)$。
G. Gleb Evstropov
如果不带修，那么每个点出发往右倍增即可。
如果带修，考虑lct，$i$连向右边第一个$a_i+1$，发现居然结束了。
H. Hristenko Oleg
每行连成一串，每列连成一串，然后合起来kru。类似于thupc22 A。
I. Ivan Smirnov
考虑只有一次询问怎么做。不会。
类似于unr2022 D1B，我们贪心匹配，在匹配不上的时候倒回去。二分需要倒到哪即可。
还有9982种做法，这里给出其中一种。
考虑邻项交换，发现这个等价于树形邻项交换中，根下面只有两条链的情况，甚至于存在原题 cerc2013 E. Escape。
那么怎么做呢?如果一个位置比左边小，那么向左合并必然不劣，然后合并是结合的，所以现在两条链都是递减的，我们每次会选小的，所以选一个$t$中的元素，然后向后二分$s$中选到了哪即可。
J. Juke Artem
考虑每条边被经过的次数。猜测它就是各链$i,p_i$跨过它的次数，其中$p_i$是$i$的位置。猜测把这些都加起来然后乘$\frac{1}{2}$就是答案。
考虑证明。注意到一次没有代价的交换让一个点离终点更近了，另一个点更远了；而只有有代价的交换才能同时降低两个距离。而我们上面所算的就是总距离。
K. Kunyavskiy Pavel
考虑有了一个分配我们应该怎么做。考虑什么样的策略是纳什均衡的，发现对手的策略相当于每个对手控制的点删了一棵子树，那么你显然可以到达每个没删的叶子，如果你的策略会到达没删的叶子中最大的那个，那么你就没有更优的策略了。
尝试dp。猜一猜，我们知道均衡当且仅当指向的子树均衡，而改向另一棵子树得到的最大值也不比指向的子树大。设$dp(u,i,j)$表示$u$子树，双方结果分别是$i,j$的答案，$g(u,i,j)$表示$u$子树，双方修改自己的策略，最大分别能达到$i,j$的答案，$g$的转移取$\max$，$dp$卷一卷，这样的。
L. Lidia Perovskaya
没太看懂题。
M. Mikhail Tikhomirov
模板 pq树。非常复杂，不学了。
Baltic Sea
A. Cakes
显然最后三个人用时相同。但是没锤子用。
注意到这玩意是线性的，设第$i$个蛋糕分成了$x_{0,i},x_{1,i},x_{2,i}$，那么答案是$\min\limits_x\max\limits_i a_ix_i$，其中向量$a_i$表示第$i$个人的用时。尝试套用博弈论基本定理，这需要我们把$i$放缩成$i_0+i_1+i_2=1,i\geq 0$的实向量，因为线性组合总是不比$\max$大的。然后我们知道它就是$\max\limits_i\min\limits_x iax$。两次三分$i$的前两维，贪心即可。
但是，这个题也可以拉格朗日对偶。就先扔在这里吧，我们要求解$\max\limits_x f(x),g(x)\leq 0$，这里$x$是个向量，$f$是个线性函数，$g$是个输出向量的线性函数，那么它等于$\min\limits_\lambda\max\limits_x f(x)-\lambda g(x)$。这里$x$就是$i$，$\lambda$就是$x$，$f=0,g(x)=ax$，对偶回去我们
$\min\max\sum$的常见做法是对偶。
B. Interesting Permutations
其实是在算选$k$个数两两互素，后面随意的方案数。
$100$以内有$25$个素数。对每个状压它是否出现即可。但是飞了。
注意到超过$50$的素数只会出现一次，所以只剩下$15$个素数。复杂度$O(\pi(n)2^{\pi(\frac{n}{2})})$。
注意到类似于求所有子集lcm之和的做法，超过根号的素数可以分组做，所以复杂度$O(\pi(n)2^{\pi(\sqrt{n})})$。
C. Blocking Crosses
退火 king。也有构造大师直接构造了。
D. Exact Number of Calls
打表一些比较均匀的解，然后找到一个比较近的尝试调整。
E. Parity Scam
看起来甚至并没有人问这个题怎么做。
F. Least Common Divisor
爆力。
G. Beautiful Automata
显然只可能有一个点没有入度，它就是起点。只可能有一个点没有出度，就是整个串。
考虑先dp出到每个点的最短路和最长路，那么就可以知道每个点的suffix link了，如果parent树有二度点则不行。然后我们搜所有到整个串对应的点的路，得到一些后缀对应的路径，于是得到一些边上的字符是哪些位置。接下来不停跳suffix link把所有后缀找出来，这样每条边上的字符在哪必然都确定了。然后我们知道每个点出边必然不同，同一位置的字符必然相同，贪心分配即可。复杂度$O(n^2)$。
H. Divisible Inversions
直接做。
I. Negative Base
感觉上必然选择$(-2)^{k+1}$。
J. Same Songs
直接dp。
K. Inelastic Balls
set 堆胡乱维护一下。
简单做法是，它就是$(i,sv_i)$的下凸壳。不懂物理。
L. Make Spoiled Binary Tree
不是很好描述，建议直接看 https://codeforces.com/blog/entry/66650?#comment-506803。感受一下你会觉得比较爆力，但是又很优美，不是很懂怎么想到的。
Minsk
A. Template for Search
枚举一个回文中心，然后向两边dp。
B. Redistribution of Digits
如果可用的数字个数比约束的总长小，我们可以放一些$0$使得它们相等。贪心地，我们要让填出来的数尽可能小，就先填小数再填大数。先尝试填$0$，考虑什么数比较值得填$0$，猜测我们选择字典序最小的数，如果两个数，一个是另一个的前缀，则选更长的。然后就结束了。
C. Partial Sums
考虑二阶前缀和膜$2$，发现比较困难。但是高阶差分膜$2$非常简单，$k$阶差分是$s_{i,j}=a_{i,j}-a{i-k,j}-a_{i,j-k}+a_{i-k,j-k}$，所以我们……还是不太清楚高阶前缀和是啥啊。
反正根据这个我们知道如果答案超过1e6的话，它差分一次就没啥效果，所以1e6以内必然还有一个答案。然后再猜一手，答案必然是$2$的幂，这个可以归纳一下发现显然有一个循环节是$2$的幂，而最小循环节必然是任意循环节的因数。所以就结束了，我们二分一个答案然后用上面的东西爆力check，复杂度$O(nm\log\log n)$。
D. Lis on Circle
dp，设$dp(i,j)$表示现在选了第$i$个人手里数字为$j$的牌的最大长度，可以从前面一个区间转移，按数字从小到大考虑，转移直接取个区间$\max$即可，复杂度$O(n\log n)$。
E. Very Simple Sum
数很小。这个东西第一维是和，第二维是xor，法法塔然后法哇塔即可。复杂度$O(v^2\log^2 v)$。
F. Random XOR
经典地，$s$是若干位的和。枚举两位$i,j$，计算它们同时出现的概率，那么每个数可以分成 : 在$i$上是$1$，$j$上是$1$，都是，都不是。考虑gf，那么四者分别贡献一个$(px+q),(py+q),(pxy+q),(p+q)$，然后这里需要奇数，那么单位根反演一下就好了。复杂度$O(n\log^2 v)$。
G. Sum of Distances in Cactus
反对仙人掌，有你有我。
在圆方树上换根dp。
H. Not A + B
。
I. Cutting
预处理一些，然后搜。感觉很能冲。
J. Paternity Testing
考虑实际上是在问区间中有多少对点满足一个在另一个的子树中，看起来不过如此啊!莫队，哦你妈，强制在线啊。那就预处理一下块间的答案，然后需要查询子树内有多少点，到根的链上有多少点，前者根号平衡一下，后者差分之后根号平衡一下，两个可持久化根号平衡即可，复杂度$O(n\sqrt{n})$。
K. Chess Positions
感觉手动调调参随机搜一搜就搜出来了（
或者看看 : https://codeforces.com/blog/entry/66763?#comment-508297
Daejeon
A. A Plus Equals B
考虑$a:=a+a,b:=b+b$让我们可以忽略末尾公共的连续$0$，所以考虑让lowbit对齐，现在末尾的$0$都扔了，只考虑前面的部分，那么$a:=a+a$相当于$b:=b/2$。显然我们没有必要产生小数部分。
考虑能不能让差折半。发现如果$a>b$，那么让$a:=a+b,a:=a/2$就好了。但是这要求$a,b$都是奇数，否则$a:=a/2$之后$a$还是偶数，那就见鬼了。不过此时我们会继续除，所以这样的事情发生不超过$2\lg v$次，然后这里等差数列带一个$\frac{1}{2}$，总操作次数大概是$2\lg^2 v$。
B. Bohemian Rhaksody
考虑什么时候一个区域是可行的，发现它只要不包含任何一个灯泡就必然可行，因为它必然分别在每个灯泡的某一侧。所以又最大子矩形了。答案必然上下左右各顶一个灯泡，枚举左右的，那么上下的分别是$\min$和$\max$，感觉上扫过去ktt即可，好像他们分治李超树之类的了。复杂度不懂啊。
C. Cactus Determinant
0.4s又是什么东西。
考虑枚举一个排列是选了若干个环，奇偶性是选的偶环的个数，所以dp，结束了。
D. Dijkstra Is Playing At My House
这是一个经典问题，好像是joi open 2017 高尔夫。
球必然会撞在一条线或者它的延长线上，或者和终点在同一直线再停下。每条线尽可能往两边延长，然后每条线建一个点，然后每条线连相交的线，这个可以线段树优化建图。
E. Eat Economically
考虑费用流，是显然的。考虑模拟费用流，给代表天数的两条边的容量$+1$，不可能产生负环，考虑所有可能的增广路 :
-
选一个没选的作为午餐/晚餐。
-
选一个没选的作为午餐/晚餐，选一个午餐/晚餐变成晚餐/午餐。
更多次的反悔不可能出现，否则画一画发现我们之前就不是最优的了。
F. Fruit Tree
主元素可以$O(1)$合并，链出现次数可以差分变成到根的出现次数，然后向上找第一个某个元素，可以对每种数建虚树做到线性。使用静态lct，总复杂度$O(n\log n)$。
G. Good Set
dfs king。
一个有限集合上的拓扑定义为一个它的子集的集合，满足交并都是封闭的，并且这个集合本身和空都在其中。这个good set说的几乎是一个拓扑，但是其中可以不包含空和全集。结论是$1,…,k$上的拓扑和$k$个点边有传递性的有向图是双射，所以可以搜这样的图来搜拓扑，然后搜出来发现数量很少，就结束了。
那么这个双射是什么呢?如果包含$u$的集合总是包含$v$，我们从$u$到$v$连一条边。发现一个集合$S$存在于这个拓扑中，当且仅当它到它的补$U-S$没有任何一条边。
反正挺离奇的。
H. Hard To Explain
维护一个可撤销的凸壳，类似于某个noi斜率优化题。
I. Increasing Sequence
又见面了lis/oh
考虑包含一个数的lis是前面的什么和后面的什么拼起来。画出前缀的转移和后缀的转移的dag，然后大力支配树一下。
J. Jealous Teachers
网络流。但是流量很大。那就network simplex/kx
题面说的很好，我们考虑先随便匹配一下，每个人直接流出$n-1$，此时只剩下$n-1$的流量，然后再跑dinic。
Ural
A. Avoid Anagrams
这玩意甚至是colorful matroid，所以问题是本质不同子序列个数，我们枚举每个字符选了多少个，就是把所有字符卷起来。
B. Broken Sequence
感觉上$20$还是可搜的，如果没有一个串有超过$20$个?，我们直接折两半，问题变成找两个向量加起来得到$0$，直接做即可。
如果有一个串超过$20$个?，那么看起来需要一些想法了。它不妨长$n$。先把另外三个串都搜出来，然后我们就知道了这个序列的所有$N(s)$。然后我们从外往里每次确定两个位置，最边上的两个由$N(n-1)$约束，里面两个由$N(n-2)$约束，每一层确定了一个另一层也确定了，也就是说这个串只需要搜一半。最后调一调，复杂度是$\tilde{O}(2^{\frac{3}{4}c})$，其中$c$是?的个数。
C. Chains Solitaire
搜。不会爆搜。
D. Double-Slit Experiment
转转，每一段三分即可。
E. Easy Equation
\[\begin{aligned} &\sum_x\sum_y\sum_z\sum_w\sum_t[x^5+y^4+z^3+w^2+t=n]\\ =&\sum_{x^5<n}\sum_{x^5+y^4<n}\sum_{x^5+y^4+z^3<n}\sum_{x^5+y^4+z^3+w^2<n}1\\ =&\sum_{x^5<n}\sum_{x^5+y^4<n}\sum_{x^5+y^4+z^3<n}\lfloor\sqrt[2]{n-1-x^5-y^4-z^3}\rfloor \end{aligned}\]然后呢?然后不会了，不过这个复杂度是$O(n^{\frac{47}{60}})$，就结束了。
F. Format a Table
看起来是，整除分块第一列，三分第二列。
G. Game with Dominoes
每一个连续段是一个nim。从小到大枚举一个长度，连续段只会变化$O(n)$次。
H. Heracles
从每个特殊点出发dij，然后状压dp。
I. IQ
枚举最大的，二分最小的，跑最大匹配。
但是它远远简单。最大的必然和最小的配对。
J. Jack and Jill
也就是在一个环上随机游走。发现如果有两个连续的走过的位置，那么它就不可能再被跨过了。所以状态数是$O(2^{\frac{n}{2}})$。实现的时候，可以把往左往右走到的第一个11中间的部分推成1。
petr指出这个是线性递推。
K. Kinder Surprise
模拟。
L. Liquid Cats
倒水。
那么xix open cup就结束了!接下来我会搁置一段时间，而去做poland oi。
XX(2019~2020)
Kazan
vp了一下。
官方题解的link挂了，可以看看这里。
A. Apollonian Network
哪里有平面图直径???
感觉比较离奇。先还原这个图，我们枚举一个三元环作为最外层的三元环，然后和这三个点都有边的就是中间那个点这样的。
然后就可以串起来啦。讨论几种情况，大力dp即可。
B. Bitwise Xor
00:57 +3
看起来是签到题。
等价于选一个子集满足其中任意两个数xor $\geq x$。
注意到xor最小值总是在相邻的两个数取得，排序之后trie优化dp即可。
C. Counting Cactus
好像做过这个捏。
让我们看看高贵的逐点牛迭。仙人掌看起来是环的exp，但是这里我们的元是点不是边，这就见鬼啦。考虑我们枚举一个点，在它上面拼接环，做法是把包含它的项拿出来，把它删掉，做$\exp$，把它补上，加进答案里。虽然怎么看都对，但感觉还是挺奇特的。
环的集合幂级数可以dp求出，设$dp(S,i)$表示现在在$i$，起点是$\mathrm{lowbit}(S)$的链的个数，那么每个环被统计恰好一次，复杂度是$O(2^nn^2)$的。
D. Determinant
这个条件也就是所有e-dcc的大小$\leq k$。考虑我们在邻接矩阵中把e-dcc排到一起，它们之间形成一棵树。考虑树怎么做，行列式是枚举了一些有向的环，而树上每个环只可能是一条边，dp即可。考虑这个图上咋做，每个环要么是一条边，要么完全在一个e-dcc内。
自底向上做，每个e-dcc会和儿子们有边，为了处理这条边的贡献，我们对每个e-dcc求出上端选和不选的答案，然后对每个和儿子相接的点，给它建一个虚点表示选择了某个儿子的情况，如果这个儿子连了自己那就是没选它，这里的边权是容易处理的。复杂度$O(nk^2)$。
E. Easy Win
2:40 +
考虑如何判一个，经典的，基础环张成环空间，我们随便找一棵生成树，看看非树边确定的环能不能xor出$0$即可，也就是它们是否线性相关。这里只有$60$位，所以答案不超过$60$。
但是我们不知道树。考虑直接把边的端点也打进向量里去，你就知道为什么$n\leq 64$了。于是问题变成最大权线性无关子集。这是个拟阵，所以可以贪心。为了动态维护，我们插入一个向量的时候，所有参与表示它的向量都可以被它替换，而剩下的都不能。简单写法是如果走到一位，这一位是1且线性基里有对应的，那么保留权值大的，把小的xor掉这一位之后扔下去继续插入。
F. Fast Spanning Tree
-4
也就是某一刻开始一条边会变得可用这样的。
扔到平面上，每次合并就是给一些行一些列都减了一个数，然后要求编号最小的$\leq 0$的点。一个经典trick是如果$a+b\geq s$，$a,b$至少一个要$\geq\lceil\frac{s}{2}\rceil$，那么我们就把$\lceil\frac{s}{2}\rceil$插入到这条边的端点的堆里去，然后启发式合并，如果有一边到了，我们就拿出来检查是不是真的到了，如果其实没有到，$s$必然折半，爆力重插即可。堆启发式合并的总长是$O(n)$，复杂度$O(n\log^2 n)$。
写起来比较混乱邪恶，主要是因为两个priority_queue是懒删除，在你懒得记录往堆里插的权值以及到底插没插的时候这玩意并不够方便。使用pbds或手写，记一个iterator则会方便的多。
G. Grammarly
1:31 +
注意到我们进入一个相等的段之前，走出来的东西总是不相等的，所以枚举一个最先走到的相等的段重新算即可，这样的段只有极长相等段的前缀或后缀，也就是说只有$O(n)$个。
H. Honorable Mention
妈的，把intersecting看成了increasing。
感觉比较厉害。首先这是一个经典费用流问题。考虑怎么才能让它稍微可以合并一点，因为是凸的我们可以wqs二分，这就扔掉了$k$的限制。那么为了合并我们需要边界的流量，也就是记左边选没选，右边选没选，如果选了是不是一段的一端这样的，然后发现是不是一端这件事好像不需要记，我们看边界上可以再分出多少段即可。为了预处理线段树每个点的答案，因为是凸的，直接闵和一下。
我们需要wqs二分，在线段树上拆成$\log$个点，在每个点二分，这是三个$\log$，分散层叠或者wqs二分的每轮离线下来分别扫每个点就是俩$\log$了。
I. Interactive Vertex
2:12 +2
点分治，一次查询确定分治中心是不是，然后对子树们建huffman树，在huffman树上走。这个题比较educational吧。
J. Jiry Matchings
有趣的是一般图最大权匹配是不凸的。但是这是在树上，所以它还是二分图，所以它还是凸的。大力合并凸函数即可。
K. K-pop Strings
搜搜题。但是我不会搜搜。
容斥，钦点一些平方串，搜出所有可能的连通性，然后全部减去即可。但是我并不知道这什么量级。不过可以想到的是如果有东西能过，这个就跟它只差多项式。
Warsaw
也vp了一下。和donghanwen一起打的。
A. Alakazam
0:15 +
这里是求期望的和，那么根据线性性，相当于每个位置都变成了平均值。
B. Bulbasaur
那么也就是求每个区间拆点后的最大流之和。显然最大流不超过$k$。
从左往右枚举左端点，我们直接向右不停尽可能远地增广，当然这里是有反悔的。然后左端点现在移动了一步，这让我们可能可以进行新的增广了。注意到如果增广了一条长$l$的路径，接下来$l$步之后才会省下$1$的流量，而最大流不超过$k$，也就是说我们增广的总长是$O(nk)$的，每次的复杂度$O(lk^2)$，复杂度$O(nk^3)$。压位一下就$O(\frac{nk^3}{w})$啦。
C. Cloyster
3:46 +16
二分。考虑画一条线圈出一个封闭区域，那么找到这条线上的最大值，找到它周围哪个比它大，如果没有它就是答案，否则答案必然和那个比它大的在这个封闭区域的同一侧。如果相邻的有两个比它大，那么我们分别从它们出发每次走到相邻的最大的，最后必然相遇于终点，于是其间必然经过这个封闭区域的边界，这说明我们找的线上的最大值不是最大值。
D. Dedenne
这个题也被搬过啊。交cf一发最优解。
也就是求$n$个叶子的trie，每个子树有$c$个叶子的点代价是$\Theta(c\log c)$，一个作为左儿子的点不能有右儿子，求最小代价。考虑dp，设$dp(i)$表示大小为$i$的答案，发现$dp$几乎是凸的，于是可以进行一个在线的闵和，每次处理差分相同的连续一段。注意到答案是$O(n\log^2 n)$级别，那么差分不超过$O(\log^2 n)$，每次计算代价，把相同的值放在一起算，可以做到$O(\log n)$，复杂度$O(\log^3 n)$。
E. Eevee
4:43 +
容斥，我们需要钦点一个颜色的上升子序列，这里上升也就是在每个栈中位置都递增，然后相邻两个颜色间的方案数就是多重集排列，每个颜色内还要乘一个阶乘。带着容斥系数dp的复杂度是$O(n^2)$，而是否上升的情况和这个转移的系数可以一边移动端点一边计算，每次移动也是$O(n^2)$的。
因为数据随机，注意到区间长度每扩展$1$，原来上升的两个颜色现在都会有$\frac{1}{2}$的概率变得不再上升，于是我们维护目前仍然可用的转移，复杂度就是$O(n^3)$的啦。
F. Flaaffy
这个题很有实力。曾经在sdptt2021 r2搬过。
dp，设$dp(i,j,0/1)$表示答案在$[i,j]$中，现在我们拨到$i-1/j+1$，还需要多少步。没有前途的。
注意到答案显然不超过$K\log$，这里$K=5$是位数，那么维度交换，设$dp(i,j,0/1)$表示现在拨到$i$，用$j$步，可以猜出的最长的区间是$[dp(i,j,0),i-1]$/$[i+1,dp(i,j,1)]$。转移就是枚举拨到哪里，相同的一侧尽可能长，相反的一侧要能接过来这样的。
注意到这里转移的代价只有$6$种。考虑能不能快速统计这个，折半，我们枚举位的一个子集把它改成$?$，改$k$个能让两个数变得一样，那么转移的代价就$\leq k$，且必然有一种方案能取到真实的代价，于是每个改了一些$?$的状态，相同的步数，只需要保留一个。每个状态的贡献是一个前缀或者后缀，挂上去扫即可。复杂度$O((\Sigma+1)^KK^2\log\Sigma)$，这里$\Sigma=10$是字符集。
G. Gurdurr
3:07 +
大力dp。注意到$101$和$010$都不再被操作，相当于只是一个限制，我们可以从这些地方断开，然后就只剩下$111$和$110$两种。设$dp(i,S,0/1,0/1)$表示一个区间，长$i$，内部状态是$S$，两边分别是$101/010$的答案，复杂度$O(2^nn)$，不是$2^nn^2$是因为$S$的总长是$O(2^n)$的。
H. Hypno
1:18 +
我们的策略必然是按答案从小到大尝试每个邻接点一次，直到继续尝试不如对着答案最小的邻接点一直冲。
这个答案不太好直接维护，如果要直接维护大概需要平衡树吧。为了dij，我们可以考虑用一个估计的顺序，使得后处理的不会更新先处理的，发现按答案最小的邻接点的答案排序就可以了。
I. Infernape
看起来$k-1$是有其作用的。考虑枚举哪个没有覆盖，剩下的求一个邻域交，维护前后缀邻域交即可，然后就变成求邻域并点数了。容易树分块做到$O(\sqrt{n})$。
更进一步的，这些邻域的并很有性质，容斥，发现容斥的时候任意两个的交都是所有邻域的交，算一算我们只要用每个大小的和减去所有的交的大小的$k-1$倍。点分做邻域数点即可。
J. Jigglypuff
0:31 +2
注意到我们只会在某个位置分开然后在下一步立刻汇合，否则必然不优。于是只需要看每个可以这么做的位置的非严格右下方是不是有另一个可以这么做的位置即可。
K. Kecleon
2:32 +1
kmp，问题是挂叶子，到根的链$+1$，单点查询，lct即可。
L. Lati@s
这个移动看起来是各维的nimber积。那么我们就是要算一个nimber的积和式。
nimber是域，是域就可以乘除，而nimber的加法是本身的逆，所以我们可以直接高消求行列式。
SPb
这一场比较简单啊。
A. Polynomial in a Black Box
-12
差分。$d$次多项式的$d+1$阶差分是$0$。为了避免被卡，随机复合一个一次多项式。
百俊在线裁判上大概是数据锅了。
B. Board Trick
2:22 +1
看看3b1b的视频。打成一个长$64$的序列，如果$a_i=1$，我们给答案xor上$i$，那么如果现在是$a$，要把答案变成$b$，给$a\operatorname{xor}b$取反即可。
C. Connectivity
4:18 +5
胡乱调过了。
D. Absolute Pairwise Distance
4:32 +4
差分，莫队二次离线。这个题很适合当二次离线例题，可以看我的提交 https://vjudge.net/solution/41662328/radHK1QnGtrQUte5hZsK 。
E. Multiplication and Division by 2
0:22 +2
乘$2$就是左移，除$2$就是右移。枚举一个区间即可。
F. Festive Baobab
2:39 +
容易建出费用流，发现压根不会反悔，直接树剖线段树维护即可。
G. Flatland Elections
扫斜率，维护切每个点时截距的排序结果，维护在这上面相距$k$的最小差即可。复杂度$O(n^2\log n)$。
H. Eggs
1:10 +2
循环队列。
I. Removing Pairs
0:10 +
模拟。
J. Boxes on a Shelf
0:5 +
也就是边上两个长度的$\frac{1}{2}$加上中间的长度要$<$架子的长度。两维保留短的，排序之后从小到大选，边上两个必然是最大的两个。
K. Two Slicers
1:36
不妨设$a>b$，那么最大的块必然是$\frac{1}{a}$，我们只需要最大化最小的。从$a$的一刀和$b$的一刀重合开始转，直到再次发生重合，得到一堆一次函数，其中转的长度的系数一些是$1$一些是$-1$，显然两种分别取个$\min$然后求交点即可。
Eurasia
A. Ants
模拟。
B. Blend
直接dp。
C. Backup
也就是让你模拟一个单调栈。
D. bit gisect
那么我们就是要在dag上二分了!
传递闭包先，这里边数$O(n)$所以是$O(n^2)$的，然后我们查询一个点的时候，可以知道能到达它的点中有没有目标，那么我们希望找到一个能到达它的点数尽可能占一半的点。
E. Slots
F. Tea Sort
G. Shooting
H. Accelerometers calibration
I. Trees
J. Team order
K. Ostap’s dream
Tokyo
打的比较拉了。
Wow the problems and solutions of this contest is so fucking beautiful that I can’t even…..
Thank you very much for a really nice contest. You made my day, or even month.
A. Cookies
这个题还是比较带劲!首先注意到如果$k=i$的时候某个数留了下来，那么$k>i$的时候必然也会留下来，并且每个人操作之后都是这样的，所以我们每次找到多出来的留下来的那个数就好了。更带劲的是，一个人放进来一个数$x$并取走$\max$，相当于一开始暂定取走$x$，然后依次考虑每个数$y$，如果$y>x$就改为取走$y$，并用$x$替换$y$。这是扫$b$得到的过程，扫$a$也是可以的，而由于之前留下来的数之后还会留下来，每次只需要插入新的那个$a_i$。
具体一点，我们把问题转化成，有一个序列$b$，每个位置可能是$\min,\max$，每次给一个$a$，从左往右扫$b$，如果这一位是$\max$，那么$b_i,a\leftarrow\max(b_i,a),\min(b_i,a)$，否则反过来，求最后$a$是多少。这个查询是会改变$b$的。
这玩意当然会有点均摊吧!可以感觉到序列$b$是越来越极端的，$\max$越来越大而$\min$越来越小。考虑我们找到下一次$a$改变的地方，这可以用线段树维护。但是这个不太行，比如所有$b$都是$\min$，$b=1,…,n$，现在来了一个$a=0$。考虑把连续的缩成一个，那么$\min$就是大根堆，$\max$就是小根堆。但是只要在其中插一些不可能触发的$\max$就卡掉了。继续强行考虑，如果一个大根堆后面是一个小根堆，这个大根堆的根比小根堆的根还要小，那么除非大根堆是进来$a$直接弹$a$，否则这个小根堆必然没有用。由于随着插入，大根堆总是越来越小，小根堆越来越大，它将会一直几乎没有用。此时我们可以交换这两个堆而不改变结果，然后跟前后合并就可以让堆的个数减少$2$。
然后这个复杂度分析比较厉害。容易想到用相邻两个堆值域交中数的个数当势能，也就是相邻两个堆，不妨假设前面是大根后面是小根，设它们的根分别是$r,l$，那么这两个堆的势能是它们中在$[l,r]$内的数的个数。势能减少到$0$就可以交换合并了。显然总势能不超过$2m$。每走一步，$r$弹进后一个堆中，新的$[l,r]$不再包含$r$(这里需要假设数互不相同。如果有相同可以随意钦点一个顺序)，$l$则弹走了，而往前一个堆中插入的数可能让势能$+1$，于是势能至少减少$1$。但是问题是交换合并的时候这东西不好处理。
那么考虑不急着交换合并，我们把$2k-1,2k$两个堆放在一起看，不妨设$2k-1$都是大根堆而$2k$都是小根堆。设目前有$l$对堆，其中$c$对势能还$>0$，那么插入会让势能减少至少$c$，而势能的总和是$m$，也就是说如果保持$c\geq\frac{l}{2}$，最多只能进行$\frac{2m}{l}$轮插入，而每轮是$O(l\log m)$的，否则我们进行一轮合并就可以让$l$折半。那么原做法复杂度显然不比这个高，总复杂度$O(m\log^2 m)$。
B. Evacuation
读错，题意啦!原来是所有人都在同一个点。注意到往边上跑的话，必然是往更近的一边跑，所以就可以分成两部分啦。考虑如何对一个位置求出跑出去的代价为$k$时的答案，那么也就是让两边距离$<k$的shelter尽可能装，$\geq k$的就没用啦。所以对于左边我们是求$\max\limits_i((i-l+1)(S-(s_{2i-l}-s_{l-1}))+g_{2i-l}-i(s_{2i-l}-s_i)+i(s_i-s_{l-1})-g_i)$，其中$s$是前缀和，$g$是$ia_i$的前缀和。看起来需要点性质。
带劲的是这玩意有决策单调，左端点离的越远，取到$\max$的地方就越靠右。这可以直接改改然后证明四边形不等式，但是我们还是感觉一下，每个位置的代价关于跑出去的代价的函数，当跑出去的代价移动$1$，它会让代价增加需要跑出去的人数那么多，而这个人数是越来越少的，也就是说它是上凸的，这就是lightning conductor了。线段树，每个点smawk即可，复杂度$O(n\log n)$。
C. Sum Modulo
怎么是解方程题。显然这是线性组合，dp，有$dp(k)=0,dp(i)=1+\sum\limits_j a_jdp(i+j)$，那么我们设出$dp(k),…,dp(k+n-1)$，然后转一圈用它们表示自己，这就可以高消出来了，然后可以算出$dp(0)$。倒过来看这当然是个线性递推，特征多项式就是$1-\sum\limits_i a_iz^i$，爆力倍增取膜即可。复杂度$O(n^2\log v+n^3)$。
D. Xor Sum
感觉是超级无敌讨论题。但是不是，二分答案，xor的限制就是每一位选奇数还是偶数个，sum的限制感觉上尽可能快地顶满是不劣的，所以从高到低贪心填即可。但是我们一直填满可能会让某一位xor的限制满足不了，这就很不好，所以可能需要留出一个数来。但是不一定是留一个数，也可能是留很多个数，想一想感觉我们不会留超过$\lg v$个数，所以dp一下每种状态离sum最小差多少即可。根据官方题解，好像实际上是$\lg v+O(1)$。
E. Count Modulo 2
0:37 +3
写个gf先。多项式定理展一下，根据多项式系数的kummer定理我们知道只有各$i$不交的时候贡献是$1$，那么我们就考虑$n$里面的每个$1$分给哪个$a$并尝试以此凑出$s$。于是1e5就非常有用了，我们最多只能留1e5给下一位，否则就不可能凑出$s$来啦。dp即可。但是t了，换个bitset就好啦!
F. Robots
1:22 +4
如果没有这个最近的限制，大家都会直接匹配。但是有这个最近的限制，不过没有关系，我们猜测还是可以凑出直接匹配来，问题是怎么凑。如果最左边的触角匹配它右边的波特，或者最右边的触角匹配它左边的波特，那么直接触发它就好了。否则，必然有一个位置匹配离它最近的波特，因为最左边的触角匹配的波特在最近的波特左边，最右边的触角匹配的波特在最近的波特右边，必然有相邻两个触角满足，左边那个匹配的波特在最近的波特左边，右边那个匹配的波特在最近的波特右边，那么画一画发现这是不可能的，因为这样离它们最近的波特就不匹配任何触角了。
但是这个其实不够劲爆，考虑如果从左往右，波特$x$匹配触角$a$，触角$b$匹配波特$y$，那么$a,b$中至少一个可以激活。用链表维护即可。
G. Matrix Inversion
too lazy cannot move.
H. Construct Points
0:55 +4
让两条直线的斜率分别是$1-\frac{1}{10^9}$和$1-\frac{1}{10^9-1}$之类的。
I. Amidakuji
容易想到给每层分配一个$d_i$，然后你可以选择$+d_i$或者$-d_i$。取各$2^i$作为$d_i$，注意到这是一个环，所以距离不超过$\frac{n}{2}$，所以其实我们只用了$\lceil\lg n\rceil-1$层。
问题是有的层我们可能其实想要$0$而不是$d_i$。不过这好像关系不大。更恐怖的问题是这样凑出来的距离的奇偶性是确定的。注意到如果$n$是奇数，$d$和$d+n$的奇偶性是不同的，而我们在最后一层放$2^{\lceil\lg n\rceil}$就可以凑出$0,…,2n$的每个数。
考虑我们让第一步可以调整奇偶性。如果$n\bmod{4}=0$，我们可以构造一个$1,3,2,4$这样的环让每个数和一个奇数一个偶数相邻。如果$n\bmod{4}=2$，由于我们还有两层可以用，先不管前两个，然后只管前两个即可。
J. Median Replace Hard
When I read that “editorial of problem from AGC will not help” and saw that its editorial is in fact quite different from mine solution (at least on the first sight) it made me strongly believe that DFA approach is actually intended solution of J (moreover, it would be hard to imagine that anything works if DFA doesn’t).
造个dfa呗。这个题可以嗯造dfa，也就是从只有一个状态开始，每次给每个点后面挂上两个字符然后最小化，直到这么做不会增加新的结点。
K. Game and Queries
感觉上这个和xxiii poi stage 2 Wcale nie Nim有点相似。考虑A的策略必然是点最小的，B的策略必然是砍最小的，但是这里如果不全是$1$，B不会去砍一个$1$，因为它们还可以消耗A的一手。然后发现大概是，如果现在除了$1$以外最小的是$x$且至少有两个，A会把一个变成$x-1$，B则会把另一个一直砍到$1$，大概是用$2x-3$步，所以这里$x=2$也是特殊的。那么大概就是一个进位的过程了，修改的时候可能会连进/退很多位，此时我们爆力处理$\log v$位，然后向上线段树二分出进/退$1$的变化。复杂度$O(n\log v)$。
L. Yosupo’s Algorithm
模板 莫队二次离线。但是我写了一发，wa on test3，wrong answer 464744th words differ - expected: ‘1998255216’, found: ‘1997238998’。乐。
带劲的是这个题可以一个$\log$。由于这是yosupo题，可以相信这个查询的形式是有意义的!考虑怎么能利用它一下，注意到如果$a_1,a_2\times b_1,b_2$都合法，那么其中最小的那一种必然不会有贡献，因为不妨设它是$a_1b_1$，那么$a_1b_2$必须没有被查到，$a_2b_1$必须没有被查到，这说明$a_2b_2$被查到了。于是考虑对$y$分治，左边$w$最大的$a$和右边所有匹配，右边$w$最大的$b$和左边所有匹配即可。
那么怎么一个$\log$呢。考虑从大到小扫$a$的$w$，把$b$按$y$排序，能匹配的就是一个后缀。其中已经和之前的$a$匹配的那些，只需要找$w$最大的一个来匹配就可以支配剩下所有的，还没匹配的则爆力全匹配上。这样就只有$O(n)$个支配对啦。