PROBLEM LINK:
Author: Arjun Bharat
Tester: Arjun Bharat
Editorialist: Arjun Bharat
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Math, modular exponentiation
PROBLEM:
Given the functional equation f(x+1)=kf(x)+g(x), g(x+1)=kg(x)+f(x), f(0)=2 and g(0)=0, the task
is to find the value of f(n) modulo 1000000007, where n and k are program inputs.
QUICK EXPLANATION:
This is achieved by first solving the equations to obtain: f(x)= 2x, if(k=1)
f(x)= (k+1)x + (k-1)x, for k>1.
Then we compute the remainder using fast modular exponentiation which is best suited for the given constraints.
EXPLANATION:
One may either add or subtract the two equations and obtain these following equations:
f(x+1)-g(x-1)=(k-1)(f(x)-g(x)),
f(x+1)+g(x+1)=(k+1)(f(x)+g(x))
Thus defining new functions h(x)=f(x)+g(x) and p(x)=f(x)-g(x),
we have p(x)=2(k-1)x, h(x)=2(k+1)x.
Substituting any one of them back will yield f(x+1)=(k+1)f(x)-(k-1)x, and thus
by superposition of the homogeneous and particular solutions to the recursive relation, set
f(x)=a(k+1)x + b(k-1)x</sup, solving gives a=b=1.
Thus we have f(x)=(k+1) + (k-1)x.
Now we proceed to obtain the remainder.
Notice that using a linear recurrence, ans(n)=(k * ans(n-1))%M
is O(n) and will not pass in under one second.
We proceed to use fast modular exponentiation. A brief snippet coded in C++ is highlighted below:
long long fn(long long n,long long k)
{
if(n==0)
return 1;
else if(n==1)
return k;
else if(n%2==0)
{
long long y = fn(n/2,k);
return ((y%M)*(y%M))%M;
}
else
{
long long z= fn(n/2,k);
return ((y%M)(y%M)(k))%M;
}
}
long long ans = fn(n,k+1)+fn(n,k-1);
ans%=M;//M=10^9+7
//This code works even when k=0, as the second call returns 0.
This is O(lg n), a marked improvement.
ALTERNATIVE SOLUTION:
The trivial solution is to use a linear recurrence as described earlier, which is not suitable based on program constraints.
Manually computing and storing f(x) and g(x) values, with or without modulo is
not advisable due to their large magnitudes, and the linear time complexity involved therein.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here: jdoodle.com/a/wPF
RELATED PROBLEMS:
TOPTWO