题解 P6633【[ZJOI2020] 抽卡】
whiteqwq
·
·
题解
P6633 [ZJOI2020] 抽卡 解题报告：
更好的阅读体验
题意
给定一个大小为 n 的可重集，每次随机抽取一个数字（可以反复抽一个数），求组成一个长度为 k 的连续段的期望时间。
## 分析
考虑构建一个自动机模型，一共 $2^n$ 个结点表示当前取到过的数字集合，容易发现一个 $1$ 个数为 $k$ 的结点有 $k$ 个自环，以及 $n-k$ 条出边。
可以发现答案是从全 $0$ 状态走到任意结束态的期望路径长度，类似全概率公式，答案实际上是每个点被经过的概率乘期望停留时间之和。
由于图是分层的，可以算出走到 $k$ 层任意结点的概率都是 $\dfrac{1}{{n\choose k}}$，期望停留时间为 $\dfrac{n}{n-k}$，我们只需要对于每一个 $k$ 算出非终止状态的结点数量与其相乘即可。
发现值域不处于一个连续段的数字互不影响，将数字分割成若干连续段，最后使用分治 FFT 合并即可。
令 $f_{i,j}$ 表示当前连续段考虑到第 $i$ 个数字，选择了 $j$ 个数字的非终止态数量，列出 dp 方程：
$$f_{i,j}=\begin{cases}f_{i-1,j-1}+f_{i-1,j}-f_{i-k-1,j-k}&i\geqslant 0\\ [j=0] & i=-1\end{cases}$$
这里将状态定义到 $-1$ 的原因是便于 $f_{k,k}$ 的定义。
将 dp 刻画成生成函数的形式：
$$F_i(x)=\begin{cases}(1+x)F_{i-1}(x)-x^kF_{i-k-1}(x)&i\geqslant 0\\1&i=-1\end{cases}$$
根据 [P6811 「MCOI-02」Build Battle 建筑大师](https://www.luogu.com.cn/problem/P6811) 中的技巧，观察到每次减 $k+1$，枚举用了多少次，于是可以算出走了多少次 $-1$，得到了 $F_i(x)$ 的通项：
$$
G_m(x)=\sum_{i=0}^{\lfloor\frac{m}{k+1}\rfloor}{i+m-(k+1)i\choose i}(-x^k)^i(1+x)^{m-(k+1)i}\\=\sum_{i=0}^{\lfloor\frac{m}{k+1}\rfloor}{m-ik\choose i}(-1)^ix^{ik}(1+x)^{m-(k+1)i}\\
F_m(x)=G_i(x)-x^kG_{i-k}(x)
$$
减去后面的东西是因为 $F_{-1}(x)$ 直接跳一步 $x^k$ 是不合法的。
令 $L=\lfloor\frac{m}{k+1}\rfloor,r_i={m-ik\choose i}(-1)^i,P(x)=x^k,Q(x)=(1+x)^{k+1}$，那么：
$$G_m(x)=(1+x)^{m\bmod(k+1)}\sum_{i=0}^L P^i(x)Q^{L-i}(x)r_i$$
可以使用分治 FFT 分治计算后面那个求和式：
$$G'(x)=(\sum_{i=0}^{\lfloor\frac{L}{2}\rfloor}P^i(x)Q^{\lfloor\frac{L}{2}\rfloor-i}r_i)\times Q^{\lceil\frac{L}{2}\rceil}(x)\\+(\sum_{i=0}^{\lceil\frac{L}{2}\rceil} P^i(x)Q^{\lceil\frac{L}{2}\rceil}r_{\lfloor\frac{L}{2}\rfloor+i})\times P^{\lfloor\frac{L}{2}\rfloor}(x)$$
那么你只需要在分治 FFT 的时候维护一下 $H_{l,r}$ 以及 $Q^L(x)$ 即可。（与 $P$ 做乘法直接平移就好了）
时间复杂度 $O(n\log^2n)$。
## 代码
注意长度 $d$ 小于 $k$ 的连续段也需要作为 $(1+x)^d$ 乘到答案里。（调了好久）
[AC 代码](https://loj.ac/s/1339356)