PROBLEM LINK:Author: vinod10 DIFFICULTY:Medium PREREQUISITES:Matrix Exponentiation , Modular multiplicative inverse PROBLEM:Given a sequence f(n) = A * f(n1) + B * f(n2), ( with base case f(1)=f(2)=1 ), find sum of f(n) where l<=n<=r. Find this sum for Q queries. QUICK EXPLANATION:S(l,r) = f(l) + f(l+1) + ..... +f(r) = { f(r+2)  f(l+1) + (A1) * ( f(l)  f(r+1) ) } / {A+B1}. Now using matrix exponentiation, f(X) can be found in logX time. Hence each query can be solved in LogN time. EXPLANATION:Given, f(l) = A * f(l1) + B * f(l2). f(l+1) = A * f(l) + B * f(l1). f(r1) = A * f(r2) + B * f(l3). f(r) = A * f(r1) + B * f(r2). Summing these all will give: S(l,r) = A * ( S(l,r)  f(r) + f(l1) ) + B * ( S(l,r)  f(r)  f(r1) + f(l1) + f(l2) ). Simplifying it gives:
S(l,r) = { f(r+2)  f(l+1) + (A1) * ( f(l)  f(r+1) ) } / {A+B1} Now calculation of f(n) requires knowledge of matrix exponentiation, and if you are not familiar with it, you can follow this blog. We know : $$ \left(\begin{array}{cc} f(n) & f(n1)\\ f(n1) & f(n2) \end{array}\right) \left(\begin{array}{cc} A & 1\\ B & 0 \end{array}\right) = \left(\begin{array}{cc} f(n+1) & f(n)\\ f(n) & f(n1) \end{array}\right) $$ therefore, $$ \left(\begin{array}{cc} A+B & 1\\ 1 & 1 \end{array}\right) \left(\begin{array}{cc} A & 1\\ B & 0 \end{array}\right)^{n3} = \left(\begin{array}{cc} f(n) & f(n1)\\ f(n1) & f(n2) \end{array}\right) $$ Using matrix multiplication M^{N3} can be calculated in logN time. Hence we calculate each term in the answer and to divide the final answer by {A+B1}, we use modular multiplicative inverse. Notice 10^{9}+7 is a prime, hence Fermat's little theorem can be used to get modular multiplicative inverse of {A+B1}, which is {(A+B1)^{MOD2}} % MOD, where MOD = 10^{9}+7. AUTHOR'S SOLUTIONS:Author's solution can be found here. asked 01 Nov '17, 13:33
