我能在患有生成函数症的情况下做出本题吗？

· · 题解

首先考虑

\mathbb E[T] = \sum_{k \in \mathbb Z_{\ge 0}} \mathbb P[T > k],

并定义：A_i(t) 为前 t 轮没有一个是 i 这一事件（\mathbb P[A_i(t)] 等于 (1-p_i)^t），则 \mathbb P[T > k] 等价于在 k 时刻，控制的卡数小于 N-K。现在假设 X(t) 是控制的卡数这一随机变量，Y(t) = N-X(t)，可以发现：

\begin{aligned} \sum_{x=r}^{N} \mathbb P[Y(t) = x] \binom xr &= \sum_{|S|=r} \mathbb P\left[t\ \text{时卡组}\subset S^\complement\right] \\ &=\sum_{|S|=r} \mathbb P\left[\bigcap_{x \in S} A_x(t)\right]. \end{aligned}

根据二项式反演，计算得到

\mathbb P[Y(t) = x] = \sum_{r=x}^m (-1)^{r-x} \binom{r}{x} \sum_{|S|=r} (1 - p_S)^t.

进一步：

\mathbb P[T>t] = \sum_{r=k+1}^m \underset{C(r,k)}{\underbrace{\left[ \sum_{x=k+1}^r (-1)^{r-x} \binom{r}{x} \right]}} \sum_{|S|=r} (1 - p_S)^t.

可以发现

\begin{aligned} C(r,k) &= - \sum_{x=0}^k (-1)^{r-x} \binom rx \\ &= (-1)^{r-1} [x^k] \dfrac{(1-x)^r}{1-x} \\ &= (-1)^{r-1-k} \binom{r-1}{k}. \end{aligned}

也即

\begin{aligned} \mathbb E[T] &= \sum_{r=K+1}^m (-1)^{r-K-1} \binom{r-1}{K} \sum_{|S|=r} \frac{1}{p_S} \\ &= \sum_{r=K+1}^m [x^K] (x-1)^{r-1} \sum_{|S|=r} \dfrac 1{p_S} \\ &= [x^K] \sum_{S \ne \varnothing} \dfrac{(x-1)^{|S|-1}}{p_S}. \end{aligned}

利用 p_S = \dfrac{n_S}{M} 的特性，同时将 p_S 列入到二元生成函数中

R(x,z) = \prod_{i=0}^{N-1} (1+(x-1)z^{n_i}),

则

\mathbb E[T] = [x^K] \sum_{\ell = 0}^{M} \dfrac{M [z^\ell] R}{\ell (x-1)}.

在 \operatorname{mod} x^{K+1} 下，G_k = [z^k] R 可以由如下过程得到：枚举 i = 0,1,\dots,N-1，枚举 w = M,M-1,\dots,1，让：

G_k \gets G_k + G_{k - n_i} \cdot (x-1) \pmod{x^{K+1}}.

则最后得到的就是 [z^k] R（这是直接由转移式推的）。留意

\dfrac{1}{x-1} \equiv \sum_{j=0}^K x^j \pmod{x^{K+1}},

就能从 G_k 中提取答案。时间复杂度是 \Theta(NMK) 的。

当然也可以用二维的分治乘法直接乘出 R，时间复杂度 \Theta(\mathsf{M}(MK) \log N)。