Sum of products (SPOJ 6286) - cos65535の日記

http://www.spoj.pl/problems/SUMMUL/

問題

nを二つ以上の足し算で表しその数字を掛け合わせる。そのような物を全て足すといくらになるかという問題。答えがでかくなるのでmod 1000000007を取る。

1<=n<=10^9

解放

答えの数値+nを考える。
すると
$\{a_0=1\\a_n=\sum^{n}_{i=1}ia_{n-i}$
というような式になる。
この式を変形すると
$\{a_0=0\\a_1=1\\a_{n+2}-3a_{n+1}+a_n=0$
という漸化式になる。
この式はフィボナッチ数と同様に
$\array{a_{n}\\a_{n-1}\)=$\array{3 & -1\\1 & 0}$^{n-1}\(\array{1\\0}$
このような行列の形で書けてO(logn)で求めることができる。最後にnを引いて出力すれば良い。

関係ないがanを実際に計算すると、
$a_n=\frac{1}{\sqrt5}$\frac{3+\sqrt5}{2}$^n-\frac{1}{\sqrt5}$\frac{3-\sqrt5}{2}$^n$
という式になる。