「赛后总结」暑假 CSP 模拟赛系列 2（8.1~8.3）

K8He / 2023-08-07 / 原文

「赛后总结」暑假 CSP 模拟赛系列 2（8.1~8.3）

点击查看目录

目录
「赛后总结」暑假 CSP 模拟赛系列 2（8.1~8.3）
20230801（letitdown round）
T2 神（~~eldenring~~）
T4 动（~~genshin~~）
20230802（Max_QAQ round 2）
T1 随
T3 A
T4 C
20230803（zero4338 round）
T2 s
T3 p
T4 m

20230801（letitdown round）

蚌。

整活大师叉哥，/bx

T2 神（eldenring）

考虑 AC 自动机，删去/加入字符串可以直接在其结尾处节点打标记，查询直接在自动机上跑，不断跳 \(\text{fail}\)。

考虑优化。我们发现删去/加入字符串只影响其结尾处节点 \(\text{fail}\) 子树，考虑对 \(\text{fail}\) 树建出 DFS 序列然后树状数组处理，区间修改，单点查询，使用差分。

CF Submission.

T4 动（genshin）

考虑设 \(f_u\) 表示从 \(u\) 节点逃离最小代价。转移方程：

\[f_u = \min_{v\text{ is in the subtree of }u} a_ub_v + f_v \]

你发现这玩意就是求一堆直线 \(y = b_vx + f_v\) 在 \(x = a_u\) 时的最小值。考虑李超线段树，支持插入查询与合并。

20230802（Max_QAQ round 2）

四个题三个概率期望，鉴定为：不可做场。

T1 随

假期望典中典！每一位的概率是可以独立计算的，而且相等，所以你只考虑每一位不在原位的概率就行了。

考虑设 \(f_{i, 0/1}\) 表示交换了 \(i\) 次，\(1\) 是否在原位的概率（\(1\) 是 \(0\) 否）。转移：

\[\begin{aligned} f_{i, 0} &= \frac{n^2 - 2}{n^2}f_{i - 1, 0} + \frac{2(n - 1)}{n^2}f_{i - 1, 1}\\ f_{i, 1} &= \frac{2}{n^2}f_{i - 1, 0} + \frac{n^2 - 2(n - 1)}{n^2}f_{i - 1, 1} \end{aligned} \]

初始状态 \(f_{0, 1} = 1\)，单个位置概率对答案贡献为 \(f_{m, 0}\)，因此答案为 \(nf_{m, 0}\)。

考虑矩阵快速幂优化，单次查询可以做到 \(O(\log_2m)\)，但是矩阵乘法常数大被卡了，最后叉哥帮我把时限从 2000ms 开到 3000ms 过的！叉哥好闪，拜谢叉哥！

另外我这个式子重定义 \(f_i\) 表示交换了 \(i\) 次，\(1\) 不在原位的概率可以写出下面这个递推式，我怀疑这玩意化简后和赛时打表老哥找的规律一样。

\[f_i = \frac{n - 2}{n}f_{i - 1} + \frac{2(n - 1)}{n ^2} \]

有没有老哥会化简，求教教。

Update：成功了！GF 大师 Rolling_star 提供超强生成函数推法！

考虑生成函数，设 \(f_k\) 的 OGF 为：

\[F(z)=\sum_{k\ge 0} f_k z^k \]

为了方便，设 \(a=\dfrac{n-2}{n}\)，\(b=\dfrac{2(n-1)}{n^2}\)

然后将 OGF 按递推式展开：

\[\begin{aligned} F(z)&=\sum_{k\ge 1} f_k z^k\\ &=\sum_{k\ge 1} (af_{k-1} z^k+bz^k)\\ &=azF(z)+b\cdot\dfrac{z}{1-z} \end{aligned} \]

解得

\[F(z)=b\cdot \dfrac{z}{(1-z)(1-az)} \]

然后分式分解：

\[F(z)=b\cdot\left[\dfrac{\frac {1}{1-a}}{1-z}-\dfrac{\frac {1}{1-a}}{1-az}\right] \]

然后就可以解出第 \(m\) 项：

\[[z^m]F(z)=b\left[\dfrac{1}{1-a}-\dfrac{1}{1-a}a^m\right] \]

进行代入：

\[\begin{aligned} [z^m]F(z) &=b\left[\dfrac{1}{1-a}-\dfrac{1}{1-a}a^m\right]\\ &=\dfrac{2(n-1)}{n^2}\left[\dfrac{1}{1-\dfrac{n-2}{n}}-\dfrac{1}{1-\dfrac{n-2}{n}}\left(\dfrac{n-2}{n}\right)^m\right]\\ &=\dfrac{2(n-1)}{n^2}\left[\dfrac{n}{2}-\dfrac{n}{2}\left(\dfrac{n-2}{n}\right)^m\right]\\ &=\dfrac{n-1}{n}\left[1-\left(\dfrac{n-2}{n}\right)^m\right]\\ &=\dfrac{n-1}{n}-\dfrac{(n-1)(n-2)^m}{n^{m + 1}}\\ &=(n-1)\left[\dfrac{n^m}{n^{m + 1}}-\dfrac{(n-2)^m}{n^{m + 1}}\right]\\ &=\dfrac{(n-1)\left[n^m-(n-2)^m\right]}{n^{m + 1}}\\ \end{aligned} \]

这个算的是一个位置贡献，最后答案要乘 \(n\)，故答案为：

\[\dfrac{(n-1)\left[n^m-(n-2)^m\right]}{n^m} \]

和打表老哥式子一模一样！！！！！好好好好好好好好好好好好好好好好好好好好好好好！！！！！！！！！！！

T3 A

设 \(f_{l, r, x, k}\) 表示 \(l\) 到 \(r\) 仅剩一张等级为 \(x\)，种类为 \(k\) 的卡牌时最大价值。特别的，\(f_{l, r, 0, 0}\) 表示 \(l\) 到 \(r\) 的区间内全扔出去了的价值。

转移：

\[\begin{aligned} f_{l, r, x, k} &= \begin{cases} \max_{i = l}^{r}\{[a_i = k](f_{l, i - 1, 0, 0} + f_{i + 1, r, 0, 0})\} &x = 1\\ \max_{i = l}^{r}\{f_{l, i - 1, x - 1, k} + f_{i, r, x - 1, k}\} &x > 1\\ \end{cases}\\ f_{l, r, 0, 0} &= \max\{\max_{i = l}^{r}\{f_{l, i, 0, 0} + f_{i + 1, r, 0, 0}\}, \max_{x \le R, k\le m}\{f_{l, r, x, k} + \operatorname{Calc}(x, k)\}\}\\ \end{aligned} \]

答案是 \(f_{1, n, 0, 0}\)。

T4 C

20230803（zero4338 round）

T2 s

考虑设 \(f_{i, j}\) 表示 \(1\sim i\) 的排列答案为 \(j\) 时的方案数。

转移时相当于在 \(1\sim i - 1\) 的排列后面插入一个数，同时更改前面数的排名。

转移方程：

\[f_{i, j} = \begin{cases} \left(\sum_{k = j}^{i - 1}f_{i - 1, k}\right) + (i - j)f_{i - 1, j} &s_i = 0\\ \left(\sum_{k = 1}^{j - 1}f_{i - 1, k}\right) + (j - 1)f_{i - 1, j - 1} &s_i = 1\\ \end{cases} \]

前缀和优化，\(O(n^2)\) 解决。

T3 p

一个厉害结论是，点集 \(S\) 的直径端点和点集 \(T\) 的直径端点中含有 \(S\cup T\) 的直径端点。

这个性质可以用于线段树的 pushup，遂用线段树维护。

倍增会被卡常，所以倍增都是邪教，快写树剖！

T4 m

设 \(f(i)\) 为至少 \(i\) 种配料出现次数小于等于一次的方案数，\(g(i)\) 为恰好 \(i\) 种配料出现次数小于等于一次的方案数。

首先答案是 \(g(0)\)，然后这玩意是个二项式反演。考虑计算 \(f(i)\)。

首先计算这 \(i\) 个调料放的方案数，选出来 \(i\) 种调料然后枚举有多少种调料出现一次然后放进多少个碗里。\(\begin{Bmatrix}i\\k\end{Bmatrix}\) 表示将 \(i\) 个有区别球分成 \(j\) 个无区别非空集合方案数。

然后考虑后边的调料瞎放，首先是这 \(k\) 碗面可以瞎放调料，然后剩下 \(2^{n - i}\) 种面选或不选。

式子就是：

\[f(i) = \dbinom{n}{i}\sum_{j = 0}^{i}\dbinom{i}{j}\sum_{k = 0}^{j}\begin{Bmatrix}j\\k\end{Bmatrix}2^{(n - i)k}2^{2^{n - i}} \]

二项式反演代入 \(g(0)\)，并交换一下运算顺序：

\[g(0) = \sum_{i = 0}^{n}(-1)^{i}2^{2^{n - i}}\dbinom{n}{i}\sum_{k = 0}^{i}2^{(n - i)k}\sum_{j = k}^{i}\dbinom{i}{j}\begin{Bmatrix}j\\k\end{Bmatrix} \]

考虑快速计算后头那一坨 \(\sum_{j = k}^{i}\dbinom{i}{j}\begin{Bmatrix}j\\k\end{Bmatrix}\)，根据组合意义有递推式：

\[F_{i, k} = (k + 1)F_{i - 1, k} + F_{i - 1, k - 1} \]

然后 \(O(n^2)\) 解决。

这个模数是 \(10^9 + 7\)，不可能有人抄成 \(10^9 + 10\) 吧？