目光呆滞
le0n
·
·
个人记录
来点 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}(x,y)=\frac{f_{n-1}(x,\frac{1}{1-xy})}{1-xy}
我们发现 f_n 其实就是，每次令 y 变成 \frac{1}{1-xy}，把迭代 1\sim n+1 次的结果乘起来得到的分式。
设迭代 i 次的结果是 \frac{A_i}{B_i}，那么有：
\frac{A_n}{B_n}=\frac{B_{n-1}}{B_{n-1}-xA_{n-1}}
为了方便直接让 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}。
那么最后问题就是求出 $[x^my^k]\frac{1}{1-P-yQ}$，直接展开可得：
$$
\begin{aligned}
[y^k]\frac{1}{1-P-yQ}&=[y^k]\sum_{i\geq 0}(P+yQ)^i\\
&=\sum_{i\geq 0}\binom{i}{k}P^{i-k}Q^k\\
&=\frac{Q^k}{(1-P)^{k+1}}
\end{aligned}
$$
因此使用多项式 $\ln,\exp$ 即可做到 $O(m\log m)$。