Day4 B
#####题意
\(n\) 个点的树，\(q\) 次询问，每次给定 \(k\) 个点，求其点导出子图的联通无序点对个数 \(n\leq250000,\sum k\leq1000000\)
做法
每个联通块必有一个最上方的点，将连通块记到最上方那个点计算贡献即可
Day4 E
题意
两个串 \(s,t\) ，从中分别取一个非空子串 \(s',t'\)，拼接起来，求字典序第 \(k\) 小的串，两个串不同当且仅当拼接成该串的 \(s'\) 或 \(t'\) 不同。
\(\lvert s\rvert, \lvert t\rvert\leq75000,k\leq1e18\)
做法
按位考虑，转化为了求以某个串的为前缀串的数量有多少。考虑对于一个确定的拼接后的串 \(H\)，计数其可能的拼接方法。
对两个串分别建 SAM，可以求得该串的前缀最长可以匹配 \(s\) 的哪一个子串和后缀匹配那一个 \(t\) 中的哪一个子串，然后就可以计数这个串的个数，以及以该串为前缀的串的个数，就可以逐位考虑。
Day4 H
题意
给定一个已经确定了一些位置的 \(n\) 的排列，输出任意合法的补出方案，使得满足 \[ \lvert p_i - p_{i+1}\rvert\neq1(1\leq i\leq n - 1) \] \(n\leq200000\)
做法
对于一个未确认的位置，周围最多对它有 4 个数的限制，所以前面的未确认的位置一定能够填
当有对于 8 个未填位置，将其匹配看做一个二分图，左侧每个点至少于右边 4 个点连边，右边亦然。
对于左边集合大小为 1,2,3,4 的点集，由于肯定于右边至少 4 个点连边，满足 Hall 定理，而对于大于等于 5 个点的点集，由抽屉原理肯定与右边所有点连边，也满足 Hall 定理，所以一定有完备匹配。
所以大于 8 个未填位置的，先任意填至剩 8 个，其余情况可以直接暴力。
Day4 L
题意
给定 \(n,k\) 以及 \(a_0,...,a_k\)，求定义一个任意两点间路径数不超过 \(k\) 的图的权值为 \(\prod_{i,j} a_{f(i,j)}\)，其中 \(f(i,j)\) 为两点间路径数，求所有 \(n\) 个点的任意两点间路径数不超过 \(k\) 的图权值和。
\(n\leq100000,k\leq3\)
做法
首先容易发现 k = 3 的情况与 k = 2 相同。对于 k = 0 时，显然没有任何边，k = 1 时，符合条件的图为森林，k = 2 时，图为森林和基环树森林，分别对不同类型的连通块计算贡献。
对于森林，n个点有标号无根树数量为 \(n^{n - 2}\)，而其贡献的 \(f_{i,j} = 1\) 的点对数量为 \(\frac{i * (i -1)}{2}\) ，不妨将所有的点对都默认为 \(a_0\) 的贡献，而联通块只是替换一定数量的点对，那么一个大小为 \(n\ (n\geq2)\) 的森林的贡献就是 \[ H_n = n^{n-2} (\frac{a_1}{a_0})^{\binom{i}{2}} \] 由于有标号，拼接时要带上组合数，有其生成函数为 \(H(x) =\sum_{k\geq2}H_k\frac{x^k}{k!}\)，而对于拼接时，由于相同大小联通块内部分配无序所以拼接的生成函数为 \(\exp({H(x))}\)。
对于基环树，对于同一棵树内的 f 为 1 ，不同的为 2，可以仍然使用替换的思路计算，先全部另为 2，再在没棵树内替换为 1。基环树为若干有根树的环排列，这里有根树的生成函数为 \[ T(x) = \sum_{k\geq1} (k^{k - 1}) (\frac{a1}{a2})^{\binom{k}{2}}\frac{x^k}{k!} \] 基环树的生成函数就是 \[ L(x) = \frac{1}{2}\sum_{k\geq3}\frac{T(x)^k}{k}=\frac{1}{2}(-\ln(1-T(x)) -\frac{T(x)^2}{2}-T(x)) \] 同样对于基环树的拼接也是 \(\exp(L(x))\)
所以对于 k = 0 时，答案的生成函数为 \(e^x\)，k = 1 时为 \(\exp(x + H(x))\)， k = 2 时为 \(\exp(x + H(x) + L(x))\)