目光呆滞

来点 Adjacent Binomial Coefficients 的无组合意义做法。

直接起手一个二元 GF $f_n(x,y)$，其中 $x^iy^j$ 项的含义是长为 $n$ 的数列，和为 $i$，最后一项为 $j$ 的答案。边界条件是 $f_0(x,y)=\frac{1}{1-xy}$，我们最后需要求的就是 $[x^my^k]f_n(x,y)$。

考虑转移 $x^iy^j\rightarrow x^{i+k}y^k$ 的系数是 $\binom{j+k}{j}$，这不禁让我们想到 $[y^k]\frac{1}{(1-y)^{j+1}}$。凑一下即可得到下面的式子：

我们发现 $f_n$ 其实就是，每次令 $y$ 变成 $\frac{1}{1-xy}$，把迭代 $1\sim n+1$ 次的结果乘起来得到的分式。

设迭代 $i$ 次的结果是 $\frac{A_i}{B_i}$，那么有：

为了方便直接让 $A_n=B_{n-1}$，$B_{n}=B_{n-1}-xA_{n-1}$。

然后我们可以发现，因为 $A_n=B_{n-1}$，所以连乘的上一项分母和下一项分子总是能抵消的，因此最后有 $f_n=\frac{1}{B_{n+1}}$。

把 $A_n=B_{n-1}$ 带入 $B$ 的递推式，有 $B_n=B_{n-1}-xB_{n-2}$，边界为 $B_0=1,B_1=1-xy$。

如果 $B_0=B_1=1$，那么 $[x^i]B$ 相当于是递推时选了 $i$ 次 $n-2$，剩下的 $n-2i$ 次选了 $n-1$ 的方案数乘以 $(-1)^i$，因此就是 $(-1)^i\binom{n-i}{i}$。

$B_1=1-xy$ 只需要再考虑 $-xy$ 项的贡献即可，可以发现最后有 $B_{n+1}=\frac{1}{1-P-yQ}$，其中 $P,Q$ 都是关于 $x$ 的多项式。

那么最后问题就是求出 $[x^my^k]\frac{1}{1-P-yQ}$，直接展开可得：

因此使用多项式 $\ln,\exp$ 即可做到 $O(m\log m)$。