Author: Anuj Maheshwari
Editorialist: Vaibhav Jain
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Linear Recurrence Relation
PROBLEM:
You are given two sequences A and B, each with size M, and an integer N. Consider the following pseudocode:
result := 0
for i := 1 to M
for j := 1 to M
array fib[1..max(2, N)]
fib[1] := A[i]
fib[2] := B[j]
for k := 3 to N
fib[k] := fib[k-1] + fib[k-2]
result := result + fib[N]
Compute the final value of the variable result
EXPLANATION:
Well approach which I am providing is quite simple.
Consider sample test case:
3 n
1 2 3
4 5 6
Now, we know for n=1 nth terms for combinations (1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6) will be 1,1,1,2,2,3,3,3 i.e. m times the total sum of first array.
Same is for n=2 where we need to sum of second array and multiply with m.
Now when n>=3
1+4=5
4+5=9
1+5=6
5+6=11
1+6=7
6+7=13
2+4=6
4+6=10
2+5=7
5+7=12
2+6=8
6+8=14
3+4=7
4+7=11
3+5=8
5+8=13
3+6=9
6+9=15
for n>=3 what we can do is take three variables s1, s2 and s3. s1 will hold sum of first array mulplied with m and s2 will hold sum of second array multiplied with m. s3 will hold sum of s1 and s2. These are initial conditions.
Now what can we see from above series is that when n=3, we need to have
(1+4)+(1+5)+(1+6)+(2+4)+(2+5)+(2+6)+(3+4)+(3+5)+(3+6)
(1+2+3)*m + (4+5+6)*m
i.e. s1+s2 which will be stored in s3
for n=4,
(4+5)+(5+6)+(6+7)+(4+6)+(5+7)+(6+8)+(4+7)+(5+8)+(6+9)
(4+5+6)*m + (5+6+7+6+7+8+7+8+9)
i.e. s2+s3
hence for n>=3
for(int i=2;i<n;i++)
{
s3=(s1+s2)%mod;
s1=s2;
s2=s3;
}
print(s3)
TIME COMPLEXITY:
O(n+m) per test case