×

# calculate f(n) = a*f(n-1) + b*f(n-2) matrix exponentiation

 -1 Given f(1)=1 , f(2)=1 , and f(n) = 100*f(n-1)+200f(n-2) . Now , i have to calculate f(n) rof n upto 10^9 , so obvious approach id to use matrix exponentiation .. I came up with this logic , but it gives wrong output . Can you please explain the reason ? It fails with n=3 , but i am not able to come up with how to resolve it . #include using namespace std; #define ll long long ll m=1000000007; ll x,y,z,w; void ml(ll F[2][2],ll M[2][2]) { x = ((F[0][0]%m)*(M[0][0]%m))%m + ((F[0][1]%m)*(M[1][0]%m))%m; y = ((F[0][0]%m)*(M[0][1]%m))%m + ((F[0][1]%m)*(M[1][1]%m))%m; z = ((F[1][0]%m)*(M[0][0]%m))%m + ((F[1][1]%m)*(M[1][0]%m))%m; w = ((F[1][0]%m)*(M[0][1]%m))%m + ((F[1][1]%m)*(M[1][1]%m))%m; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; //cout<

 1 Use this matrix for F and M: 100 1 200 0 To get result matrix for n you need (n - 2) power of F. And answer is: (F[0][0] + F[1][0]) % m; answered 30 Mar '14, 15:54 5★bulatov 126●3 accept rate: 50% please explain it also , i want to learn how to find it . (30 Mar '14, 16:19) ac_c0der2★ 2 (30 Mar '14, 16:25) kuruma3★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,642
×283
×137

question asked: 30 Mar '14, 14:29

question was seen: 6,334 times

last updated: 30 Mar '14, 16:25