「赛后总结」暑假 CSP 模拟赛系列 2（8.1~8.3）
点击查看目录
蚌。
整活大师叉哥，/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\) 时的最小值。考虑李超线段树，支持插入查询与合并。
四个题三个概率期望，鉴定为：不可做场。
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
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\) 吧？