除了老生常谈的拉格朗日反演之外,还有一个 dp + 分治 NTT 的做法.
问题转化
每经过一个非终止状态,步数都会加一,答案可以转化为每个非终止状态期望经过的次数之和.
考虑一个有 $i$ 张牌的非终止状态,会经过它的概率是 ${\binom m i}^{-1}$ ,到达它之后期望停留的步数为 $\frac{m}{m-i}$ .
如果我们能求出 $cnt(i)$ ,表示有 $i$ 张牌的非终止状态(即不存在 k-顺子 的状态)的数目,那么答案就是
$$
ans=\sum_{i=0}^{m-1} \binom m i^{-1}\frac m {m-i}\cdot cnt(i)
$$
dp 设计
每个值域连续段可以分开计算,最后卷在一起.于是只需要求出牌为 $1,2,3,\dots,m$ 时,有 $i$ 张牌的非终止状态数目.
设 $dp(i,j)$ 表示考虑了前 $i$ 张牌,选了 $j$ 张牌,且没有出现 k-顺子的方案数.
讨论第 $i$ 张牌选不选,再减去选了 $i$ 出现的不合法的情况,即 $i-k+1,\dots i$ 这些牌形成了 k-顺子,而 $i-k$ 没有被选.
$$
dp(i,j)=dp(i-1,j-1)+dp(i-1,j)-dp(i-k-1,j-k)
$$
我们需要求出每个 $dp(m,j)$ ,按照转移式朴素地进行 dp 是 $O(m^2)$ 的.
分治 NTT 优化
考虑将每个 $dp(i)$ 用一个多项式 $F_i$ 表示,即,设 $F_i=\sum_{j=0}^i dp(i,j)\cdot x^j$ ,那么转移式可以表示成
$$
F_i=(x+1)F_{i-1}-x^k\cdot F_{i-k-1}
$$
可以看成是上楼梯,每次上 $1$ 级有 $x+1$ 种方案,每次上 $k+1$ 级有 $-x^k$ 种方案,枚举上 $k+1$ 级的次数,可得
$$
F_m=\sum_{i=0}^{\lfloor m /(k+1)\rfloor}(-x^k)^{i}\cdot (x+1)^{m-i(k+1)}\cdot \binom{m-ik}{i}
$$
考虑利用分治 NTT 优化,令 $n=\lfloor m /(k+1)\rfloor$ ,
$$
\begin{aligned}
F_m&=\sum_{i=0}^{\lfloor m /(k+1)\rfloor}(-x^k)^{i}\cdot (x+1)^{m-i(k+1)}\cdot \binom{m-ik}{i}\\
&=(x+1)^{m\bmod (k+1)}\sum_{i=0}^{n}(-x^k)^i\cdot [(x+1)^{(k+1)}]^{(n-i)}\cdot\binom{m-ik}{i}
\end{aligned}
$$
令 $A=-x^k,B=(x+1)^{k+1},coef_i=\binom{m-ik}{i}$ ,则后面那个式子就是 $\sum_{i=0}^n A^i\cdot B^{n-i}\cdot coef_i$ .
设 $G(l,r)=\sum_{i=l}^r A^{i-l} B^{r-i}coef_i$ ,则 $G(l,r)=G(l,mid)\cdot B^{r-mid}+G(mid+1,r)\cdot A^{mid+1-l}$ .
时间复杂度 $O(m\log^2 m)$ .
注意当 $i=k$ 时也有 $-x^k\cdot F_{i-k-1}$ 的转移,答案应该是 $G(0,m) + [m\ge k]x^k\cdot G(0,m-k)$ .
1 | //%std |