LightOJ: Algebraic Problem

Problem Link: loj1070
Technique: Matrix Exponentiation

Given the value of a+b and ab you will have to find the value of aⁿ+bⁿ. a and b not necessarily have to be real numbers. I solved this using matrix exponentiation technique. I will now write about how I modelled the base matrix for multiplication. There may be other approaches too. But first please read this mat expo if you don't know about how to create a matrix from a recurrance relation.
First let's observe some cases.

If n = 0, a⁰+b⁰ = 1+1 = 2
If n = 1, a¹+b¹ = a+b - 0
If n = 2, a²+b² = (a+b) (a+b) - 2ab
If n = 3, a³+b³ = (a+b) ( (a+b)² - ab ) - 2ab (a+b)
..............     ..............     .............     .................
So, basically the recurrence somehow turns like this -->
(a¹+b¹) = (a+b) + (-0)
(a²+b²) = (a+b) (a+b) + 2(-ab)
So,

base  =  | (a+b)   -ab  |
             |   1           0   |
We will multiply (a+b) with base [0][0] and 2 with base [0][1], then we will get our final output by summing these two elements.
So, when n = 0 , ans will be 2.
When n = 1, ans will be a+b
When n = 2, ans will be (base)¹  = (a+b) * (a+b) + 2 * (-ab) = (a+b)² - 2ab
When n = 3, ans will be (base)²  = (a+b) * [(a+b)² -ab)] + 2 * [-ab*(a+b)]
Let's see this : (for n = 3)

In our base matrix, after performing exponentiation, at base [0][0] we get [(a+b)² -ab)], and we will multiply it with (a+b). Similarly, at base[0][1] we get [-ab*(a+b)], so we will multuply it with 2. And by summing these two elements, we will get our final output.

NOTE : As For each test case, print the case number and (aⁿ+bⁿ) modulo 2⁶⁴, we will use unsigned long long for each variable instead of applying modulus operation. This will save our time. Infact, without this, the program will get TLE.

	#include <bits/stdc++.h>
	#include <iostream>
	#include <math.h>
	#include <string>
	#include <stack>
	#include <vector>
	#include <set>
	#include <queue>
	#include <map>
	#include <stdio.h>
	#include <string.h>
	#include <algorithm>
	using namespace std;
	#define ll unsigned long long
	#define pb push_back
	#define MP make_pair
	#define vi vector<int>
	#define vll vector<ll>
	#define MAX 100010 // sqrt of MAX
	#define MOD 1000000007
	#define LMT 10000 // sqrt of MAX
	#define LEN 5000005 // MAX primes that can be within range
	#define RNG 100032 //
	#define sq( x ) ( x * x )
	#define chkC(x,n) ( x[n>>6] & ( 1<<(( n>>1 ) &31)))
	#define setC(x,n) ( x[n>>6] |= ( 1<<(( n>>1 ) &31)))
	#define SZ 2
	ll p,q,n,d=1,m=10007;
	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];
	}
	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++)
	{
	scanf("%llu %llu %llu",&p,&q,&n);
	if(n==0)
	printf("Case %d: 2\n",tc);
	else if(n==1)
	printf("Case %d: %llu\n",tc,p);
	else
	{
	memset(base.mat,0,sizeof(base.mat));
	base.mat[0][0]=p,base.mat[0][1]=-q;
	base.mat[1][0]=1,base.mat[1][1]=0;
	//print(base);
	base=matexpo(base,n-1);
	//print(base);
	ll ans=(base.mat[0][0]*p+base.mat[0][1]*2);
	printf("Case %d: %llu\n",tc,ans);
	}
	}
	//fclose(f);
	//fclose(o);
	return 0;
	}

view raw Algebra Problem.cpp hosted with ❤ by GitHub

"Don't directly copy code. First try to understand how each step works, then do your own coding."