F - (1,2,...,N) の順列のうち長さ 3 の単調減少な連続部分列を含まないものの個数 mod 10^9+9 を知りたい / Dislike 321 Editorial 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 にある有名問題である.

posted:
last update: