~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-6 skipped

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 序做，如有神助。

当然这只能处理包含根的答案。

再套上个点分树就好了。