D1
127题。
A. dare
bzoj3305。
对于所有长$2n$的合法括号序列，求 每个右括号左边的前缀和的乘积 的和。$n\leq 10^7$。
$dp(i,j)=dp(i-1,j-1)+(j+1)dp(i-1,j+1),dp(0,0)=1$，答案就是$dp(2n,0)$。
也就是$F_i=zF_{i-1}+F_{i-1}^\prime$考虑两边乘$e^\frac{z^2}{2}$凑一下，然后就可以知道答案是$z^0^{(2n)}$。
B. read
图，求环长为$3$的生成基环树个数。$n\leq 300$。
线性代数在oi中的应用/cf
答案就是枚举一个三元环，把它缩成一个点，然后矩阵树。矩阵树的时候我们可以总是删掉这个缩成的点，所以相当于删三行三列。
$n^5$是比较简单的。我们可以$O(n^3)$求出一个矩阵的所有余子式，使用伴随矩阵的结论$A^\ast=\det(A)A^{-1}$即可，所以可以枚举两个点求出所有第三个点的答案。
为了快一点，一个结论是 https://www.luogu.com.cn/blog/tiw-air-oao/yi-ci-fou-wan-zheng-di-chang-shi ，所以我们把计算删很少的余子式转化成计算很小的子式。127的打洞证明是，考虑删掉的是右下角的情况，考虑矩阵
\[T=\begin{bmatrix} A&B\\ C&D \end{bmatrix} = \begin{bmatrix} I&0\\ -A^{-1}C&I \end{bmatrix} \begin{bmatrix} A&B\\ 0&D-BA^{-1}C \end{bmatrix}\]，那么我们知道它的行列式是$\det(A)\det(D-BA^{-1}C)$。考虑它的逆
\[T^{-1}=\begin{bmatrix} A&B\\ 0&D-BA^{-1}C \end{bmatrix}^{-1} \begin{bmatrix} I&0\\ A^{-1}C&I \end{bmatrix}\]，也就是说$D-BA^{-1}C$就是$T^{-1}$的右下角。把我们所要的余子式换到右下角就得到这个式子了。
但是这里有问题，kirchhoff矩阵不可逆，不过好消息是它删去一行一列就可逆了，所以我们考虑怎么删去一行一列求逆。
据说这个问题比较经典!考虑怎么删去一行，我们把这一行都改成$1$，设这一行是$v$，设$u$是只在这一行有一个$1$的矩阵，那么就是要减去$uv^T$。现在我们已经知道$\frac{1}{A}$，要求$\frac{1}{A-uv^T}$。我们尝试让$uv^T$变成$v^Tu$。提一个$A$，得到$\frac{1}{I-A^{-1}uv^T}\cdot\frac{1}{A}$，注意到$\frac{1}{I-A^{-1}uv^T}=\sum\limits_{i=0}^\infty (A^{-1}uv^T)^i$，而幂看起来是$A^{-1}uv^TA^{-1}uv^T…$这样的，注意到$v^TA^{-1}u$也是$1\times 1$的，所以我们把它改写为$I+A^{-1}u\sum\limits_{i=1}^\infty (v^TA^{-1}u)v^T$，乘上$A^{-1}$也可以$O(n^2)$计算。所以枚举删去哪行，剩下的就可逆了，使用前面的结论即可。
可以做四元环，但是我不知道。
C. need
集训队胡策23 R3 B. 举办乘凉州喵，举办乘凉州谢谢喵，但是保证链是祖先-后代链，且答案只算子树内的。
有一个简单top tree做法，但是top tree不简单。不过这里只是子树内的，大家都知道轻子树大小和是$n\log n$级别，所以就重链剖分，轻子树的部分预处理一个二维前缀和，这里离线扫链，那么每次更新的是一个前缀的前缀和，所以复杂度很对。但是跳轻边的时候需要加上重子树减去轻子树，这里可以用一个长剖解决，也就是计算子树内距离$\leq k$的点，相当于用总点数减去距离为$k+1$的点的子树大小之和。复杂度$O(n\log n)$。
所以胡策那个题也可以不用静态top tree做到$O(n\log n)$啦，虽然需要 点分 重剖 长剖。能差分的信息的话还是很好的。等着出个$\max$之类的。
但是静态top tree真有这么不堪吗。是不是也许其实不难写!
数学选讲/chandou
需要注意 集训队胡策22 和 21集训队胡策 是一样的，一个修饰比赛年份，一个修饰集训队年份。
集训队胡策22 R1 A. 愚蠢的在线法官
考虑我们让它独立一点，$l\in\mathrm{anc}(\mathrm{lca}(u,v))=[l\in\mathrm{anc}(u)][l\in\mathrm{anc}(v)]$。所以先对树做个差分得到新的权值$w^\prime$，然后我们就知道$w(\mathrm{lca}(u,v))=\sum_l w^\prime(l)[l\in\mathrm{anc}(u)][l\in\mathrm{anc}(v)]$。
然后考虑把所有点按dfn排，那么一个点的效果就是给子树自己和自己的笛卡尔积加了它的权值。
二维差分，可以注意到这样得到的是一个基尔霍夫矩阵，要求它的生成树数量。
这个图是广义串并联图。127表示容易数生成树个数的图基本都是广义串并联图，因为串并联就是简单的可以合并生成树个数的操作。
集训队胡策22 匹配计数
发现可以用#csp做到$O(n^6)$之类的，反正过不了捏。
考虑相交对数是啥，发现对于相邻两个点，如果它们都有匹配，我们交换它们，必然改变相交对数的奇偶性。先把一个颜色交换到一起，然后对于同一个颜色内部的完美匹配，找到前两个不相邻匹配的点，交换它们就得到一个双射，只有$2i-1,2i$匹配是不能这么双射的。也就是说相交数量的奇偶性等于所有匹配了的数，每个数的颜色拿出来算逆序对数的奇偶性。
那么给逆序对连边，几乎就是算有多少导出子图边数是偶数了，但是还需要限制每个颜色选偶数个点，如果直接上#csp的话直接就做掉了，不过如果只会算偶数条边生成子图个数，也可以给每个颜色加一个完全点，对于一个选奇数个的方案这个点就可以选择贡献$1$还是$-1$把它的贡献消掉。
初等，相似，合同
初等行变换任意复合的结果是左乘一个矩阵。列变换是右乘一个。
相似变换是$PAP^{-1}$。合同变换是$PAP^T$。
nowcoder mutc 22 R3 I
crn表示膜数$P$比较smooth并且满足$\mu(P)=1$。那不就是明示小模数crt吗!
枚举这样的位置的个数，剩下的需要是错排，也就是
\[\sum_{i=0}^n\binom{n}{i}D_{n-i}i^k\]我们知道错排的egf是$e^{-\ln(1-z)-z}$，这里还有一个$\sum \frac{i^k}{i!}z^i$，看起来$[z^i]ze^z=\frac{iz^i}{i!}$，所以它就是$(Dz)^ke^z$。
展开成斯特林数，大概是
\[[z^n]\sum_{i=0}^k{k\brace i}z^i\frac{1}{1-z}=\sum_{i=0}^k{k\brace i}[i\leq n]\]如果$k\leq n$，答案就是bell数$B_k$。有个结论 touchard同余 是$B_k=B_{k-p}+B_{k-p+1}\pmod{p}$，线性递推就是$O(p^2\log k)$。
如果$k>n$，我们还需要求第二类斯特林数行后缀，第二类斯特林数行的egf是$z^\underline{k}$，反射得到$\prod\limits_i(1-iz)$。取个$\ln$之后可以发现可以$O((k-n)^2)$，但是好像有一个简单的dp做法。
cf708 E. Student’s Camp
容易想到爆力dp，也就是有交可以转移这样的，但是感觉不太能优化啊。
考虑$v-e=1$，那么我们就是找一个位置走下去，减去找两个位置都可以走下去。那么现在只需要对所有这样的走法进行dp，考虑只有一个位置的情况，从$i$转移到$j$只需要计算包含$[i,j]$的概率，它是$\binom{i+k-1}{k}\binom{n-j+k}{k}$除某个常数这样的，但是我不知道。
cf698 F. Coprime Permutation
看起来是说确定了一些映射之后有多少种自同构。
素因数集合相同的数是等价的。
cf848 E. Days of Floral Colours
直接随便找个位置断开，然后大力dp即可。
cf868 G. EI Toll Caves
越访问，有东西的概率越小，所以我们总是贪心地访问最大的。
转化成枚举一个状态计算走到它的概率的和，如果进行了$t$轮，那么有$tk\bmod{n}$个$\lfloor\frac{tk}{n}\rfloor+1$和$tk\operatorname{module}n$个$\lfloor\frac{tk}{n}\rfloor$，类欧算到$t=n$，然后就可以$\frac{1}{1-x}$之类的东西算啦。
D2
A. shk
给数$a$和素数$k,p$，保证$k\not\mid p-1$，求解$x^k=a\pmod{p}$。$a,k,p\leq 10^9$。
求$a^\frac{1}{k}$，这里求逆膜$p-1$。
可以用快速幂求逆，因为$k$是素数，而求逆和求解$kx+(p-1)y=1$是等价的。
B. shik
给$n$个长$n$的01向量，对每一个有序对求前者是否被后者包含。$n\leq 5000$。
几乎是 模板 传递闭包，据说可以归约但我不会。复杂度$O(\frac{n^3}{w\log n})$，四毛子即可。
我他妈居然手写一个bitset。不过因此比std稍快一点!
C. xuke
平面，有一些矩形被染成黑色，保证矩形没有交。你要从上往下走，每次可以往左下，下，右下走一步，如果往下走并且走到一个黑点则获得$1$的得分，求最大得分。$n\leq 10^5,v\leq 10^9$。
注意到如果下面是黑色，那么往下走必然不劣。
考虑爆力dp过程中发生了什么，经典的，dp值分成了若干段，段之间的分界线会往小的一侧移动(因为小的对大的取$\max$)，开个堆维护分界线相撞的时间即可。进入一个矩形的时候，打个标记表示这一段固定了，离开时再做区间加，反正大力平衡树可以维护。咍咍。
杂题选讲
据说是意大利国家队选拔赛 ?. ?
给一个01串的长度，每次可以问一个串是不是它的子串，在$n+\lg n+O(1)$次查询内求出它。
直接问就是$2n$。
注意到不是$0$就是$1$，除非超了。所以可以每隔根号次问一次是不是超了，做到$n+O(\sqrt{n})$。
考虑每次随机问，如果连续$\log$次都不对，则检查是否超了。这是$n+O(\log n)$。
更好的做法是，二分最长的连续$1$长度$l$，然后从这个连续$1$段开始问，每次都问$0$，如果连续得到$l+1$个$1$，说明必然超了，然后从这里重新往右问$1$即可。这就赢了。
bzoj4634 转啊转啊转/gcj wf 12 D2. Twirling Towards Freedom 加强版
$n\leq 5\times 10^5,m\leq 10^{18}$。
感觉我对旋转没有感觉。用复数来描述旋转，$z$绕$a_i$旋转，大概是$z\leftarrow i(z-a_i)+a_i=iz+(1-i)a_i$。它是各$(1-i)a_i$的线性组合，每一次选哪个的贡献是确定的，而贡献的系数只有$i,-1,-i,1$四种。
为了最大化$x^2+y^2$，它必然在凸包上，所以枚举一条直线去切即可。只有乘$i,-1,-i,1$的投影的$\max$有用，而转的过程中它们都只会改变$n$次，求个凸包得到每个何时是$\max$即可。
ipsc2016 ?/bzoj4633 道路魔法
每条边在每个距离拆出一条边，simplex。
1st ucup stage 15 hangzhou M. Stage Clear
大家都做过树的。
127表示邻项交换排序一般是，有一个合并$+$和一个看哪边更优的$<$，按$a+b<b+a$排序。在序列上我们只需要考虑形如$a+b$这样的东西之间的大小关系，而在树上还需要考虑子树的答案之间的比较。
考虑枚举我们走的生成树，这有多少种呢，首先生成树个数不超过$\prod\mathrm{deg}$，因为是容斥这个界大概还是不错的，琴一下也就不超过$(\frac{2m}{n})^{n}$，所以跑的看起来很快吧!
cf1427 G. One Billion Shades of Grey
考虑怎么描述绝对值。拆成$\max(a-b,0)+\max(b-a,0)$，这个就是费用流对偶的形式啦。
让我们复习一下费用流对偶。带超额流的最大费用循环流是
\[\max\sum_{i,j}w_{i,j}f_{i,j}\\ f_{i,j}\leq c_{i,j}\\ \sum_j(f_{j,i}-f_{i,j})=e_i\]第一种限制对偶成$g_{i,j}$，第二种限制对偶成$x_i$(相等体现在没有非负限制)，那么其对偶是
\[\min\sum_{i,j}c_{i,j}g_{i,j}+\sum_ie_ix_i\\ x_j-x_i+g_{i,j}\geq w_{i,j}\]那么可以注意到每个$g$只在一个约束中出现，而且各$c$非负，所以在固定$x$之后$g_{i,j}$必然取最小值$\max(x_i-x_j+w_{i,j},0)$，而这个限制必然可以被满足了，那么答案就是
\[\min\sum_{i,j}c_{i,j}\max(x_i-x_j+w_{i,j},0)+\sum_ie_ix_i\]纠是这样。
cf949 F. Astronomy
枚举第一个点和哪个点配对，枚举第二个点和哪个点配对，如果第一个和第二个配对则枚举第三个对吧，然后爆力check，复杂度$O(n^3\log n)$。
注意到所有点对只有$O(n^2)$条直线，至少被$n$条经过的点数感觉上很少，事实是确实是这样，我们只需要按随机顺序检查每个点就过了。
cf1110 H. Modest Substrings
造个dfa算匹配长度对吧，那么我们需要把所有数字串插进一个trie然后建acam，但是它状态数是$10^{800}$，不过我们可以猜测其实只有$O(len\Sigma)$对吧，所以把区间拆到10进制trie上，每个子树直接每次加一位来算，子树间爆力合并，复杂度$O(len^3\Sigma^2)$之类的，但是最小化够快，所以非常好对吧!
直接考虑trie上一棵满的子树是什么效果，它可以一直匹配直到长度不够，长度不够的时候它可以到达根的fail的子树中任意一个点，
线性点分治
agc009 D. Uninity。不过谁闲着没事写这个（
卡常
__builtin_expect。
稀疏矩阵消元
每次拿出size最小的行去消其它行。
压位trie
比链表快。
链表用于回滚莫队，而压位trie可以普通莫队时优势明显。
记得循环展开。可以在不同层使用不同的radix减小常数，比如1e6用$32^4$，1e5用$32\times 64^2$。
D3
A. count
初始全$0$的长$n$序列，每次在所有长$2$且全$0$的区间中等概率随机一个全改成$1$，求位置$k$最后是$1$的概率。$n,k\leq 10^7$，1e5组数据。
考虑转化成给所有长$2$区间随一个排列，然后按这个顺序尝试操作每个区间。这样正确是因为它和原问题都等价于每次随机一个长$2$区间，如果全$0$则操作。
然后就比较简单了，我们计算$(k-1,k),(k,k+1)$都没有被操作的概率，这俩看起来是独立的，所以两边分别算一下即可。$(1,2)$没有被操作，当且仅当$(2,3)$排在它之前且被操作，也就是$(2,3)$排在它和$(3,4)$之前或$(2,3)$排在$(3,4)$之后，而$(4,5)$被操作。枚举这样的极长段长度算排列个数即可，可以前缀和优化到$O(1)$。
B. team
二分图，把点集划分成若干单点，$P_2,P_3$，最小化单点个数，在此基础上最小化$P_3$个数。$n,m\leq 2\times 10^5$。
一眼网络流，因为判断能不能单点和$P_3$都是$0$等价于判定完美匹配。
考虑直接让每个点可以流$2$，跑匹配。这样看起来确实可以得到这样的东西。
最小化单点个数，我们可以让每个点第一条边费用是$1$，第二条边费用是$0$，跑最大费用流，这样会倾向于先每个点流到一条链上。最小化$P_3$个数，可以第一条边是$\infty$，第二条边是$-1$这样的。
注意到源汇边不会退流，所以每个点可能的最短路长度一共只有$\infty,-1,\infty-1,2\infty$之类的，多路增广费用流即可。
C. geometry
简单多边形，每次给一条线段，求它和多边形的边有没有交。$n,q\leq 10^5$。
考虑直线怎么做，线段只需要加个线段树。发现直线也不会做!
把多边形也拆到线段树上，我们每个点处理覆盖整个区间的边对包含于这个区间的查询线段的贡献，以及包含于这个区间的边对覆盖整个区间的查询线段的贡献，这样每条线只会出现$\log$次。
第一个是简单的，因为是简单多边形，这些直线是不相交的，直接排序即可。
第二个看起来比较困难。考虑这个$x$的区间$[l,r]$把多边形切成若干区域，每个区域至少接在一边上。对$x=l,x=r$分别求出上面哪些区间在多边形内部，如果在这上面就相交了，可以直接二分出来。如果不交，还可能在中间和某个区域相交，有一个结论，设查询直线和边界相交于$(l,y_l),(r,y_r)$，那么查询直线和某个区域相交，当且仅当它和
-
和左边界相接，且相接部分的$y>y_l$的部分
-
和左边界相接，且相接部分的$y<y_l$的部分
-
和右边界相接，且相接部分的$y>y_r$的部分
-
和右边界相接，且相接部分的$y<y_r$的部分
分别的凸包之一相交。因为是直线嘛!
只考虑第一部分，也就是左上，我们需要维护一个右下凸壳，看起来需要平衡树，但是好消息是我们每次加入的是一个和左边相接的东西，所以新的凸包必然是新加入部分的凸包的左半边拼上原来凸包的右半边。只需要求出每部分的凸包，然后用栈维护。复杂度$O(n\log v\log n)$。
博弈。
ctt 2016 D1 ?. Alice 和 Bob 又在玩游戏
剩下的必然是若干子树，可以直接dp sg值。但是怎么dp呢?
直接维护操作每个点得到的局面的sg值，那么需要支持全局xor一个数和合并，trie即可。
The Mock Turtle Theorem
可以把$n$变成$<n$的至多$k$个数。
$k=2$的时候是$2n+[\mathrm{popcnt}(n)\text{ is even}]$。$k$更大是open的。
$k=\infty$的时候是$2^n$。
$k=\infty$且要求连续的时候是$\mathrm{lowbit}$。
Turnips
$k=2$，要求选的三个距离相等。结论是$n$的三进制表示中最低的$2$在$t$位，则sg值是第$t$个$\mathrm{popcnt}$为奇数的数，如果没有$2$则是$0$。
Lasker’s Nim
可以选择把一堆分成两堆。
Wythoff’s Game
有点恐怖。sg值是open的。
anti-nim
不能操作的人赢。
如果所有sg值都为$0$时游戏必然结束的话，先手必胜当且仅当
- 整个的sg值不为$0$且
sdoi2009 E&D游戏
nac 2021 ?. Token Game
如果两个棋子挨着，后手可以模仿先手，于是后手必胜。
否则如果两个棋子在某一维上相邻，先手必胜。
nim积
有结论 :
-
如果$2^{2^k}>x$，$2^{2^k}\times_\ast x=2^{2^k}x$。
-
$2^{2^k}\times_\ast 2^{2^k}=\frac{3}{2}2^{2^k}$。
于是可以分治乘，复杂度$O(\log^2 n)$。
热博弈，平移原理，转换
双方都希望先操作$L>R$的局面。如果没有，先操作$L=R$或$L\parallel R$的。
$+$
定义$+_x={0,{0,x}}$。
D4
A. boruvka
gdcpc23 G. Classic Problem
青鱼真他妈省事。
简单题。但是我memset一个bool数组的时候长度写了sizeof int，然后调了一万年。
B. path
ccpc23 final B.
给两个路径压缩的并查集$f,g$，问能否对$f$进行find和join获得$g$。$n\leq 1000$。
考虑$g$的每棵树必然是$f$的若干棵拼起来。考虑$g$的一棵树。
注意到我们join的时候必然是操作两个根，而$g$中根之间的结构就告诉我们如何合并，但是这其实不太一定，比如$x$合并到$y$，$y$合并到$z$，然后调用find $x$，$x$就变成了$z$的儿子。
但是如果$x$子树中有一个点是$y$的儿子，那么$x$必然是先合并到$y$，然后find了那个点对吧。可以发现满足所有这种条件的合并的结构就是合法的。
注意到find只会破坏祖先-后代关系，而不会增加新的祖先-后代关系，而越往后破坏的越多，所以我们应该尽可能早地find一个点。
C. fish
妈的，什么东西。水解了。
有$n$个栈，每个栈里有$c$张牌，牌有花色和数值，有$s$种花色，没有两张牌完全相同。每次你可以选择两个花色相同的栈顶，把数值小的弹了，或者选择一个栈顶和一个空栈，把栈顶移动到空栈里。求能否让最后每个栈里只剩不超过一张牌。$n\leq 5\times 10^4$。
显然每个颜色最大的都要留下来。如果$s>n$，必然无解。如果$s<n$，要么有一个空栈，要么有两个栈顶花色相同，所以必然可以操作，所以必然有解。那么只需要考虑$s=n$。
考虑最大的牌。显然能删就删是不劣的，因为我们可以只用最大的牌去删，而最大的牌大小是不降的。同时如果一个花色出现在某个栈顶，那么接下来它必然一直在某个栈顶(可能改为在另一个)。
类似于$s>n$的证明，不停删到不能删，此时要么游戏结束，要么有一个空栈。仅剩的问题是当出现空栈的时候，把哪张牌扔进空栈。
考虑最后出现的颜色，当它出现在栈顶的时候，我们必然不能继续操作了，所以必须已经赢了。它在此之前必然没有出现过，所以它只有一张。
考虑如果一个颜色的$\max$出现了，我们几乎可以直接扔掉这个颜色的其它所有牌，因为它们一出现就会被删除，除非被$\max$压在下面。如果它不是最后出现的$\max$，接下来必然还会生成空栈，此时我们必须把它移动过去，这样这个颜色的其它所有牌还是可以被扔掉了。
gdcpc23 ?. ?
考虑首先要满足$x\bmod{a}=y\bmod{b}$，它就是$x-a\lfloor\frac{x}{a}\rfloor=y-b\lfloor\frac{y}{b}\rfloor$。第二位就是$\lfloor\frac{x}{a}\rfloor-a\lfloor\frac{x}{a^2}\rfloor=\lfloor\frac{y}{b}\rfloor-b\lfloor\frac{y}{b^2}\rfloor$，这样的。
注意到确定$a$之后，$b$可以$O(\log^2 v)$二分出来对吧。假设$a>b$(或者可能其实是$<$，我不知道)，如果$a\leq\sqrt{v}$，双指针就可以做到$O(\sqrt{v}\log v)$，不过这里因为每个$b$只需要$\log_b v$的代价所以是$O(\sqrt{v})$。如果$a$很大，如果$a^2>x$，那就直接判断是否有$x=y$。否则第二位就是$\lfloor\frac{x}{a}\rfloor=\lfloor\frac{y}{b}\rfloor$。那么枚举一个$\lfloor\frac{x}{a}\rfloor$，$a$是一个区间，$b$也是一个区间，$x-a\lfloor\frac{x}{a}\rfloor=y-b\lfloor\frac{y}{b}\rfloor$的左边是关于$a$的一次函数，右边是关于$b$的一次函数，求一个交即可。
ccpc22 final A. Graph Partitioning
第一棵树的根必然是$n$，第二棵树的根必然是$1$。
考虑相当于每个点在比它小的里选一个父亲，在比它大的里选一个父亲，两个点不能互相选，或者说每条边只能选一次。那么相当于每条边可以匹配它的端点之一，每个点拆成小的和大的，每条边可以匹配它的一端的小点和另一端的大点，当然$1,n$在一侧没有父亲所以只有一个点。于是考虑拆点之后每个连通块必须是一个基环树，环有两种定向，所以如果确实是这样，答案就是$2^\text{连通块数}$。
ccpc22 final C. DFS Order 3
注意到dfs序的最后一个点必然是叶子，我们找到它的父亲，它出发的dfs序的第二个点就是它的父亲。
ccpc22 final D. Flower’s Land 2
可以单侧递归线段树。但是据说有个牛逼随机化做法!
随机三个可逆方阵$M_i$，如果一个位置是$i$，它在同种颜色中的排名是$k$，那么一个区间可行当且仅当$M_i^{(-1)^k}$的$\prod$是$I$。
证明不会。咍咍!
ccpc22 final J. Best Carry Player 3
$k$的次高位及以下是自由的。
如果$\mathrm{highbit}(x),\mathrm{highbit}(y)\leq \mathrm{highbit}(k)$，通过xor，两步之内必然可达。
如果$>$，高位每次只能$\pm 1$，可以xor之后$\pm 1$以两步给$\mathrm{highbit}(k)$这位$\pm 1$，或者改成两次xor给$\mathrm{highbit}(k)+1$这位$\pm 1$，这里如果$k+1$是$2$的幂则总是只需一次。此后低位是一样的。
ptzwc 2023 D7 ?. Classical FFT Problem
设durfee square的边长是$k$，那么每个解要么前$k$行每行恰好有一个，要么前$k$列每列恰好有一个。加起来再减去同时满足的$k!$个。
考虑前者，只有删掉durfee square和前$k$行之后剩下多少列有关系，dp即可。
joisc 2023 D4 ?. The Last Battle
注意到B必须知道$x,y$是啥，所以信息量是恰好的。
用相同的随机数生成器生成一个随机满秩线性变换。B可以枚举哪行哪列没了来尝试解码。但是B只能看$x,y$来判断，所以每次错误率是$\frac{1}{64}$。这就死啦。
考虑如果我们只利用剩下的$7\times 7$矩阵，就只可能有$\frac{1}{64}$的正确率。我们希望让$x,y$也能编码一些信息，考虑我们让所有矩阵有$\frac{1}{2^{15}}$是合法的，那么枚举一行一列，枚举它们本来是啥，看能否变得合法。我们让它有一个性质，比如随机一个秩是$49$的矩阵这样的。
ejoi 2022 D2 ?. Game With Numbers
注意到每个数只会递归到一边。
注意到如果两个人都可以达到空，那么答案是$0$。既然两个人都不能达到空，说明不存在两个数满足一个的倍数和另一个倍数不交，那么考虑一些不同数的$\mathrm{lcm}$，既然不能达到$0$，也不存在一个数整除剩下的数的$\mathrm{lcm}$，所以每次往$\mathrm{lcm}$加入一个数，我们必然会增加一个素因数，所以$m$超过$\log v$必然无解。复杂度$O(n\log v)$。
amppz 2016 ?. Home alone: Johnny lost in New York
如果边上有两行或两列不包含起点或终点，可以把它删掉，最后接上。
现在$s,t$必然在两个对角，两维距离边界不超过$1$。
同样地，如果$s$在边上，我们可以把$s$向上移动一点。
ptzwc 2023 D6 ?. 4
枚举一个点$s$，建一张新图，$u,v$有边当且仅当$s,u,v$是三元环，那么我们相当于在这个图上做三元环计数。所有的图一共有$O(m\sqrt{m})$条边，所以复杂度是$O(m^\frac{9}{4})$，比爆力慢一点，虽然我们好像其实不会$m^2$爆力啊!
但是，$\sqrt{m}$的和其实没有那么大，因为每个点最多只有$m$个包含它的三元环对吧。所以最坏情况是$\sqrt{m}$个点每个是$m\sqrt{m}$的，这样它其实是$O(m^2)$。
注意到这个最坏情况中点数很小，考虑换成$O(\frac{nm}{w})$的三元环计数，那么最坏情况仍是$\sqrt{m}$个点$m$条边，因为连成团带来的影响要更高阶。所以这样就是$O(\frac{m^2}{w})$啦!
ptzwc 2021 D7 ?. The Hash Table
pa 2021 R5 ?. Desant 2
D5
我不知道。
D6
为什么挂了一万分。
A. war
树，有若干条链，选尽可能少的点使得每条链有至少一个点被选。$n\leq 5\times 10^5$。
贪心选最高的。在lca处需要支持查询一条祖先-后代链有没有点被选，这里lca到根的链上没有东西被选，所以可以查一个点到根的链有没有点被选，括号序一下就是入栈时间前缀的出栈时间max，BiT即可。
或者我们只需要知道有没有，所以可以每选一个点dfs下去把子树推成$1$，这样每个点只会被推一次。
有趣的是它的线性规划对偶是选尽可能多不交的链。
B. tree
icpc 22 asia pacific regional Yokohama G. Genealogy of Puppets
扫编号。dp，设$dp(i,j,k)$表示前$i$个，$j$个需要儿子的接头，$k$个需要父亲的接头。注意到我们可能选出一个环，但是由于只能在前面选最多一个需要儿子的接头，选了它之后，有且只有它所在连通块的需要父亲的接头不能选了。这样就还是可以算啦。
C. cake
简单高消解递推式然后线性递推题。
cf1648 D. Serious Business
好像做过。
unr3 配对树
考虑统计每条边的贡献，匹配相交必然不优，所以如果一条边两侧都有奇数个点，那么它肯定要贡献，否则它肯定不贡献。
所以边分治，问题变成两个01序列，支持单点修改，查询有多少个区间满足在两边都有奇数个$1$，那么也就是两个相同的前缀和，维护每种前缀和的个数即可。复杂度$O(n\log^2 n)$。
考虑怎么砍砍$\log$。考虑直接线段树合并维护这玩意，结束了。
apio2023 B. ?
枚举一个数，比它小的是$-1$，大的是$1$，那么我们要找包含它次数最多的区间满足前缀和的差的绝对值不超过这个数的出现次数，或者我们枚举这个数的时候，从前往后改每次出现，撤销回去再从后往前改每次出现，那么就是满足在某个时刻前缀和的差为$0$。对于每个前缀和，当然只有第一次出现和最后一次出现有用，当我们给前缀和的后缀$+2$的时候，最后一次出现会shift两位，会有一些东西露出来变成第一次出现。
这个shift看起来很困难。可以发现两边关于前缀和的位置都是单谷的，也就是前缀和越靠近谷底，最靠边的出现位置靠边越近，那么只有两个谷底之间的部分有用。
发现这个转化拉了，如果从小到大枚举，一个区间改之前是正的，改之后是负的，那么它的中位数就是我们改的这个数，在这俩上面双指针扫出现位置即可。需要用BiT维护，复杂度$O(n\log n)$。
ur2 树上 GCD
长剖先，那么我们要把两个集合的笛卡尔积的gcd加进去，并且要求大小只和小集合的大小相关。
那么直接枚举gcd，莫反一下，只需要查询一个数的倍数个数，复杂度看起来就非常对啊!
集训队胡策2016 Unknown
直接做。李超树会被卡空间，可以对线段树底层分块。
联合省选23 人员调度
?
这是匹配拟阵，先用个强基交换定理对吧，每个点先匹配$-\infty$，那么我们每次只需要替换一个匹配或者重新找一个匹配，否则说明原来的不是最优解。对于前者，相当于找子树中匹配的$\min$。对于后者，相当于找到根的链上未匹配的$\max$。前者dfs序线段树，后者静态lct即可。
但是其实我们并不能说明只需要重新找一次匹配，因为匹配拟阵的独立集是有完美匹配的集合，而不是完美匹配的边集，在换一个点的时候完美匹配的边集变化量可能很大。所以还得线段树分治。
集训队胡策23 【模板】线段树
收录于 oi题选做。
D7
A. a
给$x,y,z$，一棵根为$1$的树的hash值定义为$\sum_{i<j}x^iy^jz^{\mathrm{lca}(i,j)}\bmod{998244353}$，给一个hash值，构造一棵树。$T\leq 10$。
嗯折半。
B. b
构造一个排列$p$，满足$\vert p_{i+1}-p_i\vert$是素数，最小化不同的$p_{i+1}-p_i$的数量(比如$2,-2$算不同的)。$n\leq 2\times 10^6$。
爆搜打表发现，如果$n$是偶数，寻找两个素数$p,q$满足$p+q=n$，按膜$p$分组，那么每次$+p$可以遍历一组，$-q$可以切换到另一组的第一个数。奇数则对$n-1$做。
但是$n\leq 7$不能这么做，搜即可。
C. c
$n\times m$的棋盘，选一些$x,y$都严格递增的格子挖掉，对于所有可能的结果求放任意多个互不攻击的车的方案数之和，膜$998244353$。$n\leq 5\times 10^5$。
只有挖了多少格子有关系，枚举挖了$k$个，容斥，可以得到答案是
\[\sum_k\binom{n}{k}\binom{m}{k}\sum_i(-1)^i\binom{k}{i}\sum_t\binom{n-i}{t}\binom{m-i}{t}t!\]把$i$换到前面去，吸收一下然后gf一下可以知道$\sum\limits_k\binom{n}{k}\binom{m}{k}\binom{k}{i}=\frac{(n+m-i)}{i!(n-i)!(m-i)!}$，所以答案就是
\[\sum_i\sum_t\frac{(-1)^i(n+m-i)!}{i!t!(n-i-t)!(m-i-t)!}\]$\sum\frac{(-1)^i(n+m-i)!z^i}{i!}$和$\sum\frac{z^i}{i!}$都是d-finite的，所以就线性了。
构造。
thupc23 final H. ?
$u,v$的权值是$\mathrm{lowbit}(u\operatorname{xor}v)$，因为这是奇环。
如果没有奇环的话，至少要用$\lceil\lg n\rcecil$个。
cf1779 G. The Game of the Century
cf1779 F. Xorcerer’s Stones
如果$n$是偶数，直接对整棵树操作两次。
如果$n$是奇数，那么我们对大小为偶数的子树操作两次就可以让它变成$0$对吧。如果我们把xor和变成$0$了就赢了，所以我们把大小为偶数的子树的xor和拿出来跑个背包即可。但是不能选一对祖先-后代，所以需要在树上dp。
cf1765 G. Guess the String
考虑先问出第二个字符，然后我们每次问两个字符，如果border长度是$1$那就好说了，如果border长度是$0$，我们需要问反border长度。先随一个问，这样期望需要问$750$次。
agc060 E. Number of Cycles
注意到交换$x$中的两个位置，也会交换$y$中的两个位置，那么环数都会$\pm 1$，所以如果奇偶性不同就没救了。同时可以注意到答案是连续变化的。
考虑先构造出最小值和最大值。最大值总是由$1,…,n$给出，而最小值可以通过不停合并环得到，要么是$2$要么是$3$。
显然把$p_i$和$i$交换不会让环数和减少。劲爆的是必然存在一个操作让环数减少$2$。所以我们可以随机一个排列，环数期望是$\log$，然后如果大了就不停找到一个操作，如果小了就不停把$p_i$和$i$交换。
agc057 C. Increment or Xor
注意到xor是一个置换。考虑我们进行$2^n$次$+1$，每次之后决策xor啥，可以猜测这样必然能找到解。
但是我比较智障。考虑倒着建个trie，那么$+1$就是右链交换儿子，xor就是若干层交换儿子。那么通过一次xor我们可以把任何一个点移动到右链的底部，也就是说我们可以让任何一个点到根的链交换儿子。
agc055 D. ABC Ultimatum
是不是因为$n$很小所以可以直接造dfa。
先造一个nfa对吧，但是发现nfa状态数甚至是$(3n)^6$的，就是说我们要枚举往哪个位置塞。这样就得到一个$O(2^{(3n)^6})$的做法。
这里也没法增量造dfa。感觉很失败啊!
换个想法，考虑我们把串拼成一个环，这样我们实际上是判断是否存在一个三元环分解。考虑我们必然可以找到$p,q$，满足每次选的是第$i$个a，第$i+p$个b，第$i+q$个c，这里都是膜$n$的。
可以发现$p$的最小值就是前缀b个数减去a个数的最大值，$q-p$的最小值就是前缀c个数减去b个数的最大值，然后我们当然还要求$n-p-q\geq$前缀a个数减去c个数的最大值。直接dp即可。
agc054 D. (ox)
发现o是占位符，x是$>0$的限制。
直接对最终的序列dp，设$dp(i,j,k,l)$表示放了$i$个左括号，$j$个右括号，$k$个o，$l$个x的答案，那么我们要算逆序对数，就是直接在靠前的那个处算，非常好对吧!
注意到固定任意一个字符的子集，其最优解和整体最优解中它的子序列是一样的。所以先对两种括号dp，然后加入o和x即可。
thupc22 final C. ?
策略必然是不停问某一位，相当于我们可以以倒数的代价获取一位对吧。
考虑dp，直接对所有串同时dp，
可以直接逐位dp求出哪些状态是已经知道答案的，算量是$\sum\limits_i3^i2^{n-i}$。
D8
A. zoo
长$2n$的括号序列，有$n$种颜色，一些括号的颜色是确定的，给剩下的括号染色，满足每个颜色有恰好一个左括号一个右括号，且左括号在右括号左边，求方案数。$n\leq 5000$。
直接dp，从左往右扫，如果一个颜色出现两次则没锤子用，如果有左括号是简单的，如果有右括号，我们让一个没有颜色的左括号留下来，在这个右括号处选出哪个左括号和它颜色相同，发现只需要记录留了多少个括号就够了。复杂度$O(n^2)$。
B. road
树，求有多少种给边定向的方案，满足任意简单有向链上反边数量的最大值最小。$n\leq 2000$，$20$组。
最小的最大值显然是直径的一半上取整。设它是$L$。
考虑差分，设$d_u$表示$u$到根路径上朝上的边的数量减去朝下的边的数量，那么两个点有向链上反边数量就是$\frac{1}{2}(\mathrm{dist}(u,v)+d_u-d_v)$。所以合法当且仅当对于任意边$u,v$有$\vert d_u-d_v\vert=1$，且对于任意两个点有$\frac{1}{2}(\mathrm{dist}(u,v)+\vert d_u-d_v\vert)\leq L$，也就是$\vert d_u-d_v\vert\leq 2L-\mathrm{dist}(u,v)$。
注意到最大的$\mathrm{dist}(u,v)+\vert d_u-d_v\vert$必然在直径端点处取得，而如果取一个直径端点为根，所有的直径端点的$d$必然为$0$，我们又知道到最远的直径端点的距离就是到直径中点$c$的距离加上半径。所以如果$n$是偶数，限制就等价于$\vert d_u\vert\leq L-\mathrm{dist}(u,c)$。对此dp即可。
如果$n$是奇数，则要麻烦一点。
C. color
树，根是$1$，每个点有黑白之一的颜色$a_u$，有一些点的颜色是确定了的，支持修改一个点的颜色(在黑，白，未确定之中)，求给未确定的点填色，最大化点对$u,v$满足$u$是白色，$v$是黑色，$u$是$v$的祖先的数量，只需要输出最大值。$n,q\leq 2\times 10^5$，4s。
考虑必然是一个包含根的连通块尽可能选白，剩下的点尽可能选黑，然后就可以写一个dp啦。强力拆式子转化之后是，设$0$表示白，$1$表示黑，$-1$表示未确定，设$d_u$表示$\mathrm{fa}(u)$到根链上可能选$0$的点数，$g_u$表示$u$子树内可能选$1$的点数，那么答案是$\sum_u([a_u=0]g_u+[a_u=2]\max(g_u-d_u-1,0))$。每次操作是修改一个点的贡献状态，前一项比较简单，后一项是到根的链$\pm 1$，子树$\pm 1$，求$>0$的数的和。和序列上区间$\pm 1$，求$>0$的数的和类似，直接树分块即可。
也可以离线时间分块，建个虚树来算。这个据说会好写，但是时间分块这东西还是别碰对吧!
我不是很清楚在这个问题上是时间分块虚树优秀还是直接树分块优秀，大概是后者吧，好比top tree之于scaling。
杂题。
cf1361 E. James and the Chase
作为sdptt21 r3 D5 B。
arc104 F. Visibility Sequence
我们知道$p_i=j$说明从右往左跑单调栈的时候$i$被$j$弹了，那么因为单调栈的过程和卡笛尔树是双射，所以其实就是卡笛尔树计数。显然值越小限制越少，并且我们可以直接对最小的序列计数，所以设$dp(l,r,k)$表示区间$[l,r]$形成一棵卡笛尔树，根的最小值是$k$的方案数，$k\leq n$所以复杂度是$O(n^4)$。
这里有相等的，所以有一些$\pm 1$的问题。
cf1470 F. Strange Covering
考虑最上，最下，最左，最右四个点，但是很遗憾，这不一定是四个点。
不过没有关系，考虑矩形要么不交，要么相互穿过，要么交一个角。不交的情况，只需要枚举一条线把它俩分开即可。
考虑相互穿过的情况，考虑最左最右两个点，横着的矩形必须覆盖它俩，考虑剩下的最上最下两个点，竖着的矩形必须覆盖它俩。如果此时它俩没有相互穿过，那就没必要相互穿过了。否则我们确定了两个矩形的高度，现在要继续确定宽度，设往两边扩展的长度分别为$l_1,r_1,l_2,r_2$，那么是一些$x_1\geq k_1\operatorname{or}y_2\geq k_2$的限制，要最小化带系数的和。考虑枚举$l_1$，那么每个限制会对$r_1$的前缀或者全局的$l_2$或$r_2$取$\max$，也就是维护两个序列，支持区间对一个数取$\max$，求两边的带系数的和的$\min$，吉老师线段树转化为区间加即可。
考虑交一个角的情况，比如一个在左下一个在右上，那么显然左下矩形的右边和右上矩形的下边必然会截到相邻的点，另一侧类似。右下单调栈和左上单调栈必须被覆盖，但是这不是充要的，因为它俩可能不交，此时中间可能会夹着一些点。好消息是枚举右下单调栈截了哪个间隔，左上单调栈满足相交的是一个区间，所以就赢啦。这里答案是齐次的可以除一下，最后问题是有一堆一次函数，每次在一个区间中求$\max$，好消息是这个区间甚至是单调的，所以只需要正反两棵李超树，复杂度$O(n\log n)$。
集训队胡策22 >.<
收录于 oi题选做。
cf1672 H. Zigu Zagu
把所有相邻相同的位置拿出来，那么答案是两种的$\max+1$对吧。
ioi2013 wombats
考虑怎么$O(nm)$做一次，发现我们决策单调一下直接就会了$O(nm\log n)$，非常好对吧!
考虑不要爆力重构，竖着建线段树，那么合并一次是$O(m^3)$的。所以复杂度是$O(m^3q\log n)$，非常好对吧!
继续注意到这里合并的时候我们是枚举中转点，所以还是决策单调性，所以可以$O(m^2)$合并啦。
但是空间炸了，需要底层分块。
集训队胡策22 整数
收录于 oi题选做。
wc2019 数树
考虑第二问咋做，钦定一些边是交然后连剩下的边，但是可能连到别的边，那么我们就容斥对吧，再钦定一些边是算错的即可。然后就是prufer序列了，要算连通块大小乘积，转化成每个连通块选一个点的方案数即可。
但是这个比较智障，可以直接二项式反演。
考虑第三问咋做，还是二项式反演，钦点一个连通块分解，然后剩下的随便交，做exp即可。
D9
A. treecolor
感觉是嗯造的题。
B. light
数轴上有一些点$x_i$，从一个点出发游走的过程是，每次走到最近的还未走过的点，如果左右一样近则往右走。每次给一个区间，求只保留这个区间中的点，从每个点出发开始游走，走的总长度之和。$n\leq 10^5,q\leq 3\times 10^5$。
容易发现只会折返$\log$次，因为每次折返，中间走过的部分长度都会翻倍。
有趣的是可能总和其实是$O(n\log n)$而不是$O(n\log v)$。我不知道。
考虑我们找到$l,r$两个点哪个先被走到，此时必然用$x_r-x_l$的代价走到另一个。枚举一个点算对查询的贡献，对每个点处理出怎么走，枚举在哪个点最后一次折返，这要求上一次折返完成了，这一次折返能完成，并且下一次折返不能完成，也就是说如果这三次分别在$x_1,x_2,x_3$，要求$x_3\leq l<x_1,x_2<r$。所以是矩形加单点查询，复杂度$O(n\log^2 n+q\log n)$。
有一个比较劲爆的处理怎么走的方法，考虑我们现在要往右走，左边是$l$，那么要求最小的$i$满足$x_{i+1}-x_i>x_i-x_l$，也就是说$x_l<2x_i-x_{i+1}$。直接对$2x_i-x_{i+1}$跑单调栈，
C. fenwick
有一个数$x$，一开始是$0$，有两种操作，把二进制最低的$0$改成$1$和把最低的$1$改成$0$，如果前$k$位没有$0$或没有$1$那就不做操作。给一个操作序列，有一些位置是未确定的，对每个未确定的位置求如果确定它为$0$，剩下所有确定的方案中，按顺序操作后得到的$x$在$[0,r]$的方案数。$n\leq 10^5,k\leq 20$。
考虑全局怎么做，
dp。
egoi2022 legowall
算随便放的方案数然后容斥即可。但是容斥要法法。
考虑如果$w$够小，就不用法法啦，这是$O(h+w^2)$的。如果$h$够小，dp，设$dp(i,j)$表示前$i$列，有$j$个凸出到$i+1$列的行，转移枚举多少个凸出到$i+2$列，它们必须是在没有凸出到$i+1$列的放一个宽$2$的，这是$O(h^2w)$的。平衡时是$O((hw)^\frac{4}{3})$。
cf1250 D.
对于每个点，包含它的区间只能有一个颜色的合法。考虑给每个点钦点一个颜色，那么一个区间合法当且仅当和它有交的区间中最左的左端点到最右的右端点颜色都相同，如果它有颜色还要和它的颜色相同。于是记当前点的颜色和上一个颜色不同的点的位置即可。
cf1158 F.
考虑怎么算密度，考虑我们找到最短的没出现过的子序列对吧。考虑有啥好并行的dp算最短的没出现过的子序列，感觉没有啊，还得在子序列am上跑。不过子序列自动机性质很好，我们直接尽可能跳最远的转移即可。
考虑钦点出每次跳到哪，设$dp(i,j)$表示上一次跳到$i$，跳了$j$次的所有子序列的答案，转移枚举下一次跳到了$k$，那么这一段需要选$1,…,c$各至少一个，每种字符是独立的，计算$\prod(2^{\mathrm{cnt}}-1)$即可。注意到$j$不超过$\frac{n}{c}$，所以复杂度是$O(\frac{n^3}{c})$。平衡一下，如果$c=O(\log n)$，可以直接记哪些颜色出现过，复杂度$O(\frac{n^3}{\log n})$。
cf1175 G.
容易单调栈ktt做到$O(nk\log^3 n)$。shaber。
考虑单调栈上每个点维护这一段的凸壳，然后$r$移动的时候最优决策点是单调的，用李超树维护这些最优决策点，这里单调栈只弹最右边，所以只需要撤销，所以是一个$\log$的。用堆维护最优决策点的移动。复杂度$O(nk\log n)$。
还可以直接分治，但是不再赘述。感觉这种问题直接分治总是菜的啊。
还可以笛卡尔树，看起来更菜。
egoi2021 lantern
考虑我们需要买的时候再买，这样能到的高度和能到的位置总是一个区间。
考虑我们不需要记能到的位置，只需要记起点和能到的高度，然后枚举下一个要买的灯笼。这样是$O(n^3)$的状态数。
考虑分治，对中点跑这个dp，那么如果现在在做区间$[l,r]$，如果我们可以到达$l-1$或$r+1$了，可以直接调用$l-1$或$r+1$的dp结果，所以总状态数是$O(n^2)$。
或者直接注意到我们可以记最低的点来自哪个灯笼，最高的点来自哪个灯笼，那么可以认为起点是这两个灯笼中任何一个。这样状态数也是$O(n^2)$。
考虑如何优化dp，我们枚举最左的灯笼$i$，按右端点从小到大枚举$j$，如果$j$从$k$转移来，要求$r_k\geq l_j$，并且$k$出发能直接到达$j$。
联合省选22 最大权独立集问题
设$dp(u,v,w)$表示$u$子树，把$v$换出去了，把$w$换进来了的答案。但是这个状态数是$O(n^3)$。
考虑设$dp(u,v,w)$表示$u$子树，把$v$换出去了，把换进来的东西放到了$w$，不计进来的东西移动的代价的答案。这样$u$必须是$\mathrm{lca}(v,w)$，所以状态数是$O(n^2)$。
然后考虑转移，转移讨论三条边操作的顺序，看起来只需考虑$u$的父边是第几个。
如果它是第一个，那么必须有$v=u$，此时我们换进来了一个什么东西，把它放到$w$去，不妨设$w$在左子树，那么左子树的父边需要接下来操作，这会换出来一个东西$x$，然后右子树就换入它，右子树换出的东西就停在$u$，所以我们大概是$dp(lc,x,w)+dp(rc,?,?)$这样的东西。对每个$x$处理出右子树最小的$dp(rc,?,?)$，这部分是$O(n^2)$。然后对每个$w$预处理最小的$dp(lc,x,w)+dp(rc,?,?)$，这还是$O(n^2)$，这就结束了。
如果它是第二个，那么不妨设第一个是左子树，它会把$u$换走，然后换过来的东西$x$就被换出子树，换过来的东西换入右子树，这样大概是$dp(lc,u,w)+dp(rc,)$
如果它是第三个
D10
A. jump
从$0$出发走两条路径到达任何一个$\geq n$的点，每次可以走$a$或走$b$，要求两条路径步数相同。$0,…,n-1$中每个点有一个权值，对于一个方案，把所有经过的点拿出来，相邻两个点的贡献是距离乘上权值的xor，求最大贡献和。$n\leq 5\times 10^4,\frac{n}{a}\leq 10^3$。
这个权值看起来没啥性质。dp，设$dp(x,y,z,w)$表示两边分别在$i=ax+by,j=az+bw$，每次我们把靠后的一边往前推一步。
注意到由于每次把靠后的往前推，只有$i-j<b$的状态可能转移到。所以不需要记$w$，因为必然有$w=\lfloor\frac{ax+by-az}{b}\rfloor=\lfloor\frac{a(x-z)}{b}\rfloor+y$。继续注意到我们只需要记$i$和$x-z$，因为$i-j=a(x-z)+b(y-w)=a(x-z)-\lfloor\frac{a(x-z)}{b}\rfloor$，而步数差是$x+y-z-w=x-z+\lfloor\frac{a(x-z)}{b}\rfloor$。复杂度$O(\frac{n^2}{a})$。
B. graph
图，$i$可以走到$2i,2i+1$，所有操作都在膜$2^m-1$下进行。求$s$到$t$所有长$n$的路径经过$[l,r]$中点的总次数。$n,l,r\leq 10^9,m\leq 30$，$5000$组多测。
考虑$l=r$怎么做，我们只需要算出$s$到$l$的方案数，$l$到$t$的方案数。
注意到走恰好$m$步相当于加上任意数，但是有两种方案加$0$，那么也就是每个位置都加上总和。而走$<m$步到达某个数只有一种方案。$m$步内的答案统计是个线性变换，所以可以矩阵快速幂啦。
考虑我们从$s$出发到达区间$[l,r]$，然后把区间外面的推成$0$，然后再走到$t$。显然还是线性变换，所以还是可以矩阵快速幂。
C. makepair
树，每个点的度数要么是$3$要么是$1$，有偶数个叶子。对于每个叶子，去掉它和另外任意一个叶子之后在剩下的叶子中找一个完美匹配，满足所有匹配对在树上的链两两没有交点，每个叶子有一个权值，求所有匹配点对的权值xor的和的最大值。$n\leq 3\times 10^5,v\leq 2^{12}$。
注意到删两个点，匹配是唯一的。如果以一个点为根，有两棵子树叶子个数是奇数，那么必然在它这里产生一对匹配，否则必然没有，那么所有匹配链经过的边都确定了，而显然这样确定出的匹配是不交的。也可以考虑一条边在一对匹配上，当且仅当它两侧叶子个数都是奇数。
注意到删一个叶子，以它为根，所有点上方的叶子个数奇偶性都取反了，也就是说所有点父边是否是匹配边的状态都取反了。但是这玩意没法知道到底是哪些点匹配。
注意到删两个叶子，它们链上的边是否是匹配边的状态都取反了。但是这玩意还是没法知道。
考虑爆力怎么做。dp，设$dp(u,v)$表示$u$
cf1580 D.
两个选的数之间只有$\min$有用。卡笛尔树先，我们找到全局$\min$，然后它的贡献就确定了，左右卷卷即可。复杂度是树卷积。
cf878 E.
感觉比较厉害。找到最后一个正数，把它和前一个数合并必然不劣。如果所有数都是负的，那么我们必然把所有数从右往左合并。跑出合并的树即可。
但是可能会有巨大的数，发现不会有巨大的负数，只会有巨大的正数，所以一个数足够大的时候，就可以把它看成inf了。
cf1285 F.
考虑