123 - The sum

لینک سوال

مفهوم سوال :

سوال مجموع N جمله اول دنباله فیبوناچی رو می خواد .

دنباله فیبوناچی :

F1  = F2 = 1

Fn+1 = Fn + Fn-1

حل :

دنباله فیبوناچی رشد خیلی سریعی داره ، ولی چون محدودیت این سوال پایینه ، میشه با long long هم زدش .

برای بدست آوردن فیبوناچی هم می تونید یه آرایه بگیرید و dynamic مقدار دنباله رو محاسبه کنید .

در توحالت کلی برای بدست اوردن جمله n ام دنباله فیبوناچی ، در بهترین زمان می تونید از روش زیر استفاده کنید .

یه ماتریس 2*2 در نظر می گیریم که شامل :

1 1

0 1 

هستش .

رابطه داریم که میگه :

این ماتریس به توان n که برسه ، داریه ها به صورت زیر میشن :

Fn+1  Fn

Fn   Fn-1

برای بدست آوردن توان n ام این ماتریس ، میشه از روشی logarithmic استفاده کرد .