Matrix Exponentiation

Where there is recurrence , there is Matrix Expo.

We use matrix expo to calculate very large number, terms of the recurrence where even DP can't help us to pre-calculate the result.

You are all requested to read this blog  Matrix Expo  for understanding the matrix exponentiation.
Here is a sample code for generating Fibonacci numbers.

	#include <bits/stdc++.h>
	using namespace std;
	#define ll long long
	#define MOD 1000000007
	#define SZ 5
	long long a,b,c,n,d=1;
	struct Matrix
	{
	ll mat[SZ][SZ];
	};
	Matrix matmul( Matrix A, Matrix B)
	{
	Matrix C;
	for(int i=0; i <= d; i++)
	{
	for(int j = 0; j <= d ; j++)
	{
	ll val = 0ll;
	for(int k = 0; k <= d; k++)
	{
	val += ( A.mat[i][k]*B.mat[k][j] ) % MOD;
	}
	C.mat[i][j] = val;
	}
	}
	return C;
	}
	Matrix matexpo( Matrix BASE, long long p )
	{
	if( p==1ll || p==0ll )
	return BASE;
	Matrix R = matexpo(BASE,(ll)p >> 1ll);
	R = matmul(R,R);
	if( p&1ll ) R = matmul( R,BASE );
	return R;
	}
	void print( Matrix ret )
	{
	for(int i = 0; i <= d; i++)
	{
	for(int j = 0; j <= d; j++)
	cout<< ret.mat[i][j] << " ";
	cout<<endl;
	}
	}
	int main()
	{
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	//FILE*f=freopen("input.txt","r",stdin);
	//FILE*o=freopen("output.txt","w",stdout);
	Matrix base;
	int t;
	scanf("%d", &t);
	for(int tc = 1;tc <= t; tc++)
	{
	memset(base.mat,0,sizeof(base.mat));
	scanf("%lld", &n);
	// creating base matrix for fibonacci recurrence
	base.mat[0][0]=1;
	base.mat[0][1]=1;
	base.mat[1][0]=1;
	base.mat[1][1]=0;
	// print(base);
	if(n<=1)
	{
	printf("Case %d: 1\n",tc);
	continue;
	}
	base = matexpo(base,n-1); // for calculating n-th power, we need base ^ ( n-1 )
	//print(base); // printing the base after n-th power
	ll ans = 0;
	ll f[] = {1,0}; // known elements where fib[0]=0, fib[1]=1
	// if fib[0]=a,fib[1]=b, change values in the array f[]
	for(int i = 0; i <= d; i++)
	ans += ( base.mat[0][i]*f[i] ) % MOD;
	printf("Case %d: %lld\n", tc, ans);
	}
	//fclose(f);
	//fclose(o);
	return 0;
	}

view raw Matexpo.cpp hosted with ❤ by GitHub

Note: For different types of recurrence , the base matrix will change accordingly. We have to generate this base matrix carefully , else every other things are pretty much same.