[ZJOI2020] 抽卡

• 题目链接

  luoguP6633

  uoj#588

  loj#3315

• 题目大意

  给定一个集合 (S={a_1,a_2dots,a_m}) ，随机放回抽样，问抽到存在连续元素段长为 (k) 的期望次数。

  答案对 (998244353) 取模。

  (|S|=mle2 imes10^5，1le a_ile 2m，2le kle m)，保证存在长为 (k) 的连续段。

• 题解

  考虑所有长为 (k) 的连续段集合 (K) ，那么我们要求的就是最早出现一个元素的期望，这可以 (min-max) 容斥，转为求其一个子集所有元素均出现的期望。

  而在集合 (S) 中选出特定 (i) 个元素的期望为 (sum_{j=1}^ifrac{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} floor}inom{len-ik}{i}x^{ik}(x-1)^i ]

  那么再加上选择最后连续 (k) 个的贡献，一个长为 (len) 的极长连续段贡献即为：

  [G_{len}(x)-x^kG_{len-k}(x) ]

  (G) 以及最后合并答案均可以分治 (FFT) 实现，复杂度 (mathcal O(mlog^2m)) 。