自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:19:06，当前版本为作者最后更新于2021-05-07 18:45:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先设一个简单的东西 $h_i$ 表示一个人走到 $i$ 的方案数，就是

$$h_i = ph_{i-1} + qh_{i-2},\quad h_0=0,h_1=1$$

然后考虑原问题，容易想到容斥，我们强制某些格子不被踩过，然后将容斥系数附到答案里。
设 $g_i$ 表示所有人走到 $i$ 并强制不经过 $i-1$ 及若干个格子的方案数，枚举上一个强制不经过的格子，就有

$$g_i = -\sum\limits_{j=1}^{i-2}(qh_{i-j-1})^mg_j,\quad g_0=0,g_1=1 $$

再设 $f_i$ 表示所有人按照条件走出 $i$ 的方案数，同样枚举最后一个强制不经过的格子，就有

$$f_i = \sum\limits_{j=1}^i (h_{i-j+1}+qh_{i-j})^mg_j $$

然后我们必然可以把 $h$ 的 GF $H$ 分解成 $\frac A{1-\alpha x}+\frac B{1-\beta x}$，其具体值留作读者练习。
再考虑 $h$ 的 $m$ 次方数列，$\hat h$，设其 GF 为 $\widehat H$，自然

$$\begin{aligned} \widehat H(x) &= \sum\limits_{i\ge 0} x^i \sum\limits_{j=0}^m \binom mj A^j \alpha^{ij} B^{m-j} \beta^{i(m-j)} \\ &= \sum\limits_{j=0}^m \binom mj A^j B^{m-j} \sum\limits_{i\ge 0} x^i \alpha^{ij} \beta^{i(m-j)} \\ &= \sum\limits_{j=0}^m \binom mj A^j B^{m-j} \frac 1{1-\alpha^j \beta^{m-j} x} \end{aligned} $$

分治 NTT 计算，设 $\widehat H = \frac PQ$，而注意到 $f,g$ 转移时卷上的数列与 $\hat h$ 的递推式显然相同，因此它们 GF 的分母都是 $Q$，从而容易将它们也写作有理分式。
进一步可以将 $F$ 写作有理分式，然后问题转化为常系数线性齐次递推。
总时间复杂度 $O(m \log m(\log n+\log m))$。

Update： 求解 $\widehat H$ 的分母，只需计算 q-二项式系数即可。