突然又想起来做atc了。之前阅读了arc058~103和agc001~022D，但是今天我不关心比赛，我只想钦点难度，这就不得不说 https://kenkoooo.com/atcoder/ 。
选择了2000~3199。
arc150d
考虑一个点$u$被染的期望次数，只考虑它到根的链上发生的操作，注意到在这条链全黑之前$u$总是坏点，所以我们可以把只染坏点改成可以染所有点，这不会改变$u$被染次数的期望。问题变成有$l$个数，每次随机选一个，求全选过至少一次之后，第一个数期望被选了多少次，经典地，答案是调和数。
arc149d
直接平衡树，复杂度是$O(n\log^2 n)$的，看起来不是很能过。
先填成满点集。然后每次平移之后，发现原点左右短的那一段中每个点的答案都是它的对称点反过来，所以短的一段就不需要处理了，复杂度线性。是不是其实挺套路的，但是我不会啊（
arc149e
感觉很离奇。
等价于窗口是一个集合，然后窗口之外的部分，每次拿第一个加进窗口，然后把窗口的最小值扔进外面的最后。
设窗口和外面大小分别是$m_1,m_2$。注意到如果$k$很大，那么$m_2$轮之后，窗口里面必然是前$m_1$大的数，因为它们不可能被弹掉，并且总会进去。所以此时不管拿什么加进去，都会立刻把它拿出来，所以我们只需要做$m_2$轮，之后窗口外面只是在转转转，感觉这个是重要观察。如果$k$很小，没加入过的部分啥用没有，所以全都归结为$k=m_2$的情况。
考虑对于最终的外面的部分，我们把每个数分成加进去立刻弹出来得到的，或者弹出一个之前的东西得到的。容易发现第二类数是单增的，而第一类数在初始序列和最终序列中是相同的。如果一个数不是前缀最大值，那么它必然是第二类数，所以现在可能是第一类数的数是单增的。窗口里面的数和这些数最后会被排序，按操作顺序考虑，第一个弹掉的数可以是窗口中的一个数或者外面的第一个数，第二个弹掉的数还可以是外面第二个数，但是不能和第一个弹掉的重复，这样每个数都有$m_1+1$种可能的位置。分配完位置之后，容易发现它必然也可以构造一个合法的操作序列。由于窗口一开始可以是乱的，所以还要乘上$m_1!$。
abc271h
考虑讨论一下，我们可能用一种横着的一种斜着的，两种横着的，或者两种斜着的。猜测不可能用超过两种操作。所以求个直线交就赢了。
然后发现有问题。由于黑白染色之后斜着的只能走到同色点，所以我们可能会先用一个横着的改变颜色，然后用两种斜着的。枚举第一步怎么走，然后还是求直线交即可。
另一个做法是大力数位dp。感觉很阴间。
abc271g
终于有一个黄色的题。
考虑设$dp(i,j)$表示第$i$次访问在$j$时刻的概率，那么转移就比较简单，两边零散部分胡乱算，中间几何分布，然后矩阵快速幂，好像就结束了。复杂度$O(24^3\log n)$。
abc270h
看起来我们需要转化它一个。
排序不亏。考虑结束的瓶颈是离目标差最大的那个数，所以倒过来变成给每个数$-1$，然后把一个数置为$a_i$。考虑所有数的最大值$x$，我们知道每次操作之后$x:=\max(x-1,a_i)$，其中$i$是随机选择的那个数。
于是考虑随机游走，如果我们现在在$x$，有$\frac{1}{n}$的概率走到每一个满足$a_i>x-1$的$a_i$，剩下的情况则走到$x-1$。只考虑各$a_i$，可以直接考虑它们之间的转移，然后现在我们就会消一消$O(n^3)$了。
考虑怎么线性。注意到我们要解什么$Ax=x$，而这个$A$看起来是一个上海森堡矩阵，所以我们只需要消$n$次。并且第$i$行的后$i$个数是相同的(除了$i=1$)，所以消的时候也保持了这个性质，直接维护即可。但是由于需要快速幂，还是带$\log$。
abc270g
这是一阶常系数非齐次线性递推，所以循环节长度显然不超过$p$。它还是可以矩阵快速幂算，给向量补一个$1$即可。
bsgs。需要特判$a=0$，此时没有逆。
abc269h
也就是偏序是树，求每个长度的反链数量。
看时限，猜测根号。考虑根号分治，感觉长的不是很会做。
猜测法法塔，$n^2$ dp是显然的，所以直接链分治，对轻儿子建huffman树，法法塔合并即可。复杂度$O(n\log^2 n)$。
abc269g
让人想起某个图论题。
先全都选小的。翻卡相当于加一个数，那么这是一个背包，重量的和不超过$m$，要用最小的花费凑出一个重量。如果没有最小花费，大家都会合并两个重量相同的直到只有根号个物品，但是这里有最小花费，我们就不是很知道应该怎么合并了。
考虑一个强行做法，重量还是只有根号种，那么每种跑一个单调队列优化多重背包就赢了。复杂度$O(m\sqrt{m})$。
考虑一个简单做法，我们直接二进制拆分，注意到个数超过$2^k$的重量只有$\sqrt{\frac{m}{2^k}}$种，所以拆出来的总个数还是$O(\sqrt{m})$。所以那个合并的好像只是常数优秀啊?
arc148d
感觉上只有每个数都出现偶数次，bob才能赢。如果有一个数出现奇数次，那么有两个数出现奇数次，那么alice上来选其中一个，接下来bob选什么alice选什么，最后bob不得不选另一个出现奇数次的数，alice就赢了。但是这要求这两个数的和不能是$0$。更一般地，如果$m$是奇数，那么bob能赢当且仅当每个数都出现偶数次。考虑找到一个最大匹配，如果bob选了最大匹配中的数，那么alice跟着选，否则选最大匹配外的数。注意到如果最大匹配外只剩下两个数$x,y$，那么$x-y,y-x$必然不同，而按照上面的策略最后必然会只剩下两个数，所以不管前面怎么选，alice先选$x,y$中某一个，必然可以把差调成非$0$的。
对于$m$是偶数的情况，如果我们同时给相差$\frac{m}{2}$的数连边(称为 第二类边)，然后存在使用偶数条第二类边的完美匹配，bob按照这个完美匹配选也赢了。现在证明除此之外都是alice赢。考虑找到一个最大匹配(不一定使用偶数条第二类边)，然后按照刚才的策略选，那么匹配外只剩下两个数$x,y$的时候，$x-y,y-x$必然不同，所以alice就赢了。
为了算这个完美匹配，每一类内部匹配必然不劣这样的。
arc148e
恐怖故事，这里排列是本质不同的。哦好像其实只差除每个重数的阶乘。
考虑怎么才能让这些位置独立一点，不知道干什么的时候你就容斥一下，但是好像比较的输。
考虑这个大概是阈值图有向哈密顿路计数，于是考虑某个阈值图上的方向，我们每次删一个完全点或者一个单点。如果删了完全点，图会分裂成若干个单点和一个连通块，我们可以在这个连通块里面选任意多不交且并是所有点的有向链，然后以任意顺序串起来，挂一个单点也是简单的，然后就可以$O(n^2)$ dp了。
考虑如何优化，挂一个单点是$dp(i,j)=dp(i-1,j-1)$这样的，看起来就是$F_i=zF_{i-1}$，挂一个完全点可以选择它合并两条链，接到一条链的一端，或者自己作为一条链，是$dp(i,j)=j(j-1)dp(i-1,j)+2jdp(i-1,j)+dp(i-1,j-1)$，看起来就是$F_i=z(1+2\mathrm{D}+z\mathrm{D}^2)F_{i-1}$。但是并不是很会处理导数。
考虑换个想法，我们不要维护若干链，而是直接维护一个排列，可以在任意位置插入。一个完全点可以随便插，而一个单点不能插，需要放在旁边等一会，记录还剩多少个单点，可以得到另一个$O(n^2)$ dp。
考虑倒过来，我们从外往里考虑，称一个可以插入剩下的任何一个东西的间隔是一个槽，那么随着扫描线移动槽还是槽，加入一个完全点可以增加一个槽，加入一个单点需要占一个槽。然后就选出增加的槽和占的槽的位置就好了。
abc268h
贪心，在acam上不停走直到出现一个匹配，然后把这次匹配之前的部分分一段。
abc268g
先插个trie，然后一个点的排名相当于dfs序中前面点的个数，拆成每一层前面的点的个数，这个可以用期望的线性性拆开，然后每一层的期望是好算的。
arc147d
读错题了。麻。
也就是从左往右每一步，我们可以加入一个元素或者删除一个元素。这个贡献让我们觉得应该扫值域，但是扫值域好像不是很好，但是扫序列更不好。
完全不会。我们先枚举每个间隔中变化了的那个数，那么再确定第一个集合，就确定了整个序列。注意到设如果第一个集合包含第$i$个元素，$i$的出现次数是$c$，那么不包含的情况下$i$的出现次数就是$n-c$，所以不管第一个集合是啥，总贡献总是$\prod (c+n-c)=n^m$。这个变化了的数的方案数是$m^{n-1}$，乘起来就得到答案。
arc147e
考虑所有没过的人首先要进去，然后需要一些人进去调剂一下。可以感觉到问题相当于我们要选一个尽可能小的子集，使得外面的人都过了，并且里面的人排序之后都过了。
考虑先把线最高的老哥干了，我们需要一个线比他低并且分比他的线高的老哥来跟他换，不然啥用没有。找到分比他的线高的人中线最低的，把他加进来，交换他们的分数，然后把刚才那个老哥删掉。从大到小枚举线，用堆维护分比当前的线高的人中线最低的。
感觉比D简单。
abc267h
很遗憾，相同的数是有区别的，所以我们不得不法了。看起来就是把$10$个东西卷起来，记录一个奇偶性，然后直接卷即可。
abc267g
也就是求一个序列有$k$个严格上升的重排数量。
考虑欧拉数是怎么算的，我们把最大的数插进去，它可能插在一个上升或者一个下降，而必然造成一个上升一个下降。
从小到大排序然后dp，注意到可能有重复的数，也就是说现在考虑$a_i$，我们插入到另一个$a_i$后面不会产生上升。所以设$dp(i,j,k)$表示前$i$个，有$j$个严格上升的方案数，那么插入到一个左边是$a_i$的间隔不影响严格上升数，插入到一个严格上升不影响严格上升数，插入到一个左边不是$a_i$的下降或者平的间隔使得严格上升数增加$1$。复杂度$O(n^2)$。
abc266h
先染色，把不能走到的都杀了。然后看起来比较像是一个lis，分治BiT即可。
abc266g
太智障了，我上来就写了个三元gf。注意到没有两个rg相交，所以我们直接放rg就赢了。但是可能有放r和g的时候产生的rg，所以容斥一下就赢了。
还是考虑一下怎么三元gf!发现三元gf和直接计数区别不大，那么就不考虑了!
abc265f
容易想到转转成切比雪夫，但是想了想发现三维的曼哈顿画出来一个八面体而不是正方体，所以转不动的。
再看看，发现$d$很小，直接大力dp，前缀和优化即可。离奇。
abc265g
值很少，逆序对数可以直接在线段树上合并。
arc146c
也就是偶数大小的子集xor和不为$0$。考虑给每个数补一个$n+1$位，那么只有偶数大小的子集xor和可能为$0$了。为了不线性相关，前面$i$个数，选择奇数个的话，张出$2^{i-1}$个数，第$i+1$个数不能选在这里面，然后就结束了。
这里是集合，所以我们还需要除一个阶乘。
arc146d
看起来这是一个基环树森林。
考虑简单想法是全填$1$，但是如果$x,y$中有一个$1$我们就死了，所以考虑此时把那一个换大，然后这就会导致更多的问题。注意到全取$m+1$是合法的(但是爆了上限)，所以这个过程必然结束。复杂度也许是$O(nm)$。
然后发现std居然就是这个。注意到每条边最多贡献一次调整，所以复杂度是线性。
arc146e
考虑从下往上扫值域，那么如果我们现在扫到$i$，如果一个间隔左右都是$i$，那么它是一个槽，接下来这里会继续插入得到一个峰，否则这里就确定了。接下来插入$i+1$，对于每个槽可以选择放俩，或者放一个直接得到一个峰，然后剩下的$i+1$可以插在槽中间获得一个新的槽。然后就可以开始dp了，设$dp(i,j)$表示前$i$个数，有$j$个槽的方案数(好像边上需要特殊处理?)，然后注意到一个灵异事件，我们先全都放一个，那么剩下的每放一个都会得到一个新的槽，所以槽的数量是确定的，组合数选一选乘起来就赢了。
agc058b
最后每个数会扩展出一段，然后要求这一段里面没有更大的数。dp，设$dp(i,j)$表示前$i$个数，最后一段结束于$i$，值是$j$的方案数，前缀和优化一下即可。
或者感觉官方题解更为简洁。
agc058c
让人不得不想起一个2-sat题，但是我们先不管这些。$1$只能连$2$，$2$可以连$1,3$，这样的，考虑如果两个数相邻并且可以连边，那么直接连上必然不劣，但是问题是可能还有这两个点到外面的边，这些边有可能交叉。
再想想，注意到如果有相邻两个相同的，那么它们必然可以连一样的边。如果我们连了相邻的$1,2$，那么$1$必然没用了，因为如果它又连了一个$2$，那么那个$2$和之前那个$2$可以连一样的边。所以现在任意两个相邻的数都是不同的，并且$1,4$分别不和$2,3$相邻。
注意到如果只剩下$2,3$那么直接构造就赢了，猜测如果剩下$1,4$则必然无解，但是很遗憾这个不对。考虑合并相邻的$2,3$，并强行钦点其中一个删掉，比如删掉了一个$2$，那么$2$的另一边可能是$3,4$之一，如果是$3$我们就合并两个$3$，否则合并一个$3$一个$4$，再下一个是$2$或者$1$，我们还需要继续决策。也就是说如果存在一个$2$，它的一边是$3$一边是$4$，则可以删掉$2,4$，如果两边都是$3$，则可以删掉$2,3$。同样的，如果存在一个$3$，它的一边是$2$一边是$1$，则可以删掉$3,1$。考虑极长的$2,3$交替段，边界上一定可以删掉$2,4$或者$3,1$，那么如果$2$不比$4$少，$3$不比$1$少，则必然可以把$1,4$删完。为了证明必要性，注意到每棵树都存在一条边连接相邻的两个点，并且其中一个点是叶子，所以钦点删掉一个等价于钦点一个是叶子，所以这个操作可以生成所有树。
agc058d
看起来很复杂。不知道干什么你就容斥一下，发现相当于钦点若干个区间是abcabcabc…的子串，这样的区间称为 连续段，剩下的部分随意。直接写gf失败了，因为我们不能保证极长。可以考虑写成dp，但是看起来太困难了。类似于 顺子 那个题，考虑一个长$l$的极长连续段的容斥系数应该是$[l\leq 2]$，这样所有极长连续段的系数乘起来就得到答案。然后我们设任意连续段容斥系数的ogf是$T$，则有$\frac{1}{1-T}=1+z+z^2$，解得$T=\frac{z-z^3}{1-z^3}$，它的系数是$0,1,0,-1,1,0,-1,1,0,-1,…$这样的。然后就每次钦点一个任意长度的段了。
注意到这个容斥系数相当于不能选长度$\bmod{3}=2$的段，$\bmod{3}=1$的段让某个字符多出现了一次，$\bmod{3}=0$的段中各字符出现次数相同。一个$\bmod{3}=1$的段是$(xyz)^k(x+y+z)$，$\bmod{3}=0$的段是$3(xyz)^k$，所以答案就是$\frac{1}{1-\frac{x+y+z-3xyz}{1-xyz}}=\frac{1-xyz}{1-x-y-z+2xyz}$，考虑如何展开$\frac{1}{1-x-y-z+2xyz}$，直接大力展，结果看起来是什么
\[\sum_i\sum_{j=0}^i\binom{i}{j}2^j(-1)^{i-j}(xyz)^j\sum_{u+v+w=i-j}\binom{i-j}{u,v,w}x^uy^vz^w\]，枚举$j$，然后因为要提取$[x^ay^bz^c]$，$u,v,w,i$都确定了，复杂度$O(n)$。
常数元gf还是可以尝试处理的!
abc264h
dp，设$dp(u,d)$表示$u$子树，高度为$d$的答案，那么$dp(u,d)=[d=1]+\left(\sum\limits_{v}dp(v,d-1)\right)-\sum\limits_{v}dp^2(v,d-1)$。挂一个叶子的时候，它只可能向上更新$\log$个点，维护儿子们的dp值的和和平方和即可。复杂度$O(n\log^2 n)$。
abc264g
猜测我们要么在很少的步数内停止，要么重复一个很短的循环节。建个acam先，那么相当于我们从根出发走一条路径，那么如果有一个正环我们就走上去，否则走一条最长路，spfa即可，复杂度$O(\Sigma^7)$。好像过不了啊?
注意到一个点的转移只跟最后两个字符有关，所以状态数是$O(\Sigma^2)$的了，边数不超过输入的串的数量，复杂度$O(\Sigma^5)$，看起来就赢了。
abc263h
感觉很眼熟。二分答案，相当于画了一个圆，现在每条直线是一条弦，那么拿个数据结构扫一扫就可以求出交点的数量。复杂度$O(n\log v)$。
abc263f
dp，设$dp(u,i)$表示$u$子树最终的胜者是$i$的答案，转移比较直接。
abc263g
一般图最大匹配。我们当然希望把它变成二分图，注意到奇数和偶数，或者$1$和$1$的和才可能是素数，那么我们枚举$1$自己凑了多少，剩下的dinic即可。
但是很遗憾这个不太行，可以三分$1$凑了多少，或者注意到我们把一个$1$扔进去要么最大流增加$1$要么不变，所以二分$1$最少用了多少，然后剩下的自己拼。
好像还有只需要跑$O(1)$遍的做法。考虑随着我们增加自己凑的$1$的数量，答案的变化是$+1,+1,+1,…,+1,0,…,0,-1,-1,…,-1$，那么注意到这个东西只要知道了最左边和最右边的值，正中间的位置就确定了，而正中间必然是一个最大值，所以删光$1$跑一遍，加满$1$跑一遍，就得到了多少个$1$最优。看起来还是很有趣。
abc262h
考虑了容斥，感觉不太行。
考虑每个数最大的可能值，发现它顶到这个上界的时候才可能作为某个区间的最大值，所以把相同的$x$分为一类，每个数只可能在一类中有贡献。
对每一类分开做，设当前处理的是$x$，直接dp，设$dp(i)$表示确定了前$i$个，第$i$个是$x$的方案数，枚举上一个，要求中间不能跨过一个区间，复杂度线性。总共是$O(n\log n)$，瓶颈是排序。
abc262f
考虑爆力怎么做，注意到所有操作必然用完，因为删最后一个字符就可以让答案变小，所以我们枚举转了多少次，问题是求一个转$t$下之后最小的长$k-t$的子序列。枚举转到前面去的部分从哪里开始，然后就先尽可能选择a，然后往后尽可能选择b，然后往后尽可能选择c，直到个数用完结束。注意如果选了一个之后后面不够选了，那么就不能选它，大概是求一个区间$\min$之类的。
如果允许转转的话，也就是我们可以选完了一些再回到开头继续选，但是每选一个字符需要多付出$1$的代价。感觉一下发现我们必然会从一个最小的字符开始选，妈的，怎么是排列啊?那么就结束了，从这两个位置分别模拟即可。
注意到这个区间$\min$是可以用单调队列维护的。
abc262g
考虑什么样的序列可以用一个栈搞成上升的，经典结论是，如果存在$i<j<k$满足$a_k<a_i<a_j$，那么不可能搞成上升的，否则必然可以。
容易想到找到选的的最大值。区间dp，设$dp(l,r,i,j)$表示区间$[l,r]$，选的值在$[i,j]$中的答案，转移枚举最大值也就是那个$a_j$，然后递归两边，复杂度$O(n^6)$。注意到枚举最大值可以前缀和优化掉，复杂度$O(n^5)$。
arc145d
这里固定了总和，所以看起来还是很恐怖的，我们可以平移一下做到$n$以内的差距，那么需要一个数调节一下。
先考虑没有总和怎么做。wiki一下，发现我们可以选择若干个三进制表示不包含$2$的数。好像就结束了。
abc261h
首先所有没有出度的点是确定的。然后从它们开始传播，先手会希望走到一个已经确定的点，而后手希望走到一个还未确定的点。类似dij做即可。
abc261g
注意到每个字符经过若干次替换变成了一个串，考虑如果可以判断一个串由一个字符操作得到的最小代价，就可以直接dp了。dp，设$dp(c,l,r)$表示字符$c$最少经过多少次操作可以变得和$t_l,…,t_r$相同，转移枚举一个操作，然后直接dp，复杂度$O(n^4\Sigma)$，认为$n,k$同阶。
abc260g
考虑如果直角边相等是怎么做的，发现可以大力差分成两个三角形一个矩形。这里看起来是一样的。
arc144d
看起来很眼熟啊。猜测它必然是每一位的一个函数的和，考虑如果我们确定了$f(0)$和各$f(2^k)$，那么$f(S)=\sum\limits_{i\in S}f(2^i)-f(0)(\operatorname{popcnt}(S)-1)$。那么问题变成，数一个序列$f$和一个数$x$，要求$f-x$的任意子集和$\geq -x,\leq k-x$。显然我们把负的加起来$\geq -x$，正的加起来$\leq k-x$就赢了，所以考虑枚举一个$x$，枚举有$t$个负的，$s$个$0$，组合数选出来，然后把$-x$插板进去，这里经典的可以直接插进$t+1$个变量表示$\geq -x$。正的部分是一样的。写出来大概是
\[\sum_{s=0}^{n}\binom{n}{s}\sum_{t=0}^{n-s}\binom{n-s}{t}\sum_{x=0}^k\binom{x+t}{t}\binom{k-x+n-t-s}{n-t-s}\]右边两个组合数，可以写成gf，它们是$\frac{1}{(1-z)^{t+1}},\frac{1}{(1-z)^{n-t-s+1}}$，所以右边一共就是$\binom{k+n-s+1}{n-s+1}$，所以它和$t$是无关的。就线性了。
让我想到高阶差分的trick是否和这个有些关系，但是不是很懂。
abc259h
让人想起某个agc题。
但是完全不是。根号分治，出现次数多的颜色可以直接dp，少的爆力枚举一对，复杂度$O(n^3)$。
abc259g
让人想到网络流。最小割，但是这个边权可能是负数。经典地，先选择所有正的值，然后如果一个正的的行和列都没选，要把它割掉，如果负的的行和列选了恰好一个，要把它割掉，如果负的的行和列选了两个，要割一个inf。
所以直接建，每行每列建一个点，源连行而列连汇，割表示选。考虑怎么表示都选了，发现就从列到行连一个inf就好了。选了恰好一个的部分直接放进行和列的贡献里。使用dinic，复杂度$O(n^4)$。
abc258h
妈的，原来是选任意多个啊。
记选的上一个数的奇偶性，前缀和优化，矩阵快速幂。
abc258f
直接走过去，或者找到上下左右第一个main road上的点，然后沿main road直接走过去。
arc143d
也就是说我们要让尽可能少的边不在环里。
注意到我们选的所有的环必然是交替走前$m$条边和后$n$条边(称为 第一类 和 第二类)，因为如果连续走了第一类边，可以转一下多走两条第二类边。
于是猜测我们直接只建$n$个点，把边看成$a_i$连到$b_i$，跑割边就赢了。感觉这个题目给的图就好像改成了有向边。众所周知e-dcc直接dfs可以定向成scc，那么每条边都在一个环上。如果一个e-dcc是一个单点，那么它的那条第二类边也是割边。
arc143e
考虑什么时候是有解的。猜测如果一个连通块不全是B，那么就有解，但是这个假了，比如两个W就是无解的。
完全不会啊。考虑一个叶子，发现它和它的父亲的顺序是确定的，如果它是白色，那么删掉父亲之前必须删它，所以可以把它挂到父亲上，在删掉父亲之前/之后恰好一个把它删掉。那么父亲的颜色就会先改变白色的儿子数量次，然后考虑它的父亲这样的。如果考虑完子树之后一个点最终是白色的，那么也就是它和它的儿子中有奇数个白色，那么根是白色当且仅当整棵树有奇数个白色。
然后这个东西就连连边，开个堆toposort一下就好了。
abc257g
dp，设$dp(i)$表示后缀$i$的答案，转移是一个区间，z algo一下然后线段树。
或者设$dp(i)$表示前缀$i$的答案，注意到如果$dp(i)$不是inf，$dp(i)\geq dp(i-1)$，并且$dp(i)\leq dp(i-1)+1$。那么只需要尽可能往前转移，还是一个z algo就赢了。
arc142d
注意到如果能操作一步，第二步再操作回来必然是可行的，所以这个就是那个唯一的$S$。
一个 可以移动一步 的方案和选若干非平凡链，然后给每条链定向的方案是双射。
注意到如果一个点不在任何一条链中，那么就不合法了，因为一个棋子可以移动到这上面来，也可以在它的链上移动。如果两条链相对，那么也是不合法的。如果一条链的中间向外发出另一条链，那么也是不合法的。
猜测，如果两个链头或两个链尾相邻，或者一个链头/链尾和另一条链的中间相邻，则不合法。然后开始大力dp，设$dp(u,0/1,0/1)$表示$u$子树，$u$的链的方向是从下往上/从上往下，$u$不是/是最高的点的方案数，$g(u)$表示$u$的链从一棵子树到另一棵子树的方案数。转移考虑
-
$dp(u,0,0)$ : 如果$u$是链上最低的点，那么儿子们可以选$dp(v,0,1)$，否则一个儿子选$dp(v,0,0)$，剩下的都选$g(v)$。$dp(u,1,0)$是类似的。
-
$dp(u,0,1)$ : 一个儿子选$dp(v,0,0)$，剩下的儿子选$dp(v,1,1)$。$dp(u,1,1)$是类似的。
-
$g(u)$ : 两个儿子分别选$dp(v,0,0),dp(v,1,0)$，剩下的选$g(v)$。
可以注意到$dp(u,0,…)$和$dp(u,1,…)$好像是一样的，那么就只剩下三个状态了。
abc256h
线段树。如果一个区间的值都相同了，那么直接打推平标记，否则爆力递归下去，每个连续段会付出$\log$的代价减少$1$的势能，复杂度$O(n\log^2 n)$。
abc256f
$a_i$对$d_j$的贡献系数是$\binom{j-i+2}{2}$。爆力展开它，然后维护$i^2a_i,ia_i,a_i$的和就好了。
abc256g
考虑顶点上怎么放，接下来内部就比较简单了。枚举最后每条边放了多少，然后枚举第一个顶点放没放，矩阵快速幂优化dp。
abc255h
注意到这个是推平，set维护上一次推平时间的连续段即可。
abc255g
每一堆等价于一个nimber，设$f(i)$表示大小为$i$的堆对应的nimber，那么有$f(i)=\operatorname{mex}\limits_{j<i,(i,i-j)\notin(x,y)}f(j)$，注意到只有很少位置的转移被影响了，继续考虑第一个被影响的位置的$f$就是它的转移中被挖掉的位置中最小的那个，没被影响的位置是在填补前面的空缺，但是没有什么会产生空缺，所以没被影响的位置是前面的$\max+1$。考虑一下，对于任意一个被影响的位置，维护每个$f$的出现次数，把它的被挖掉的转移指向的$f$的出现次数$-1$，然后如果出现了$0$那就找到最小的那个，否则就是$\max+1$。为了简单维护这个，把$=\max+1$的位置拿出来，它们组成$1,2,…,\max$，剩下的位置必然是被影响了的，只需要在一个map里存它们就行了。复杂度$O(n\log n)$。
abc254h
每个数必然是先除若干次然后乘若干次。先考虑一个多项式复杂度的做法，$a$中每个数枚举除和乘各多少次，然后跑一个最小权完美匹配，复杂度$O(n^3)$。
考虑给$b$中每个数不停整除$2$，每除一次扔进一个hash table里面，然后给$a$中每个数不停除$2$，每除一次去hash table里面查一下，这样可以得到一个$n\log n$点和边的图，可以尝试network simplex或者zkw费用流冲一下。
考虑点正常做法。定义一个数的核是它不停整除$2$之后得到的数，把每个数挂到它的核上，从大到小枚举一个核，尝试给上面挂着的$a,b$找一个配对，然后如果$b$多了那就没救了，如果$a$多则除一个$2$递归下去。如果我们要配对$a,b$，它们分别进行了$c_a,c_b$次整除(而$a$没有进行下取整除)，那么我们可以省掉$\min(c_a,c_b)$次。如果一个$a$在第一个核处没有用到，接下来就永远不能省了，所以我们匹配的时候一定是先匹配整除次数最多的。复杂度$O(n\log v)$。
abc254g
如果最后要往上走，我们必然是，(往上走到顶，走到某个楼，)*往上走到目标高度，(走到目标楼)?，这样的。这是一个正则表达式。如果要往下走，swap一下。
考虑在楼间走的话，肯定会走到一个往上延伸的最长的电梯，求出这个之后倍增一下就好了。复杂度$O(n\log n)$。
arc141c
考虑$p$字典序最小这个条件看起来非常强，发现如果我们交换两个左括号，序列还是合法的，但是字典序变化了，所以这要求所有左括号的编号是递增的，所有右括号的编号是递增的，否则一换就更小了。也就是说$p$必须可以分成两个上升子序列，一个全放左括号，另一个全放右括号。
看样例可以猜测各种结论，但是好像不是很容易猜到。
完全不会。考虑如果我们确定了一个$s$，应该怎么找字典序最小和最大的重排。对于字典序最小，发现如果前缀和是$0$，我们必然贪心选择最左的左括号，否则选择最左的括号。那么可以知道如果$p_i>p_{i+1}$，说明$p_i$这里前缀和是$0$，选了一个靠后的左括号，而$p_{i+1}$必然是右括号。然而这个不是充要的，最左的左括号可能就是最左的括号。对于字典序最大，如果和是$0$，我们贪心选择最右的右括号，否则选择最右的括号。
然后就比较奇妙了。考虑直接把$s$画成折线，那么在选最小的字典序的时候，对于$x$轴下方的部分，我们会轮流选左括号和右括号，而$x$轴上方的部分我们会一串选过去。注意到$p_i>p_{i+1}$的部分就确定了$x$轴下方的部分，同理$q_i<q_{i+1}$确定了$x$轴上方的部分，所以我们就得到了整个括号序列。如果有位置没有确定那么必然不合法，然后再check一下这俩序列是不是字典序最小和最大的就结束了。
arc141d
也就是一个可比图的大小$\geq m$的独立集。但是好像没找到可比图怎么求独立集啊。
妈的，为什么我一个arc都不会。强行构造，把每个数分解成$a\times 2^b$，那么每个$a$最多选一个数，一共有$m$个不同的$a$，所以每个必须选一个数。假设选了一个$b$的序列，那么如果$a_1\mid a_2$，我们知道必须有$b_1>b_2$，并且这个是充要的，所以给每个$a$求出可能选的最小的$b$和最大的$b$即可。复杂度是调和数。
arc141e
先按$(x-y)\bmod{n}$分组，那么每次就是有一个偏移量地在两个组之间连边。
如果只有一个组，连通块数是$\gcd(n,a,b,c,…)$这样的，其中$a,b,c,…$是每次连的偏移量。
考虑把每组看成一个点，随便找一棵生成树，钦点这个生成树上的偏移量都是$0$，那么也就是我可以在一个连通块的组之间编号相同的点上自由移动。那么此时它就变成了一个组。合并的时候直接合并。
刚才说我一个arc都不会。现在看来我会的都在后面/jy
abc253h
状态数是bell数，预处理两个子集之间的边数，复杂度是$O(B_n)$的。然而看起来dfs并过不了。
考虑点牛逼做法，我们直接生成森林计数就赢了啊/yiw，大概是对每个子集矩阵树一下，然后枚举数量自己卷自己若干次，这里卷是子集卷积。复杂度$O(2^nn^3)$。
abc253g
注意一下这些操作都是啥，每轮大概是把一个数跟若干个数换了一遍，发现这相当于把这个数移动到某个位置，而一个区间的数往前移动，直接用pbds的平衡树维护即可。或者你可以继续考虑，发现除了第一次和最后一次，剩下的操作都非常简单，可以用链表维护。
abc252h
原来 out of …, choose … 是 从中选出 的意思/jy
也就是从每个集合选一个，求$k$大xor和。如果没有这个颜色的限制，那么我们都会线性基。考虑为什么$n$这么小，发现大小为$1$的颜色是没有用的，于是只剩下$35$种颜色，算一算发现此时只有1e11种方案。
考虑折一半，我们尽可能让两边方案数相同，然后分别搜出所有方案。最坏情况下大的一边大概是$3^{12}$，看起来很阳间。然后一边插个trie，另一边所有数同时在trie上二分，复杂度$O(3^{\frac{n}{6}}\log v)$。
abc252g
经典问题。区间dp，设$dp(l,r)$表示$[l,r]$对应的树的数量，$g(l,r)$表示$[l,r]$对应的从左往右根编号递增的森林数量，复杂度$O(n^3)$。
arc140d
也就是每个点有一条边，确定了若干条，剩下的随便连，求连通块数之和。
注意到连通块数就是环的个数，问题变成算环的总数。考虑先把已经有的边缩起来，如果一个连通块已经有一个环，那么这个环贡献剩下的随便选的方案数，否则它上面有恰好一个点还要向外连边，而剩下的点连到这个点的时候方案数是它缩之前的大小。
于是我们好像就比较会了。枚举一个环，环上每个点贡献它的大小，环外每个点贡献$n-1$，那么直接分治法法塔卷出每个环大小的方案数即可，复杂度$O(n\log^2 n)$。
arc140e
也就是任意一个$2\times 2$的子矩阵不是全部相同的。
让我们想起fjoi2022 D2 B的构造，考虑取$23$，并转转$23$次，就赢了。具体写起来看起来官方题解比较简单。
这个构造的解释收录在 如果我不知道把一些东西放在哪里，那就放在这里吧。
abc251h
$(n,i)$处的一个数，对$(k,j)$的贡献是$\binom{n-k}{i-j}$。那么一个前缀的贡献是$\sum\limits_{i=0}^r\binom{n-k}{i-j}=\sum\limits_{i=0}^{r-j}\binom{n-k}{i}$，那么求一个也就是求一行组合数的若干个前缀和。只求一个看起来也较为恐怖，但是注意到有一个$\bmod{7}$，那么我们lucas一下，设$t=n-k$，有
\[\begin{aligned} S(t,l)=&\sum_{i=0}^l\binom{t}{i} =&\sum_{i=0}^l\binom{\lfloor t/7\rfloor}{\lfloor i/7\rfloor}\binom{t\bmod{7}}{i\bmod{7}} =&\sum_{7i\leq l}\sum_{j=0}^7\binom{\lfloor t/7\rfloor}{i}\binom{t\bmod{7}}{j}+\sum_{i=0}^{l\bmod{7}}\binom{t}{l-i} =&S(\lfloor\frac{t}{7}\rfloor,\lfloor\frac{l}{7}\rfloor)2^{t\bmod{7}}+\sum_{i=0}^{l\bmod{7}}\binom{t}{l-i} \end{aligned}\]后面可以lucas，前面递归下去，复杂度是俩$\log$。注意到实际上后面只跟$t,l$的$7$进制表示有关，所以预处理一些东西可以做到一个$\log$。然后我们得到了一个$O(km\log n)$。
注意到求出$j=k$之后，剩下的每次就是每个加了一个$\binom{n-k}{r-j}$，可以算一个之后递推出所有的，每次修改$7$进制表示的均摊$O(1)$位，复杂度$O(km+m\log n)$。模拟$7$进制$+1$听起来有点阴间，不过应该并不难写。
abc251g
考虑直接求出这个半平面交，那么我们给每个方向的半平面求一个限制最强的，然后这里也不需要真的求，只要爆力检查每个查询点就行了。复杂度$O(n(m+q))$。
abc250h
当然按$t$从小到大扫，我们需要求出房子的连通性。如果没有边权，我们从每个点出发bfs $\frac{t}{2}$的距离，如果bfs到了同一个点则合并。但是现在有边权，上个堆先，然后每条边上的相遇时间还需要再开一个堆，听起来就很困难。不过可以注意到，对每个点求出端点到最近的房子的距离$d$，那么边$(u,v,w)$会在$\frac{d_u+d_v+w}{2}$时刻被扫到(从第二个堆中弹出)，求$d$听起来就好写多了，然后按这个排序，搞个并查集即可。如果要在线，可以跑个kru重构树。
abc250f
一块可以差分成两个前缀和和一个三角形。双指针。
abc250g
这是一个经典模拟费用流题来着。容易建一个匹配，发现这上面你甚至不需要反悔。线段树维护最大的$p_j-p_i(i<j)$即可。
好像也可以slope trick。也可以直接从左往右加边，加入一个点时可以换前面的一个，也可以连前面的一个没连的，维护两个堆就好了。甚至可以维护一个堆。所以有没有可能单向链上的费用流天然支持slope trick。
arc139c
直接画到平面上，相当于有一个网格，每条线上只能选一个点。直接猜测它是一个削了一些的棋盘，那么直接选对角线就赢了，但是看一眼样例觉得并不对。画一画，发现这些点不都是连通的，消一手hermite标准型，再画一画，发现它有八个连通块。那么每部分相当于一个削了一些的棋盘，画一画你就懂了!
我的做法大概是，假设$n\geq m$，那么枚举一个起点，然后贪心地沿着下边界线走即可。代码我随机调整出来了，可以看看 https://atcoder.jp/contests/arc139/submissions/35605206 。
arc139d
发现最后剩下的数肯定是所有数里面前$x-1$小和后$n-x+1$大，因为它们不可能被删，而必然被加入。
注意到两个好像是对称的，所以只考虑前$x-1$小。dp，设$dp(i,j)$表示前$i$个选了$j$个的方案数，转移枚举这一个选了多少，设$i$出现$c_i$次，看起来是$dp(i,j)=\sum \frac{(j-k-c_i)i}{(j-k-c_i)!}dp(i-1,k)$，最后要乘一个$k!$。直接做是$O(n^2m)$的，可以法法塔做到$O(nm\log n)$，感觉应该可过吧。好像先求值最后插值就$O(nm)$了。
考虑一个简单点的做法，枚举一个什么东西，直接算它的贡献。想了想，如果枚举一个值，算它在前$x-1$小的方案数，那么我们需要考虑它的出现次数，这里一个想法是钦点大小相同的数前面的更小然后枚举位置，另一个想法是枚举一个排名，尝试一下发现前者比较恶心，所以考虑后者。
如果我们钦点排名为$r$的数是$t$，一开始$<t$的数有$pc_t$个，$>t$的数有$sc_t$个，那么要求后面有不超过$r-1-pc_t$个数$<t$，不超过$n+k-r-sc_t$个数$>t$，剩下的$=t$。大力枚举一下，可以得到
\[\sum_{r=0}^{x-1}\sum_{t=1}^mt\sum_{i=0}^{r-1-pc_t}\binom{k}{i}(t-1)^i\sum_{j=0}^{n+k-r-sc_t}\binom{k-i}{j}(m-t)^j\]看了一眼，能且只能把$r$往后换，换完之后搞一搞它就变成$g(i,j,t)=\sum\limits_{r=pc_t+1+i}^{n+k-sc_t-j}[r\leq x-1]$了，可以$O(1)$算，于是得到
\[\sum_{t=1}^mt\sum_{i=0}^k\binom{k}{i}(t-1)^i\sum_{j=0}^{k-i}\binom{k-i}{j}(m-t)^jg(i,j,t)\]固定$t$，从大到小枚举$i$，后面那个$\sum$可以递推出来，复杂度$O(mk)$。
abc249g
最大xor和不得不使用线性基，先处理$\leq k$的限制，枚举这个xor和在哪一位开始和$k$不同，前面我们在线性基上表示出来，这得到了一个xor和，剩下的低位可以随便选，而线性基外的数也可以随便选，对这些数(当然是尝试消了之后的)再建一个线性基求最大xor和，精细实现一下，复杂度$O(n\log v+\log^2 v)$。
然后好像不是很深刻。大概是注意到我们给一个xor上另一个不改变张成的空间，所以可以把两部分拼在一起消一消，消成上三角之后就赢了。
abc248h
注意到这个题看起来很经典。直接卡笛尔树，扔到平面上得到$O(n)$次矩形加减，查询$\leq y-x+k$的位置个数。扫$y$，分块维护$x$，$y$右移是全局$+1$，直接每一块开个有序的vector，查询的时候二分，修改的时候归并就行了。复杂度$O(n\sqrt{n\log n})$。
等会啊，题解怎么俩$\log$啊¿
分治，考虑如果$\min,\max$在同一边，那么把值域看成一维，另一边是一个二维偏序。如果$\min,\max$不在同一边，那么是一个三维偏序。但是继续注意到到中点的$\min/\max$是单调的，所以又变成序列上位置的限制了，然后就只剩两维了。
数点的时候单调性还是很重要。
abc248g
这位更是。枚举一个$\gcd$，然后带一个$\varphi$的容斥系数，搜出每个连通块并dp。复杂度$O(nd(n))$。
abc247h
看错题大师。也就是最终序列一个颜色内部可以任意重排，考虑什么情况下可以换出来，注意到每个环上的颜色都是一样的所以比较好做，猜测如果环数$\geq n-k$并且和$k$奇偶性相同就行，因为我们每操作一次环数的奇偶性都会变化，如果操作不同的两个环则会把环连起来，否则会分裂一个环。
然后就比较简单，枚举一个个数，每一类内部是斯特林子集数，求出来之后分治法法塔即可。或者直接写个dp然后分治法法塔。
abc247g
从小到大扫学校，枚举前两个人的学科，设$dp(i,0/1/2)$表示前$i$个学校，选了前$0/1/2$个人的最大能力和。复杂度$O(v^4+n)$。
为了优化，前缀和一下，好像就$O(v^3)$了。
然后好像我比较智障啊!这个就直接，每个学校和每个学科匹配最多一个人，跑费用流即可。
arc138d
这个看起来是，$k$-格雷码之类的东西。wiki了一下好像没有找到啊。
那就强行构造。如果$k$是偶数，那么必然无解，因为popcnt的奇偶性是不变的。如果$k$是奇数，那么popcnt是奇数和偶数的部分是交替进行的。
然而还是不是很会。考虑我们每次是xor上一个popcnt为$k$的数，那么随便跑一个基，如果不满秩则没救，如果满秩，那么每次xor上基中一个数原来的值(而不是基中的值)就可以得到所有数。跑一个格雷码表示每个数是否要xor上即可。
据说直接搜就过了。并且是洛谷原题7949。看起来是分很低的原因。
abc246h
如果没有?，子序列自动机。但是现在有，考虑一个经典dp，设$dp(i,j)$表示前$i$个位置以$j$结尾的本质不同子序列数量，转移是$dp(i,s_i)=\sum dp(i-1,j)-dp(i-1,s_i)$，也就是前面所有子序列都可以接一个$s_i$，但是其中有$dp(i-1,s_i)$个已经出现过了。注意到转移是线性变换，维护一个后缀和就好了。复杂度是线性。
abc246g
二分答案，问题转化为xix open cup gp of peterhof G. Game On Tree。
好像一直忘了认为最小/最大化的博弈论问题可以二分转化成直接的输赢。见到这种问题就先二分即可。
abc245h
如果是和，那么大家都会做。如果$m$有原根，那么我们找到一个原根，大家还是都会做。
考虑先都除一个$g=\gcd(n,m)$，现在各$a_i$也必须和$m$互素(把$g$那部分也都除掉了)。互素就构成乘法群，猜测如果$g=1$，凑出每个数的方案数是相等的，因为不管前面怎么选，由于逆元存在且唯一，最后一个数总有恰好一种方案把它调成对的，也就是说答案就是$\varphi(m)^{k-1}$。
考虑$g>1$。分解$g$，然后我们知道只要确定了包含分解的各部分的数都是啥，剩下的数的变化就只是每个数选的时候方案数多乘一个$g$。枚举多少个数包含这些，然后dp，设$dp(i,j,k)$表示前$i$个数，上一个选了$j$，当前乘积是$k$的方案数，那么这一次选择若干个$>j$的数，然后它们还可以乘上一个$\perp m$的数，如果选了$d$那么有$\frac{g}{d}\varphi(m)$个这样的数，如果这次选的这些里面有乘的数相等的，重排的时候就要除一个阶乘，复杂度毛估估是$O(d^3(n)\log n)$。并过不了。
考虑直接在序列上做，而不是把数插回去。设$dp(i,j)$表示前$i$个数，当前乘积是$j$的方案数，转移直接枚举选啥。也可以做到$O(d^3(n)\log n)$。
看起来我们需要注意到一点什么。注意到刚才说 然后它们还可以乘上一个$\perp m$的数，如果选了$d$那么有$\frac{g}{d}\varphi(m)$个这样的数，发现所有$d$的乘积就是$g$啊?所以矩阵快速幂的时候所有的系数都可以是$1$了。
看起来我们还需要注意到一点什么。每个素因数是独立的，所以可以分开矩阵快速幂，现在只需要记一个次数了，就赢了。
还是要记得独立啊/oh，所以这个真的是直接做题啊。
abc245g
也就是求一个到不同颜色的关键点的最短路。考虑如果我们从每个关键点开始跑dij，那么这会形成若干个块，每个块是到某个关键点距离最近的点，定义一个块的颜色是这个关键点的颜色。如果一个点所在的块和它的颜色相同，那么它必然希望寻找一个和这个块邻接的块。首先从它出发需要走到一个块边界上的点，然后沿着一条块间的边走到另一块，然后走到那一块的关键点。所以我们对每个点计算它走一条边能走到的不同块的点中，到那个块的关键点的最短距离，然后对每个块建一个源，到每个点连这个最短距离，跑dij即可。由于每条边只会被两边的块枚举各一次，复杂度$O(n\log n+m)$。
abc244h
动~态~凸~包~
经典的，$a_ix+b_iy=a(x+\frac{b_i}{a_i}y)$。每个点看成一条直线$x+yz$，李超树维护即可。这里是需要注意精度的。也可以对时间分治，归并排序就可以做到一个$\log$了。
abc244g
也就是钦点了每个点经过奇数还是偶数次。随便找一条路径，然后如果一个数出现次数不对，那就让它走到下一个再回来，这样它和下一个的出现次数都$+1$，到最后一个的时候如果它不对，就让它走到任意一个邻接点，走回来，再走过去。这样dfs会生成$2n-2$条边，总共不超过$4n$。
arc137c
读错题大师。没看见最大的想了一年。
这个看起来就比较厉害。发现相当于数轴上有一些棋子，然后你可以把最右边的往左移动，当然想起staircase nim，考虑空位的变化，相当于选择一堆，拿走一个并把它分成相邻的两堆，然后把最后一堆扔掉。每一堆都可以是空的。
还是考虑staircase nim吧。但是完全不行。那还有啥方向啊。
可以尝试考虑一个胜负确定的无限集合。注意到先手可以每次把最后一堆搞成空，后手就只能拿一个，所以如果总个数是奇数那么先手赢了。如果总个数是偶数，如果最后一堆是空的，先手只能拿$1$个，此时后手就赢了。如果最后一堆是奇数个，他可以拿倒数第二堆的最后一个，这样就少了偶数个，并且此时最后一堆是空；如果最后一堆是偶数个，他可以拿最后一堆的最后一个。所以只有最后一堆是空的，并且总个数是偶数的时候后手才能赢。
arc137d
看错题了/oh
我们知道答案是各
\[\sum_{i\leq n}\binom{n-i+k-1}{k-1}a_i\]。kummer定理，注意到$\binom{n-i+k-1}{k-1}=1$当且仅当$n-i$和$k-1$的$1$位不交，法嘛塔算补集子集的xor和即可。
arc137e
让人想起 志愿者招募。
一眼网络流。但是不是很懂怎么处理这个$\min(x_j,a_j)$。
哦好像还是好处理的，只要给$i$天的入点到出点连一个费用为$d$，容量为$a_i$的，一个费用为$0$，容量为$\infty$的。然后每个人还是表示成一个环。最大费用循环流。
需要考虑背一个network simplex/oh
abc243f
大力dp，设$dp(i,j,k)$表示前$i$个，抽了$j$次，抽出了其中$k$个，那么枚举第$i$个抽到多少次，把这些次抽到乘上概率和前面的任意归并。复杂度$O(n^4)$。
abc243g
也就是$dp(1)=1,dp(i)=\sum\limits_{j^2\leq i} dp(j)$。发现这玩意只有$\log\log$层，我们展开两层好像就赢了，所以写一写
\[\sum_{i^2\leq n}\sum_{j^2\leq i}dp(j)=\sum_{j^2\leq n}dp(j)\sum_{j^2\leq i^2\leq n}i\]然后就赢了。复杂度$O(\sqrt[4]{n})$。
abc242h
考虑球说的是每个操作有一个选到的概率，然后这个分母$\leq 400$。容易想到min-max容斥，考虑对格子min-max容斥，有
\[\sum_T(-1)^{\vert T\vert}\frac{s}{f(T)}\]其中$s$是权值和，$f(T)$是包含$T$中至少一个位置的区间的权值和。然后我尝试推了推，但是困难并且没有必要，我们直接对$T$ dp，注意到每个包含$T$中至少一个位置的区间，包含的是$T$中位置的一个区间，考虑在它包含的第一个元素处统计，设$dp(i,j)$表示选了$i$，$f(T)=j$的方案数，转移枚举下一个选$k$，然后所有包含$k$而不包含$i$的区间就要加到$j$上。复杂度$O(n^3)$。
有些时候失败是因为你尝试的技术太普遍了，比如这个题是区间，如果是任意集合就不好做，如果你用在任意集合上也适用的技术，就要考虑一下是不是转化的复杂了。
abc242f
也就是每一行每一列要么没有黑车，要么没有白车。
考虑枚举哪些行，哪些列属于黑色，这些行和这些列的笛卡尔积中黑色随便放，剩下的行和剩下的列的笛卡尔积中白色随便放。但是可能有若干行/列并没放黑车，再钦点这个的数量进行容斥。复杂度$O(n^4)$。
arc136c
环形积木大赛。
找到最小值，先操作那么多次，然后就变成链了。遗憾的，第一个样例就把我卡了。
考虑为什么它是错的，一个选择最小值并操作的证明是，$\sum a_{i+1}>a_i$每次最多减少$1$，并且在最后$=0$，而选择$\min$进行操作确实让它减少$1$。但是这里它不一定减少$1$了，比如操作一圈它就并不减少。但是发现还是存在操作让它减少$1$的，因为我们只需要让操作的右端点是一个下降的左侧，而这是一个环，下降必然和上升相伴出现，所以必然也可以选一个左端点。
但是比如有且只有一个1e9的时候你就死了，考虑一下发现$\sum a_{i+1}>a_i=0$的时候也可能是所有数全都相同，我们跟最大值取一个$\max$就赢了。
arc136e
请注意是在原图，而不是$s$的导出子图中不可达。
考虑这是它的闭包上的一个可比图最大权独立集，也就是最大权反链，关于最大权反链，好像我们只知道可以网络流跑，但是边数是$n^2$的，并且增广次数很大不好优化。
考虑这个偏序是在说啥。$i\leq_G j$，当且仅当可以选择一个开头是$i$，结尾是$j$的递增序列，使得相邻两项不互素。感觉这个条件达到的不是很困难，考虑$i,j$的任意两个素因数$p,q$，如果有一个$pq$的倍数在$i+1,…,j-1$之中，那么选择它就赢了。考虑搞一个充要的条件，发现任意这个序列等价于选择一个素数序列作为不互素的部分，注意到$i$是$i$的任何素因数的倍数，那么我们选的第一个素数必然是$i$的最小素因数，这里$i$跟$0$在某种意义上很像。同理，选的最后一个素数必然是$j$的最小素因数。我们可以在中间再放一个数，但是想了想发现最多只有一个，因为放多个只会比放一个难，看起来我们必然选择$2$。所以，如果$i,j$都是奇数，我们选的必然是$i,i+\operatorname{minp}(i),j-\operatorname{minp}(j),j$(因为是奇数，所以$>i$的第一个$\operatorname{minp}(i)$的倍数必然是$i+\operatorname{minp}(i)$)，那么$i\leq_G j$当且仅当$i<j,i+\operatorname{minp}(i)\leq j-\operatorname{minp}(j)$；而偶数最多选一个。容易感觉到已经不可能比这个条件更优秀了。注意到$i+\operatorname{minp}(i)\leq j-\operatorname{minp}(j)\Rightarrow i<j$，所以只剩下一维了。
现在可以$O(n^2)$。枚举选择哪个偶数，然后算一个最大权反链，扫$i$，每个位置相当于一个区间$[i-\operatorname{minp}(i)+1,i+\operatorname{minp}(i)]$，如果两个区间不交则不合法，差分算覆盖每个位置的区间个数即可。需要进一步考虑偶数，注意到如果$i$是偶数，限制直接变成$i\leq j-\operatorname{minp}(j)$就好了，反过来也是一样的。所以就线性了。
妈的，这个题好有趣。
abc241h
大概就是什么
\[[z^m]\prod_i\frac{1-(a_iz)^{b_i+1}}{1-a_iz}\]感觉以前跟空的大概说过这个怎么做。分子分母分别乘起来，分子只有$O(n)$项，分母有$O(2^n)$项。考虑怎么求逆的远处系数，看了一眼发现它是线性递推。需要先做一次取膜，线性递推可以爆力乘法，复杂度$O(2^nn+n^2\log m)$。
一个简单一点的做法是，注意到我们知道所有根，所以可以直接部分分式掉，就不需要法法塔做取膜了。使用线性逆元，复杂度$O(2^nn)$。
abc241g
这是一个经典网络流问题。对每个人，让他剩下的比赛全赢，剩下的人不能赢更多次，然后一场比赛可以选择流到哪个人，每个比赛建一个点，每个人建一个点即可。复杂度大概是$O(n^4)$。
abc240h
怎么还有串串呢。注意到不会有长度超过$\Theta(\sqrt{n})$的串，因为每个串的长度最多是上一个$+1$。然后对这些串排个序，求lis即可。
abc240g
枚举每一维上走了多少步，如果走了$n$步，最后走出了$k$的距离，方案数是$\binom{n}{\frac{n-k}{2}}$，如果$2\not\mid n-k$则是$0$。然后就是三个东西卷起来，化一化发现是三个超几何函数卷起来提取$z^{\frac{n-x-y-z}{2}}$次项，它是d-finite的，贺个ode自动机即可。
或者，考虑两维的情况，发现范德蒙德卷积一下可以化成两个组合数的乘积，然后直接卷就行了。
abc239h
考虑直接在各$\frac{m}{x}$上随机游走，复杂度是$O(m^{\frac{3}{4}})$。感觉我是一级智障。
abc239g
模板 最小割。
arc135d
感觉很困难。我总结了一下，爆力是多项式复杂度的题都放在了abc，指数级的都放在了arc/jy
发现写不动线性规划，因为有个绝对值。
考虑一个简单想法，由于操作可逆，猜测我们并不需要做一个让答案变大的操作，那么维护每个位置$+1$之后答案是变小，变大还是不变，变小的往正里操作，变大的往负里操作，猜测复杂度是$O(n^3)$。
考虑点正常做法。考虑什么样的矩阵可以搞出来，考虑每行每列的交错和，如果都相等那么就行，证明考虑把它们都操作成只剩第一行第一列非$0$即可，否则必然不行。
那么黑白染色，我们可以让这些交错和中黑色贡献$1$，白色贡献$-1$。设行的交错和是$r$，列的交错和是$c$，注意到答案的下界是$\max(\sum\vert r_i\vert,\sum\vert c_i\vert)$。那么开始贪心，枚举一行，然后枚举一列，如果往这个位置放可以同时减少$r,c$的绝对值，则放直到一边变成$0$，否则看下一列。如果各列都是$0$了，那么剩下的行全都随便堆到同一列，容易发现必然合法。
arc135e
发现前面的数越小越好，所以这个题爆力竟是多项式复杂度。
不知道干什么的时候就打个表。发现$\frac{a_i}{i}$以大约根号的速度收敛到了某个数。继续打表猜测$\frac{a_i}{i}$的差分单调递减并且不同元素个数是$O(n^{\frac{1}{3}})$级别的，所以如果能一次跳过一段就赢了。
再打打表感觉没啥想法。我们需要考虑本质上这个序列是如何生成的。考虑为什么$\frac{a_i}{i}$会收敛到一个数，注意到如果上一个数是$k(i-1)$，那么这个数可以是$ki$，但是如果$(k(i-1),ki]$中还有$i$的倍数，就不会选$ki$了。如果$k<i$，则不可能出现这样的事情，所以它会稳定在某个数。找到最大的$t$使得$(k-t)i>k(i-1)$，也就是$t=\lfloor\frac{k-1}{i}\rfloor$，然后选择$(k-t)i$，并置新的$k$为$k-t$。刚才我们说要跳过$t$相同的一段，好像直接解出来即可。
最后的问题是如何计算$t$相同的一段的和，发现提出$t$好像就是一个和和一个平方和。复杂度是$O(n^\frac{1}{3})$，证明考虑$t$超过$n^\frac{1}{3}$的时候$i$不超过$n^\frac{1}{3}$，因为减去$n^\frac{1}{3}$个$n^\frac{1}{3}$就不到$n^\frac{1}{3}$了。
abc238f
dp一个轮廓，按第一维排序，设$dp(i,j)$表示选了$i$，一共选了$j$个人的方案数，转移枚举选的上一个轮廓上的人，然后把这一段加进去。复杂度$O(n^3)$。
abc238g
容易想到$\frac{nv}{w\log v}$之类的东西。但是三进制bitset听起来就很慢啊。
考虑平方数怎么做。好像还是不会。
注意到这东西是某种前缀和，拆成前缀，问题是判断两个前缀是否相同，维护一个hash即可。精细实现一下，复杂度$O(n\log v/\log\log v+q+v\log\log v)$。
abc237h
本质不同回文子串数量是$O(n)$。直接跑最长反链。
abc237g
直接线段树分裂合并。贺。
arc134e
考虑如何判断胜负。感觉很难做到多项式复杂度。
然而这个题是恐怖故事。不知道干什么的时候你就考虑一个胜负确定的无穷集合，发现如果不全是$1$并且有一个奇数，我们膜$2$就赢了。继续发现如果所有数膜$k$都是$0$或$t$($t=1$或$2$)，并且有数膜$k$是$t$，我们膜$k$就赢了。看起来这个是一轮之内赢的充要条件。
然后手动讨论尝试缩减状态数。如果取$k=2,4$不行，说明所有数都是$4$的倍数。如果取$k=3$不行，要么所有数都是$3$的倍数，要么同时有膜$3$余$1,2$的数。对于后者考虑膜$12$之后剩下$4,8$，模拟一下发现它是先手必败的，所以如果没有$>12$的数则先手必败，否则必胜。对于前者，只有$2^\frac{200}{12}$种情况了，可以爆搜。
感觉爆搜题真是太离奇了。
不过好像打表也可以发现这个结论啊。
abc236h
注意到有个$a_i\neq a_j$并且$n$很小，那么容斥，钦点一个等价类划分，方案数是bell数。考虑怎么让它少一点，dp，设$dp(S,T)$表示前面的集合包含了$S$，当前集合包含了$T$的答案，复杂度$O(3^nn)$。
abc236g
容易想到均摊一下，但是$L$很大，容易想到同余最短路，但是这里是恰好$L$，跟均摊结合的不是很好。
考虑还是矩阵快速幂。相当于最小瓶颈路，写个$min,+$矩乘好像就赢了啊?
arc133d
感觉很眼熟。前缀xor好像有什么性质来着。可以发现它是$4k,4k+1,4k+2,4k+3$处分别是$4k,1,4k+3,0$。那么我们要在这里面选两个数xor得到给定的数。$(4k,1),(4k,0),(4k+3,1),(4k+3,0)$都是由高位确定了的。$(1,0)$看起来就是一个等差数列求和。$(4k_1+1,4k_2+3)$需要对高位数位dp一下。
abc235h
建个kru重构树先，那么问题是选择若干子树中的叶子的方案数。直接dp，让每个点最多染一次，设$dp(u,i)$表示$u$子树操作了$i$次的方案数，复杂度$O(nk)$。
abc235f
模拟。
abc235g
容斥。
abc234h
类似于平面最近点对，按$k$同时对两维分块，那么每一块如果有$c$个点，则贡献$\Theta(c^2)$对，记$m=4\times 10^5$是答案个数，那么我们知道对于每一块有$\sum c_i^2\leq m$。然后我们爆力枚举八连通的两块统计答案。考虑复杂度，注意到假设所有块排成一排不会影响复杂度，所以复杂度是$m+\sum c_ic_{i+1}$这样的，那么基本不等式一下，我们知道$c_ic_{i+1}\leq\frac{c_i^2+c_{i+1}^2}{2}$，所以复杂度就是线性。
abc234g
两个单调栈转化成区间乘除，然后线段树优化dp。注意可能乘$0$，可以直接只对$dp$值取膜这样的。
arc132d
考虑$r$ between $s,t$说的是啥，好像这是一个经典问题，把两种字符的数量前缀和看成两维坐标，那么串就是折线，between就是在两条折线之间。dp，只有在折线上的位置有意义，复杂度线性。
对于高维的情况，也可以直接这么转化。
arc132e
感觉很奇怪。考虑每个位置可能被左边推成向右或者被右边推成向左，问题是谁最后推了它。可以想到考虑各洞触发的顺序。如果左边有$l$个洞，右边有$r$个洞，设它各种情况的概率是$f(l,r,0/1/2)$，那么如果不是两边最近的洞被触发了就啥事没有，否则它会有一半的概率被推一次，现在我们大概会$O(n^2)$。想不到吧，这个题爆力是多项式复杂度/jy
感觉一下感觉这个dp不好优化。不知道干什么的时候你就打个表，但是表也看不出啥来，不过可以感觉到和调和数之类的有点关系。考虑直接计算，我们枚举右边最后一个推过来了的洞，那么它后面所有洞都不能推过来，前面的则随意。枚举它是第几个触发的，设$g(i)$是$i$个洞都没推过来的概率，有$g(i)=\frac{2i-1}{2i}g(i-1)$可以写出……一个$n^4$的式子。感觉不是很有前途。
题解比较牛逼。直接注意到最后必然是某两个洞或者一个洞和一个边界中间没被覆盖，从它出发左边都是往左的脚印，右边都是往右的。直接枚举中间那一段，那么左右又独立了，直接dp即可。
arc132f
感觉我们需要先考虑takahashi。枚举他出了啥，算他一局都没赢的概率，但是另外两个人不独立了。容斥，钦点若干局takahashi赢了，那么两个人都得输给他，这就独立了，复杂度$O(5^k)$。
为了优化，把式子写出来。
\[ans(S)=\sum_{T}(-1)^{\vert T\vert}f(\operatorname{mask}(S,T))\]其中$\operatorname{mask}$表示取其中$T$包含的位，剩下的置零，$f(S)$表示在$S$中非零的位两个人全部输给takahashi，剩下的位随意的方案数，这个等于两个人分别输的方案数乘起来。$\operatorname{mask}(S,T)$有$4^k$种，所有的$f$可以用一个类似于法嘛塔的东西$O(4^kk)$算。
继续注意到这个看起来是一个带系数的超集和，还是法嘛塔就好了。复杂度$O(4^kk)$。
abc233h
/xia，看起来很厉害。
考虑二分，然后就矩形数点了，那么每轮一起做一次扫描线BiT就好了。复杂度$O(n\log^2 n)$。
abc233f
找到任意一棵生成树，然后不停把叶子换成正确的。如果一个连通块中初始值和目标值的集合不同则无解。
abc233g
注意到不会做两次相邻的操作。整个操作一次是一个上界，如果想做到更优，假设行数$>$列数，则必然有一行没有被操作过。dp，设$dp(i,j,k,l)$表示子矩形$[i,j]\times[k,l]$的答案，复杂度$O(n^5)$。
abc232g
从小到大排序，也就是每个点到一个前缀连$a_i+b_j$，到一个后缀连$a_i+b_j-m$，前缀和优化建图即可。
abc232h
怎么感觉见过。题面告诉你必然有解，于是考虑某种归纳，我们不停沿着边走，由于$(1,1)\neq (a,b)$，必然有一边是可以走的。最后我们会到达$(a,b)$。
需要特判只剩两行或者两列的情况。
abc231g
看起来就是求
\[\frac{1}{\binom{n+k-1}{n}}[z^k]\prod_j\sum_i(i+a_j)z^i\]直接化简，后面是
\[(1-z)^{-2n}\prod_j(a_j+(1-a_j)z)\]后者有$O(n)$项，前者是经典的，直接统计答案，复杂度$O(n^2)$。
abc231h
感觉就很网络流。考虑每行每列建一个点，每个棋子连一条边，我们要让每个点至少有一条邻边被选了，也就是上下界最小费用流。
arc131d
所有点都会往中间挤。枚举中点的位置，然后向一边扫$d$的距离并维护分数，开个堆维护每一个点到下一段的距离，每次取出最早的事件处理。复杂度$O(n\log n)$。
arc131e
怎么看怎么像挑战ramsey数，但是这里是不同色啊。显然$\bmod{3}=2$的是无解的，尝试构造一个$\bmod{3}=0$，但是好像不太会。
感觉很离奇。注意到我们让每个点到前面所有点的边的颜色都是相同的，那么就必然不会出现一个不同色$K_3$，因为这上面编号最大的点到另外两个点的颜色是相同的。然后就变成了普及组题，我们需要把$1,2,3,…,n-1$分成若干组使得每组的和相等。可以发现$n-1+n-6=n-2+n-5=n-3+n-4$，那么只要搜出$6,7,9,10$的解就赢了，搜一下发现真的有解。
agc056c
贪心放$0$，如果走到一个约束发现不满足了，就不停把上一个改成$1$。但是可能有一段已经满足了，此时再改就不行了，所以把它删掉。复杂度$O(n)$。但是有问题，比如$[1,10],[8,11]$这样的。
换个想法，考虑把$0$看成$1$，$1$看成$-1$然后拆前缀和，限制就是两个位置前缀和相等，而我们希望这条折线尽可能往上走。容易想到差分约束，但是很遗憾我们只能放$\pm 1$而不能放$0$，好像就不太行啊。但是，可以猜测它行，因为区间长度都是偶数。边权只有$01$，复杂度是线性。
或者考虑按前缀和从小到大扫。维护前缀和$=k$的位置，当一个位置上有一个限制的时候，我们就确定了它的另一侧的前缀和的值，把它们都加入。然后进行扩展，$=k$的位置希望两边都是$k+1$，除非已经确定了。复杂度是线性。注意到这个就是dij所做的。
abc230f
容易建一个$n$个状态的自动机，也就是对每个$[i,j]$使得没有$j^\prime>j$满足$s(i,j)=s(i,j^\prime)$连边$i\rightarrow j$，问题是求路径数。然后可以dp，设$dp(i)$表示走到$i$的路径数，如果后面的总和是$0$就可以贡献进答案，开个hash table对每个前缀和维护最后一个dp值即可。
abc230g
转而计算都互素的对数。
\[\sum_i\sum_{j>i}[\gcd(i,j)=1][\gcd(p_i,p_j)=1]=\sum_{d_1}\mu(d_1)\sum_{d_2}\mu(d_2)\binom{\sum\limits_{d_1\mid i,d_2\mid p_i}1}{2}\]根据排序不等式，复杂度是$\sum d^2(i)=O(n\log^3 n)$。
arc130d
dp。设$dp(u,i)$表示$u$子树，$p_u=i$，比儿子们大的方案数，小的就反过来。转移枚举$p_u$在每个子树中的排名，比它大的和小的分别插起来，设$\operatorname{size}(u)$是子树大小，看起来是
\[dp(u,i)=(i-1)!(n-i)![z^{i-1}]\prod_v\sum_jz^j\frac{1}{j!}\sum_{k\leq j}dp(v,k)\]之类的。前缀和一下然后树卷积，复杂度$O(n^2)$。
arc130e
知道$i$就知道每次给哪个加了$1$，那么剩下的约束就是它必须最小，然后就可以得到差分约束了。
考虑强行做，我们先考虑$a_{i_1}$，钦点它是$1$，然后考虑$a_{i_2}$，它有可能是$1$也有可能是$2$。比如$i$是$1,2,1,1$，那么$a_2$必须是$2$。注意到一个数连续多次出现好像很有用，如果没有一个数连续出现两次，那么所有数出现的时候就可以$=$当时的$\min$，那么考虑如果一个数某刻连续出现两次了，就把当前作为$\min$相同的数都$+1$，每个数加两次就无解了所以复杂度是线性。最后check一遍。但是再感觉一下，一个数出现两次，中间隔了一个很小的数，看起来也没啥问题。所以就，如果一个数不是$\min$了，就把当前作为$\min$的数都$+1$。
然后假了。挂在了$1,2,3,1,2,1$，这里$1$对$2$有限制，$2$对$3$有限制，$1$去更新$2$的时候，$2$没有更新$3$，所以就死了。不过至少我们可以每次更新都重新跑一遍，复杂度$O(n^2)$。
考虑它是个什么结构。考虑按照$\min$把时间分成若干段，那么每一段里面一个数只会出现一次，并且在这一段出现了下一段必然也出现，除非下一段是最后一段。目标就是让每个数尽可能出现在靠前的段。
考虑刚才的贪心在干啥，我们遇到一个数就尝试把它放进当前这一段，如果这一段已经有这个数就新开一段，如果新开一段的时候，这段里面一个数没有出现过，则向前找到它的所有出现并抬升一段。于是现在我们已经理解了刚才说的一串限制的情况。实现就开一堆deque就行了。
虽然不会，但是没太懂为什么这个题3200啊。
abc229g
枚举中点的位置，然后让两边往中间凑，二分一下，前缀和算算就好了。是不是可以双指针。
arc129d
考虑设$1,2$分别被操作了$x,y$次，那么$3$的操作次数就确定了，因为它必须把$2$搞成$0$。然后就得到$n$个限制，每个限制对应一个操作次数非负，答案是一个一次函数，随机增量即可。复杂度$O(n)$。
这个看着不像atc题，考虑差分，设差分是$d$，我们知道这个操作相当于$d_i+=1,d_{i+1}-=1$，注意到如果总和不为$0$必然无解，否则差分都为$0$等价于原序列都为$0$。然后只需要设$1$被操作了$x$次，得到一个一维线性规划。或者对上面那个东西建出的线性规划进行观察应该可以得到同样的结果。
abc228f
首先把$h_2$对$h_1$取$\min$，$w_2$同理。然后问题变成选择一个$h_1\times w_1$的矩形，使得总和减去其中和最大的$h_2\times w_2$子矩形的和最小。
那么我们先枚举一个，然后考虑怎么求这个和。求出每个$h_2\times w_2$子矩形的和，那么问题变成求若干个矩形$\min$，对第一维单调队列，然后对第二维单调队列即可。复杂度$O(hw)$。
abc228g
这是一个nfa。直接猜测状态数很少，开个int128当状态即可。看一眼题解发现状态数是$2^h+2^w$。是不是可以dfa最小化一下做1e18。
abc228h
也就是把值域分成了若干段，每一段都贴到其中最大的上面去，看起来是经典斜率优化问题。
abc227e
dp，设$dp(i,j,k,l)$表示用了$i,j,k$个K，E，Y，逆序对数是$l$的方案数，然后就可以算对逆序对数的贡献了。复杂度$O(n^5)$。
abc227f
经典的。枚举第$k$大$x$，建一个新图，$w>x$的边代价是$w-x$，否则是$0$，然后跑最短路$d$，用$kx+d$更新答案。注意到如果$x$比真实的第$k$大大了或者小了，答案都会被算大，所以就赢了。复杂度$O(n^4)$。
abc227g
$\frac{n^\underline{k}}{k!}$。区间埃筛即可，复杂度$O(k\log\log n+\sqrt{n})$。
abc226f
看了一眼，就是各环长的$\operatorname{lcm}$。感觉好像谁给我看过这个题。
搜个分拆数先，然后拆成这样的方案数就是随便排再除各环长再除各环长出现次数的阶乘。然后算就行了。
也可以直接dp。
abc226g
讨论你妈，直接simplex得了。
或者看看我的提交 https://atcoder.jp/contests/abc226/submissions/35830543 。大概是，人$i$匹配物品$i$显然优，并且如果不存在人$i-1,…,j$，人$i$匹配物品$j$也是优的。所以不停reduce保证这个性质即可。
abc226h
如果$l_i=0,r_i=1$，那么枚举这个值，然后有一个值$=$它，$k-1$个$>$它，$n-k$个$<$它，然后就可以看到beta积分了。或者你也可以直接猜测它是$1-\frac{k}{n+1}$。
考虑一般的情况，直接枚举这个值$x$和它的位置，剩下的数可能比它小或者比它大，我们限制大的有恰好$k-1$个，那么每个贡献一个$\frac{(r-x)z+x-l}{r-l}$这样的东西，最后我们要提取$[z^{k-1}]$。注意到$x,z$的次数都很小，直接把每一段分开做，积就行了。
agc055b
难道是经典题吗。给每个位置加上$i\bmod{3}$，那么操作变成把XXX变成YYY。注意到可以任意移动XXX的位置，比如XXXY->YYYY->YXXX，所以我们不停删除连续三个相同字符，猜测如果剩下的部分相等那么有解，否则无解。
或者直接考虑，注意到可以任意移动ABC的位置，比如ABCB->BCAB->BABC这样的，所以我们不停删除连续三个连续字符。
agc055c
设$p$的lis长度是$l$，那么各$a_i$要么是$l-1$要么是$l$，取决于它是否在所有lis中。设有$k$个位置是$l-1$。
考虑如何判定一个$a$是否可能出现。把在所有lis中的数拿出来，这把剩下的数分成若干段，这些数必须不能在所有lis中。
为了让lis足够长我们需要放一些数，感觉一下每次可以放$x+1,x$这样的东西，它会给lis贡献$1$，于是一个长$l$的区间可以贡献$1,…,\lfloor\frac{l}{2}\rfloor$个。
为了让lis足够短，我们可能希望它贡献$0$个，比如让lis选最小的若干个数，剩下的选最大的若干个数。但是这个构造会有问题，最后一段会接到lis中最后一个位置的后面使得lis长度变长，或者如果最后一个位置就是$n$，倒数第二段中任何一个数都可能代替最后一个。注意到如果选最小的若干个数就，后面的问题解决了，但是前面出现了问题。于是我们选择最小的若干个数放在后若干个间隔，最大的若干个数放在前若干个间隔，这就赢了。所以lis的长度可以在$k,…,k+\sum\lfloor\frac{l}{2}\rfloor$中。
dp，设$dp(i,j,0/1)$表示前$i$个，$\sum\lfloor\frac{l}{2}\rfloor=j$，当前选的空段的奇偶性是$0/1$的方案数，转移考虑这一个选啥，复杂度$O(n^2)$。据说可以直接拿组合数算。
好像需要特判$l=2$的情况。
abc225f
dp。问题是in any order，所以我们先按字典序从小到大排，然后就必然是按顺序选了。复杂度$O(n^4)$。
然后这个当然是不对的，在一个是另一个的前缀的时候就假了。考虑按照，如果$ab<ba$，则$a$在前面，$ab=ba$则短的在前面的顺序排，那么经典的，我们知道这等价于$a^\infty<b^\infty$，所以它是全序。
dp看起来也是不对的，因为如果前面的长度不同，往后接一个的效果也不同，所以需要倒着dp变成往前接。
abc225g
考虑网络流。一个位置要被两个方向分别选一次才能贡献，考虑最小割，注意到权值都是正的，我们把它改成，选择一些格子，如果$(i,j)$选了，$(i+1,j+1)$没选，则付出$c$，$(i+1,j-1)$没选，则付出$c$；如果$(i,j)$不选，付出$a_{i,j}$。最小割，连源表示选了，汇表示没选，然后就直接结束了。
abc225h
容易$n^2$ dp。再想想，发现我们是要用若干个间隔拼出一个间隔，那么对于长$k$的间隔(左闭右开)，选了$i$个间隔($i-1$个人)的方案的权值和是$[z^k]\left(\frac{z}{(1-z)^2}\right)^i=\binom{k+i-1}{2i-1}$，分治法法塔即可。
abc224g
注意到我们必然在某个足够大的值开始不停$+1$，剩下的部分都remake了。枚举这个位置，设为$p$，那么这一过程可以认为是先remake若干次直到落入$[p,t]$，然后不停$+1$。前者的期望是$b\frac{n}{t-p+1}$，后者是$a\frac{t-p}{2}$，求导并检查零点附近的两个整点即可，或者直接三分。
abc224h
看起来又是网络流。中间的边有下界就好了。
abc223g
直接换根。
abc223h
看起来是区间线性基之类的东西。
考虑一个左端点往右只有$\log v$种不同的线性基，那么就开$\log$个，从右往左扫，插入一个数的时候，依次尝试插入每个线性基，如果到某一个插不进去了，那么后面的肯定都插不进去。复杂度$O(n\log^2 v+q\log v)$。
考虑优化，感觉我比较智障，直接维护编号最小的线性基即可。复杂度$O((n+q)\log v)$。
arc128d
注意到相邻相同的是必然不可能被删的。考虑什么样的子序列合法，也就是考虑这个子序列相邻两个数之间能不能删空。发现只有两边的数有用，所以我们至少会多项式复杂度了。
猜测如果一开始没有相邻相同的，那么必然可以删空。但是很遗憾不是这样的，比如$(0)101010(1)$就不行，当然括号表示两边我们选的那个子序列中的数。猜测如果区间里(包括两边)有三种数，那么必然可以。设三种数分别是$0,1,2$，其中左端点左边是$0$，右端点右边是$1$，剩下的是$2$。注意到如果有$abababab…$这样的段，它必然终结于一个$c$，所以我们总可以把中间删成任意相邻三个互不相同的，不停删除最多的字符然后使用这个就好了。
需要特判很短的情况。使用前缀和优化，复杂度$O(n)$。
arc128e
当然贪心，于是考虑何时有解，发现好像还是一个出现太多次的数会带来问题。猜测如果没有一个数出现次数超过$\left\lceil\frac{\sum a_i}{k}\right\rceil$则有解，构造考虑直接放合法的中出现次数最多的，但是这个不太对，我们还需要限制$=\left\lceil\frac{\sum a_i}{k}\right\rceil$的不超过$\sum a_i\bmod{k}$个，然后每$k$个一段直接构造就行了。于是模拟，直接开个桶维护出现次数即可。
没懂为什么有3000。
abc222g
$l$个$2$就是$\frac{2(10^{l+1}-1)}{9}$。$k\mid\frac{2(10^{l+1}-1)}{9}$，也就是$\frac{9}{2}k\mid 10^{l+1}-1$，也就是$10^{l+1}\equiv 1\pmod{\frac{9}{2}k}$。如果$10$和$\frac{9}{2}k$不互素，必然无解，否则bsgs即可。
或者欧拉定理。
abc221f
注意到任意两个点距离都是$d$的点集，其虚树必然是一个菊花，枚举这个中心直接统计即可。如果$d$是奇数，中心出现在边上。
问题是怎么统计。长剖预处理子树的信息，主要问题是子树外的信息，递归重儿子的时候复杂度很对，递归轻儿子的时候只需要保留重儿子相同长度的信息，所以还是很对。复杂度线性。
等会啊，$d$是直径啊。那好像就比较简单，注意到长$d$的链都经过整棵树的center，于是虚树的中心总是必然是它，以它为根跑每个距离的点数即可。
abc221g
拉。转$45$度之后两维是独立的，或者说这个是${(0,2d),(0,-2d),(2d,0),(-2d,0)}={(d,d),(-d,-d)}\times{(d,-d),(-d,d)}$，前者只影响$a+b$，后者只影响$a-b$。于是对两边分别dp，bitset一下，复杂度$O(\frac{n^2v}{w})$。但是bitset怎么构造方案?记一个$g(i)$表示如果加入$t$的时候$dp(i)$从$0$变成了$1$，则$g(i)=t$，那么求出$g$就可以知道怎么转移的了。可以直接存下每一轮的$dp$，空间是$O(n^2v)$个bit。考虑如何做到$O(nv)$，每插入一个数，把当前的$dp$和上一轮的$dp$ xor起来并不停find_next找到新出现的位即可。这里xor等价于取反之后and，可能会让你手写的快一点。
abc221h
也就是把$n$分拆成$k$部分，每个数出现次数不超过$m$。看起来就是$[z^k]\prod\limits_i\frac{1-z^{i(m+1)}}{1-z^i}$。上下都只需要保留$n$次。
abc220g
求出每条直线，然后考虑一个斜率作为底，两个底可以拼成等腰梯形当且仅当不在同一条直线上并且中点在这个斜率上的投影相同，对每个中点维护最大和次大的权值和即可。一共有$O(n^2)$个中点。
abc220h
那么没有监控的就是两端都没装摄像头的。经典的，有一个牛逼方法求所有导出子图的 $-1$的边数次 的和。
考虑找一条边$(u,v)$，先假设$u,v$都没有自环，考虑它对剩下的部分的贡献。对于剩下的部分的一个方案，设单独再选$u,v$的贡献是$x,y$，那么选$uv$是$-xy$，不选当然是$1$，那么总共是$x+y-xy+1$。如果$x=1,y=1$它是$2$，$x=1,y=-1$它是$2$，$x=-1,y=-1$它是$-2$。所以乘个$2$先。
那么也就是至少一边邻接偶数个点则贡献是$1$，否则是$-1$。考虑构造一个这个东西，容易想起来偶数乘任何数都是偶数，所以我们在剩下的点中，$u$的邻接点和$v$的邻接点连成完全二分图(如果一个点同时邻接$u,v$，则连一个自环)，那么选了$c_u,c_v$个$u,v$的邻接点，贡献就带一个$(-1)^{c_uc_v}$，于是可以把$u,v$删掉了。显然删掉一对重边不影响答案。
考虑有自环的情况，我们让$x,y$仍然是不考虑自环的贡献，那么如果$u$有自环而$v$没有，则贡献$-x+y+xy+1$，如果$x=1,y=1$它是$2$，$x=1,y=-1$它是$-2$，$x=-1,y=1$它是$2$，$x=-1,y=-1$它是$2$，也就是$c_u$是奇数而$c_v$是偶数的时候贡献$-1$，别的时候都是$1$。还是连成完全二分图，此时不对的贡献在$x=1,y=-1$和$x=-1,y=-1$，于是它可以看成$(-1)^{c_uc_v+c_v}$，我们给$v$的邻接点都连一个自环，就把它调成对的了。
考虑$u,v$都有自环，此时贡献是$-x-y-xy+1$，$x=1,y=1$它是$-2$，$x=1,y=-1$它是$2$，$x=-1,y=-1$它是$2$。可以感觉到应该把贡献写为$(-1)^{(c_u+1)(c_v+1)}$，那么还是给$u,v$的邻接点都连一个自环，如果一个点同时是$u,v$的邻接点则不连，这样我们得到$(-1)^{c_uc_v+c_u+c_v}$，再整个取反一下即可。
复杂度$O(\frac{n^3}{w})$。
arc127c
每个去掉前导零之后的长度都是有序的，问题是把它们归并起来。考虑对于一个长$k$的$s$，长$l$的串有多少比$s$小，那么第一位是不自由的，后面如果$l\geq k$那么贡献是$s_{2,…,k}-1$，否则是$s_{2,…,l}$。考虑从前往后确定每一位，每填一位我们会让$k:=k+1$，此时第一种贡献会$+1$，所以我们应该维护排名比$x$小的串中排名最大的那个，$+1$是连续的所以看起来很正确。然后确定一位之后贡献会增加一些，这里增加不超过$\log$所以可以压位做到$O(1)$，复杂度$O(n)$。
arc127d
感觉很厉害。考虑从高到低比较$a_i\operatorname{xor}a_j,b_i\operatorname{xor}b_j$，也就是我们每次往后插入一位这样的。考虑$a_i\operatorname{xor}a_j=b_i\operatorname{xor}b_j$就是$a_i\operatorname{xor}b_i=a_j\operatorname{xor}b_j$，也就是说在前若干位$a_i\operatorname{xor}a_j,b_i\operatorname{xor}b_j$相同是一个等价关系，那么我们每次将一个等价类划分成两个，就要计算这两部分之间的贡献。考虑$a_i,a_j,b_i,b_j$这一位的值，$a_i\operatorname{xor}a_j>b_i\operatorname{xor}b_j$就是$b_i=b_j$，也就是$a_i,a_j$相同的贡献$b_i\operatorname{xor}b_j$，$b_i,b_j$相同的贡献$a_i\operatorname{xor}a_j$。直接一边开四个桶塞进去然后算，剩下的问题是算一个集合中选两个数的xor和之和。注意到每一位是独立的，直接做即可。复杂度，相当于拿着各$a_i\operatorname{xor}b_i$在trie上走，那么trie上的每一层会付出$O(n\log v)$的代价，总复杂度$O(n\log^2 v)$。
arc127e
考虑如何判定一个集合是否可行。不在其中的数必须被弹掉，那么考虑把不在其中的数放在左边若干个位置，在其中的放在右边若干个位置，分别从小到大排，感性理解一下就是小的数难以被弹掉，大的数容易被弹掉。集合的大小是确定的$a-b$，所以从小到大考虑每个数的话，如果知道两边有多少，那么每个数的位置都是确定的。
注意到左边最后剩下哪些排名的数是确定的，可以模拟一遍求出。那么每当我们在右边扫到一个pop，则要求左边剩下的最大的数比右边最大的数大。考虑倒着扫右边，设$dp(i,j)$表示右边从右往左放了$i$个数，第$i$个是$j$的方案数，转移枚举下一个放$k$，这中间有一段pop，有多少个可以算出来，它们会尝试匹配左边留下来的数，如果$>k$的部分还没匹配完这些pop就不行。显然合法的$k$是一个后缀，前缀和优化即可，复杂度$O(n^2)$。
看起来我比较智障啊。考虑要把尽可能大的数留下来，我们按$1,…,n$的顺序push，然后得到一个序列。猜测所有每一位都比这个序列小的序列都能留下来，证明考虑在这些留下来了的位置从小到大放我们想要的序列，剩下的位置放弹掉了的东西，每次pop掉的数只会更大。然后直接dp即可，复杂度$O(n^2)$。
arc126d
考虑选出这个子序列，然后把它们都换到某个位置去。设$dp(i,j,S)$表示前$i$个数，已经选了$S$中的数，要都换到$j,…,j+k-1$去的最小代价，复杂度$O(2^kn^2)$。考虑优化，我们必然换到中位数处，所以就$O(2^kn)$了。
arc126e
考虑最优策略是啥，首先最后所有数都会变成平均数，猜测它是所有数到平均数的距离和，减去其中最小的那个。但是这个很假。
结论是，答案是所有无序对差的绝对值之和的一半。知道了这个就直接平衡树维护即可。考虑证明，首先它显然是一个上界，因为每次操作不会让答案增加超过我们减少的部分。考虑什么样的操作是紧的，注意到操作最小值和严格次小值就是紧的，所以