ログインしてください。
F - (1,2,...,N) の順列のうち長さ 3 の単調減少な連続部分列を含まないものの個数 mod 10^9+9 を知りたい / Dislike 321 解説
by
nok0
maspy さんの解説より, \([x^N]e^{-bx}\frac{1}{1-ce^{dx}}\) を求められれば良い.
\(\frac{1}{1-f}=1+f+f^2+f^3+\ldots\) を用いると,
\[[x^N]\sum_{k=0}^\infty c^k \exp((dk-b)x) =\frac{1}{N!}\sum_{k=0}^\infty c^k(dk-b)^N\]
である.\(d^N\) で割ると結局
\[\sum_{k=0}^\infty c^k (k-b')^N =c^{b'} \left(\sum_{k=0}^\infty c^k k^N + \sum_{k=-b'}^{-1}c^k k^N \right)\]
を求められれば良いが,これはどちらも Library Checker にある有名問題である.
投稿日時:
最終更新: