前言

本文为洛谷省选计划 2021 Week 3 的做题记录。

每道题的超链接后面都有该题的通过状态，其中 AC 表示已经通过，NC 表示未完成。

正文

题解：

考虑将 0∼T−10 \sim \text{T} - 1 内的数以 lcm⁡(P,Q)\operatorname{lcm}(\text{P}, \text{Q}) 为块长分块，那么问题就转化为求出每一块的答案和最后一块的答案。

先考虑如何求出每一块的答案，注意到对于一对 Ai\text{A}_i 和 Bj\text{B}_j，它们合法当且仅当 gcd⁡(P,Q)∣∣Ai−Bj∣\gcd (\text{P}, \text{Q}) \mid |\text{A}_i - \text{B}_j|，那么我们求出 Ai\text{A}_i 和 Bj\text{B}_j 在模 gcd⁡(P,Q)\gcd(\text{P}, \text{Q}) 的每一个剩余系中的个数，然后相乘并求和即可。

再考虑如何求出最后一块的答案，我们枚举所有的 Ai\text{A}_i，它能贡献到的所有 Bj\text{B}_j 即为 (Ai+P⋅k) mod Q (k∈N)(\text{A}_i + \text{P}\cdot k ) \bmod \text{Q}~(k \in \N)，这个差分即可。

代码实现

题解：

对于相邻的两层玻璃，我们有办法将它们合并为一层玻璃，并求出它的透光率和反射率。

具体地，我们考虑每一个局面：前 ii 层玻璃的透光率和反射率分别为 P\text{P} 和 Q\text{Q}（i=0i = 0 时 P=1,Q=0\text{P} = 1,\text{Q} = 0），现在我们要将第 i+1i +1 层的玻璃合并进来，设合并后的玻璃的透光率和反射率分别为 P′\text{P}' 和 Q′\text{Q}'，那么有：

P′=ai+11−Q⋅bi+1Q′=bi+1+Q⋅ai+121−Q⋅bi+1\begin{aligned} \text{P}' &= \frac{a_{i +1}}{1 - \text{Q} \cdot b_{i +1}} \\ \text{Q}' &= b_{i+1} + \frac{\text{Q} \cdot a_{i+1}^2}{1 - \text{Q} \cdot b_{i + 1}} \end{aligned}

直接依次枚举每一层玻璃做即可。

代码实现

题解：

问题转化为求有多少个大小为 nn 的堆。

由于堆的结构是确定的，因此 DP\mathcal{DP} 是平凡的。

注意由于 mm 可能不超过 nn，因此要用Lucas\mathcal{Lucas} 定理求组合数。

代码实现

题解：

设 nn 的答案为 fnf_n，那么有递推式 fn=fn−1+fn−2⋅2+1f_n = f_{n - 1} +f_{n - 2} \cdot 2 + 1，其意义为花费 fn−2⋅2+1f_{n - 2} \cdot 2 +1 的代价把第 nn 个环卸下，然后转化为 n−1n - 1 的子问题。

对其稍加推导可得另外一个递推式 fn=fn−1⋅2+[n≡1(mod2)]f_n = f_n - 1\cdot 2 + [n \equiv 1 \pmod{2}]，然后将答案转化为二进制可以得到 101010⋯101010\cdots 的形式，再将其乘 33 又可以得到 fn=⌊2n+13⌋\displaystyle f_n = \lfloor\frac{2^{n +1}}{3}\rfloor。

用压位高精做即可。

代码实现

题解：

对于一个数 xx，若它在 [l,r][l, r] 中不存在小于它的因数，那么可以发现答案只和 xx 这一类数有关。

我们可以通过欧拉筛求出每个数的最小质因子，以判断 [l,r][l, r] 中的每个数是否合法（注意这里要特判 11 的情况）。

求出来这一类数的数量后，我们枚举最后一个这一类数出现在哪里，然后简单计数即可。

代码实现

题解：

先将答案的表达式进行一定的变形：

∑i=0nf(i)⋅xi⋅(ni)=∑i=0nxi⋅(ni)∑j=0maj⋅ij=∑j=0maj∑i=0nxi⋅(ni)⋅ij=∑j=0maj∑i=0nxi⋅(ni)∑k=0min⁡(i,j){jk}⋅(ik)⋅k!=∑k=0mk!∑j=kmaj⋅{jk}∑i=knxi⋅(ni)⋅(ik)=∑k=0mnk‾∑j=kmaj⋅{jk}∑i=knxi⋅(n−ki−k)=∑k=0mnk‾⋅xk∑j=kmaj⋅{jk}∑i=0n−kxi⋅(n−ki)=∑k=0mnk‾⋅xk⋅(x+1)n−k∑j=kmaj⋅{jk}\begin{aligned} &\sum_{i = 0}^n f(i) \cdot x^i \cdot \binom{n}{i} \\ =&\sum_{i = 0}^n x^i\cdot \binom{n}{i} \sum_{j =0}^ma_j \cdot i^j \\ =&\sum_{j = 0}^ma_j\sum_{i = 0}^nx^i \cdot \binom{n}{i} \cdot i^j \\ =&\sum_{j = 0}^ma_j\sum_{i =0}^nx^i\cdot \binom{n}{i} \sum_{k = 0}^{\min(i, j)} \begin{Bmatrix}j\\k\end{Bmatrix}\cdot \binom{i}{k} \cdot k! \\ =&\sum_{k = 0}^{m}k!\sum_{j = k}^m a_j \cdot \begin{Bmatrix}j\\k\end{Bmatrix}\sum_{i = k}^nx^i\cdot\binom{n}{i}\cdot\binom{i}{k} \\ =&\sum_{k = 0}^{m} n^{\underline{k}} \sum_{j = k}^m a_j \cdot \begin{Bmatrix}j\\k\end{Bmatrix}\sum_{i = k}^nx^i\cdot\binom{n - k}{i - k} \\ =&\sum_{k = 0}^{m} n^{\underline{k}} \cdot x^k\sum_{j = k}^m a_j \cdot \begin{Bmatrix}j\\k\end{Bmatrix}\sum_{i = 0}^{n - k}x^i\cdot\binom{n - k}{i} \\ =&\sum_{k = 0}^{m} n^{\underline{k}} \cdot x^k \cdot (x +1)^{n - k}\sum_{j = k}^m a_j \cdot \begin{Bmatrix}j\\k\end{Bmatrix} \end{aligned}

这些项维护起来都十分简单，于是就做完了。

代码实现

题解：

二叉树具有很好的可合并性质，因此我们可以考虑对于每一个大小 ii 都计算其答案，每次枚举其左右子树大小并 O(1)\mathcal{O}(1) 地转移，这样做的时间复杂度便是 O(n2)\mathcal{O}(n^2) 的。

具体地，对于所有大小为 nn 的合法的二叉树，我们设 fnf_n 表示其个数，gng_n 表示其答案，hnh_n 表示所有合法的二叉树中每个点到根节点的距离的总和，转移不难但有些细节。

代码实现

题解：

考虑容斥，枚举 ii 表示钦定 ii 组学生讨论蔡徐坤的方案数，那么它需要带上一个容斥系数 (−1)i(-1)^i。

首先钦定 ii 组的方案数为 (n−i⋅3i)\displaystyle \binom{n - i \cdot 3}{i}，对于剩下的位置，如果我们分别枚举每一种学生的出现次数，那么即使用前缀和优化也只能做到 O(n3)\mathcal{O}(n^3) 的时间复杂度，不过我们可以先枚举前两种学生的出现次数，在分别枚举每一种学生的出现次数，这样用前缀和优化可以做到 O(n2)\mathcal{O}(n^2) 的时间复杂度。

值得一提的是，本题存在一个基于 NTT\mathcal{NTT} 的、时间复杂度为 O(n2log⁡2n)\mathcal{O}(n^2\log_2 n) 的做法，并且能够用和上述做法本质相同的方式将其时间复杂度优化至 O(n2)\mathcal{O}(n^2)。

代码实现

题解：

考虑将 (n⋅ki)\displaystyle \binom{n\cdot k}{i} 写成 [xi](x+1)n⋅k[x^i](x +1)^{n\cdot k} 的形式，那么问题转化为将 (x+1)n⋅k(x + 1)^{n \cdot k} 中所有  mod k=r\bmod k = r 的项的系数求和。

我们先 O(k2)\mathcal{O}(k^2) 地预处理组合数并求出 (x+1)k(x + 1)^k，然后做快速幂 + 循环卷积即可，时间复杂度为 O(k2+k2log⁡2n)\mathcal{O}(k^2 + k^2 \log_2n)。

本题的另外一个做法是考虑组合数的递推式，然后用矩阵快速幂加速递推，时间复杂度为 O(k3log⁡2n)\mathcal{O}(k^3\log_2n)。

代码实现

题解：

首先我们不考虑任何限制，算出任意两点间的最短距离和，这个分横竖讨论一下即可。

接下来考虑去掉不合法的点对的贡献。

第一种是两点在同一个障碍内的情况，这个用上面的方法算即可。

第二种是两点不在同一个障碍内，但至少一个点在障碍内的情况，这个也可以分横竖讨论。

然而第二种情况会算重，算重的部分为两点在不同障碍内的情况，这个我们把障碍排序，然后横竖各扫一遍即可。

最后我们还需要加上绕路的贡献。

对于一个上下长为 lenlen 的障碍，它的贡献为 2⋅∑i=1len∑j=1lenmin⁡(i,len−i+1,j,len−j+1)\displaystyle 2 \cdot \sum_{i = 1}^{len}\sum_{j = 1}^{len} \min (i, len - i +1, j, len - j +1)。

考虑偶数的情况，设 len′=len2len' = \dfrac{len}{2}，那么原式可以化为 8⋅∑i=1len∑j=1lenmin⁡(i,j)\displaystyle 8 \cdot \sum_{i = 1}^{len} \sum_{j = 1}^{len} \min (i, j)，这个对每个数讨论其作为 min⁡(i,j)\min(i, j) 的次数即可。奇数的情况仅需多讨论一种很小的情况即可。

代码实现

题解：

注意到 nn 很小，因此我们可以考虑枚举行的翻转状态 SS，然后再考虑列的翻转状态。

对于一列的初始状态 TT，它的贡献为 00 和 11 的出现次数的较小值，记其为 fTf_T。注意到一列的初始状态 TT 在行的翻转 SS 过后得到的状态为 T xor ST~\texttt{xor}~S，不妨设初始状态 TT 的出现次数为 gTg_T，设翻转状态 SS 的答案为 ansSans_S，那么有 ansS=∑T xor U=SfT⋅gU\displaystyle ans_S = \sum_{T~\texttt{xor}~U = S}f_T \cdot g_U，这其实就是一个异或卷积，用 FWT\mathcal{FWT} 求解即可。

代码实现

题解：

设 fif_i 表示至少有 ii 种颜色满足要求的方案数，gig_i 表示恰好有 ii 种颜色满足要求的方案数。

fif_i 可以简单计算，列出二者的关系式也不难，二项式反演后用 NTT\mathcal{NTT} 加速计算即可。

代码实现

题解：

设 sign⁡(x)\operatorname{sign}(x) 表示 (−1)x(-1)^x。

可以发现对于任意两条路径 P,Q\text{P},\text{Q}，所有 i∈(1,k)i \in (1, k) 对应的 sign⁡(Pi−Qi)\operatorname{sign}(\text{P}_i - \text{Q}_i) 都会贡献两遍，也就是说，答案仅和起点和终点有关。

套上 LGV\mathcal{LGV} 引理的板子即可。

代码实现

题解：

考虑全期望公式，对于每个字符 cc，统计最终整个字符串全部为这个字符的期望步数。由于这是条件期望，把它再乘上对应的概率即可。

先考虑如何求概率。设 pip_i 表示当前整个字符串包含 ii 个字符 cc，最终能够到达目标状态的概率。转移显然有 pi=i⋅(n−i)n⋅(n−1)⋅(pi−1+pi+1)+(1−2⋅i⋅(n−i)n⋅(n−1))⋅pi\displaystyle p_i = \frac{i \cdot (n - i)}{n \cdot (n - 1)}\cdot (p_{i - 1} +p_{i +1}) +(1 - \frac{2 \cdot i \cdot (n - i)}{n \cdot (n - 1)})\cdot p_i，整理可得 pi=pi−1+pi+12p_i = \dfrac{p_{i - 1}+p_{i +1}}{2}，又根据 p0=0p_0 = 0 和 pn=1p_n = 1 可得 pi=inp_i = \dfrac{i}{n}。

再考虑如何求期望。设 fif_i 表示在能够到达目标状态的前提下，当前整个字符串包含 ii 个字符 cc，最终到达目标状态的期望步数。注意由于 fif_i 是条件期望，因此转移时还需乘上相应的概率，即 fi=i−12⋅i⋅fi−1+i+12⋅i⋅fi+1+n⋅(n−1)2⋅i⋅(n−i)\displaystyle f_i = \frac{i - 1}{2 \cdot i} \cdot f_{i - 1} +\frac{i+ 1}{2\cdot i}\cdot f_{i+ 1} + \frac{n\cdot (n - 1)}{2\cdot i \cdot (n - i)}（注意要特判 f1f_1 的转移）。求解方程组可以用高斯消元做到 O(n3)\mathcal{O}(n^3)，但由于转移实际上是链状的，并且 fn=0f_n=0，因此可以用待定系数法做到 O(n)\mathcal{O}(n)。

代码实现

题解：

根据期望的线性性，考虑每个节点最后存在标记的概率，再根据古典概型的性质，转化为计数问题。

每个时刻，每个节点存在三种状态：自己存在标记、自己不存在标记但自己的祖先存在标记以及自己和自己的祖先都不存在标记。我们可以很容易的求出它们之间的转移系数，这样我们就得到了一个 O(nk)\mathcal{O}(nk) 的做法。

状态只有三种，转移式是线性的，转移系数是固定的。综合这三点，我们用矩阵快速幂加速转移即可。

代码实现

题解：

对答案的表达式进行莫比乌斯反演，那么关键的问题在于求解图中所有生成树的边权和之和。

对于一条边，设其原本的边权为 ww，我们不妨将其表示为二项式 w⋅x+1w\cdot x +1，然后根据矩阵树定理对基尔霍夫矩阵求行列式，那么答案即为行列式的 xx 项系数。

代码实现

题解：

考虑把求第 kk 小转化为求第 n−k+1n - k + 1 大，根据扩展 min⁡−max⁡\min - \max 容斥，问题转化为求 ∑T≠∅(−1)∣T∣+k⋅(∣T∣−1k−1)⋅E(min⁡(T))\displaystyle \sum_{T \ne \emptyset} (-1)^{|T| + k} \cdot \binom{|T| - 1}{k - 1}\cdot \text{E}(\min(T))。

这个问题直接做必然是不行的，不过我们可以注意到 mm 很小，并且有 E(min⁡(T))=m∑i∈Tpi\text{E}(\min(T)) = \dfrac{m}{\displaystyle \sum_{i \in T} p_i}，那么我们可以考虑把 ∑i∈Tpi\displaystyle \sum_{i \in T} p_i 记入状态中，跑一个背包 DP\mathcal{DP}。

然而直接做还需要记录 ∣T∣|T| 这一维，不过由于 (∣T∣−1k−1)=(∣T∣−2k−1)+(∣T∣−2k−2)\displaystyle \binom{|T| - 1}{k - 1} = \binom{|T| - 2}{k - 1} +\binom{|T| - 2}{k - 2}，那么我们多记录 kk 这一维即可省掉 ∣T∣|T| 这一维，由于 kk 很小，因此时间复杂度是可接受的。

代码实现

题解：

先将答案的表达式进行一定的变形：

∑i=0n∑j=0i2j⋅j!⋅{ij}=∑j=0n2j⋅j!∑i=0n{ij}=∑j=0n2j⋅j!∑i=0n∑k=0jkik!⋅(−1)j−k(j−k)!=∑j=0n2j⋅j!∑k=0j(−1)j−kk!⋅(j−k)!∑i=0nki=∑j=0n2j⋅j!∑k=0j(−1)j−k(j−k)!⋅kn+1−1k!⋅(k−1)\begin{aligned} &\sum_{i = 0}^n \sum_{j = 0}^i 2^j \cdot j! \cdot \begin{Bmatrix}i \\ j\end{Bmatrix} \\ = &\sum_{j = 0}^n 2^j \cdot j! \sum_{i = 0}^n\begin{Bmatrix}i \\ j\end{Bmatrix} \\ = &\sum_{j = 0}^n 2^j \cdot j! \sum_{i = 0}^n \sum_{k = 0}^j \frac{k^i}{k!} \cdot \frac{(-1)^{j - k}}{(j - k)!} \\ = &\sum_{j = 0}^n 2^j \cdot j! \sum_{k = 0}^j \frac{(-1)^{j - k}}{k! \cdot (j - k)!} \sum_{i = 0}^n k^i \\ = &\sum_{j = 0}^n 2^j \cdot j! \sum_{k = 0}^j \frac{(-1)^{j - k}}{(j - k)!} \cdot \frac{k^{n + 1} - 1}{k!\cdot(k - 1)} \end{aligned}

可以发现后面的部分呈卷积形式，用 NTT\mathcal{NTT} 优化即可。

代码实现

未完待续 ……