Problem F: Dimensional Drift
Setter: ankit_907
Tester: vishaaaal
Difficulty:
MEDIUM
Question:
Given is a recurrence relation:
\large \frac{(F_{n}-F_{n-2})}{(F_{n-1})} = (1+F_{n-2})(F_{n-1}^2+3\cdot F_{n-1}+3)
Here, F_{0}=2^{a/b}-1,F_{1}=2^{c/d}-1
Let F_{n}=2^{e/f}-1
Find e\cdot f^{-1} modulo 10^{9}+7
Quick Explanation:
On rearranging the terms, we can condense it into a simpler expression. The final answer can be found using Matrix Exponentiation on the received recursive relation to get the n^{th} term.
Detailed Explanation:
We can condense the above expression using the following steps:
F_{n}-F_{n-2} = F_{n-1}\cdot(F_{n-1}^{2}+3\cdot F_{n-1}+3+F_{n-2}\cdot F_{n-1}^{2}+3\cdot F_{n-1}\cdot F_{n-2}+3\cdot F_{n-2})
→ F_{n}-F_{n-2} = F_{n-1}^{3}+3\cdot F_{n-1}^2+3\cdot F_{n-1}+F_{n-2}\cdot F_{n-1}^{3}+3\cdot F_{n-1}^2\cdot F_{n-2}+3\cdot F_{n-2}\cdot F_{n-1})
→ F_{n}-F_{n-2}= F_{n-1}^3(1+F_{n-2})+3\cdot F_{n-1}^2(1+F_{n-2})+3\cdot F_{n-1}(1+F_{n-2})
→ 1+F_{n}= F_{n-1}^3(1+F_{n-2})+3\cdot F_{n-1}^2(1+F_{n-2})+3\cdot F_{n-1}(1+F_{n-2}) + (1+F_{n-2})
→ 1+F_{n}= (1+F_{n-2})(F_{n-1}^3+3\cdot F_{n-1}^2+3\cdot F_{n-1}+1)
→ 1+F_{n}=(1+F_{n-2})(1+F_{n-1})^3
So, our final recursive relation turns out as: (1+F_{n})=(1+F_{n-2})(1+F_{n-1})^3
Lets define another function G_{n} =(1+F_{n})
Hence our new relation turns out as : G_{n}=(G_{n-2})(G_{n-1})^3
As you know, this is not a linear recursive relation. Hence we cannot directly apply matrix exponentiation in this. So, we would have to convert it into a recursive relation.
How to do so?
Taking log_{2}() on both sides:
→ log_{2}(G_{n})=log_{2}(G_{n-2})+3*log_{2}(G_{n-1})
Lets define define H_{n}=log_{2}(G_{n})
Hence our final functional relation turns out as :
H_{n}=H_{n-2}+3\cdot H_{n-1}
Notice that this relation properly satisfies all our requirements to solve this question. We have got a recursive relation of the exponents, which we actually needed, and the equation is fit enough for us to apply Matrix Exponentiation.
The recursive relation matrix to aid us in this turns out as :
T=\begin{bmatrix}
3 & 1\\
1& 0\end{bmatrix}
F_{n}=T\cdot F_{n-1}
So all thats left is applying the matrix multiplication
Time Complexity:
O(K^2*Log_{2}(n))
where K is the dimension of the matrix. Here K=2, since ours is a 2 x 2 matrix.
solution code
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
#define ll long long
inline ll mod(ll a){
if(a>0){
if(a < MOD) return a;
return a%MOD;
}
else {
a *= -1;
if(a > MOD) a %= MOD;
return (MOD - a);
}
}
inline ll add(ll a,ll b){
a = mod(a); b = mod(b);
return mod(a+b);
}
inline ll prod(ll a,ll b){
a = mod(a); b = mod(b);
return mod(a*b);
}
vector<vector<ll>> mat= {{2,1},{1,0}};
void prod(vector<vector<ll>> &m1,vector<vector<ll>> &m2){
const ll a = add(prod(m1[0][0],m2[0][0]) , prod(m1[0][1],m2[1][0]));
const ll b = add(prod(m1[0][0],m2[0][1]) , prod(m1[0][1],m2[1][1]));
const ll c = add(prod(m1[1][0],m2[0][0]) , prod(m1[1][1],m2[1][0]));
const ll d = add(prod(m1[1][0],m2[0][1]) , prod(m1[1][1],m2[1][1]));
m1[0][0] = a; m1[0][1] = b; m1[1][0] = c; m1[1][1] = d;
}
void matrix_expo(ll p){
vector<vector<ll>>res = {{1,0},{0,1}};
while(p){
if(p&1) prod(res,mat);
p>>=1; prod(mat,mat);
}
for(int i=0;i<2;i++) for(int j=0;j<2;j++) mat[i][j] = res[i][j];
}
ll power(ll x,ll y)
{
if(x > MOD) x %= MOD;
ll res=1;
while(y)
{
if(y&1) res=(res*x)%MOD;
x=(x*x)%MOD; y>>=1;
}
return res;
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
mat[0][0] = 2; mat[0][1] = 1; mat[1][0] = 1; mat[1][1] = 0;
ll n; cin>>n;
ll a,b,c,d; cin>>a>>b>>c>>d;
ll arr[2] = {prod(c,power(d,MOD-2)),prod(a,power(b,MOD-2))};
matrix_expo(n-1);
ll ans = add(prod(mat[0][0],arr[0]),prod(mat[0][1],arr[1]));
cout<<ans<<'\n';
}
}