Given an integer N. Your task is to find the number of binary strings of length N having no consecutive 1s.
As the number can be large, return the answer modulo 10^9+7.
Example 1:
Input:
N = 3
Output:
5
Explanation:
All the binary strings of length 3 having
no consecutive 1s are "000", "001", "101",
"100" and "010".
Example 2:
Input: 
N = 2
Output:
3
Explanation: 
All the binary strings of length 2 having no 
consecutive 1s are "10", "00" and "01".
Your Task:
You dont need to read input or print anything. Complete the function countStrings() which takes the integer N as the input parameter, and returns the number of binary strings of length N with no consecutive 1s.
Expected Time Complexity: O(log(N))
Expected Auxiliary Space: O(Height of the recursive call stack)
Constraints:
1 ≤ N ≤ 10^{18}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code: #User function Template for python3

class Solution: 

    def countStrings(self, N): 

        # Code here



Solutions:
from functools import lru_cache

class Solution:

	@lru_cache()
	def recSol(self, n):
		if n == 1:
			return (1, 0, 0, 1)
		(a1, b1, c1, d1) = self.recSol(n // 2)
		(a2, b2, c2, d2) = self.recSol(n - n // 2)
		a3 = a1 * (a2 + c2) + b1 * a2
		b3 = a1 * (b2 + d2) + b1 * b2
		c3 = c1 * (a2 + c2) + d1 * a2
		d3 = c1 * (b2 + d2) + d1 * b2
		a3 %= 10 ** 9 + 7
		b3 %= 10 ** 9 + 7
		c3 %= 10 ** 9 + 7
		d3 %= 10 ** 9 + 7
		return (a3, b3, c3, d3)

	def countStrings(self, N):
		return sum(list(self.recSol(N))) % (10 ** 9 + 7)


class Solution:
	m = 1000000007

	def f(self, n):
		if n == 0:
			return (0, 1)
		(a, b) = self.f(n // 2)
		c = a * (b * 2 - a) % self.m
		d = (a * a + b * b) % self.m
		if n % 2 == 1:
			return (d, c + d)
		return (c, d)

	def countStrings(self, N):
		(ans, _) = self.f(N + 2)
		return ans % self.m


from math import sqrt

class Solution:
	m = 1000000007

	def f(self, n):
		if n == 0:
			return (0, 1)
		(a, b) = self.f(n // 2)
		c = a * (b * 2 - a) % self.m
		d = (a * a + b * b) % self.m
		if n % 2 == 1:
			return (d, c + d)
		return (c, d)

	def countStrings(self, N):
		(ans, _) = self.f(N + 2)
		return ans % self.m


from collections import defaultdict

def fib(n):
	F = [[1, 1], [1, 0]]
	if n == 0:
		return 0
	power(F, n - 1)
	return F[0][0]

def multiply(F, M):
	x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
	y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
	z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
	w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
	F[0][0] = x % (10 ** 9 + 7)
	F[0][1] = y % (10 ** 9 + 7)
	F[1][0] = z % (10 ** 9 + 7)
	F[1][1] = w % (10 ** 9 + 7)

def power(F, n):
	if n == 0 or n == 1:
		return
	M = [[1, 1], [1, 0]]
	power(F, n // 2)
	multiply(F, F)
	if n % 2 != 0:
		multiply(F, M)

def nth_fibonnaci(n):
	if n > 0:
		(n1, n2) = (1, 1)
		if n > 3:
			for _ in range(n // 3):
				(n1, n2) = (n2, (n2 << 2) + n1)
		if n % 3 == 0:
			return n1
		elif n % 3 == 1:
			return n2 - n1 >> 1
		elif n % 3 == 2:
			return n2 + n1 >> 1
	else:
		return -1

class Solution:

	def countStrings(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 2
		if N == 2:
			return 3
		if N == 3:
			return 5
		return fib(N + 2)


class Solution:

	def mult(self, A, B, MOD):
		C = [[0, 0], [0, 0]]
		for i in range(2):
			for j in range(2):
				for k in range(2):
					C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
		return C

	def power(self, A, n, MOD):
		if n == 1:
			return A
		H = self.power(A, n // 2, MOD)
		res = self.mult(H, H, MOD)
		if n % 2:
			res = self.mult(res, A, MOD)
		return res

	def countStrings(self, N):
		MOD = 10 ** 9 + 7
		return self.power([[1, 1], [1, 0]], N + 1, MOD)[0][0]


class Solution:

	def countStrings(self, N):

		def func(n):
			if n == 0:
				return 0
			elif n == 1 or n == 2:
				return 1
			if n in cache:
				return cache[n]
			if n % 2:
				k = (n + 1) // 2
				(a, b) = (func(k) % mod, func(k - 1) % mod)
				cache[n] = (a * a % mod + b * b % mod) % mod
			else:
				k = n // 2
				(a, b) = (func(k) % mod, func(k - 1) % mod)
				cache[n] = (2 * b % mod + a) % mod * a % mod
			return cache[n]
		mod = 10 ** 9 + 7
		cache = {}
		return func(N + 2) % mod


mod = 10 ** 9 + 7

class Solution:

	def multiply(self, a, b):
		mul = [[0 for j in range(3)] for j in range(3)]
		for i in range(3):
			for j in range(3):
				for k in range(3):
					temp = a[i][k] * b[k][j] % mod
					mul[i][j] += temp
					mul[i][j] %= mod
		for i in range(3):
			for j in range(3):
				a[i][j] = mul[i][j]

	def power(self, mat, N):
		M = [[1, 1, 0], [1, 0, 0], [0, 1, 0]]
		if N == 1:
			return (mat[0][0] + mat[0][1]) % mod
		self.power(mat, N // 2)
		self.multiply(mat, mat)
		if N % 2 != 0:
			self.multiply(mat, M)
		return (mat[0][0] + mat[0][1]) % mod

	def countStrings(self, N):
		mat = [[1, 1, 0], [1, 0, 0], [0, 1, 0]]
		if N == 2:
			return 3
		if N == 1:
			return 2
		return self.power(mat, N)


class Solution:

	def countStrings(self, N):
		M = 10 ** 9 + 7

		def matrix_multiply(a, b):
			nonlocal M
			c = [[0, 0], [0, 0]]
			for i in range(2):
				for j in range(2):
					for k in range(2):
						c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % M
			return c

		def matrix_power(a, n):
			nonlocal M
			ans = [[1, 0], [0, 1]]
			while n > 0:
				if n % 2 == 1:
					ans = matrix_multiply(ans, a)
				a = matrix_multiply(a, a)
				n //= 2
			return ans
		return matrix_power([[1, 1], [1, 0]], N + 1)[0][0]


class Solution:
	m = 10 ** 9 + 7

	def multiply(self, a, b):
		arr = [[0, 0], [0, 0]]
		arr[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % (10 ** 9 + 7)
		arr[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % (10 ** 9 + 7)
		arr[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % (10 ** 9 + 7)
		arr[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % (10 ** 9 + 7)
		return arr

	def bin_pow(self, a, n):
		arr = [[1, 1], [1, 1]]
		while n > 0:
			if n & 1:
				arr = self.multiply(arr, a)
			a = self.multiply(a, a)
			n = n >> 1
		return arr

	def countStrings(self, N):
		a = [[1, 1], [1, 0]]
		a = self.bin_pow(a, N)
		return a[0][0]


class Solution:

	def power(self, n):
		if n == 0 or n == 1:
			return [[1, 1], [1, 0]]
		fib = self.power(n // 2)
		temp = self.multiply(fib, fib)
		if n % 2 == 1:
			temp = self.multiply(temp)
		return temp

	def multiply(self, f, m=[[1, 1], [1, 0]]):
		temp = [[0, 0], [0, 0]]
		for i in range(2):
			for j in range(2):
				for k in range(2):
					temp[i][j] += f[i][k] * m[k][j] % self.mod
		return temp

	def countStrings(self, N):
		self.mod = 10 ** 9 + 7
		ans = self.power(N + 1)
		return ans[0][0] % self.mod


mod = 10 ** 9 + 7

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

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

class Solution:

	def countStrings(self, N):
		mat = [[1, 1], [1, 0]]
		ans = func(mat, N + 2)
		return ans[0][1] % mod


class Solution:
	m = 10 ** 9 + 7

	def f(self, n):
		if n == 0:
			return (0, 1)
		(a, b) = self.f(n // 2)
		c = a * (b * 2 - a) % self.m
		d = (a * a + b * b) % self.m
		if n % 2 == 1:
			return (d, c + d)
		return (c, d)

	def countStrings(self, N):
		(ans, _) = self.f(N + 2)
		return ans % self.m


class Solution:
	mod = 10 ** 9 + 7

	def multiply(self, A1, A2):
		res = [[0, 0], [0, 0]]
		for k in range(2):
			for i in range(2):
				sm = 0
				for j in range(2):
					sm += A1[k][j] * A2[j][i]
				res[k][i] = sm % self.mod
		return res

	def pow(self, A, N):
		res = [[1, 1], [1, 1]]
		while N:
			if N % 2:
				res = self.multiply(res, A)
				N -= 1
			A = self.multiply(A, A)
			N //= 2
		return res[0][1] % self.mod

	def countStrings(self, N):
		A = [[1, 1], [1, 0]]
		return self.pow(A, N + 1)


class Solution:
	mod = 10 ** 9 + 7

	def multiply(self, F, M):
		x = (F[0][0] % self.mod * M[0][0] % self.mod % self.mod + F[0][1] % self.mod * M[1][0] % self.mod % self.mod) % self.mod
		y = (F[0][0] % self.mod * M[0][1] % self.mod % self.mod + F[0][1] % self.mod * M[1][1] % self.mod % self.mod) % self.mod
		z = (F[1][0] % self.mod * M[0][0] % self.mod % self.mod + F[1][1] % self.mod * M[1][0] % self.mod % self.mod) % self.mod
		w = (F[1][0] % self.mod * M[0][1] % self.mod % self.mod + F[1][1] % self.mod * M[1][1] % self.mod % self.mod) % self.mod
		(F[0][0], F[0][1], F[1][0], F[1][1]) = (x, y, z, w)

	def power(self, F, n):
		if n == 0 or n == 1:
			return
		M = [[1, 1], [1, 0]]
		self.power(F, n // 2)
		self.multiply(F, F)
		if n % 2 != 0:
			self.multiply(F, M)

	def fib(self, n):
		F = [[1, 1], [1, 0]]
		if n == 0:
			return 0
		self.power(F, n - 1)
		return F[0][0]

	def countStrings(self, n: int) -> int:
		res = self.fib(n + 2)
		return res


class Solution:

	def countStrings(self, N):
		MOD = 10 ** 9 + 7
		M = [[1, 1], [1, 0]]
		(dp0, dp1) = (1, 1)
		if N == 1:
			return 2
		power = N - 1
		while power > 0:
			if power % 2 == 1:
				(dp0, dp1) = ((dp0 * M[0][0] + dp1 * M[0][1]) % MOD, (dp0 * M[1][0] + dp1 * M[1][1]) % MOD)
			M = [[(M[0][0] * M[0][0] + M[0][1] * M[1][0]) % MOD, (M[0][0] * M[0][1] + M[0][1] * M[1][1]) % MOD], [(M[1][0] * M[0][0] + M[1][1] * M[1][0]) % MOD, (M[1][0] * M[0][1] + M[1][1] * M[1][1]) % MOD]]
			power //= 2
		return (dp0 + dp1) % MOD


class Solution:

	def matrix_multiply(self, A, B):
		C = [[0, 0], [0, 0]]
		for i in range(2):
			for j in range(2):
				C[i][j] = (A[i][0] * B[0][j] + A[i][1] * B[1][j]) % 1000000007
		return C

	def matrix_power(self, A, n):
		if n == 0:
			return [[1, 0], [0, 1]]
		elif n % 2 == 0:
			B = self.matrix_power(A, n // 2)
			return self.matrix_multiply(B, B)
		else:
			B = self.matrix_power(A, n - 1)
			return self.matrix_multiply(A, B)

	def countStrings(self, n):
		if n == 0:
			return 1
		elif n == 1:
			return 2
		M = [[1, 1], [1, 0]]
		M_n = self.matrix_power(M, n)
		return (M_n[0][0] + M_n[0][1]) % 1000000007


class Solution:

	def countStrings(self, n):
		mod = 10 ** 9 + 7

		def matrix_multiplication(mat1, mat2, mod):
			matrix = [[0, 0], [0, 0]]
			for i in range(2):
				for j in range(2):
					for k in range(2):
						matrix[i][j] = (matrix[i][j] + mat1[i][k] * mat2[k][j]) % mod
			return matrix

		def power_m(mat, n, mod):
			if n == 1:
				return mat
			else:
				sq = power_m(mat, n // 2, mod)
				res = matrix_multiplication(sq, sq, mod)
			if n % 2 != 0:
				res = matrix_multiplication(res, mat, mod)
			return res
		mat = [[1, 1], [1, 0]]
		return power_m(mat, n + 1, mod)[0][0]