Consider the generalized Fibonacci number G, which is dependent on a, b and c as follows :-
G(1) = 1, G(2) = 1. G(n) = aG(n-1) + bG(n-2) + c.
Your task is to calculate G(n)%m for given values of n and m.
Example 1:
Input:
a = 3, b = 3, c = 3, n = 3, m = 5
Output:
4
Explanation:
G(1) = 1 and G(2) = 1 
G(3) = 3*G(2) + 3*G(1) + 3 = 3*1 + 3*1 + 3 = 9
We need to return answer modulo 5, so 9%5 = 4, is the answer.
Example 2:
Input:
a = 2, b = 2, c = 2, n = 4, m = 100
Output:
16
Explanation:
G(1) = 1 and G(2) = 1 
G(3) = 2*G(2) + 2*G(1) + 2 = 2*1 + 2*1 + 2 = 6
G(4) = 2*G(3) + 2*G(2) + 2  = 2*6 + 2*1 + 2 = 16
We need to return answer modulo 100, so 16%100 = 16, is the answer.
Your Task:
You don't need to read input or print anything. Your task is to complete the function genFibNum() which takes 5 Integers a, b, c, n, and m as input and returns G(n)%m.
Expected Time Complexity: O(logn)
Expected Auxiliary Space: O(1)
Constraints:
1 <= a,b,c,n,m <= 10^{9}+7

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Mathematics

Matrices

Data structures

Number theory

Starter code: #User function Template for python3



class Solution:

    def genFibNum(self, a, b, c, n, m):

        # code here 

Solutions:
class Solution:
	mat = [[0 for i in range(3)] for j in range(3)]
	res = [[0 for i in range(3)] for j in range(3)]

	def mul(self, res, mat, m):
		res1 = [[0 for i in range(3)] for j in range(3)]
		for i in range(3):
			for j in range(3):
				for k in range(3):
					res1[i][j] += res[i][k] * mat[k][j]
					res1[i][j] %= m
		for i in range(3):
			for j in range(3):
				res[i][j] = res1[i][j]

	def mat_exp(self, n, m):
		while n > 0:
			if n & 1:
				self.mul(self.res, self.mat, m)
			self.mul(self.mat, self.mat, m)
			n //= 2

	def genFibNum(self, a, b, c, n, m):
		self.res = [[0 for i in range(3)] for j in range(3)]
		self.res[0][0] = self.res[1][1] = self.res[2][2] = 1
		self.mat[0][0] = a
		self.mat[0][1] = b
		self.mat[0][2] = self.mat[1][0] = self.mat[2][2] = 1
		self.mat[1][1] = self.mat[1][2] = self.mat[2][0] = self.mat[2][1] = 0
		if n <= 2:
			return 1 % m
		else:
			self.mat_exp(n - 2, m)
			return (self.res[0][0] + self.res[0][1] + c * self.res[0][2]) % m


def multiply(mat1, mat2, m):
	ans = [[0 for i in range(3)] for j in range(3)]
	for i in range(3):
		for j in range(3):
			for k in range(3):
				ans[i][j] += mat1[i][k] * mat2[k][j] % m
	return ans

def func(mat, n, m):
	if n == 1:
		return mat
	temp = func(mat, n // 2, m)
	if n % 2 == 0:
		return multiply(temp, temp, m)
	return multiply(multiply(temp, temp, m), mat, m)

class Solution:

	def genFibNum(self, a, b, c, n, m):
		mat = [[a, b, 1], [1, 0, 0], [0, 0, 1]]
		if n == 1 or n == 2:
			return 1 % m
		res = func(mat, n - 2, m)
		return (res[0][0] + res[0][1] + c * res[0][2]) % m


class Solution:

	def multiply(self, a, b, MOD):
		n = len(a)
		ans = [[0 for _ in range(n)] for __ in range(n)]
		for i in range(n):
			for j in range(n):
				for k in range(n):
					ans[i][j] = (ans[i][j] + a[i][k] * b[k][j] % MOD) % MOD
		for i in range(n):
			for j in range(n):
				a[i][j] = ans[i][j]

	def matrixExponentiation(self, ans, a, b, n, m):
		startingMatrix = [[a, b, 1], [1, 0, 0], [0, 0, 1]]
		while n > 0:
			if n % 2 == 1:
				self.multiply(ans, startingMatrix, m)
				n -= 1
			self.multiply(startingMatrix, startingMatrix, m)
			n >>= 1

	def genFibNum(self, a, b, c, n, m):
		if n <= 2:
			return int(1 % m)
		ans = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
		self.matrixExponentiation(ans, a, b, n - 2, m)
		return (ans[0][0] + ans[0][1] + ans[0][2] * c) % m


class Solution:

	def matrixMul(self, a, b, mod):
		prod = []
		for i in range(len(a)):
			prod.append([])
			for j in range(len(a[0])):
				pp = 0
				for k in range(len(a[0])):
					pp = (pp + a[i][k] * b[k][j]) % mod
				prod[-1].append(pp)
		return prod

	def matrixExp(self, matrix, exp, mod):
		ans = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
		while exp > 0:
			if exp & 1 == 1:
				ans = self.matrixMul(ans, matrix, mod)
			exp = exp >> 1
			matrix = self.matrixMul(matrix, matrix, mod)
		return ans

	def genFibNum(self, a, b, c, n, m):
		matrix = [[a, b, c], [1, 0, 0], [0, 0, 1]]
		exp = n - 2
		final_mat = self.matrixExp(matrix, exp, m)
		fib = 0
		for i in final_mat[0]:
			fib = (fib + i) % m
		return fib