luogu P5388 最终幻想 母函数

阅读量: searchstar 2021-11-15 13:35:39
Categories： Tags：

yamengxi大佬写了一个优美的公式，但是没有给出证明。时隔两年，本蒟蒻终于可以帮大佬补个证明了。

假设答案是fn(k)，那么根据c__z__a的题解，可以得到以下递推表达式：

下面用母函数来求fn(k)的通项。设

那么有

n > 1时，有

所以

的第k项是2k，的第k项是Cn + kn，所以的第k项是，所以的第k项是

所以Gn(x)的第k项是

咦？怎么跟yamengxi的不太一样？

此外，我完全看不出这个东西怎么能化简到，希望未来有大佬可以补上这个证明。

Hexo支持Latex风格的公式编辑
algorithm2e无限循环