山东二轮省集题解合集

Day1

A

打表，发现答案是 \(\prod\limits_{i=1}^n (2i-1)\)。

证明可以考虑拿 GF 推。

首先有 dp,\(f(i,j)\) 表示到第 \(i\) 个括号当前左括号减右括号的个数为 \(j\)，转移是简单的 \(f(i,j)=f(i,j+1)+f(i,j-1)\times (j-1)\) 把 \(f(i,j)\) 写成一个形式幂级数的形式，那么有 \(F_i=\sum\limits_{j=0}^n c_jx^j\)。第 \(j\) 项对应 \(f(i,j)\)。那么我们的转移可以对应写成 \(F_i=xF_{i-1}+F_{i-1}'\)。

两边同时乘上一个 \(e^{-\frac{x^2}{2}}\)，换元得到 \(G_i=G_{i-1}'\)。起始项为 \(G_0=e^{\frac{-x^2}{2}}\)，那么导 \(2n\) 次出来的就是 \((2n-1)!!\)。

B

线性代数在 oi 中没有用。

C

首先把询问的贡献拆开，每一条链的答案实际上是距 \(x\) 不超过 \(k\) 的点数再加上下面那一段距离 \(son_x\rightarrow y\) 每一个点距离为 \(k\) 的答案。

那么就变成了两个问题，一个一个考虑。

对于第一个问题，考虑容斥。改为统计距离 \(x\) 为 \(k\) 的点的子树 \(siz\) 的和，最后拿 \(x\) 的子树大小减去。这样能归约到第二个问题里面去。

对于第二个问题，考虑把每一条链重剖，那么我们要统计的本质上是到链顶的所有轻儿子内到链顶距离不超过 \(k\) 的点的个数，和下面那一段里面距离为 \(k\) 的点的个数。那么我们也把这两种问题分开做。

我们对于每一条重链，预处理出来距离为 \(k\) 的点数的和。这个直接枚举每一条重链，加入其所有轻儿子预处理即可。由于所有轻子树的大小和是 \(O(n\log n)\) 的，所以这部分复杂度 \(O(n\log n)\)。

然后长链剖分（本质是 dsu on tree），处理出来每一个深度在每一个点有多少个。做一个从根到该点的前缀和，那么第二部分的答案就了，这部分复杂度是 dsu 的复杂度，也是 \(O(n\log n)\) 的。

综上，复杂度 \(O(n\log n)\)。

Day 2

A

直接两边开根，有 \(x\equiv a^{\frac{1}{k}}\pmod p\)，然后上费马小定理，有 \(x\equiv a^{k^{\varphi(p)-1}}\pmod p\)，那么对后面这部分上扩欧求 \(k\) 在模 \(\varphi(p)\) 意义下的逆元即可。注意特殊处理 \(p=2\) 的情况（\(p=2\) 时，定义 \(0^0=0\) 也可）。

B

首先有个唐氏的 \(O(\frac{n^3}{w})\) 的做法，直接拿 bitset 上去搞。

然后开始四毛子，将序列每 \(B\) 个分成一块，处理出来对于每一个块包含它的有哪些，丢到一个 bitset 里，然后答案就是把每个串的 \(\frac{n}{B}\) 个 bitset 与起来。

考虑怎么处理每一个块包含他的有哪些。把每一个块当成一个二进制数，那么我们要处理的就是每一个二进制数对应的答案。首先处理出 \(2^k,k\in[0,B-1]\) 对应的答案，然后每个数 \(x\) 从 \(x-\text{lowbit}(x)\) 转移，设 \(x\) 的对应的 bitset 为 \(f(x)\)，则有 \(f(x)=f(x-\text{lowbit}(x))\land f(\text{lowbit}(x))\)。

C

不会。

Day 3

A

开始找规律，首先发现 \(f(n,1)=f(n-1,1)+(-1)^n\frac{1}{n!}\)，接下来发现 \(f(n,k)=f(n-1,k)+(-1)^n(1-f(k,k))\frac{1}{n!}\)。而一个性质是 \(f(n,1)=f(n,n)\)，因此我们线性预处理 \(f(n,1)\)，然后大力求解后面的式子即可。

考虑一个看起来比较正确的做法，令 \(f(n,k)\) 表示答案，\(g(i)=1-f(i,1)\)，表示最左边的不被涂黑的概率，那么有 \(f(n,k)=1-g(k)g(n-k-1)\)，意味着从 \(k\) 断开，然后递归到两边处理。那么我们用上述方法预处理 \(g\) 即可。

B

网络流。考虑到最小化孤立点数本质上是最小化流量为 \(0\) 的点数，那么把每个点向对应的源汇连两条边，费用分别为 \(-\infty\) 和 \(1\) ，那么这样就会先增广 \(-\infty\) 的边，即让每个点都尽可能有流量。如果剩下一条边被经过，则意味着出现了一个大小为 \(3\) 的连通块，为了最小化，故将其费用设为 \(1\) 即可。

直接费用流会超时，但由于增广路长度只可能为 \(-2\infty\) 或 \(-\infty+1\)（这样可能有点怪），因此多路增广即可做到根号复杂度。

C

计算几何在 oi 中没有用。