G - Sum of Binom(A, B) 解説 by harurun4635


\(\displaystyle f =\sum_{i} a_i ! x^{a_i}\)\(\displaystyle g = \sum_{j} \frac{1}{b_j !}x^{-b_j}\) を畳み込むと \(\displaystyle f * g = \sum_{i} \sum_{j} \frac{a_i!}{b_j!} x^{a_i - b_j}\) となります。

指数部分に \(a_i - b_j\) が出現するため、答えは \(\displaystyle \sum_{k \ge 0} [x^k](f*g) \times \frac{1}{k!}\) と簡単に記述できます。

実装時は適当なoffsetをつけることで指数が正になるようにしてください。

投稿日時:
最終更新: