Implement matrix multiplication and fast exponentiation
Problem Description
This problem consists of three interconnected parts, all requiring efficient computation and proper handling of modular arithmetic.
1. Matrix Multiplication
Implement a function multiply(A, B) that performs matrix multiplication. Given two matrices A of dimensions n × m and B of dimensions m × p, the function should return their product C, which will be an n × p matrix. All calculations should be performed modulo a given MOD value.
2. Exponentiation by Squaring
Implement a function pow(x, k, MOD=None) that calculates x^k efficiently. The result should be x^k mod MOD if MOD is provided. The algorithm must achieve O(log k) time complexity. Special consideration should be given to the base case where k = 0 and x = 0.
3. Fibonacci Sequence using Matrix Exponentiation
Implement a function fib(n, MOD=None) that calculates the n-th Fibonacci number, F(n), modulo a given MOD value. The Fibonacci sequence is defined as F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2) for n ≥ 2. This function must use a 2×2 matrix exponentiation approach to achieve O(log n) time complexity. The input n can be as large as 10^9.
Required Function Signatures
multiply(A, B) -> Cpow(x, k, MOD=None) -> valuefib(n, MOD=None) -> value
Constraints
- For
fib(n),ncan be up to10^9.
AI interview prep
Core dilemma
The central dilemma is to correctly and efficiently apply advanced algorithmic techniques (binary exponentiation for scalars and matrices) to handle extremely large inputs (up to 10^9) while meticulously managing modular arithmetic to prevent overflow and ensure correctness.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Implement matrix multiplication and fast exponentiation
Problem Description
This problem consists of three interconnected parts, all requiring efficient computation and proper handling of modular arithmetic.
1. Matrix Multiplication
Implement a function multiply(A, B) that performs matrix multiplication. Given two matrices A of dimensions n × m and B of dimensions m × p, the function should return their product C, which will be an n × p matrix. All calculations should be performed modulo a given MOD value.
2. Exponentiation by Squaring
Implement a function pow(x, k, MOD=None) that calculates x^k efficiently. The result should be x^k mod MOD if MOD is provided. The algorithm must achieve O(log k) time complexity. Special consideration should be given to the base case where k = 0 and x = 0.
3. Fibonacci Sequence using Matrix Exponentiation
Implement a function fib(n, MOD=None) that calculates the n-th Fibonacci number, F(n), modulo a given MOD value. The Fibonacci sequence is defined as F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2) for n ≥ 2. This function must use a 2×2 matrix exponentiation approach to achieve O(log n) time complexity. The input n can be as large as 10^9.
Required Function Signatures
multiply(A, B) -> Cpow(x, k, MOD=None) -> valuefib(n, MOD=None) -> value
Constraints
- For
fib(n),ncan be up to10^9.