際際滷

Information
Science
Fibonacci Sequence is Magic

2014/01/28 tozangezan

はじめに
? シケプリではありません(蒙に仝プリ々が
�`う)
? コラムが决？と�Aく湖じです
? Ruby��④燭�覆い里任泙箸發淵秋`ス
コ�`ドは�dせません
? 書指は�u晒塀で燕される方双の�麻をし
ます。

�Qう�u晒塀
? 參和の塀を�Qいます

? このうちのkと箔める�の桑催nが嚥えら
れるので、anを基える圭隈を深えます。
? k=2としたものがFibonacci方双です。
? やり圭はたくさんあります。
?

(參和、�u晒塀の�S方をいじればすこし匯違晒できます)

�v方の壅｢を聞う
F(n){
if n < K then 1
else
F(n-1)+F(n-2)+´+F(n-k)
}
(廣)どの冱�Zでもないので�g佩できません

? 壅｢�v方というのは
協�xした�v方の嶄に
揖じ�v方を柵び竃す
�C��があるものだと
房っておけばよいと
房います。
? �u晒塀をそのまま
コ�`ドに��い燭蕕�
んな湖じになります。

�Wい�
? よく深えると、さっきのコ�`ドは富なく
とも仝1を卦す指方々だけ�v方が柵ばれて
います
? これは基えの方と匯崑
? 箭えば、50桑朕のフィボナッチ方は
12586269025で、このプログラムだと方蛍
はかかりそう
? �麻楚はだいたい O(αn) αは採かの協方
? (Fibonacci方双なら仔署方とか)

�麻楚�峺方�v方
? 児云議に峺方�v方はダメです

? 歌深
http://www.youtube.com/watch?v=Q4gTV4r0
zRs
? 仝F(n)は採業も�麻したところで�飴�ﾍ�
じでは´々という�k�だけで互堀になりま
す。

�v方のメモ晒壅｢をする
F(n){
if ＾F(n)�麻�gみ￣
then ＾�麻�gみの�｡�
if n < K then 1
else
F(n-1)+F(n-2)+´+F(n-k)
}
(廣)どの冱�Zでもないので�g佩できません

? さっきのものに2佩��
きたし、�o�jに�麻
しないようにしまし
た。
? かなり堀く�咾�茲�
になります。
? まだ�u晒塀から��
がつくでしょう。

メモ晒壅｢での�麻楚
? �v方はnの�､△燭�1指しか柵び竃されない
としてよい
? (屎�_には採指か柵ばれてるだろうけど恷兜
の1猟だけだしどうでもいい)
? nの�､砲茲辰鍋v方は1指ずつ柵ばれて�
O(n)
? �v方1指ではK��の方の才を�麻するので
O(k)
? これら畠何まとめるとO(nk)

�啜柘�鮫隈を聞う
a[N] # 塘双
? 書業は�v方を聞わず
に、ル�`プをまわす
a*1+=a*2+=´=a*k+=1
だけでかいてみまし
for i in (k+1)..n
た。
a[i]=a[i-1]+a[i-2++´+a*i-k]
? 云輝はk��の方の才を
箔めるのでもル�`プ
を聞うんですがね。
? コ�`ドが玉め。

�啜柘�鮫隈での�麻楚
? メモ晒壅｢と揖じ
? n指くらいル�`プをまわしていて、 (O(n))
? それぞれではk��の方の才を�麻 (O(k))
? 畠何まとめると O(nk)
? やっぱりメモ晒壅｢と揖じ

��}
? 參和の方双を深える

れるので、anを109+7で護ったあまりを基
えよ。
? k �Q 100
? n �Q 100 000
? 盾基箭� さっきのメモ晒壅｢,�啜柘�鮫隈

��}

えよ。
? k �Q 100
? n �Q 1 000 000 000 000 000 000
? 盾基箭� さっきのメモ晒壅｢,�啜柘�鮫隈

�e弊順
? ここから枠はコ�`ド��涼羌垢覆里任�
きません。
? 秤烏親僥の��Yレベルなら�eにこのくら
いでゴ�`ルして措いんじゃないでしょう
か。
? ここから枠はkが寄きいのには��Iできま
せんが、nが寄きいのに��Iできる圭隈で
す。

佩双拙�\
? k=2のとき、
? k=3のとき、

? 一=4のとき、

佩双拙�\
? こういう湖じの侘になるので、anを誼るた
めには1を�Kべたベクトルにn-k指さっきの
ような佩双をかければよい。
? 佩双のかけ麻
? A, A2, A4, A8, A16, A32, ´は揖じものをかける
�I尖をすると、畠何でO(log n)指で箔めら
れる
? ほかのものが誼たいときは、箭えば
A21= A ～ A4 ～ A16 などと2�M方っぽくする。

佩双拙�\での�麻楚
? ということは、佩双のかけ麻はO(log n)指
佩えばよい。
? ここで聞う佩双はk肝屎圭佩双なので1指
のかけ麻はO(k3)かかる (協�xに惄辰橡慟�
に�麻するしかない)
? ということで畠悶での�麻楚はO(k3 log n)

��}

えよ。
? k �Q 100
? n �Q 1 000 000 000 000 000 000
? 盾基箭� 佩双拙�\

��}

えよ。
? k �Q 1 000
? n �Q 1 000 000 000 000 000 000
? 盾基箭� 佩双拙�\

屁塀の護り麻を聞う圭隈
? �gは、この��}の及n�の�､蓮�
仝xnをxk-xk-1-xk-2-´-1で護ったあまりの�S方
の�t才々に吉しいです。(�^苧待)

xnをxk-xk-1-xk-2-´-1で護ったあまりは、x[n/2]を
xk-xk-1-xk-2-´-1で護ったあまりを2�\し(nが謎
方ならさらにxをかける)、その塀をxk-xk-1-xk2-´-1で護ったあまりを箔めればよいです。

屁塀の護り麻を聞う圭隈
? k-1肝の謹�塀屈つの�\麻はO(k2)でできま
す
? この謹�塀の�\麻はO(log n)指柵ばれます

? ということで畠悶での�麻楚はO(k2 log n)
です。

歌深��}
? http://tdpc.contest.atcoder.jp/tasks/tdpc_fibo
nacci
? けっこう謹くの冱�Zで(Rubyでも)盾くこと
ができるっぽいです。
? 盾基箭
http://tdpc.contest.atcoder.jp/submissions/1193
05 (C++, 48佩)

おまけ
? 屁塀のかけ麻は�み�zみなのでFFTで�麻
できてO(k log k)になります。
? が、その屁塀を護ったあまりの�麻がど
うやったらO(k2)から鯛ちるかわかりませ
ん。
? �lか縮えてください
? あと、書指109+7で護ったあまりを箔めた
のは基えが寄きくなりすぎるからです。

際際滷

秤烏親僥シケスラ　酷庄恢看稼温界界庄

More Related Content

秤烏親僥シケスラ　酷庄恢看稼温界界庄

際際滷

秤烏親僥シケスラ 酷庄恢看稼温界界庄

More Related Content

秤烏親僥シケスラ 酷庄恢看稼温界界庄

秤烏親僥シケスラ　酷庄恢看稼温界界庄

秤烏親僥シケスラ　酷庄恢看稼温界界庄