luoguP7896 题解 - Moke 的游戏
x义x
·
·
题解
贺的官方题解
猜猜我官方题解哪里来的？
考虑 (0,0)\rightarrow(n,-1) 且除了最后一步外从未接触 y=-1 的路径们，记其生成函数为 F。
讨论其第一步，我们有
F=x\sum_{i=-1}a_{i}F^{i+1}
自然，
\boxed{F^{<-1>}=\dfrac{x}{\sum_{i=-1}a_ix^{i+1}}}
考虑所希望的 (0,0)\rightarrow (n,0) 且除了起点和终点从未接触过 y=0 的路径，故技重施，有
ans=x\sum_{i=0}a_iF^i
而接触 y=0 恰好 m+1 次的就是
\boxed{ans=\left(x\sum_{i=0}a_iF^i\right)^m}
使用拉格朗日反演：
\begin{aligned}
&[x^{n-m}]\left(\sum_{i=0}a_iF^i\right)^m\\=&\dfrac{[x^{n-m-1}]}{n-m}\cdot m\left(\sum_{i=1}ia_ix^{i-1}\right)\left(\sum_{i=0}a_ix^{i}\right)^{m-1}\cdot\left(\sum_{i=-1}a_ix^{i+1}\right)^{n-m}
\end{aligned}
于是问题变为求一个稀疏多项式的高次幂的前较低项系数。有 ODE：
f(f^m)'=mf'f^m
也就得到了一个 f^m 的整式递推。