~10-11 部分题解。
密码xoi。
删去了部分一句话题解。
10.1
T4 euclid
看 \(lcp(i,j) l\le j\le r\) 最长的 \(j\) 的位置。
建出后缀数组后，发现本质上就需要查询 \(i\) 前面第一个 \(l\le j\le r\)，以及后面的第一个 \(l\le j\le r\)。
直接做有些麻烦。
换维后，把 \(i\) ，一个个插入，变成了可持久化线段树上二分，就好了。
10-2
T1 safe
首先逆序对二分图，直接转成顺序对两个团。
顺序对一定有传递性，所以我们选出来的必定是两条上升子序列。
判定性问题不难。可以 \(dp[x][s1]\) 表示做到 \(x\) 最后是否取负，另一个子序列结尾最小值。
那最优化就可以按位贪心。如果这一位取负的话，后面能接上，那就可以，否则不行。
T3 euclid
妙妙博弈。
考虑如果现在在 \(x\) 这个点，如果 \(y\) 这个子树对方必赢，那不可能走到 \(y\)。
否则我们对于对方必输的点维护一个 \(f_x\) 表示这个点 \(x\) 在至少拥有多大的时候，在这个点开始能赢。
如果他能到达能对面输的点，并且这个点权值要小于当前点权值，他能赢。
题解感觉就很妙妙呀，就是不管是谁，每次都只能走权值更小的点，否则是负收益。
然后看谁走最后一步。完事了！！！
T4 keter
很怪的题呀。
conclusion 1:
\([1,n]\times [1,n]\) 里面整点凸包最多有 \(n^{\frac{2}{3}}\) 个点。
考虑选的斜率 \((x,y)\) ，一定是一条斜线一条斜线的 \((1,1),(1,2)(2,1),(1,3)(2,2)(3,1)\)。
然后求和就是 \(\sum i^2\le n\) 级别的，点数是 \(\sum i\) 级别，那自然是 \(n^{\frac{2}{3}}\)。
直接背包的复杂度是 \(O(mn^2)\)，\(m=O(n^2)\) 是可选斜率个数。
根据结论，我们可以换维做到 \(O(mn^{\frac{5}{3}})\)。
然后根据一个贪心，如果我们要选 \((x,y)\) 那么 \((i,j),i\le x,j\le y\) 一定被选光了。
conclusion 2:
合法的 \((x,y)\) 级别也是 \(O(n^{\frac{2}{3}})\) 的。
证明很不严谨，并且似乎常数很大？
\[ \begin{aligned} \sum_{x,y}[\sum_{i\le x,j\le y}(i+j)[\gcd(i,j)=1]\le 2n]\\ F(x,y)=(\sum_{d\le min(x,y)} d\mu(d)\sum_{i\le x/d,j\le y/d}(i+j))\le 2n\\ F(x,y)=\sum_{d\le min(x,y)} d\mu(d)(\frac{x}{d})^2\frac{y}{d}+(\frac{y}{d})^2\frac{x}{d}\le 2n\\ F(x,y)=(x^2y+y^2x)\sum_{d\le min(x,y)} \frac{\mu(d)}{d^2}\le 2n \end{aligned} \]
这个 \(\sum_{d\le min(x,y)} \frac{\mu(d)}{d^2}\) 不太会分析，那就当成是 \(O(1)\) 的吧！！。
\[ \begin{aligned} F(x,y)&=(x^2y+y^2x)\le 2n\\ \sum_{x,y}F(x,y)&=\sum_{x,y}[\max(x^2y,xy^2)\le 2n]\\ &=\sum_{x}\max(\frac{n}{x^2},\sqrt{\frac{n}{x}}) \end{aligned} \]
在 \(x=n^{\frac{1}{3}}\) 的时候，\(\max\) 有的区分。
分别积分一下，得到 \(O(n^{\frac{2}{3}})\) 的界。
然后 \(m=\frac{2}{3}\) ,总复杂度 \(n^{\frac{7}{3}}\)
10-5
T3 euclid
记住后缀排序，基数排序是从后往前排的。
感觉从高位往低位做很困难，但是反过来就容易了。
从低向高合并，如何判断这一位是 \(0\) 还是 \(1\)，递归到子问题！
也就是将新的字符串重新标号，然后变成 \(n-1\) 的子问题。
T4 euclid+
赞美保证有解。
首先一个obs是如果 \([a,b],[c,d]\) 那么能得到他们的交，一定也合法。
然后由于一定是长的区间包含，短的区间；不难想到从短往长去合并区间。
由于保证有解，我们一定要么没有与其相交的区间，要么相交。
如果此时被覆盖，那么那两个拼起来的区间，一定和该区间有交，那么把两段交拼起来。也是合法的。
不相交正确性显然。
相交的话，考虑与他前面交的极长那段，和后面极长那段，不难发现这两段都是合法的。然后本质上就是不交情况。
然后拿并查集维护连续段就好。
10-8
T3
式子简单的，就折线嘛。
主要是如何处理 \(\bmod p\)。
我们可以直接扩域 \(Z(p_1,p_2\cdots p_k)\) 这样乘法运算就是，互质部分直接乘，因子部分直接加。
求逆也很简单，做完了。
T4
发现这东西类似链覆盖呀。
考虑链覆盖的时候我们在干什么，我们最后减去了链边的贡献。
也类似的考虑，我们先让每个状态直接连到 \(0\) 然后，考虑合并两条链的贡献。
那就直接减去原先这条链的贡献，就好。
网络流建模，就是左边的点，连向右边的点，一个右边的点，实际上会回到左边，接上继续做。
然后直接费用流就行。
10-11
T3
李超树/维护凸包。
现在想想，是个很板子的李超。自己却做成了“维护最大子段”。
T4 euclid
Q1
如果我们知道了每个连通块的大小，如何知道构成的树的个数。
\(d_1,d_2,\cdots d_k\),\(\sum d=n\)
\[ \begin{aligned} F_k(x)&=\sum_{i=1}\frac{k^i}{(i-1)!}x^i=kx\cdot e^{kx}\\ \prod F_{d_i}(x)&=\prod d_i x^k e^{\sum d_i x}=\prod d_i x^k e^{nx}\\ [x^{2k-2}]\prod F_{d_i}(x)&=[x^{k-2}]e^{nx}\prod d_i\\ &=\frac{n^{k-2}}{(k-2)!}\prod d_i\\ \end{aligned} \]
所以答案就是 \(n^{k-2}\prod d_i\)。
然后我们先二项式反演一下。变成求钦定 \(k\) 条边相同的答案。
然后一个连通块的贡献就是 \(siz_i\times k\) 了。
发现如果我们要去维护 \(siz_i\) 那么必然会 \(n^3\)。
正确的解决办法是考虑 \(d_i\) 可以变成在这个连通块里任意选一个点的方案数。
然后此时我们只需要知道最上面的点所在连通块被没被选即可。
这样变成 \(n^2\) 的了。
10-11
T3
积和式的求解是难的，但是判断积和式是否 \(=0\) 是容易的。
这个题如果我们钦定后，那么判断积和式减去他的超集是否为 \(0\) 就好。
所以还是经典套路，把每条边随机一个权值，放入。然后计算行列式的值。
值得注意的是：行列式交换两行是要变号的！！！！。
T4
被暴力过了。/kk
树上 \(\max,+\) 背包是存在 \(nw\) 的做法的，直接按 dfs 序做，如有神助。
当然这只能处理包含根的答案。
再套上个点分树就好了。