神树大人挥动魔杖 题解
Aleph1022
·
·
题解
首先设一个简单的东西 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-二项式系数即可。