[ZJOI2020] 抽卡
-
题目链接
luoguP6633
uoj#588
loj#3315
-
题目大意
给定一个集合 \(S=\{a_1,a_2\dots,a_m\}\) ，随机放回抽样，问抽到存在连续元素段长为 \(k\) 的期望次数。
答案对 \(998244353\) 取模。
\(|S|=m\le2\times10^5，1\le a_i\le 2m，2\le k\le m\)，保证存在长为 \(k\) 的连续段。
-
题解
考虑所有长为 \(k\) 的连续段集合 \(K\) ，那么我们要求的就是最早出现一个元素的期望，这可以 \(min-max\) 容斥，转为求其一个子集所有元素均出现的期望。
而在集合 \(S\) 中选出特定 \(i\) 个元素的期望为 \(\sum_{j=1}^i\frac{m}{j}\) ，所以问题转化为求子集中元素并为 \(i\) 的容斥系数和。
我们考虑在容斥过程中一个极长连续段的贡献。可以发现，若我们选择了某一连续段 \([i,i+k-1]\)，那么接下来有贡献的只有选择 \([i+1,i+k]\) ，因为若选择任意开头 \(j>i+1\) 的连续段，我们关于 \((i,j)\) 中的选择不会影响并的大小，而根据二项式定理，容斥系数和为 \(0\) ，没有贡献。
那么我们可以将一个极长连续段分为若干长为 \(k+1\) 的连续段，然后计算贡献，利用生成函数，即得：
\[G_{len}(x)=\sum_{i=0}^{\lfloor \frac{len}{k+1}\rfloor}\binom{len-ik}{i}x^{ik}(x-1)^i \]那么再加上选择最后连续 \(k\) 个的贡献，一个长为 \(len\) 的极长连续段贡献即为：
\[G_{len}(x)-x^kG_{len-k}(x) \]\(G\) 以及最后合并答案均可以分治 \(FFT\) 实现，复杂度 \(\mathcal O(m\log^2m)\) 。